【java基礎(chǔ)系列】-Map集合之HashMap（java8）

提起Map想必大家都不陌生矢炼，用的最多的比如：HashMap、TreeMap阿纤、ConconrentHashMap等等句灌，本文主要介紹HashMap底層的一點東西，說的不全欠拾，后續(xù)會繼續(xù)補(bǔ)充胰锌。。藐窄。

你懂得越多资昧，你不懂的越多

簡介

HashMap在java.util包下，是AbstractMap的字類荆忍，屬于非線程安全的集合格带，HashMap的源碼相信很多人都看過，我再稍微總結(jié)下刹枉，做個筆記叽唱，以便后續(xù)復(fù)習(xí)，
先介紹下HashMap類的幾個變量：

DEFAULT_LOAD_FACTOR = 0.75f ：默認(rèn)裝載因子（0.75）
EFAULT_INITIAL_CAPACITY = 1 << 4：默認(rèn)初始容量（16）
MAXIMUM_CAPACITY = 1 << 30：最大容量（2^30）

接下來通過一個例子一步步介紹它底層的一些邏輯微宝，首先是構(gòu)造方法棺亭，HashMap提供了4中構(gòu)造方法：

//四種構(gòu)造方法
public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap() 
public HashMap(Map<? extends K, ? extends V> m)

具體的實現(xiàn)這里不多說了，重點是前三種構(gòu)造方法芥吟，雖然有初始容量和負(fù)載因子侦铜，但是方法內(nèi)部都沒有去初始化一個table专甩。具體什么時候回初始化钟鸵，下邊會介紹到。

擾動函數(shù)

介紹擾動函數(shù)之前涤躲，我們先看下HashMap的put()方法棺耍，可以看到在put方法里邊還有一個putVal()方法

public V put(K key, V value) {
      return putVal(hash(key), key, value, false, true);
 }

然后在這個方法里有個hash(key)，這個函數(shù)即被稱為擾動函數(shù)（到底是什么的擾動种樱，下邊再說）蒙袍，源碼如下：

static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

方法的實現(xiàn)非常簡單俊卤，首先獲取key的hashCode（就是最底層的hashCode()），然后將hashCode右移16位害幅，之后兩者異或消恍。先說下這樣做的好處是可以讓hashCode的高低位都參與到index（數(shù)據(jù)在map中的位置）的計算中，具體原因下邊再說以现。

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)   //1
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)   //2
            tab[i] = newNode(hash, key, value, null);
        else {
        ......

進(jìn)到putVal()方法的內(nèi)部狠怨，我們只看前半部分，后邊的擴(kuò)容邏輯暫時不看邑遏，注意注釋位置

1佣赖、首先判斷table是不是空，如果是空則resize()初始化记盒，上邊說的構(gòu)造函數(shù)未初始化的table憎蛤，就是在這初始化的，這塊有點像懶加載纪吮，用到的時候才創(chuàng)建
2俩檬、計算一個位置（index），看這個位置是否為空碾盟，如果為空則新建一個節(jié)點豆胸，可以看到計算方式為(n - 1) & hash，這里的n指的是table的長度巷疼，hash其實就是上邊擾動函數(shù)算出的hash值（高低16位異或那個）晚胡，這個地方還牽扯到另一個點就是為什么table的容量必須是2的n次冪，即便初始化的時候構(gòu)造參數(shù)不是2的n次冪嚼沿，hashmap內(nèi)部也會轉(zhuǎn)成2的n次冪大泄琅獭（就是下邊這個方法）。

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

這里就是通過一系列的右移+位或操作骡尽，因為或操作只要有一個1結(jié)果就是1遣妥，這樣就可以將位都變成1，比如10二進(jìn)制為1010攀细，右移1位為0101箫踩，位或結(jié)果為1111，之后再右移谭贪、或操作結(jié)果都是1111境钟，對應(yīng)十進(jìn)制為15，最后得到n+1=16俭识。為什么一定要轉(zhuǎn)為2的n次冪慨削，往下看。

2的n次冪

這里之所以把2的n次冪作為一個模塊，是因為之前一直沒搞懂這塊（異或缚态、與操作啥的磁椒，亂七八糟），所以打算著重記錄下玫芦，這里主要介紹兩個方面：一是為什么集合容量一定是2的n次冪浆熔；其次是這塊和擾動函數(shù)之間的關(guān)系。

我們知道桥帆，hash函數(shù)主要關(guān)注的無非兩點（分布均勻和較低的碰撞率）蘸拔，其實只需要關(guān)注碰撞率就好。碰撞率低數(shù)據(jù)分布自然均勻环葵，這里的2的n次冪和擾動函數(shù)就是實現(xiàn)低碰撞率的调窍，具體怎么實現(xiàn)呢，往下看：

我們假設(shè)容量n=2^4=16张遭，那么n-1=15用二進(jìn)制標(biāo)識就是01111邓萨，下面列舉4個隨機(jī)數(shù)與01111與操作。

alt

可以發(fā)現(xiàn)結(jié)果都不同菊卷，很好的避免了hash碰撞缔恳。

如果容量不是2的n次冪，假如容量n=10,那么n-1=9洁闰，用二進(jìn)制表示為01001歉甚，同樣對4個數(shù)進(jìn)行與操作，很明顯有3個結(jié)果是重復(fù)的扑眉，說明碰撞率很高纸泄。

alt

到這里我們知道了為什么容量一定是2的n次冪，那擾動函數(shù)起什么作用呢腰素？上邊說到擾動函數(shù)是將hashCode 的高低16位進(jìn)行異或操作聘裁，為的是讓高低位都可以參與到index的計算中，我們還是舉個例子說明：

假設(shè)容量n=16弓千，n-1=15二進(jìn)制是01111衡便，hash=....1010 0000 0110 0110，我們知道0與任何數(shù)都是0洋访，那么hash&(n-1)=(....1010 0000 0110 0110) & (01111)=.......0110镣陕，這里的結(jié)果省略了前邊的一堆0，可以看到結(jié)果就是hash的后四位（0110）姻政。

那么如果不使用擾動函數(shù)呆抑，直接hashCode & (n-1)，這樣的話如果兩個數(shù)的hashCode的后四位一樣扶歪，比如.....0101 0110
和......0110 0110理肺，計算出的結(jié)果都是0110，碰撞率很高善镰，所以相比于直接使用hashCode妹萨，擾動函數(shù)計算出的hash值，hash結(jié)果就沒那么碰巧炫欺。

講到這里乎完，我們應(yīng)該知道為什么容量取2的n次冪和引入擾動函數(shù)，其實兩者是結(jié)合使用的品洛，都是為了減小碰撞率树姨。

至此，我們大致了解了HashMap的為避免hash碰撞的做法和邏輯桥状，下邊我們分析下發(fā)生hash碰撞后HashMap做了什么帽揪？

putVal(）后半段（hash碰撞解決過程）

我們接著看putVal()方法，看下半部分的邏輯

 else {      //發(fā)生了碰撞
     Node<K,V> e; K k;
         if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))             //1辅斟、相同key转晰，直接覆蓋
             e = p;
         else if (p instanceof TreeNode)                                  //2、是否是紅黑樹的節(jié)點
             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
          else {                   
            for (int binCount = 0; ; ++binCount) {        //3士飒、尾插法插入元素
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)         //3-1 查邢、判斷鏈表長度是否大于默認(rèn)值8
                        treeifyBin(tab, hash);
                        break;
                 }
                 if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))    //3-2、鏈表中是否有相同的key
                        break;
                    p = e;
              }
         }
         if (e != null) {                 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
         }
  }
        ++modCount;
        if (++size > threshold) 
            resize();
        afterNodeInsertion(evict);
        return null;

這段主要是發(fā)生hash碰撞后的處理流程酵幕，根據(jù)注釋位置扰藕，大致介紹下：

1、這里的p指的是上邊根據(jù)(n-1) & hash算出的位置所對應(yīng)的值芳撒，如果key和hash值相同邓深，說明是同一個key，直接覆蓋
2笔刹、判斷是否是紅黑樹的節(jié)點庐完，如果是則直接put荚板，紅黑樹相關(guān)操作后續(xù)再說糠聪。
3、不是相同的key尺锚，且不是紅黑樹節(jié)點酷师，走正常的添加邏輯讶凉，也就是尾插法將元素放到最后一個位置，在這中間有兩個判斷山孔，
- 3-1懂讯、判斷鏈表的長度是否大于臨界值8，如果大于則進(jìn)入一個叫treeifyBin(tab, hash)的方法台颠，這個方法在這就不細(xì)說了褐望，主要做了兩件事：如果整個table的長度小于64只進(jìn)行resize()擴(kuò)容勒庄，否則如果長度大于64則將當(dāng)前鏈表結(jié)構(gòu)轉(zhuǎn)為紅黑樹。
- 3-2瘫里、在尾插法遍歷過程中实蔽，如果發(fā)現(xiàn)有相同的Key，直接break跳出循環(huán)谨读。

至此局装，我們已經(jīng)了解了HashMap的put大致流程，接下來看下HashMap的擴(kuò)容機(jī)制劳殖。

擴(kuò)容機(jī)制 resize()

我們知道铐尚，當(dāng)table的長度大于64并且某一鏈表的長度大于8的時候，會觸發(fā)擴(kuò)容哆姻，也就是resize()宣增，先看源碼

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;   
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {              //1、如果原始table的長度大于最大值（2^30）矛缨，將臨界值設(shè)為int的最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
        //2统舀、如果老數(shù)組長度的2倍<最大容量 && 老數(shù)組的長度>默認(rèn)容量，將新的臨界值設(shè)為原始臨界值的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&   oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;                           //3劳景、到此為止誉简，計算出了新的capcity（容量）和threshold（臨界值）
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {                        
            for (int j = 0; j < oldCap; ++j) {             //4、遍歷老數(shù)組盟广，復(fù)制元素到新數(shù)組
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)         //5闷串、如果鏈表只有一個節(jié)點，直接放到 hash & (newCap - 1) 位置
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)               //6筋量、如果是紅黑樹節(jié)點烹吵，走紅黑樹擴(kuò)容邏輯
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {                                                            //7、鏈表擴(kuò)容邏輯（重點桨武，下邊細(xì)說）
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {       //7-1肋拔、判斷元素在新數(shù)組中的位置是否需要改變
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {                                   // 8、需要改變位置的鏈表尾插邏輯
                                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;        //9呀酸、需要改變位置的鏈表放到table中的新位置
                        }
                    }
                }
            }
        }
        return newTab;
    }

以上就是rezise()擴(kuò)容機(jī)制的詳細(xì)流程凉蜂，下邊重點說下普通鏈表的擴(kuò)容邏輯（注釋7）性誉，首先判斷的是元素在新數(shù)組的位置是否需要改變窿吩，判斷公式為e.hash & oldCap错览，注意不是hash & (oldCap-1)，下邊舉幾個個例子說明下倾哺，假設(shè)初始容量是oldCap=16（0001 0000)刽脖，擴(kuò)容后容量為newCap=32（0010 0000）。

1忌愚、假設(shè)e.hash=10（0000 1010），那么e.hash & oldCap = 10(0000 1010) & 32(0010 0000)=0(0000 0000)菜循，結(jié)論是擴(kuò)容后不需要變更位置,翘地，我們驗證下：

擴(kuò)容之前的index=e.hash & (oldCap-1)=10(0000 1010) & 15(0000 1111) = 10(0000 1010)
擴(kuò)容后index=e.hash & (newCap)=10(0000 1010) & 31(0001 1111) = 10(0000 1010)癌幕，擴(kuò)容后位置不變

2、假設(shè)e.hash=17（0001 0001）昧穿，則e.hash & oldCap = 17(0001 0001) & 16(0001 0000)=16(0001 0000)勺远，結(jié)論是擴(kuò)容后需要變動位置，解釋如下：

擴(kuò)容之前的index=e.hash & (oldCap-1)=17(0001 0001) & 15(0000 1111) = 1(0000 0001)
擴(kuò)容后index=e.hash & (newCap)=17(0001 0001) & 31(0001 1111) = 17(0001 0001)时鸵，擴(kuò)容后的位置變了

注釋8意思是：如果改變鏈表頭結(jié)點在table中的位置胶逢，則新建一個鏈表，再把新鏈表的頭結(jié)點放到table中的新位置饰潜，對應(yīng)注釋9位置代碼初坠。可以發(fā)現(xiàn)新鏈表的頭結(jié)點在table中的位置是newTab[j+oldCap]彭雾，其實就是原始位置索引加上原始長度碟刺，這也對應(yīng)了上邊說的hash=17在原始table中的位置是1，rehash后在新table中的位置是17（1+16）薯酝。

拓展

說到擴(kuò)容就不得不提一下jdk1.7中在多線程下擴(kuò)容形成死鏈的問題半沽，在jdk1.7中擴(kuò)容使用的是頭插法，核心代碼如下：

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            //這個while循環(huán)是我們問題的關(guān)鍵
            while(null != e) {
                Entry<K,V> next = e.next;    //t1吴菠、線程1執(zhí)行到此處
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);          //重新計算位置
                e.next = newTable[i];             //頭插法插入當(dāng)前元素
                newTable[i] = e;
                e = next;
            }
        }
    }

首先我們了解下頭插法：
假設(shè)有3個元素者填，

1、插入元素a做葵，此時e指向a占哟，next指向b

2、插入b酿矢，此時e指向b重挑，next指向c:

3、插入c:

死鏈的產(chǎn)生：當(dāng)兩個線程都執(zhí)行擴(kuò)容方法時棠涮，假設(shè)線程1執(zhí)行到代碼注釋t1處（此時e指向的是a）谬哀，此時線程2來了，重新執(zhí)行了擴(kuò)容并將table更新為newTab严肪，這時線程1來了史煎，對于線程1來說谦屑，由于e指向的是a，然后執(zhí)行代碼e.next = newTable[i]篇梭，e.next指向了鏈表的頭結(jié)點（也就是c）,然后又執(zhí)行newTable[i] = e后將頭結(jié)點賦為a氢橙，此時的結(jié)構(gòu)就像下圖這樣

alt

在jdk1.8中采用尾插法避免了死鏈的問題，但是這并不意味著在jdk1.8中可以在并發(fā)場景下使用HashMap恬偷，因為它內(nèi)部并沒有集成鎖機(jī)制悍手，多線程下仍然存在數(shù)據(jù)不一致的情況。至此袍患，我們大致了解了HashMap的擴(kuò)容機(jī)制以及jdk1.7中的死鏈相關(guān)問題坦康。

小結(jié)

此篇文章大概介紹了HashMap中的幾個關(guān)注點：擾動函數(shù)、table長度為什么是2的n次冪诡延、hash碰撞解決滞欠、擴(kuò)容機(jī)制（resize）以及jdk1.7死鏈問題。至于擴(kuò)容引入的關(guān)于紅黑樹相關(guān)知識肆良，后期打算單獨拉一個模塊來詳細(xì)介紹下筛璧，這里就不多說了。