面試官：HashMap死循環形成的原因是什麼？

2020 年 3 月 12 日
筆記

介紹

之前的文章已經分析了HashMap在JDK1.7的實現，這篇文章就只分析HashMap死循環形成的原因

死循環形成是在擴容轉移元素的時候發生的

void resize(int newCapacity) {      Entry[] oldTable = table;      int oldCapacity = oldTable.length;      if (oldCapacity == MAXIMUM_CAPACITY) {          threshold = Integer.MAX_VALUE;          return;      }        Entry[] newTable = new Entry[newCapacity];      transfer(newTable, initHashSeedAsNeeded(newCapacity));      table = newTable;      threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);  }

發生的具體時機在transfer函數中，默認情況下rehash為false

void transfer(Entry[] newTable, boolean rehash) {      int newCapacity = newTable.length;      for (Entry<K,V> e : table) {          while(null != e) {              Entry<K,V> next = e.next;              if (rehash) {                  e.hash = null == e.key ? 0 : hash(e.key);              }              int i = indexFor(e.hash, newCapacity);              e.next = newTable[i];              newTable[i] = e;              e = next;          }      }  }

正常的transfer過程

例子不考慮擴容閾值，假設放4個元素時開始擴容

主要有2個有意思的地方

原來在oldTable[i]位置的元素，會被放到newTable[i]或者newTable[i+oldTable.length]的位置
鏈表在轉移的時候會反轉

並發下異常的transfer

假設執行緒1執行完Entrynext = e.next後被掛起，此時e指向key3，next指向key7

void transfer(Entry[] newTable, boolean rehash) {      int newCapacity = newTable.length;      for (Entry<K,V> e : table) {          while(null != e) {              Entry<K,V> next = e.next; // 執行緒1執行完這一句被掛起              if (rehash) {                  e.hash = null == e.key ? 0 : hash(e.key);              }              int i = indexFor(e.hash, newCapacity);              e.next = newTable[i];              newTable[i] = e;              e = next;          }      }  }