面試中一個hashmap到底能問出什麼？看完這個我終於明白了

前言：

hashmap是面試中問的最多的一道題，關於它的底層原理和擴容機制是必問的。根據你對hashmap的回答，面試官能對你的基礎和技術有個大致的瞭解。這篇文章主要介紹了JAVA關於HashMap容易被提問的面試題，因為好久沒看的原因，所以今天就總結一下。文中題目提問頻率高的幾道題，本人在網上總結到的，相信對你的面試有一定幫助，想要入職JAVA的朋友可以瞭解下。

另外本人整理收藏了20年多家公司面試知識點整理 ，以及各種Java核心知識點免費分享給大家，下方只是部分截圖 想要資料的話也可以點選795983544領取 暗號CSDN。

1.為什麼我們建議在定義HashMap的時候，就指定它的初始化大小呢？

答：在當我們對HashMap初始化時，如果沒有為其設定初始化容量，那麼系統會預設建立一個容量為16的大小的集合。當我們向HashMap中新增元素時，如果HashMap的容量值超過了它的臨界值（預設16*0.75=12）時，（0.75是HashMap的載入因子）HashMap將會重新擴容到下一個2的指數次冪（2^4=16 下一個2的指數次冪是2^5=32）。由於HashMap擴容要進行resize的操作，頻繁的resize，會導致HashMap的效能下降，所以建議在確定HashMap集合的大小的情況下，指定其初始化大小，避免做過多的resize操作，導致效能下降。

2.HashMap什麼時候進行擴容？

答：當我們不斷的向HashMap中新增元素時，它會判斷HashMap當前的容量值(當前元素的個數)是否超過了它的臨界值（在沒有指定其初始化大小時，預設16*0.75=12），如果新增的元素個數超過了臨界值，它就會開始進行擴容。

3.HashMap在擴容時，擴容到多大？

答：HashMap在擴容時，它會擴容到下一個2的指數次冪，即當前容量的2倍，比如當前容量是2^{4=16，將會擴容到下一個2的指數次冪2}5=32.

4.HashMap是如何進行擴容的？

答：HashMap進行擴容時會呼叫resize()函數，重新計算HashMap所需的新的容量，然後重新定義一個新的容器，將原陣列資料進行Hash, 放入新的容器中。這個過程將會導致HashMap的效能下降。

resize()函數的原始碼：

//HashMap 擴容操作
final Node<K,V>[] resize() {
  //儲存當前table
  Node<K,V>[] oldTab = table;
  //儲存當前table的容量
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  //儲存當前閾值
  int oldThr = threshold;
  //初始化新的table容量和閾值
  int newCap, newThr = 0;
  
  //1. resize()函數在size(HashMap當前的元素個數) > threshold(當前閾值，預設16*0.75=12)時呼叫。
  //當oldCap(HashMap的元素個數)大於0表示原來的table表非空，oldCap(threshold)為oldCap x load_factor(載入因子：0.75)
  if (oldCap > 0) {
    //若舊table容量大於等於最大容量，更新閾值為Integer.MAX_VALUE(最大整形值)，這樣以後就不會自動擴容了
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
   //擴容到下一個2的指數次冪，容量翻倍，使用左移，效率更高
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold //閾值翻倍
  }
  
  //2. resize()函數在table為空被呼叫。oldCap小於等於0且oldThr大於0，表示使用者使用HashMap的建構函式建立了一個HashMap，
  //使用的建構函式為HashMap(int initialCapacity, float loadFactor)或HashMap(int initialCapacity)或HashMap(Map<? extends K, ? extends V> m)，
  //導致了oldTab為null,oldCap為0，oldThr為使用者指定的HashMap的初始化容量
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr; //當table沒有初始化時，threshold為初始容量， threshold = tableSizeFor(t);
  
  //3. resize()函數在table為空被呼叫。oldCap小於等於0且oldThr大於0，表示使用者使用HashMap的無參建構函式HashMap()函數建立了一個HashMap，
  //此時，所有值均採用預設值，oldTab(table)表為空，oldCap為0，oldThr等於0.
  else {        // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  //如果新的閾值為0
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor; //新的tbale容量*載入因子
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
         (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
    //初始化table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    //把oldTab中的節點reHash到newTab中去
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
      //如果節點是單個節點，直接在newTab中進行重定位
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
      //如果節點是TreeNode節點，要進行紅黑樹的rehash操作
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
      //如果是連結串列，進行連結串列的rehash操作
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
        //將同一桶中的元素根據(e.hash & oldCap)是否為0進行分割，分成兩個不同的連結串列，完成rehash操作
          do {
            next = e.next;
         //根據演演算法 e.hash & oldCap 判斷節點位置rehash後是否發生改變，最高位==0，這是索引不變的連結串列
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
         //最高位==1，這是索引發生改變的連結串列
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) { //原bucket位置的尾指標不為空(即還有node)
            loTail.next = null;  //連結串列最後一個節點為null
            newTab[j] = loHead; //連結串列的頭指標放在新桶的相同下標(j)處
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead; //rehash後節點新的位置一定為原來基礎上加上oldCap
          }
        }
      }
    }
  }
  return newTab;
}

5.為什麼說HashMap是執行緒不安全的？

答：HashMap在多執行緒並行時執行緒不安全，主要表現在下面兩個方面：

(1) 當向HashMap中put(新增)元素時導致的多執行緒資料不一致

比如有兩個執行緒 A 和 B ，首先 A 希望插入一個 key-value鍵值對到HashMap 中，它首先計算記錄所要落到的 hash 桶的索引座標，然後獲取到該桶裡面的連結串列頭結點，此時執行緒 A 的時間片用完了，而此時執行緒 B 被排程得以執行，和執行緒 A 一樣執行，只不過執行緒 B 成功將記錄插到了桶裡面。假設執行緒 A 插入的記錄計算出來的 hash 桶索引和執行緒 B 要插入的記錄計算出來的 hash 桶索引是一樣的，那麼當執行緒 B 成功插入之後，執行緒 A 再次被排程執行時，它依然持有過期的連結串列頭但是它對此一無所知，以至於它認為它應該這樣做，如此一來就覆蓋了執行緒 B 插入的記錄，這樣執行緒 B 插入的記錄就憑空消失了，造成了資料不一致的行為。

簡單來說就是在多執行緒環境下，向HashMap集合中新增元素會存在覆蓋的現象，導致了執行緒不安全。

(2) 當HashMap進行擴容呼叫resize()函數時引起死迴圈

HashMap在put的時候，插入的元素超過了容量（由負載因子決定）的範圍就會觸發擴容操作，就是rehash，這個會重新將原陣列的內容重新hash到新的擴容陣列中，在多執行緒的環境下，存在同時其他的元素也在進行put操作，如果hash值相同，可能出現同時在同一陣列下用連結串列表示，造成閉環，導致在get時會出現死迴圈，所以HashMap是執行緒不安全的。

HashMap的執行緒不安全主要體現在下面兩個方面：

1.在JDK1.7中，當並行執行擴容操作時會造成環形鏈和資料丟失的情況。

2.在JDK1.8中，在並行執行put操作時會發生資料覆蓋的情況。

6.說說HashMap 的資料結構

HashMap是一個key-value鍵值對的資料結構，從結構上來講在jdk1.8之前是用陣列加連結串列的方式實現，jdk1.8加了紅黑樹，HashMap陣列的預設初始長度是16，HashMap陣列只允許一個key為null，允許多個value為null

HashMap的內部實現，HashMap是使用陣列+連結串列+紅黑樹的形式實現的，其中陣列是一個一個Node[]陣列，我們叫他hash桶陣列，它上面存放的是key-value鍵值對的節點。HashMap是用hash表來儲存的，在HashMap裡為解決hash衝突，使用鏈地址法，簡單來說就是陣列加連結串列的形式來解決，當資料被hash後，得到陣列下標，把資料放在對應下標的連結串列中。

HashMap是基於雜湊表的Map介面的非同步實現。此實現提供所有可選的對映操作，並允許使用null值和null鍵。此類不保證對映的順序，特別是它不保證該順序恆久不變。HashMap實際上是一個「連結串列雜湊」的資料結構，即陣列和連結串列的結合體。HashMap底層就是一個陣列結構，陣列中的每一項又是一個連結串列。當新建一個HashMap的時候，就會初始化一個陣列。HashMap主幹為一個Entry陣列，而每個Entry存放著一個鍵值對和同時指向另一個Entry的參照，如果發生雜湊衝突，該參照即指向另一個Entry。

HashMap是由陣列+連結串列結構組成，陣列是HashMap主體，連結串列則是為了解決雜湊衝突而存在，如果對於Entry不含連結串列的位置，對其操作的時間複雜度為O(1)，如果定位到具有連結串列的位置，則時間複雜度為O(n)。

HashMap中重要欄位:

transient int size ：實際儲存的KEY-VALUE對個數

int threshold ：閥值，當表為空的時候，該值初始容量為16，後期擴容使用

final float loadFactor ：負載因子，代表表的填充度，預設為0.75

transient int modCount ： 用於快速失敗，迭代時丟擲異常

在JDK1.8中 HashMap底層改為連結串列+陣列+紅黑樹的形式，當Hash衝突多次在同一個位置發生的時候，（確切的說是該位置連結串列長度大於8時），在此位置將用紅黑樹來儲存資料提高讀取效率.

HashMap 包含如下幾個構造器：

HashMap()：構建一個初始容量為 16，負載因子為 0.75 的 HashMap。

HashMap(int initialCapacity)：構建一個初始容量為 initialCapacity，負載因子為 0.75 的 HashMap。

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負載因子建立一個 HashMap。

HashMap的基礎構造器HashMap(int initialCapacity, float loadFactor)帶有兩個引數，它們是初始容量initialCapacity和負載因子loadFactor。

負載因子loadFactor衡量的是一個雜湊表的空間的使用程度，負載因子越大表示雜湊表的裝填程度越高，反之愈小。對於使用連結串列法的雜湊表來說，查詢一個元素的平均時間是O(1+a)，因此如果負載因子越大，對空間的利用更充分，然而後果是查詢效率的降低；如果負載因子太小，那麼雜湊表的資料將過於稀疏，對空間造成嚴重浪費。

HashMap的實現中，通過threshold欄位來判斷HashMap的最大容量：

threshold = (int)(capacity * loadFactor);

結合負載因子的定義公式可知，threshold就是在此loadFactor和capacity對應下允許的最大元素數目，超過這個數目就重新resize，以降低實際的負載因子。預設的負載因子0.75是對空間和時間效率的一個平衡選擇。當容量超出此最大容量時， resize後的HashMap容量是容量的兩倍：

7.HashMap 的工作原理是什麼?

一，儲存方式： Java中的HashMap是以鍵值對(key-value)的形式儲存元素的。

二，呼叫原理： HashMap需要一個hash函數，它使用hashCode()和equals()方法來向集合/從集合新增和檢索元素。當呼叫put()方法的時候，HashMap會計算key的hash值，然後把鍵值對儲存在集合中合適的索引上。如果key已經存在了，value會被更新成新值。

HashMap的實現原理：

1. 利用key的hashCode重新hash計算出當前物件的元素在陣列中的下標

2. 儲存時，如果出現hash值相同的key，此時有兩種情況。(1)如果key相同，則覆蓋原始值；(2)如果key不同（出現衝突），則將當前的key-value放入連結串列中

3. 獲取時，直接找到hash值對應的下標，再進一步判斷key是否相同，從而找到對應值。

4. 理解了以上過程就不難明白HashMap是如何解決hash衝突的問題，核心就是使用了陣列的儲存方式，然後將衝突的key的物件放入連結串列中，一旦發現衝突就在連結串列中做進一步的對比。

總結：

本文著重講解了面試中 HashMap 面試題，相信讀者仔細品讀以後，對HashMap 的實現會有一個清晰地認識，JDK7 中的 HashMap 的實現原理屬於經典實現，不管 JDK7 是否已經再被使用，但是其基本原理還是值得學習！後續將繼續講解 JDK8 中的 HashMap實現原理，屆時將對比 JDK7，幫助讀者掌握兩者之間的共性和差異！

以上純屬個人總結，如有不對的，歡迎指出！感謝諸君的支援，點個贊吧！

另外本人整理收藏了20年多家公司面試知識點整理 共127頁的PDF 以及各種知識點整理 免費分享給大家，想要資料的話點選795983544暗號CSDN自行領取。今天的分享就到這了，希望大家多多支援我，一個不甘平凡的小碼農！