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

答：在當(dāng)我們對(duì)HashMap初始化時(shí)，如果沒(méi)有為其設(shè)置初始化容量，那么系統(tǒng)會(huì)默認(rèn)創(chuàng)建一個(gè)容量為16的大小的集合。當(dāng)我們向HashMap中添加元素時(shí)，如果HashMap的容量值超過(guò)了它的臨界值（默認(rèn)16*0.75=12）時(shí)，（0.75是HashMap的加載因子）HashMap將會(huì)重新擴(kuò)容到下一個(gè)2的指數(shù)次冪（2^4=16 下一個(gè)2的指數(shù)次冪是2^5=32）。由于HashMap擴(kuò)容要進(jìn)行resize的操作，頻繁的resize，會(huì)導(dǎo)致HashMap的性能下降，所以建議在確定HashMap集合的大小的情況下，指定其初始化大小，避免做過(guò)多的resize操作，導(dǎo)致性能下降。

2. HashMap什么時(shí)候進(jìn)行擴(kuò)容？

答：當(dāng)我們不斷的向HashMap中添加元素時(shí)，它會(huì)判斷HashMap當(dāng)前的容量值(當(dāng)前元素的個(gè)數(shù))是否超過(guò)了它的臨界值（在沒(méi)有指定其初始化大小時(shí)，默認(rèn)16*0.75=12），如果添加的元素個(gè)數(shù)超過(guò)了臨界值，它就會(huì)開始進(jìn)行擴(kuò)容。

3. HashMap在擴(kuò)容時(shí)，擴(kuò)容到多大？

答：HashMap在擴(kuò)容時(shí)，它會(huì)擴(kuò)容到下一個(gè)2的指數(shù)次冪，即當(dāng)前容量的2倍，比如當(dāng)前容量是2^4=16，將會(huì)擴(kuò)容到下一個(gè)2的指數(shù)次冪2^5=32.

4. HashMap是如何進(jìn)行擴(kuò)容的？

答：HashMap進(jìn)行擴(kuò)容時(shí)會(huì)調(diào)用resize()函數(shù)，重新計(jì)算HashMap所需的新的容量，然后重新定義一個(gè)新的容器，將原數(shù)組數(shù)據(jù)進(jìn)行Hash, 放入新的容器中。這個(gè)過(guò)程將會(huì)導(dǎo)致HashMap的性能下降。

resize()函數(shù)的源碼：

//HashMap 擴(kuò)容操作
final Node<K,V>[] resize() {
  //保存當(dāng)前table
  Node<K,V>[] oldTab = table;
  //保存當(dāng)前table的容量
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  //保存當(dāng)前閾值
  int oldThr = threshold;
  //初始化新的table容量和閾值
  int newCap, newThr = 0;
  
  //1. resize()函數(shù)在size(HashMap當(dāng)前的元素個(gè)數(shù)) > threshold(當(dāng)前閾值，默認(rèn)16*0.75=12)時(shí)調(diào)用。
  //當(dāng)oldCap(HashMap的元素個(gè)數(shù))大于0表示原來(lái)的table表非空，oldCap(threshold)為oldCap x load_factor(加載因子：0.75)
  if (oldCap > 0) {
    //若舊table容量大于等于最大容量，更新閾值為Integer.MAX_VALUE(最大整形值)，這樣以后就不會(huì)自動(dòng)擴(kuò)容了
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
   //擴(kuò)容到下一個(gè)2的指數(shù)次冪，容量翻倍，使用左移，效率更高
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold //閾值翻倍
  }
  
  //2. resize()函數(shù)在table為空被調(diào)用。oldCap小于等于0且oldThr大于0，表示用戶使用HashMap的構(gòu)造函數(shù)創(chuàng)建了一個(gè)HashMap，
  //使用的構(gòu)造函數(shù)為HashMap(int initialCapacity, float loadFactor)或HashMap(int initialCapacity)或HashMap(Map<? extends K, ? extends V> m)，
  //導(dǎo)致了oldTab為null,oldCap為0，oldThr為用戶指定的HashMap的初始化容量
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr; //當(dāng)table沒(méi)有初始化時(shí)，threshold為初始容量， threshold = tableSizeFor(t);
  
  //3. resize()函數(shù)在table為空被調(diào)用。oldCap小于等于0且oldThr大于0，表示用戶使用HashMap的無(wú)參構(gòu)造函數(shù)HashMap()函數(shù)創(chuàng)建了一個(gè)HashMap，
  //此時(shí)，所有值均采用默認(rèn)值，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中的節(jié)點(diǎn)reHash到newTab中去
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
      //如果節(jié)點(diǎn)是單個(gè)節(jié)點(diǎn)，直接在newTab中進(jìn)行重定位
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
      //如果節(jié)點(diǎn)是TreeNode節(jié)點(diǎn)，要進(jìn)行紅黑樹的rehash操作
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
      //如果是鏈表，進(jìn)行鏈表的rehash操作
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
        //將同一桶中的元素根據(jù)(e.hash & oldCap)是否為0進(jìn)行分割，分成兩個(gè)不同的鏈表，完成rehash操作
          do {
            next = e.next;
         //根據(jù)算法 e.hash & oldCap 判斷節(jié)點(diǎn)位置rehash后是否發(fā)生改變，最高位==0，這是索引不變的鏈表
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
         //最高位==1，這是索引發(fā)生改變的鏈表
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) { //原bucket位置的尾指針不為空(即還有node)
            loTail.next = null;  //鏈表最后一個(gè)節(jié)點(diǎn)為null
            newTab[j] = loHead; //鏈表的頭指針?lè)旁谛峦暗南嗤聵?biāo)(j)處
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead; //rehash后節(jié)點(diǎn)新的位置一定為原來(lái)基礎(chǔ)上加上oldCap
          }
        }
      }
    }
  }
  return newTab;
}

5. 為什么說(shuō)HashMap是線程不安全的？

答：HashMap在多線程并發(fā)時(shí)線程不安全，主要表現(xiàn)在下面兩個(gè)方面：

(1) 當(dāng)向HashMap中put(添加)元素時(shí)導(dǎo)致的多線程數(shù)據(jù)不一致

比如有兩個(gè)線程 A 和 B ，首先 A 希望插入一個(gè) key-value鍵值對(duì)到HashMap 中，它首先計(jì)算記錄所要落到的 hash 桶的索引坐標(biāo)，然后獲取到該桶里面的鏈表頭結(jié)點(diǎn)，此時(shí)線程 A 的時(shí)間片用完了，而此時(shí)線程 B 被調(diào)度得以執(zhí)行，和線程 A 一樣執(zhí)行，只不過(guò)線程 B 成功將記錄插到了桶里面。假設(shè)線程 A 插入的記錄計(jì)算出來(lái)的 hash 桶索引和線程 B 要插入的記錄計(jì)算出來(lái)的 hash 桶索引是一樣的，那么當(dāng)線程 B 成功插入之后，線程 A 再次被調(diào)度運(yùn)行時(shí)，它依然持有過(guò)期的鏈表頭但是它對(duì)此一無(wú)所知，以至于它認(rèn)為它應(yīng)該這樣做，如此一來(lái)就覆蓋了線程 B 插入的記錄，這樣線程 B 插入的記錄就憑空消失了，造成了數(shù)據(jù)不一致的行為。

簡(jiǎn)單來(lái)說(shuō)就是在多線程環(huán)境下，向HashMap集合中添加元素會(huì)存在覆蓋的現(xiàn)象，導(dǎo)致了線程不安全。

(2) 當(dāng)HashMap進(jìn)行擴(kuò)容調(diào)用resize()函數(shù)時(shí)引起死循環(huán)

HashMap在put的時(shí)候，插入的元素超過(guò)了容量（由負(fù)載因子決定）的范圍就會(huì)觸發(fā)擴(kuò)容操作，就是rehash，這個(gè)會(huì)重新將原數(shù)組的內(nèi)容重新hash到新的擴(kuò)容數(shù)組中，在多線程的環(huán)境下，存在同時(shí)其他的元素也在進(jìn)行put操作，如果hash值相同，可能出現(xiàn)同時(shí)在同一數(shù)組下用鏈表表示，造成閉環(huán)，導(dǎo)致在get時(shí)會(huì)出現(xiàn)死循環(huán)，所以HashMap是線程不安全的。

HashMap的線程不安全主要體現(xiàn)在下面兩個(gè)方面：

1.在JDK1.7中，當(dāng)并發(fā)執(zhí)行擴(kuò)容操作時(shí)會(huì)造成環(huán)形鏈和數(shù)據(jù)丟失的情況。

2.在JDK1.8中，在并發(fā)執(zhí)行put操作時(shí)會(huì)發(fā)生數(shù)據(jù)覆蓋的情況。

6. 說(shuō)說(shuō)HashMap 的數(shù)據(jù)結(jié)構(gòu)

HashMap是一個(gè)key-value鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)，從結(jié)構(gòu)上來(lái)講在jdk1.8之前是用數(shù)組加鏈表的方式實(shí)現(xiàn)，jdk1.8加了紅黑樹，HashMap數(shù)組的默認(rèn)初始長(zhǎng)度是16，HashMap數(shù)組只允許一個(gè)key為null，允許多個(gè)value為null

HashMap的內(nèi)部實(shí)現(xiàn)，HashMap是使用數(shù)組+鏈表+紅黑樹的形式實(shí)現(xiàn)的，其中數(shù)組是一個(gè)一個(gè)Node[]數(shù)組，我們叫他hash桶數(shù)組，它上面存放的是key-value鍵值對(duì)的節(jié)點(diǎn)。HashMap是用hash表來(lái)存儲(chǔ)的，在HashMap里為解決hash沖突，使用鏈地址法，簡(jiǎn)單來(lái)說(shuō)就是數(shù)組加鏈表的形式來(lái)解決，當(dāng)數(shù)據(jù)被hash后，得到數(shù)組下標(biāo)，把數(shù)據(jù)放在對(duì)應(yīng)下標(biāo)的鏈表中。

HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。HashMap底層就是一個(gè)數(shù)組結(jié)構(gòu)，數(shù)組中的每一項(xiàng)又是一個(gè)鏈表。當(dāng)新建一個(gè)HashMap的時(shí)候，就會(huì)初始化一個(gè)數(shù)組。HashMap主干為一個(gè)Entry數(shù)組，而每個(gè)Entry存放著一個(gè)鍵值對(duì)和同時(shí)指向另一個(gè)Entry的引用，如果發(fā)生哈希沖突，該引用即指向另一個(gè)Entry。

HashMap是由數(shù)組+鏈表結(jié)構(gòu)組成，數(shù)組是HashMap主體，鏈表則是為了解決哈希沖突而存在，如果對(duì)于Entry不含鏈表的位置，對(duì)其操作的時(shí)間復(fù)雜度為O(1)，如果定位到具有鏈表的位置，則時(shí)間復(fù)雜度為O(n)。

HashMap中重要字段:

transient int size ：實(shí)際儲(chǔ)存的KEY-VALUE對(duì)個(gè)數(shù)

int threshold ：閥值，當(dāng)表為空的時(shí)候，該值初始容量為16，后期擴(kuò)容使用

final float loadFactor ：負(fù)載因子，代表表的填充度，默認(rèn)為0.75

transient int modCount ： 用于快速失敗，迭代時(shí)拋出異常

在JDK1.8中 HashMap底層改為鏈表+數(shù)組+紅黑樹的形式，當(dāng)Hash沖突多次在同一個(gè)位置發(fā)生的時(shí)候，（確切的說(shuō)是該位置鏈表長(zhǎng)度大于8時(shí)），在此位置將用紅黑樹來(lái)儲(chǔ)存數(shù)據(jù)提高讀取效率.

HashMap 包含如下幾個(gè)構(gòu)造器：

HashMap()：構(gòu)建一個(gè)初始容量為 16，負(fù)載因子為 0.75 的 HashMap。

HashMap(int initialCapacity)：構(gòu)建一個(gè)初始容量為 initialCapacity，負(fù)載因子為 0.75 的 HashMap。

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負(fù)載因子創(chuàng)建一個(gè) HashMap。

HashMap的基礎(chǔ)構(gòu)造器HashMap(int initialCapacity, float loadFactor)帶有兩個(gè)參數(shù)，它們是初始容量initialCapacity和負(fù)載因子loadFactor。

負(fù)載因子loadFactor衡量的是一個(gè)散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。對(duì)于使用鏈表法的散列表來(lái)說(shuō)，查找一個(gè)元素的平均時(shí)間是O(1+a)，因此如果負(fù)載因子越大，對(duì)空間的利用更充分，然而后果是查找效率的降低；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過(guò)于稀疏，對(duì)空間造成嚴(yán)重浪費(fèi)。

HashMap的實(shí)現(xiàn)中，通過(guò)threshold字段來(lái)判斷HashMap的最大容量：

threshold = (int)(capacity * loadFactor);

結(jié)合負(fù)載因子的定義公式可知，threshold就是在此loadFactor和capacity對(duì)應(yīng)下允許的最大元素?cái)?shù)目，超過(guò)這個(gè)數(shù)目就重新resize，以降低實(shí)際的負(fù)載因子。默認(rèn)的負(fù)載因子0.75是對(duì)空間和時(shí)間效率的一個(gè)平衡選擇。當(dāng)容量超出此最大容量時(shí)， resize后的HashMap容量是容量的兩倍：

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

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

二，調(diào)用原理： HashMap需要一個(gè)hash函數(shù)，它使用hashCode()和equals()方法來(lái)向集合/從集合添加和檢索元素。當(dāng)調(diào)用put()方法的時(shí)候，HashMap會(huì)計(jì)算key的hash值，然后把鍵值對(duì)存儲(chǔ)在集合中合適的索引上。如果key已經(jīng)存在了，value會(huì)被更新成新值。

HashMap的實(shí)現(xiàn)原理：

1. 利用key的hashCode重新hash計(jì)算出當(dāng)前對(duì)象的元素在數(shù)組中的下標(biāo)

2. 存儲(chǔ)時(shí)，如果出現(xiàn)hash值相同的key，此時(shí)有兩種情況。(1)如果key相同，則覆蓋原始值；(2)如果key不同（出現(xiàn)沖突），則將當(dāng)前的key-value放入鏈表中

3. 獲取時(shí)，直接找到hash值對(duì)應(yīng)的下標(biāo)，在進(jìn)一步判斷key是否相同，從而找到對(duì)應(yīng)值。

4. 理解了以上過(guò)程就不難明白HashMap是如何解決hash沖突的問(wèn)題，核心就是使用了數(shù)組的存儲(chǔ)方式，然后將沖突的key的對(duì)象放入鏈表中，一旦發(fā)現(xiàn)沖突就在鏈表中做進(jìn)一步的對(duì)比。

純屬個(gè)人總結(jié)，如有不對(duì)的，歡迎指出！感謝諸君的支持，點(diǎn)個(gè)贊吧！

以上就是JAVA--HashMap高頻率面試題的詳細(xì)內(nèi)容，更多關(guān)于JAVA HashMap面試題的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論