點(diǎn)擊關(guān)注，與你共同成長(zhǎng)！

關(guān)于HashMap常見面試考點(diǎn)（底層原理+擴(kuò)容機(jī)制）

問：簡(jiǎn)單說說 HashMap 的底層原理？

答：當(dāng)我們往 HashMap 中 put 元素時(shí)，先根據(jù) key 的 hash 值得到這個(gè) Entry 元素在數(shù)組中的位置（即下標(biāo)），然后把這個(gè) Entry 元素放到對(duì)應(yīng)的位置中，如果這個(gè) Entry 元素所在的位子上已經(jīng)存放有其他元素就在同一個(gè)位子上的 Entry 元素以鏈表的形式存放，新加入的放在鏈頭，從 HashMap 中 get Entry 元素時(shí)先計(jì)算 key 的 hashcode，找到數(shù)組中對(duì)應(yīng)位置的某一 Entry 元素，然后通過 key 的 equals 方法在對(duì)應(yīng)位置的鏈表中找到需要的 Entry 元素，所以 HashMap 的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，此外 HashMap 中 key 和 value 都允許為 null，key 為 null 的鍵值對(duì)永遠(yuǎn)都放在以 table[0] 為頭結(jié)點(diǎn)的鏈表中。

之所以 HashMap 這么設(shè)計(jì)的實(shí)質(zhì)是由于數(shù)組存儲(chǔ)區(qū)間是連續(xù)的，占用內(nèi)存嚴(yán)重，故空間復(fù)雜度大，但二分查找時(shí)間復(fù)雜度?。∣(1)），所以尋址容易而插入和刪除困難；而鏈表存儲(chǔ)區(qū)間離散，占用內(nèi)存比較寬松，故空間復(fù)雜度小，但時(shí)間復(fù)雜度大（O(N)），所以尋址困難而插入和刪除容易；所以就產(chǎn)生了一種新的數(shù)據(jù)結(jié)構(gòu)叫做哈希表，哈希表既滿足數(shù)據(jù)的查找方便，同時(shí)不占用太多的內(nèi)容空間，使用也十分方便，哈希表有多種不同的實(shí)現(xiàn)方法，HashMap 采用的是鏈表的數(shù)組實(shí)現(xiàn)方式。

特別說明，對(duì)于 JDK 1.8 開始 HashMap 實(shí)現(xiàn)原理變成了數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)，數(shù)組鏈表部分基本不變，紅黑樹是為了解決哈希碰撞后鏈表索引效率的問題，所以在 JDK 1.8 中當(dāng)鏈表的節(jié)點(diǎn)大于 8 個(gè)時(shí)就會(huì)將鏈表變?yōu)榧t黑樹。區(qū)別是 JDK 1.8 以前碰撞節(jié)點(diǎn)會(huì)在鏈表頭部插入，而 JDK 1.8 開始碰撞節(jié)點(diǎn)會(huì)在鏈表尾部插入，對(duì)于擴(kuò)容操作后的節(jié)點(diǎn)轉(zhuǎn)移 JDK 1.8 以前轉(zhuǎn)移前后鏈表順序會(huì)倒置，而 JDK 1.8 中依然保持原序。

問：HashMap 默認(rèn)的初始化長(zhǎng)度是多少？為什么默認(rèn)長(zhǎng)度和擴(kuò)容后的長(zhǎng)度都必須是 2 的冪？

答：在 JDK 中默認(rèn)長(zhǎng)度是 16（在 Android SDK 中的 HashMap 默認(rèn)長(zhǎng)度為 4），并且默認(rèn)長(zhǎng)度和擴(kuò)容后的長(zhǎng)度都必須是 2 的冪。因?yàn)槲覀兛梢韵瓤聪?HashMap 的 put 方法核心，如下：

public V put(K key, V value) {
 
   ......
 
   //計(jì)算出 key 的 hash 值
 
   int hash = hash(key);
 
   //通過 key 的 hash 值和當(dāng)前動(dòng)態(tài)數(shù)組的長(zhǎng)度求當(dāng)前 key 的 Entry 在數(shù)組中的下標(biāo)
 
   int i = indexFor(hash, table.length);
 
   ......
 
}
 
 
//最核心的求數(shù)組下標(biāo)方法
 
static int indexFor(int h, int length) {
 
   // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
 
   return h & (length-1);
 
}

可以看到獲取數(shù)組索引的計(jì)算方式為 key 的 hash 值按位與運(yùn)算數(shù)組長(zhǎng)度減一，為了說明長(zhǎng)度盡量是 2 的冪的作用我們假設(shè)執(zhí)行了 put("android", 123); 語(yǔ)句且 "android" 的 hash 值為 234567，二進(jìn)制為 111001010001000111，然后由于 HashMap 默認(rèn)長(zhǎng)度為 16，所以減一后的二進(jìn)制為 1111，接著兩數(shù)做按位與操作二進(jìn)制結(jié)果為 111，即十進(jìn)制的 7，所以 index 為 7，可以看出這種按位操作比直接取模效率要高。

如果假設(shè) HashMap 默認(rèn)長(zhǎng)度不是 2 的冪，譬如數(shù)組長(zhǎng)度為 6，減一的二進(jìn)制為 101，與 111001010001000111 按位與操作二進(jìn)制 101，此時(shí)假設(shè)我們通過 put 再放一個(gè) key-value 進(jìn)來，其 hash 為 111001010001000101，其與 101 按位與操作后的二進(jìn)制也為 101，很容易發(fā)生哈希碰撞，這就不符合 index 的均勻分布了。

通過上面兩個(gè)假設(shè)例子可以看出 HashMap 的長(zhǎng)度為 2 的冪時(shí)減一的值的二進(jìn)制位數(shù)一定全為 1，這樣數(shù)組下標(biāo) index 的值完全取決于 key 的 hash 值的后幾位，因此只要存入 HashMap 的 Entry 的 key 的 hashCode 值分布均勻，HashMap 中數(shù)組 Entry 元素的分部也就盡可能是均勻的（也就避免了 hash 碰撞帶來的性能問題），所以當(dāng)長(zhǎng)度為 2 的冪時(shí)不同的 hash 值發(fā)生碰撞的概率比較小，這樣就會(huì)使得數(shù)據(jù)在 table 數(shù)組中分布較均勻，查詢速度也較快。不過即使負(fù)載因子和 hash 算法設(shè)計(jì)的再合理也免不了哈希沖突碰撞的情況，一旦出現(xiàn)過多就會(huì)影響 HashMap 的性能，所以在 JDK 1.8 中官方對(duì)數(shù)據(jù)結(jié)構(gòu)引入了紅黑樹，當(dāng)鏈表長(zhǎng)度太長(zhǎng)（默認(rèn)超過 8）時(shí)鏈表就轉(zhuǎn)為了紅黑樹，而紅黑樹的增刪改查都比較高效，從而解決了哈希碰撞帶來的性能問題。

問：簡(jiǎn)單說說你對(duì) HashMap 構(gòu)造方法中 initialCapacity（初始容量）、loadFactor（加載因子）的理解？

答：這兩個(gè)參數(shù)對(duì)于 HashMap 來說很重要，直接從一定程度決定了 HashMap 的性能問題。

initialCapacity 初始容量代表了哈希表中桶的初始數(shù)量，即 Entry< K,V>[] table 數(shù)組的初始長(zhǎng)度，不過特別注意，table 數(shù)組的長(zhǎng)度雖然依賴 initialCapacity，但是每次都會(huì)通過 roundUpToPowerOf2(initialCapacity) 方法來保證為 2 的冪次。

loadFactor 加載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種飽和度百分比，其衡量了一個(gè)散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。散列當(dāng)前飽和度的計(jì)算為當(dāng)前 HashMap 中 Entry 的存儲(chǔ)個(gè)數(shù)除以當(dāng)前 table 數(shù)組桶長(zhǎng)度，因此當(dāng)哈希表中 Entry 的數(shù)量超過了 loadFactor 加載因子乘以當(dāng)前 table 數(shù)組桶長(zhǎng)度時(shí)就會(huì)觸發(fā)擴(kuò)容操作。對(duì)于使用鏈表法的散列表來說，查找一個(gè)元素的平均時(shí)間是O(1+a)，因此如果負(fù)載因子越大則對(duì)空間的利用更充分，從而導(dǎo)致查找效率的降低，如果負(fù)載因子太小則散列表的數(shù)據(jù)將過于稀疏，從而對(duì)空間造成浪費(fèi)。系統(tǒng)默認(rèn)負(fù)載因子為 0.75，一般情況下無需修改。

因此如果哈希桶數(shù)組很大則較差的 Hash 算法分部也會(huì)比較分散，如果哈希桶數(shù)組很小則即使好的 Hash 算法也會(huì)出現(xiàn)較多碰撞，所以就需要權(quán)衡好的 Hash 算法和擴(kuò)容機(jī)制，也就是上面兩個(gè)參數(shù)的作用。

問：簡(jiǎn)單說說 JDK1.7 中 HashMap 什么情況下會(huì)發(fā)生擴(kuò)容？如何擴(kuò)容？

答：HashMap 中默認(rèn)的負(fù)載因子為 0.75，默認(rèn)情況下第一次擴(kuò)容閥值是 12（16 * 0.75），故第一次存儲(chǔ)第 13 個(gè)鍵值對(duì)時(shí)就會(huì)觸發(fā)擴(kuò)容機(jī)制變?yōu)樵瓉頂?shù)組長(zhǎng)度的二倍，以后每次擴(kuò)容都類似計(jì)算機(jī)制；這也就是為什么 HashMap 在數(shù)組大小不變的情況下存放鍵值對(duì)越多查找的效率就會(huì)變低（因?yàn)?hash 碰撞會(huì)使數(shù)組變鏈表），而通過擴(kuò)容就可以一定程度的平衡查找效率（盡量散列數(shù)組化）的原因所在。

下面給出 JDK 1.7 的具體擴(kuò)容流程：

//JDK1.7擴(kuò)容最核心的方法，newTable為新容量數(shù)組大小
 
void transfer(HashMapEntry[] newTable) {
 
   //新容量數(shù)組桶大小為舊的table的2倍
 
   int newCapacity = newTable.length;
 
   //遍歷舊的數(shù)組桶table
 
   for (HashMapEntry<K,V> e : table) {
 
       //如果這個(gè)數(shù)組位置上有元素且存在哈希沖突的鏈表結(jié)構(gòu)則繼續(xù)遍歷鏈表
 
       while(null != e) {
 
           //取當(dāng)前數(shù)組索引位上單向鏈表的下一個(gè)元素
 
           HashMapEntry<K,V> next = e.next;
 
           //重新依據(jù)hash值計(jì)算元素在擴(kuò)容后數(shù)組中的索引位置
 
           int i = indexFor(e.hash, newCapacity);
 
           //將數(shù)組i的元素賦值給當(dāng)前鏈表元素的下一個(gè)節(jié)點(diǎn)
 
           e.next = newTable[i];
 
           //將鏈表元素放入數(shù)組位置
 
           newTable[i] = e;
 
           //將當(dāng)前數(shù)組索引位上單向鏈表的下一個(gè)元素賦值給e進(jìn)行新的一圈鏈表遍歷
 
           e = next;
 
       }
 
   }
 
}

可以看到，整個(gè)擴(kuò)容過程就是一個(gè)取出數(shù)組元素（實(shí)際數(shù)組索引位置上的每個(gè)元素是每個(gè)獨(dú)立單向鏈表的頭部，也就是發(fā)生 Hash 沖突后最后放入的沖突元素）然后遍歷以該元素為頭的單向鏈表元素，依據(jù)每個(gè)被遍歷元素的 hash 值計(jì)算其在新數(shù)組中的下標(biāo)然后進(jìn)行交換（即原來 hash 沖突的單向鏈表尾部變成了擴(kuò)容后單向鏈表的頭部）。下面給出圖解流程：

問：簡(jiǎn)單說說 JDK 1.8 中 HashMap 是如何擴(kuò)容的？與 JDK 1.7 有什么區(qū)別？

答：

可以看見，1.7 中整個(gè)擴(kuò)容過程就是一個(gè)取出數(shù)組元素（實(shí)際數(shù)組索引位置上的每個(gè)元素是每個(gè)獨(dú)立單向鏈表的頭部，也就是發(fā)生 Hash 沖突后最后放入的沖突元素）然后遍歷以該元素為頭的單向鏈表元素，依據(jù)每個(gè)被遍歷元素的 hash 值計(jì)算其在新數(shù)組中的下標(biāo)然后進(jìn)行交換（即原來 hash 沖突的單向鏈表尾部變成了擴(kuò)容后單向鏈表的頭部）。

而在 JDK 1.8 中 HashMap 的擴(kuò)容操作就顯得更加的騷氣了，由于擴(kuò)容數(shù)組的長(zhǎng)度是 2 倍關(guān)系，所以對(duì)于假設(shè)初始 tableSize =4 要擴(kuò)容到 8 來說就是 0100 到 1000 的變化（左移一位就是 2 倍），在擴(kuò)容中只用判斷原來的 hash 值與左移動(dòng)的一位按位與操作是 0 或 1 就行，0 的話索引就不變，1 的話索引變成原索引加上擴(kuò)容前數(shù)組。

1.8 源碼核心實(shí)現(xiàn)如下：

final Node<K,V>[] resize() {

  Node<K,V>[] oldTab = table;

  //記住擴(kuò)容前的數(shù)組長(zhǎng)度和最大容量

  int oldCap = (oldTab == null) ? 0 : oldTab.length;

  int oldThr = threshold;

  int newCap, newThr = 0;

  if (oldCap > 0) {

      //超過數(shù)組在java中最大容量就無能為力了，沖突就只能沖突

      if (oldCap >= MAXIMUM_CAPACITY) {

          threshold = Integer.MAX_VALUE;

          return oldTab;

      } //長(zhǎng)度和最大容量都擴(kuò)容為原來的二倍

      else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

               oldCap >= DEFAULT_INITIAL_CAPACITY)

          newThr = oldThr << 1; // double threshold

  }......

  ......

  //更新新的最大容量為擴(kuò)容計(jì)算后的最大容量

  threshold = newThr;

  //更新擴(kuò)容后的新數(shù)組長(zhǎng)度

  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

  table = newTab;

  if (oldTab != null) {

      //遍歷老數(shù)組下標(biāo)索引

      for (int j = 0; j < oldCap; ++j) {

          Node<K,V> e;

          //如果老數(shù)組對(duì)應(yīng)索引上有元素則取出鏈表頭元素放在e中

          if ((e = oldTab[j]) != null) {

              oldTab[j] = null;

              //如果老數(shù)組j下標(biāo)處只有一個(gè)元素則直接計(jì)算新數(shù)組中位置放置

              if (e.next == null)

                  newTab[e.hash & (newCap - 1)] = e;

              else if (e instanceof TreeNode) //如果是樹結(jié)構(gòu)進(jìn)行單獨(dú)處理

                  ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

              else { // preserve order

                  //能進(jìn)來說明數(shù)組索引j位置上存在哈希沖突的鏈表結(jié)構(gòu)

                  Node<K,V> loHead = null, loTail = null;

                  Node<K,V> hiHead = null, hiTail = null;

                  Node<K,V> next;

                  //循環(huán)處理數(shù)組索引j位置上哈希沖突的鏈表中每個(gè)元素

                  do {

                      next = e.next;

                      //判斷key的hash值與老數(shù)組長(zhǎng)度與操作后結(jié)果決定元素是放在原索引處還是新索引

                      if ((e.hash & oldCap) == 0) {

                          //放在原索引處的建立新鏈表

                          if (loTail == null)

                              loHead = e;

                          else

                              loTail.next = e;

                          loTail = e;

                      }

                      else {

                          //放在新索引（原索引+oldCap）處的建立新鏈表

                          if (hiTail == null)

                              hiHead = e;

                          else

                              hiTail.next = e;

                          hiTail = e;

                      }

                  } while ((e = next) != null);

                  if (loTail != null) {

                      //放入原索引處

                      loTail.next = null;

                      newTab[j] = loHead;

                  }

                  if (hiTail != null) {

                      //放入新索引處

                      hiTail.next = null;

                      newTab[j + oldCap] = hiHead;

                  }

              }

          }

      }

  }

  return newTab;

}

可以看見，這個(gè)設(shè)計(jì)非常贊，因?yàn)?hash 值本來就是隨機(jī)性的，所以 hash 按位與上 newTable 得到的 0（擴(kuò)容前的索引位置）和 1（擴(kuò)容前索引位置加上擴(kuò)容前數(shù)組長(zhǎng)度的數(shù)值索引處）就是隨機(jī)的，所以擴(kuò)容的過程就能把之前哈西沖突的元素再隨機(jī)的分布到不同的索引去，這算是 JDK1.8 的一個(gè)優(yōu)化點(diǎn)。

此外，在 JDK1.7 中擴(kuò)容操作時(shí)哈西沖突的數(shù)組索引處的舊鏈表元素?cái)U(kuò)容到新數(shù)組時(shí)如果擴(kuò)容后索引位置在新數(shù)組的索引位置與原數(shù)組中索引位置相同，則鏈表元素會(huì)發(fā)生倒置（即如上面圖1，原來鏈表頭擴(kuò)容后變?yōu)槲舶停欢?JDK1.8 中不會(huì)出現(xiàn)鏈表倒置現(xiàn)象。

其次，由于 JDK1.7 中發(fā)生哈西沖突時(shí)僅僅采用了鏈表結(jié)構(gòu)存儲(chǔ)沖突元素，所以擴(kuò)容時(shí)僅僅是重新計(jì)算其存儲(chǔ)位置而已，而 JDK1.8 中為了性能在同一索引處發(fā)生哈西沖突到一定程度時(shí)鏈表結(jié)構(gòu)會(huì)轉(zhuǎn)換為紅黑數(shù)結(jié)構(gòu)存儲(chǔ)沖突元素，故在擴(kuò)容時(shí)如果當(dāng)前索引中元素結(jié)構(gòu)是紅黑樹且元素個(gè)數(shù)小于鏈表還原閾值（哈西沖突程度常量）時(shí)就會(huì)把樹形結(jié)構(gòu)縮小或直接還原為鏈表結(jié)構(gòu)（其實(shí)現(xiàn)就是上面代碼片段中的 split() 方法）。