Map 類集合

image

Java Map類集合，與Collections類集合存在很大不同铅乡。它是與Collection 類平級(jí)的一個(gè)接口疗锐。

在集合框架中允乐，通過(guò)部分視圖方法這一根 微弱的線聯(lián)系起來(lái)。

（在之后的分享中茫因，我們會(huì)討論到Collections 框架的內(nèi)容）

Map類集合中的存儲(chǔ)單位是K-V鍵值對(duì)蚪拦，就是 使用一定的哈希算法形成一組比較均勻的哈希值作為Key，Value值掛在Key上冻押。

Map類 的特點(diǎn)：

• 沒(méi)有重復(fù)的Key驰贷，可以具有多個(gè)重復(fù)的Value

• Value可以是List/Map/Set對(duì)象

• KV是否允許為null，以實(shí)現(xiàn)類的約束為準(zhǔn)

從jdk1.0-1.5洛巢，這幾個(gè)重點(diǎn)KV集合類括袒，見證了Java語(yǔ)言成為工業(yè)級(jí)語(yǔ)言的成長(zhǎng)歷程。

知識(shí)點(diǎn)：

1. Map 類 特有的三個(gè)方法是keySet()稿茉、values()锹锰、entrySet()芥炭，其中values()方法返回的視圖的集合實(shí)現(xiàn)類是Values extends AbstractCollection<V>，沒(méi)有實(shí)現(xiàn)add操作恃慧，實(shí)現(xiàn)了remove/clear等相關(guān)操作园蝠，調(diào)用add方法時(shí)會(huì)拋出異常。
2. 在大多數(shù)情況下糕伐，直接使用ConcurrentHashMap替代HashMap沒(méi)有任何問(wèn)題砰琢，性能上面差別不大，且線程安全良瞧。
3. 任何Map類集合中陪汽，都要盡量避免KV設(shè)置為null值。
4. Hashtable - HashMap - ConcurrentHashMap 之間的關(guān)系 大致相當(dāng)于 Vector - ArrayList - CopyOnWriteArrayList 之間的關(guān)系褥蚯，當(dāng)然HashMap 和 ConcurrentHashMap之間性能差距更小挚冤。

一、hashCode()

哈希算法 哈希值

在Object 類中赞庶，hashCode()方法是一個(gè)被native修飾的類训挡，JavaDoc中描述的是返回該對(duì)象的哈希值。

那么哈希值這個(gè)返回值是有什么作用呢歧强？

主要是保證基于散列的集合澜薄，如HashSet、HashMap以及HashTable等摊册，在插入元素時(shí)保證元素不可重復(fù)肤京，同時(shí)為了提高元素的插入刪除便利效率而設(shè)計(jì)；主要是為了查找的便捷性而存在茅特。

拿Set進(jìn)行舉例忘分，

眾所周知，Set集合是不能重復(fù)白修，如果每次添加數(shù)據(jù)都拿新元素去和集合內(nèi)部元素進(jìn)行逐一地equal()比較妒峦，那么插入十萬(wàn)條數(shù)據(jù)的效率可以說(shuō)是非常低的。

所以在添加數(shù)據(jù)的時(shí)候就出現(xiàn)了哈希表的應(yīng)用兵睛，哈希算法也稱之為散列算法肯骇，當(dāng)添加一個(gè)值的時(shí)候，先去計(jì)算出它的哈希值祖很，根據(jù)算出的哈希值將數(shù)據(jù)插入指定位置累盗。這樣的話就避免了一直去使用equal()比較的效率問(wèn)題。

具體表現(xiàn)在：

• 如果指定位置為空突琳，則直接添加
• 如果指定位置不為空若债，調(diào)用equal() 判斷兩個(gè)元素是否相同，如果相同則不存儲(chǔ)

上述第二種情況中拆融，如果兩個(gè)元素不相同蠢琳，但是hashCode()相同啊终，那就是發(fā)生了我們所謂的哈希碰撞。

哈希碰撞的概率取決于hashCode()計(jì)算方式和空間容量的大小傲须。

這種情況下蓝牲，會(huì)在相同的位置，創(chuàng)建一個(gè)鏈表泰讽，把key值相同的元素存放到鏈表中例衍。

image

在HashMap中就是使用拉鏈法來(lái)解決hashCode沖突。

總結(jié)

hashCode是一個(gè)對(duì)象的標(biāo)識(shí)已卸，Java中對(duì)象的hashCode是一個(gè)int類型值佛玄。通過(guò)hashCode來(lái)指定數(shù)組的索引可以快速定位到要找的對(duì)象在數(shù)組中的位置，之后再遍歷鏈表找到對(duì)應(yīng)值累澡，理想情況下時(shí)間復(fù)雜度為O(1)梦抢，并且不同對(duì)象可以擁有相同的hashCode。

HashMap 底層實(shí)現(xiàn)

帶著問(wèn)題

1. HashMap 的長(zhǎng)度為什么默認(rèn)初始長(zhǎng)度是16愧哟，并且每次resize()的時(shí)候奥吩，長(zhǎng)度必須是2的冪次方？
2. 你熟悉HashMap的擴(kuò)容機(jī)制嗎蕊梧？
3. 你熟悉HashMap的死鏈問(wèn)題嗎霞赫？
4. Java 7 和 Java 8 HashMap有哪些差別？
5. 為什么Java 8之后肥矢，HashMap端衰、ConcurrentHashMap要引入紅黑樹？

0. 簡(jiǎn)介

1. HashMap 基于哈希表的Map接口實(shí)現(xiàn)的橄抹，是以Key-Value存儲(chǔ)形式存在靴迫；
2. 非線程安全惕味；
3. key value都可以為null楼誓；
4. HashMap中的映射不是有序的；
5. 在 JDK1.8 中名挥，HashMap 是由 數(shù)組+鏈表+紅黑樹構(gòu)成疟羹，新增了紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)；
6. 當(dāng)一個(gè)哈希桶存儲(chǔ)的鏈表長(zhǎng)度大于8 會(huì)將鏈表轉(zhuǎn)換成紅黑樹禀倔，小于6時(shí)則從紅黑樹轉(zhuǎn)換成鏈表榄融；
7. 1.8之前和1.8及以后的源碼，差別較大

1. 存儲(chǔ)結(jié)構(gòu)

在 JDK1.8 中救湖，HashMap 是由 數(shù)組+鏈表+紅黑樹構(gòu)成愧杯，新增了紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)。

通過(guò)哈希來(lái)確認(rèn)到數(shù)組的位置鞋既，如果發(fā)生哈希碰撞就以鏈表的形式存儲(chǔ) 力九，但是這樣如果鏈表過(guò)長(zhǎng)來(lái)的話耍铜，HashMap會(huì)把這個(gè)鏈表轉(zhuǎn)換成紅黑樹來(lái)存儲(chǔ)，閾值為8跌前。

下面是HashMap的結(jié)構(gòu)圖：

image

2. 重要屬性

2.1 table

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

在JDK1.8中我們了解到HashMap是由數(shù)組加鏈表加紅黑樹來(lái)組成的結(jié)構(gòu)其中table就是HashMap中的數(shù)組棕兼。

2.2 size

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

HashMap中 鍵值對(duì)存儲(chǔ)數(shù)量。

2.3 loadFactor

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

負(fù)載因子抵乓。負(fù)載因子是權(quán)衡資源利用率與分配空間的系數(shù)伴挚。當(dāng)元素總量 > 數(shù)組長(zhǎng)度 * 負(fù)載因子 時(shí)會(huì)進(jìn)行擴(kuò)容操作。

2.4 threshold

    /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

擴(kuò)容閾值灾炭。threshold = 數(shù)組長(zhǎng)度 * 負(fù)載因子茎芋。超過(guò)后執(zhí)行擴(kuò)容操作。

2.5 TREEIFY_THRESHOLD/UNTREEIFY_THRESHOLD

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

樹形化閾值咆贬。當(dāng)一個(gè)哈希桶存儲(chǔ)的鏈表長(zhǎng)度大于8 會(huì)將鏈表轉(zhuǎn)換成紅黑樹败徊，小于6時(shí)則從紅黑樹轉(zhuǎn)換成鏈表。

3. 增加元素

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

3.1 hash()

可以看到實(shí)際執(zhí)行添加元素的是putVal()操作掏缎，在執(zhí)行putVal()之前皱蹦，先是對(duì)key執(zhí)行了hash()方法，讓我們看下里面做了什么

    static final int hash(Object key) {
        int h;
        // key.hashCode()：返回散列值也就是hashcode
        // ^ ：按位異或
        // >>>:無(wú)符號(hào)右移眷蜈，忽略符號(hào)位沪哺，空位都以0補(bǔ)齊
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

key==null說(shuō)明，HashMap中是支持key為null的情況的酌儒。

同樣的方法在Hashstable中是直接用key來(lái)獲取hashCode辜妓，沒(méi)有key==null的判斷，所以Hashstable是不支持key為null的忌怎。

再回來(lái)說(shuō)這個(gè)hash()方法籍滴。這個(gè)方法用專業(yè)術(shù)語(yǔ)來(lái)稱呼就叫做擾動(dòng)函數(shù)**。

使用hash()也就是擾動(dòng)函數(shù)榴啸，是為了防止一些實(shí)現(xiàn)比較差的hashCode()方法孽惰。換句話來(lái)說(shuō)，就是為了減少哈希碰撞鸥印。

JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡(jiǎn)化勋功，但是原理不變。我們?cè)倏聪翵DK1.7中是怎么做的库说。

        // code in JDK1.7
        static int hash(int h) {
            // This function ensures that hashCodes that differ only by
            // constant multiples at each bit position have a bounded
            // number of collisions (approximately 8 at default load factor).
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

相比于 JDK1.8 的 hash 方法 狂鞋，JDK 1.7 的 hash 方法的性能會(huì)稍差一點(diǎn)點(diǎn)，因?yàn)楫吘箶_動(dòng)了 4 次潜的。

?

知識(shí)延伸外鏈： JDK 源碼中 HashMap 的 hash 方法原理是什么骚揍？ - 胖君的回答 - 知乎
https://www.zhihu.com/question/20733617/answer/111577937

3.2 putVal()

再來(lái)看真正執(zhí)行增加元素操作的putVal()方法，

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 當(dāng)數(shù)組為空或長(zhǎng)度為0啰挪，初始化數(shù)組容量（resize() 方法是初始化或者擴(kuò)容用的）
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 計(jì)算數(shù)組下標(biāo) i = (n-1) & hash
        // 如果這個(gè)位置沒(méi)有元素信不，則直接創(chuàng)建Node并存值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 這個(gè)位置已有元素
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // hash值纤掸、key值相等，用e變量獲取到當(dāng)前位置這個(gè)元素的引用浑塞，后面用于替換已有的值
                e = p;
            else if (p instanceof TreeNode)
                // 當(dāng)前是以紅黑樹方式存儲(chǔ)借跪，執(zhí)行其特有的putVal方法 -- putTreeVal
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 當(dāng)前是以鏈表方式存儲(chǔ)，開始遍歷鏈表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // 這里是插入到鏈表尾部酌壕！
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 超過(guò)閾值掏愁，存儲(chǔ)方式轉(zhuǎn)化成紅黑樹
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    // onlyIfAbsent 如果為true - 不覆蓋已存在的值
                    // 把新值賦值進(jìn)去
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 記錄修改次數(shù)
        ++modCount;
        // 判斷元素?cái)?shù)量是否超過(guò)閾值 超過(guò)則擴(kuò)容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

3.3 HashMap 的長(zhǎng)度為什么默認(rèn)初始長(zhǎng)度是16，并且每次resize()的時(shí)候卵牍，長(zhǎng)度必須是2的冪次方果港？

這是一個(gè)常見的面試題。這個(gè)問(wèn)題描述的設(shè)計(jì)糊昙，實(shí)際上為了服務(wù)于從Key映射到數(shù)組下標(biāo)index的Hash算法辛掠。

前面提到了，我們?yōu)榱俗孒ashMap存儲(chǔ)高效释牺，應(yīng)該盡量減少哈希碰撞萝衩，也就是說(shuō)，應(yīng)該讓元素分配得盡可能均勻没咙。

Hash 值的范圍值-2147483648到2147483647猩谊，前后加起來(lái)大概40億的映射空間，只要哈希函數(shù)映射得比較均勻松散祭刚，一般應(yīng)用是很難出現(xiàn)碰撞的牌捷。但問(wèn)題是一個(gè)40億長(zhǎng)度的數(shù)組，內(nèi)存是放不下的涡驮。所以這個(gè)散列值是不能直接拿來(lái)用的暗甥。

所以才需要一個(gè)映射的算法。這個(gè)計(jì)算方式就是3.2中有出現(xiàn)的(n - 1) & hash捉捅。

我們來(lái)進(jìn)一步演示一下這個(gè)算法：

1. 假設(shè)有一個(gè)key="book"
2. 計(jì)算book的hashCode值撤防，結(jié)果為十進(jìn)制的3029737，二進(jìn)制的101110001110101110 1001锯梁。
3. 假定HashMap長(zhǎng)度是默認(rèn)的16即碗，計(jì)算Length-1的結(jié)果為十進(jìn)制的15焰情，二進(jìn)制的1111陌凳。
4. 把以上兩個(gè)結(jié)果做與運(yùn)算，101110001110101110 1001 & 1111 = 1001内舟，十進(jìn)制是9合敦，所以 index=9。

通過(guò)這種與運(yùn)算的方式验游，能夠和取模運(yùn)算一樣的效果hashCode % length充岛，在上述例子中就是3029737 % 16=9保檐。

并且通過(guò)位運(yùn)算的方式大大提高了性能。

可能到這里崔梗，你還是不知道為什么長(zhǎng)度必須是2的冪次方夜只，也是因?yàn)檫@種位運(yùn)算的方法。

長(zhǎng)度16或者其他2的冪蒜魄，Length-1的值是所有二進(jìn)制位全為1扔亥，這種情況下，index的結(jié)果等同于HashCode后幾位的值谈为。只要輸入的HashCode本身分布均勻旅挤，Hash算法的結(jié)果就是均勻的。如果HashMap的長(zhǎng)度不是2的冪次方伞鲫，會(huì)出現(xiàn)某些index永遠(yuǎn)不會(huì)出現(xiàn)的情況粘茄，這個(gè)顯然不符合均勻分布的原則和期望。所以在源碼里面一直都在強(qiáng)調(diào)power-of-two expansion和size must be power of two秕脓。

另外柒瓣，HashMap 構(gòu)造函數(shù)允許用戶傳入的容量不是 2 的 n 次方，因?yàn)樗梢宰詣?dòng)地將傳入的容量轉(zhuǎn)換為 2 的 n 次方吠架。

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

4. HashMap 擴(kuò)容

接下來(lái)我們來(lái)講講HashMap擴(kuò)容相關(guān)的知識(shí)嘹朗。

4.1 擴(kuò)容

HashMap的初始長(zhǎng)度是16，假設(shè)HashMap中的鍵值對(duì)一直在增加诵肛，但是table數(shù)組容量一直不變屹培，那么就會(huì)發(fā)生哈希碰撞，查找的效率肯定會(huì)越來(lái)越低怔檩。所以當(dāng)鍵值對(duì)數(shù)量超過(guò)某個(gè)閾值的時(shí)候褪秀，HashMap就會(huì)執(zhí)行擴(kuò)容操作。

那么擴(kuò)容的閾值是怎么計(jì)算的呢薛训？

閾值 = 數(shù)組長(zhǎng)度 * 負(fù)載因子

threshold = capacity * loadFactor

每次擴(kuò)容后媒吗，threshold 加倍

上述計(jì)算就出現(xiàn)在resize()方法中。下面會(huì)詳細(xì)解析這個(gè)方法乙埃。我們先繼續(xù)往下講闸英。

loadFactor這個(gè)參數(shù)，我們之前提到過(guò)介袜，負(fù)載因子是權(quán)衡資源利用率與分配空間的系數(shù)甫何。至于為什么是0.75呢？這個(gè)實(shí)際上就是一個(gè)作者認(rèn)為比較好的權(quán)衡遇伞，當(dāng)然你也可以通過(guò)構(gòu)造方法手動(dòng)設(shè)置負(fù)載因子 辙喂。public HashMap(int initialCapacity, float loadFactor) {...)。

接下去再來(lái)到這里的主角resize()方法

    final Node<K,V>[] resize() {
        // 舊數(shù)組引用
        Node<K,V>[] oldTab = table;
        // 舊數(shù)組長(zhǎng)度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 舊閾值
        int oldThr = threshold;
        // 新數(shù)組長(zhǎng)度、新閾值
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 舊數(shù)組已經(jīng)超過(guò)了數(shù)組的最大容量
                // 閾值改成最大巍耗，直接返回舊數(shù)組秋麸，不操作了
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // newCap 變成原來(lái)的 兩倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 執(zhí)行擴(kuò)容操作，新閾值 = 舊閾值 * 2
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            // 初始閾值被手動(dòng)設(shè)置過(guò)
            // 數(shù)組容量 = 初始閾值
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 初始化操作
            // 數(shù)組容量 = 默認(rèn)初始容量
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 初始閾值 = 容量 * 默認(rèn)負(fù)載因子
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            // 如果在前面閾值都沒(méi)有被設(shè)置過(guò)
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 更新閾值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            // 創(chuàng)建數(shù)組
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // 更新table引用的數(shù)組
        table = newTab;
        if (oldTab != null) {
            // 擴(kuò)容
            for (int j = 0; j < oldCap; ++j) {
                // 遍歷舊數(shù)組
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    // 取出這個(gè)位置的頭節(jié)點(diǎn)
                    // 把舊引用取消炬太，方便垃圾回收
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 紅黑樹的處理
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        ....
                    }
                }
            }
        }
        return newTab;
    }

                        // 鏈表的處理  這個(gè)鏈表處理實(shí)際上非常的巧妙
                        // 定義了兩條鏈
                        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) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                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;
                        }

上述代碼紅黑樹和鏈表的處理不知道大家看懂了沒(méi)有灸蟆，我反正在第一次看的時(shí)候有點(diǎn)暈乎。但是理解了之后有感覺(jué)非常的巧妙亲族。

拿鏈表處理打比方次乓，它干的就是把在遍歷舊的table數(shù)組的時(shí)候，把該位置的鏈表分成high鏈表和low鏈表孽水。具體是什么意思呢票腰？看下下面的舉例。

1. 有一個(gè)size為16的HashMap女气。有A/B/C/D/E/F六個(gè)元素杏慰，其中A/B/C的Hash值為5，D/E/F的Hash值為21炼鞠，我們知道計(jì)算數(shù)組下標(biāo)的方法是與運(yùn)算（效果相當(dāng)于取模運(yùn)算）缘滥，這樣計(jì)算出來(lái)，A/B/C/D/E/F的index = 5谒主，都會(huì)被存在index=5的位置上中朝扼。
2. 假設(shè)它們是依次插入，那么在index為5的位置上霎肯，就會(huì)有A->B->C->D->E->F這樣一個(gè)鏈表擎颖。
3. 當(dāng)這個(gè)HashMap要進(jìn)行擴(kuò)容的時(shí)候，此時(shí)我們有舊數(shù)組oldTable[]观游，容量為16搂捧，新數(shù)組newTable[]，容量為32（擴(kuò)容數(shù)組容量加倍）懂缕。
4. 當(dāng)遍歷到舊數(shù)組index=5的位置的時(shí)候允跑，進(jìn)入到上面提到的鏈表處理的代碼段中，對(duì)鏈表上的元素進(jìn)行Hash & oldCapacity的操作搪柑，Hash值為5的A/B/C計(jì)算之后為0聋丝，被分到了low鏈表，Hash為21的D/E/F被分到了high鏈表工碾。
5. 然后把low鏈表放入新數(shù)組的index=5的位置弱睦，把high鏈表放入到新數(shù)組的index=5+16=21的位置。

紅黑樹相關(guān)的操作雖然代碼不同倚喂，但是實(shí)際上要干的事情是一樣的每篷。就是把相同位置的不同Hash大小的鏈表元素在新table數(shù)組中進(jìn)行分離。希望講到這里你能聽懂端圈。

4.2 HashMap 死鏈問(wèn)題

Java7的HashMap會(huì)存在死循環(huán)的問(wèn)題焦读，主要原因就在于，Java7中舱权，HashMap擴(kuò)容轉(zhuǎn)移后矗晃，前后鏈表順序倒置，在轉(zhuǎn)移過(guò)程中其他線程修改了原來(lái)鏈表中節(jié)點(diǎn)的引用關(guān)系宴倍，導(dǎo)致在某Hash桶位置形成了環(huán)形鏈表张症，此時(shí)get(key)，如果key不存在于這個(gè)HashMap且key的Hash結(jié)果等于那個(gè)形成了循環(huán)鏈表的Hash位置鸵贬，那么程序就會(huì)進(jìn)入死循環(huán)俗他；

Java8在同樣的前提下并不會(huì)引起死循環(huán)，原因是Java8擴(kuò)容轉(zhuǎn)移后前后鏈表順序不變阔逼，保持之前節(jié)點(diǎn)的引用關(guān)系兆衅。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    // JDK8 移出了hashSeed計(jì)算，因?yàn)橛?jì)算時(shí)會(huì)調(diào)用Random.nextInt()嗜浮，存在性能問(wèn)題
    // 很重要的transfer()
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 在此步驟完成之前羡亩，舊表上依然可以進(jìn)行元素的增加操作，這就是對(duì)象丟失原因之一
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// 寥寥幾行危融，卻極為重要
void transfer(Entry[] newTable, boolean rehash) {
    // newCapacity 是舊表的兩倍畏铆，這個(gè)擴(kuò)容大小
    int newCapacity = newTable.length;
    // 使用foreach 方式遍歷整個(gè)數(shù)組下標(biāo)
    for (Entry<K,V> e : table) {
        // 如果在這個(gè)slot上面存在元素，則開始遍歷上面的鏈表吉殃，知道e==null辞居，退出循環(huán)
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            // 當(dāng)前元素總是直接放在數(shù)組下標(biāo)的slot上，而不是放在鏈表的最后
            // 倒序插入新表
            // 這里是形成死鏈的關(guān)鍵步驟
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

延伸閱讀蛋勺。

https://www.yuque.com/docs/share/d4b7fbf9-5952-4b8b-ba69-5d70a07abb0d

5. Java 8 與 Java 7對(duì)比

1. 發(fā)生hash沖突時(shí)速侈，Java7會(huì)在鏈表頭部插入，Java8會(huì)在鏈表尾部插入
2. 擴(kuò)容后轉(zhuǎn)移數(shù)據(jù)迫卢，Java7轉(zhuǎn)移前后鏈表順序會(huì)倒置倚搬，Java8還是保持原來(lái)的順序
3. 引入紅黑樹的Java8極大程度地優(yōu)化了HashMap的性能‘
4. put 操作達(dá)到閾值時(shí)，Java7中是先擴(kuò)容再新增元素乾蛤，Java8是先新增元素再擴(kuò)容每界；
5. Java 8 改進(jìn)了 hash() 擾動(dòng)函數(shù)，提高了性能

6. 為什么要使用紅黑樹家卖？

很多人可能都會(huì)答上一句眨层，為了提高查找性能，但更確切地來(lái)說(shuō)的話上荡，采用紅黑樹的方法是為了提高在極端哈希沖突的情況下提高HashMap的性能趴樱。

極端哈希沖突的情況下馒闷，去測(cè)量Java7和Java8版本的HashMap的查詢性能差距。

image

Java 7的結(jié)果是可以預(yù)期的叁征。 HashMap.get()的性能損耗與HashMap本身的大小成比例增長(zhǎng)纳账。 由于所有鍵值對(duì)都在一個(gè)巨大的鏈表中的同一個(gè)桶中，查找一個(gè)條目需要平均遍歷一半這樣的列表（大小為n）捺疼。 因此O(n)復(fù)雜性在圖上可視化疏虫。

與此相對(duì)的是Java8，性能提高了很多啤呼，發(fā)生災(zāi)難性哈希沖突的情況下卧秘，在JDK 8上執(zhí)行的相同基準(zhǔn)測(cè)試會(huì)產(chǎn)生O（logn）最差情況下的性能。

關(guān)于此處的算法優(yōu)化實(shí)際上在JEP-180中有描述到官扣，

另外如果Key對(duì)象如果不是Comparable的話翅敌，那么發(fā)生重大哈希沖突時(shí)，插入和刪除元素的效率會(huì)變很差惕蹄。（因?yàn)榈讓訉?shí)現(xiàn)時(shí)紅黑樹哼御，需要通過(guò)compare方法去確定順序）

當(dāng)HashMap想要為一個(gè)鍵找到對(duì)應(yīng)的位置時(shí)，它會(huì)首先檢查新鍵和當(dāng)前檢索到的鍵之間是否可以比較（也就是實(shí)現(xiàn)了Comparable接口）焊唬。如果不能比較恋昼，它就會(huì)通過(guò)調(diào)用tieBreakOrder(Objecta,Object b) 方法來(lái)對(duì)它們進(jìn)行比較。這個(gè)方法首先會(huì)比較兩個(gè)鍵對(duì)象的類名赶促，如果相等再調(diào)用System.identityHashCode 方法進(jìn)行比較液肌。這整個(gè)過(guò)程對(duì)于我們要插入的500000個(gè)元素來(lái)說(shuō)是很耗時(shí)的。另一種情況是鸥滨，如果鍵對(duì)象是可比較的嗦哆，整個(gè)流程就會(huì)簡(jiǎn)化很多。因?yàn)殒I對(duì)象自身定義了如何與其它鍵對(duì)象進(jìn)行比較婿滓，就沒(méi)有必要再調(diào)用其他的方法老速，所以整個(gè)插入或查找的過(guò)程就會(huì)快很多。值得一提的是凸主，在兩個(gè)可比的鍵相等時(shí)（compareTo 方法返回 0）的情況下橘券，仍然會(huì)調(diào)用tieBreakOrder 方法。

又可能會(huì)有人說(shuō)了卿吐，哪有這么極端的哈希沖突旁舰？

這個(gè)實(shí)際上是一個(gè)安全性的考慮，雖然在正常情況下很少有可能發(fā)生很多沖突嗡官。但是想象一下箭窜，如果Key來(lái)自不受信任的來(lái)源（例如從客戶端收到的HTTP頭名稱），那么就有可能收到偽造key值衍腥，并且這種做法不難磺樱，因?yàn)楣Ｋ惴ㄊ谴蠹叶贾赖哪擅ǎ僭O(shè)有人有心去偽造相同的哈希值的key值，那么你的HashMap中就會(huì)出現(xiàn)上述這種極端哈希沖突的情況竹捉。 現(xiàn)在芜辕，如果你去對(duì)這個(gè)HashMap執(zhí)行多次的查詢請(qǐng)求，就會(huì)發(fā)現(xiàn)程序執(zhí)行查詢的效率會(huì)變得很慢活孩，cpu占用率很高物遇，程序甚至?xí)芙^對(duì)外提供服務(wù)乖仇。

延伸外鏈：https://www.yuque.com/docs/share/a934d775-66a6-4d11-8e42-a1dfb88f5674