HashMap底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表，JDK1.8中還引入了紅黑樹，當(dāng)鏈表長(zhǎng)度超過(guò)8個(gè)時(shí)，會(huì)將鏈表轉(zhuǎn)成紅黑樹，以提升其查找性能。

那么，給出一個(gè)<key, value>節(jié)點(diǎn)，HashMap是如何確定這個(gè)節(jié)點(diǎn)應(yīng)該放在具體哪個(gè)位置呢？（以JDK1.8為例）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // HashMap沒有被初始化，則先進(jìn)行初始化
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // 節(jié)點(diǎn)所在index = (n - 1) & hash，該位置沒有數(shù)據(jù)，則直接將新節(jié)點(diǎn)放在數(shù)組的index位置上
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else { // index上已經(jīng)有節(jié)點(diǎn)了
    Node<K,V> e; K k;
    // 如果新key與原來(lái)的key一樣，則e指向原節(jié)點(diǎn)p（后面會(huì)用新value替換e所指向的value）
    if (p.hash == hash &&
      ((k = p.key) == key || (key != null && key.equals(k)))) 
      e = p;
    // 如果該節(jié)點(diǎn)是樹節(jié)點(diǎn)，則采用樹的插入算法，插入新節(jié)點(diǎn)
    else if (p instanceof HashMap.TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else { // 該節(jié)點(diǎn)是鏈表節(jié)點(diǎn)
      for (int binCount = 0; ; ++binCount) {
        // 將新節(jié)點(diǎn)插入到index所在鏈表的末端
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          // 鏈表節(jié)點(diǎn)超過(guò)8個(gè)，則進(jìn)行鏈表轉(zhuǎn)樹處理
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        // 同樣的，如果key已經(jīng)存在的話，則不進(jìn)行插入操作，而是后面進(jìn)行value替換
        if (e.hash == hash &&
          ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    // e != null的情況，就是key已經(jīng)存在了，這里統(tǒng)一進(jìn)行了新值value，替換舊值e.value的操作
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  // 插入后數(shù)組size 大于閾值的話，需要進(jìn)行擴(kuò)容
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

看源碼，節(jié)點(diǎn)落在數(shù)組中的index = （數(shù)組長(zhǎng)度 - 1） & key的hashcode，如果該index上沒有數(shù)據(jù)，則直接插到該index上，如果節(jié)點(diǎn)已經(jīng)有數(shù)據(jù)了，則把新節(jié)點(diǎn)插入該index對(duì)應(yīng)的鏈表中（如果鏈表節(jié)點(diǎn)大于8個(gè)，會(huì)進(jìn)行鏈表轉(zhuǎn)樹，之后的插入算法就變成了樹的插入算法）。

每次put之后，會(huì)檢測(cè)一下是否需要擴(kuò)容，size超過(guò)了 總?cè)萘?* 負(fù)載因子，則會(huì)擴(kuò)容。默認(rèn)情況下，16 * 0.75 = 12個(gè)。

1、為什么初始容量是16

當(dāng)容量為2的冪時(shí)，上述n -1 對(duì)應(yīng)的二進(jìn)制數(shù)全為1，這樣才能保證它和key的hashcode做&運(yùn)算后，能夠均勻分布，這樣才能減少hash碰撞的次數(shù)。至于默認(rèn)值為什么是16，而不是2 、4、8，或者32、64、1024等，我想應(yīng)該就是個(gè)折中處理，過(guò)小會(huì)導(dǎo)致放不下幾個(gè)元素，就要進(jìn)行擴(kuò)容了，而擴(kuò)容是一個(gè)很消耗性能的操作。取值過(guò)大的話，無(wú)疑會(huì)浪費(fèi)更多的內(nèi)存空間。因此在日常開發(fā)中，如果可以預(yù)估HashMap會(huì)存入節(jié)點(diǎn)的數(shù)量，則應(yīng)該在初始化時(shí)，指定其容量。

2、為什么負(fù)載因子是0.75

也是一個(gè)綜合考慮，如果設(shè)置過(guò)小，HashMap每put少量的數(shù)據(jù)，都要進(jìn)行一次擴(kuò)容，而擴(kuò)容操作會(huì)消耗大量的性能。如果設(shè)置過(guò)大的話，如果設(shè)成1，容量還是16，假設(shè)現(xiàn)在數(shù)組上已經(jīng)占用的15個(gè)，再要put數(shù)據(jù)進(jìn)來(lái)，計(jì)算數(shù)組index時(shí)，發(fā)生hash碰撞的概率將達(dá)到15/16，這違背的HashMap減少hash碰撞的原則。

補(bǔ)充知識(shí)：HashMap只有容量達(dá)到閥值才發(fā)生擴(kuò)容嗎？大錯(cuò)特錯(cuò)！

看了網(wǎng)上很多文章，說(shuō)HashMap在元素達(dá)到負(fù)載因子對(duì)應(yīng)數(shù)的時(shí)候就發(fā)生擴(kuò)容。如果你看過(guò)源碼就會(huì)發(fā)現(xiàn)，其實(shí)還有一種情況也可能會(huì)發(fā)生擴(kuò)容：樹形化的時(shí)候。

對(duì)象最終是如何放入HashMap中的?

HashMap底層是由數(shù)組+鏈表組成的，為了方便不懂的人更容易理解，那我們就先假設(shè)HashMap底層就是數(shù)組，先不管鏈表。

當(dāng)一個(gè)對(duì)象add到HashMap中，此時(shí)HashMap的add方法是如何來(lái)確定這個(gè)對(duì)象是放在數(shù)組中的哪個(gè)位置的呢？

拿JDK1.8來(lái)說(shuō)（其他JDK版本稍有不同，但大同小異）,大家應(yīng)該知道每一個(gè)對(duì)象天生都繼承了或程序員自己覆蓋了Object類的 hashCode（）方法，此方法返回對(duì)象的hashcode值。

HashMap會(huì)有一個(gè)方法，先拿到要add進(jìn)HashMap中的對(duì)象的hashCode，再將這個(gè)hashCode異或上對(duì)象自身hashCode右移16位（是不是感覺說(shuō)的不是人話？這個(gè)步驟叫擾亂，這樣做的目的是為了讓hashCode每一位都盡可能用到，如果不理解沒關(guān)系并不影響接下來(lái)的閱讀），hashCode經(jīng)過(guò)上述步驟之后再&（數(shù)組長(zhǎng)度-1），計(jì)算的結(jié)果就是這個(gè)對(duì)象在數(shù)組中的位置了。我自己都覺得說(shuō)的不是人話，下面舉個(gè)例子，便于理解：

這里有一個(gè)Student對(duì)象的hashCode是：a

先把這個(gè)a右移16位 ， b=a>>>16;

然后a=a&b;

數(shù)組中的位置等于: a&(數(shù)組長(zhǎng)度-1)；

上述源碼如下：

h=key.hashCode();

h = key.hashCode()) ^ (h >>> 16）

數(shù)組位置=h&(數(shù)組長(zhǎng)度-1)；

好了， 我們已經(jīng)知道元素是如何在hashMap中的數(shù)組上如何定位了，現(xiàn)在假設(shè)一個(gè)極端情況（不可能發(fā)生，但是我用這個(gè)舉例子）:

假設(shè)數(shù)組長(zhǎng)度為1，根據(jù)源碼：

數(shù)組位置=h&（數(shù)組長(zhǎng)度-1）

那么有：

數(shù)組位置=h&（1-1）=0 ，無(wú)論什么對(duì)象，都定位到數(shù)組的第0個(gè)位置。

這個(gè)很好理解吧。無(wú)論元素是否一樣，由于數(shù)組長(zhǎng)度為1，所以元素通通定位到數(shù)組中第0個(gè)位置。大家都知道一個(gè)數(shù)組只能放一個(gè)元素?。磕窃趺崔k呢？我們用鏈表來(lái)解決這個(gè)問(wèn)題，把定位到這個(gè)位置的元素通過(guò)鏈表連接。這就是我一開始說(shuō)的：hashMap是數(shù)組+鏈表。

那樹形化又是什么東東呢？

想一下我們?yōu)槭裁匆肏ashMap，是因?yàn)橥ㄟ^(guò)Hash算法在理想情況下時(shí)間復(fù)雜度O(1)就能找到元素，特別快，但是我都說(shuō)了是理想情況，如果遇到上述發(fā)生hash碰撞（誰(shuí)jb取的名字，就是上面我才說(shuō)的，兩個(gè)元素定位到數(shù)組中同一個(gè)位置），且hash碰撞比較頻繁的話，那么當(dāng)我們get一個(gè)元素的時(shí)候，定位到了這個(gè)數(shù)組，還需要在數(shù)組中遍歷一次鏈表最終才能找到要get的元素，是不是已經(jīng)失去一部分使用HashMap的初心了？（因?yàn)樾枰闅v鏈表，所以時(shí)間復(fù)雜度就比之前高了）

所以JDK1.8使用紅黑樹這種數(shù)據(jù)結(jié)構(gòu)來(lái)解決鏈表過(guò)長(zhǎng)的問(wèn)題（可以簡(jiǎn)單理解為用紅黑樹遍歷比鏈表遍歷速度快，時(shí)間復(fù)雜度低，不懂紅黑樹的可以去搜搜看），默認(rèn)鏈表長(zhǎng)度達(dá)到8就將鏈表樹形化（變?yōu)榧t黑樹）。

回到最最開始我提到的，那為什么樹形化的時(shí)候可能會(huì)發(fā)生擴(kuò)容呢？

想想剛剛的例子數(shù)組長(zhǎng)度為1，所有元素全部在數(shù)組的第0個(gè)位置形成一條鏈表，這例子是一種極端情況，數(shù)組長(zhǎng)度過(guò)小，那自然就會(huì)經(jīng)常發(fā)生hash碰撞，那形成長(zhǎng)鏈表是肯定的，這個(gè)時(shí)候樹形化其實(shí)是治標(biāo)不治本，因?yàn)橐疰湵磉^(guò)長(zhǎng)的根本原因是數(shù)組過(guò)短，所以在JDK1.8源碼中，執(zhí)行樹形化之前，會(huì)先檢查數(shù)組長(zhǎng)度，如果長(zhǎng)度小于64，則對(duì)數(shù)組進(jìn)行擴(kuò)容，而不是進(jìn)行樹形化。

所以發(fā)生擴(kuò)容的時(shí)候有兩種情況，一種是元素達(dá)到閥值了，一種是HashMap準(zhǔn)備樹形化但又發(fā)現(xiàn)數(shù)組太短，這兩種情況均可能發(fā)生擴(kuò)容。

以上這篇HashMap容量和負(fù)載因子使用說(shuō)明就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論