一局服、簡(jiǎn)介

哈希表也叫散列表，是一種非常重要的數(shù)據(jù)結(jié)構(gòu)暴氏，底層實(shí)現(xiàn)是一個(gè) key - value 鍵值對(duì)祝蝠。應(yīng)用場(chǎng)景及其豐富音诈，許多緩存技術(shù)（比如 Redis）的核心其實(shí)就是在內(nèi)存中維護(hù)一張大的哈希表。Java 中的 HashMap 就是這樣一種結(jié)構(gòu)绎狭，不僅經(jīng)常用于開發(fā)當(dāng)中细溅，而且 HashMap 的實(shí)現(xiàn)原理也常常出現(xiàn)在各類的面試題中。

在哈希表中進(jìn)行添加坟岔，刪除谒兄，查找等操作，性能十分之高社付，不考慮哈希沖突的情況下承疲，僅需一次定位即可完成，時(shí)間復(fù)雜度為 O(1)鸥咖，接下來(lái)我們就來(lái)看看哈希表是如何實(shí)現(xiàn)達(dá)到驚艷的常數(shù)階 O(1) 的燕鸽。

我們知道，在數(shù)組中根據(jù)下標(biāo)查找某個(gè)元素啼辣，一次定位就可以達(dá)到啊研，哈希表利用了這種特性，哈希表的主干就是數(shù)組鸥拧。比如我們要新增或查找某個(gè)元素党远，我們通過(guò)把當(dāng)前元素的關(guān)鍵字通過(guò)某個(gè)函數(shù)映射到數(shù)組中的某個(gè)位置，通過(guò)數(shù)組下標(biāo)一次定位就可完成操作富弦。

存儲(chǔ)位置 = f(關(guān)鍵字)

其中沟娱，這個(gè)函數(shù) f 一般稱為哈希函數(shù)，這個(gè)函數(shù)的設(shè)計(jì)好壞會(huì)直接影響到哈希表的優(yōu)劣腕柜。

舉個(gè)例子济似，比如我們要在哈希表中執(zhí)行插入操作：

查找操作同理，先通過(guò)哈希函數(shù)計(jì)算出實(shí)際存儲(chǔ)地址盏缤，然后從數(shù)組中對(duì)應(yīng)地址取出即可砰蠢。

哈希沖突

然而沒(méi)有完美的設(shè)計(jì)，如果兩個(gè)不同的元素唉铜，通過(guò)哈希函數(shù)得出的實(shí)際存儲(chǔ)地址相同怎么辦台舱？也就是說(shuō)，當(dāng)我們對(duì)某個(gè)元素進(jìn)行哈希運(yùn)算潭流，得到一個(gè)存儲(chǔ)地址竞惋，然后要進(jìn)行插入的時(shí)候俩功，發(fā)現(xiàn)已經(jīng)被其他元素占用了，其實(shí)這就是所謂的哈希沖突碰声，也叫哈希碰撞。前面我們提到過(guò)熬甫，哈希函數(shù)的設(shè)計(jì)至關(guān)重要胰挑，好的哈希函數(shù)會(huì)盡可能地保證計(jì)算簡(jiǎn)單和散列地址分布均勻。但是椿肩，我們需要清楚的是瞻颂，數(shù)組是一塊連續(xù)的固定長(zhǎng)度的內(nèi)存空間，再好的哈希函數(shù)也不能保證得到的存儲(chǔ)地址絕對(duì)不發(fā)生沖突郑象。那么哈希沖突如何解決呢贡这？哈希沖突的解決方案有多種：開放定址法（發(fā)生沖突，繼續(xù)尋找下一塊未被占用的存儲(chǔ)地址）厂榛，散列函數(shù)法盖矫，鏈地址法，而 HashMap 即是采用了鏈地址法击奶。

二辈双、繼承結(jié)構(gòu)

和大多數(shù)集合類一樣，HashMap 也實(shí)現(xiàn)了 Cloneable 接口和 Serializable 接口柜砾，分別用來(lái)支持克隆以及支持序列化湃望。Map 接口也不用多說(shuō)，定義了一套 Map 集合類型的方法規(guī)范痰驱。

三证芭、屬性

public class HashMap<K,V> extends AbstractMap<K,V>

? ? implements Map<K,V>, Cloneable, Serializable {

? ? private static final long serialVersionUID = 362498820763181265L;

? ? // 默認(rèn)的初始化容量

? ? static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

? ? // 最大容量

? ? static final int MAXIMUM_CAPACITY = 1 << 30;

// 默認(rèn)負(fù)載因子

? ? static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 桶的樹化閾值

? ? static final int TREEIFY_THRESHOLD = 8;

// 桶的鏈表還原閾值

? ? static final int UNTREEIFY_THRESHOLD = 6;

// 最小樹形化容量閾值

? ? static final int MIN_TREEIFY_CAPACITY = 64;

? ? // 存儲(chǔ)元素的數(shù)組

? ? transient Node<K,V>[] table;

? ? // 用于存放 HashMap 的集合

? ? transient Set<Map.Entry<K,V>> entrySet;

? ? // 實(shí)際存儲(chǔ)的 key-value 鍵值對(duì)的個(gè)數(shù)

? ? transient int size;

? ? transient int modCount;

? ? int threshold;

? ? // 負(fù)載因子，代表了 table 的填充度有多少担映，默認(rèn)是 0.75

? ? final float loadFactor;

}

HashMap 的默認(rèn)初始化容量為 16废士，默認(rèn)負(fù)載因子為 0.75。

因?yàn)樵?JDK 1.8 以后采用了數(shù)組 + 鏈表 + 紅黑樹的結(jié)構(gòu)另萤，所以新增了 3 個(gè)與紅黑樹相關(guān)的參數(shù)湃密。第一個(gè)是桶的樹化閾值（TREEIFY_THRESHOLD），即鏈表轉(zhuǎn)成紅黑樹的閾值四敞，在存儲(chǔ)數(shù)據(jù)時(shí)泛源，當(dāng)鏈表長(zhǎng)度 > 該值時(shí)，則將鏈表轉(zhuǎn)換成紅黑樹忿危。第二個(gè)是桶的鏈表還原閾值（TREEIFY_THRESHOLD）达箍，即紅黑樹轉(zhuǎn)為鏈表的閾值，當(dāng)在擴(kuò)容時(shí)铺厨，此時(shí) HashMap 的數(shù)據(jù)存儲(chǔ)位置會(huì)重新計(jì)算缎玫，在重新計(jì)算存儲(chǔ)位置后硬纤，當(dāng)原有的紅黑樹內(nèi)數(shù)量 < 6 時(shí)，則將紅黑樹轉(zhuǎn)換成鏈表赃磨。第三個(gè)是最小樹形化容量閾值（MIN_TREEIFY_CAPACITY）筝家，即當(dāng)哈希表中的容量 > 該值時(shí)，才允許樹形化鏈表邻辉，即將鏈表轉(zhuǎn)換成紅黑樹溪王，否則，若桶內(nèi)元素太多時(shí)值骇，則直接擴(kuò)容莹菱，而不是樹形化，為了避免進(jìn)行擴(kuò)容吱瘩、樹形化選擇的沖突道伟，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD。

threshold 為閾值使碾，當(dāng) table == {} 時(shí)蜜徽，該值為初始容量（初始容量默認(rèn)為 16），當(dāng) table 被填充了票摇，也就是為 table 分配內(nèi)存空間后娜汁，threshold 一般為 capacity * loadFactory。HashMap 在進(jìn)行擴(kuò)容時(shí)需要參考 threshold兄朋，后面會(huì)詳細(xì)談到掐禁。

modCount 用于快速失敗，由于 HashMap 非線程安全颅和，在對(duì) HashMap 進(jìn)行迭代時(shí)傅事，如果期間其他線程的參與導(dǎo)致 HashMap 的結(jié)構(gòu)發(fā)生變化了（比如 put，remove 等操作）峡扩，需要拋出異常 ConcurrentModificationException蹭越。

四、數(shù)據(jù)結(jié)構(gòu)

因?yàn)?JDK 1.8 之后教届，HashMap 采用了數(shù)組 + 鏈表 + 紅黑樹的結(jié)構(gòu)响鹃，所以我們來(lái)看看在 HashMap 中鏈表和紅黑樹以及哈希函數(shù)是怎么實(shí)現(xiàn)的。

0x01案训、鏈表

static class Node<K,V> implements Map.Entry<K,V> {

? ? final int hash;

? ? final K key;

? ? V value;

? ? Node<K,V> next;

? ? Node(int hash, K key, V value, Node<K,V> next) {

? ? ? ? this.hash = hash;

? ? ? ? this.key = key;

? ? ? ? this.value = value;

? ? ? ? this.next = next;

? ? }

? ? public final K getKey()? ? ? ? { return key; }

? ? public final V getValue()? ? ? { return value; }

? ? public final String toString() { return key + "=" + value; }

? ? public final int hashCode() {

? ? ? ? return Objects.hashCode(key) ^ Objects.hashCode(value);

? ? }

? ? public final V setValue(V newValue) {

? ? ? ? V oldValue = value;

? ? ? ? value = newValue;

? ? ? ? return oldValue;

? ? }

? ? public final boolean equals(Object o) {

? ? ? ? if (o == this)

? ? ? ? ? ? return true;

? ? ? ? if (o instanceof Map.Entry) {

? ? ? ? ? ? Map.Entry<?,?> e = (Map.Entry<?,?>)o;

? ? ? ? ? ? if (Objects.equals(key, e.getKey()) &&

? ? ? ? ? ? ? ? Objects.equals(value, e.getValue()))

? ? ? ? ? ? ? ? return true;

? ? ? ? }

? ? ? ? return false;

? ? }

}

Node 是 HashMap 的一個(gè)內(nèi)部類买置，用來(lái)存放鏈表的節(jié)點(diǎn)信息，這個(gè)鏈表是單向的强霎。

0x02忿项、紅黑樹

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

? ? TreeNode<K,V> parent;? // red-black tree links

? ? TreeNode<K,V> left;

? ? TreeNode<K,V> right;

? ? TreeNode<K,V> prev;? ? // needed to unlink next upon deletion

? ? boolean red;

? ? TreeNode(int hash, K key, V val, Node<K,V> next) {

? ? ? ? super(hash, key, val, next);

? ? }

? ? /**

? ? * Returns root of tree containing this node.

? ? */

? ? final TreeNode<K,V> root() {

? ? ? ? for (TreeNode<K,V> r = this, p;;) {

? ? ? ? ? ? if ((p = r.parent) == null)

? ? ? ? ? ? ? ? return r;

? ? ? ? ? ? r = p;

? ? ? ? }

? ? }

? ? ...

}

0x03、哈希函數(shù)

static final int hash(Object key) {

? ? int h;

? ? return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

這里有個(gè)點(diǎn)比較有意思，這個(gè)哈希算法要將取到的哈希值與該哈希值右移 16 位后的數(shù)做異或運(yùn)算轩触。

為什么要這么做呢寞酿？直接通過(guò) key.hashCode() 獲取 hash 不就得了嗎？為什么在右移 16 位后進(jìn)行異或運(yùn)算脱柱？

答案：與 HashMap 的 table 數(shù)組下計(jì)算標(biāo)有關(guān)

我們?cè)谙旅嬷v解的 put/get 方法代碼塊中都出現(xiàn)了這樣一段代碼

// put 方法代碼塊中

tab[i = (n - 1) & hash])

// get 方法代碼塊中

tab[(n - 1) & hash])

我們知道這段代碼是根據(jù)索引得到 tab 中節(jié)點(diǎn)數(shù)據(jù)伐弹，它是如何與 hash 進(jìn)行與運(yùn)算后得到索引位置呢？假設(shè) tab.length() = 1 << 4

這樣做的根本原因是當(dāng)發(fā)生較大碰撞時(shí)也用樹形存儲(chǔ)降低了沖突榨为，減少了系統(tǒng)的開銷掸茅。

五、構(gòu)造方法

HashMap 共有四種形式的構(gòu)造方法柠逞，我們先看無(wú)參構(gòu)造方法：

public HashMap() {

? ? this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

無(wú)參構(gòu)造方法采用的就是默認(rèn)的負(fù)載因子，將默認(rèn)的負(fù)載因子 0.75 賦值給 loadFactor景馁。

再來(lái)看一下兩個(gè)參數(shù)的構(gòu)造方法：

public HashMap(int initialCapacity, float loadFactor) {

? ? // 當(dāng)指定的初始容量小于 0 時(shí)拋出 IllegalArgumentException 異常

? ? if (initialCapacity < 0)

? ? ? ? throw new IllegalArgumentException("Illegal initial capacity: " +

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? initialCapacity);

? ? // 當(dāng)指定的初始容量大于 MAXIMUM_CAPACITY 時(shí)板壮，就讓初始容量等于 MAXIMUM_CAPACITY

? ? if (initialCapacity > MAXIMUM_CAPACITY)

? ? ? ? initialCapacity = MAXIMUM_CAPACITY;

? ? // 設(shè)定 threshold，當(dāng) HashMap 的 size 達(dá)到 threshold 時(shí)合住，就要進(jìn)行 resize绰精，也就是擴(kuò)容

? ? if (loadFactor <= 0 || Float.isNaN(loadFactor))

? ? ? ? throw new IllegalArgumentException("Illegal load factor: " +

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loadFactor);

? ? this.loadFactor = loadFactor;

? ? this.threshold = tableSizeFor(initialCapacity);

}

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;

}

這個(gè)構(gòu)造方法的參數(shù)分別為初始化容量和負(fù)載因子。tablesizefor() 的主要功能是返回一個(gè)比給定整數(shù)大且最接近的 2 的冪次方整數(shù)透葛，如給定 10笨使，返回 2 的 4 次方 16。

注意：HashMap 要求容量必須是 2 的冪僚害。

首先硫椰，int n = cap - 1 是為了防止 cap 已經(jīng)是 2 的冪時(shí)，執(zhí)行完后面的幾條無(wú)符號(hào)右移操作之后萨蚕，返回的 capacity 是這個(gè) cap 的 2 倍靶草，因?yàn)?cap 已經(jīng)是 2 的冪了，就已經(jīng)滿足條件了岳遥。

如果 n 這時(shí)為 0 了（經(jīng)過(guò)了 cap - 1 之后）奕翔，則經(jīng)過(guò)后面的幾次無(wú)符號(hào)右移依然是 0，最后返回的 capacity 是1（最后有個(gè) n + 1 的操作）浩蓉。這里只討論 n 不等于 0 的情況派继。以 16 位為例，假設(shè)開始時(shí) n 為 0000 1xxx xxxx xxxx（x 代表不關(guān)心 0 還是 1）

第一次右移 n l= n >>> 1捻艳，由于 n 不等于 0驾窟，則 n 的二進(jìn)制表示中總會(huì)有一位為 1，這時(shí)考慮最高位的 1认轨。通過(guò)無(wú)符號(hào)右移 1 位纫普，則將最高位的 1 右移了 1 位，再做或操作，使得 n 的二進(jìn)制表示中與最高位的 1 緊鄰的右邊一位也為 1昨稼，如 0000 11xx xxxx xxxx节视。

第二次右移 n l= n >>> 2，注意假栓，這個(gè) n 已經(jīng)經(jīng)過(guò)了 n l= n >>> 1 操作寻行。此時(shí) n 為 0000 11xx xxxx xxxx，則 n 無(wú)符號(hào)右移兩位匾荆，會(huì)將最高位兩個(gè)連續(xù)的 1 右移兩位拌蜘，然后再與原來(lái)的 n 做或操作，這樣 n 的二進(jìn)制表示的高位中會(huì)有 4 個(gè)連續(xù)的 1牙丽，如 0000 1111 xxxx xxxx简卧。

第三次右移 n l= n >>> 4，這次把已經(jīng)有的高位中的連續(xù)的 4 個(gè) 1烤芦，右移 4 位举娩，再做或操作，這樣 n 的二進(jìn)制表示的高位中會(huì)有 8 個(gè)連續(xù)的 1构罗，如 0000 1111 1111 xxxx铜涉。

第。遂唧。芙代。你還忍心讓我繼續(xù)推么？相信聰明的你已經(jīng)想出來(lái)了盖彭，容量最大也就是 32 位的正數(shù)纹烹，所以最后一次n l= n >>> 16 可以保證最高位后面的全部置為 1，當(dāng)然如果是 32 個(gè) 1 的話召边，此時(shí)超出了 MAXIMUM_CAPACITY滔韵，所以取值到 MAXIMUN_CAPACITY。

再來(lái)看一下一個(gè)參數(shù)的構(gòu)造方法：

public HashMap(int initialCapacity) {

? ? this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

這個(gè)構(gòu)造方法的參數(shù)是初始化容量掌实，采用默認(rèn)的負(fù)載因子陪蜻。

六、常用方法

0x01贱鼻、put(K key, V value)

public V put(K key, V value) {

? ? return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

? ? ? ? ? ? ? ? ? boolean evict) {

? ? // 判定 table 不為空并且 table 長(zhǎng)度不可為 0宴卖，否則將從 resize 函數(shù)中獲取

? ? Node<K,V>[] tab; Node<K,V> p; int n, i;

? ? if ((tab = table) == null || (n = tab.length) == 0)

? ? ? ? n = (tab = resize()).length;

? ? // 這樣寫法有點(diǎn)繞，其實(shí)這里就是通過(guò)索引獲取 table 數(shù)組中的一個(gè)元素看是否為 null

? ? if ((p = tab[i = (n - 1) & hash]) == null)

? ? ? ? // 若判斷成立邻悬，則 new 一個(gè) Node 出來(lái)賦給 table 中指定索引下的這個(gè)元素

? ? ? ? tab[i] = newNode(hash, key, value, null);

? ? else {? // 若判斷不成立

? ? ? ? Node<K,V> e; K k;

? ? ? ? // 對(duì)這個(gè)元素進(jìn)行 Hash 和 key 值匹配

? ? ? ? if (p.hash == hash &&

? ? ? ? ? ? ((k = p.key) == key || (key != null && key.equals(k))))

? ? ? ? ? ? e = p;

? ? ? ? else if (p instanceof TreeNode)? // 如果數(shù)組中的這個(gè)元素 P 是 TreeNode 類型

? ? ? ? ? ? // 判定成功則在紅黑樹中查找符合條件的節(jié)點(diǎn)并返回此節(jié)點(diǎn)

? ? ? ? ? ? e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

? ? ? ? else {? // 若以上條件均判斷失敗症昏，則執(zhí)行以下代碼

? ? ? ? ? ? // 向 Node 單向鏈表中添加數(shù)據(jù)

? ? ? ? ? ? for (int binCount = 0; ; ++binCount) {

? ? ? ? ? ? ? ? if ((e = p.next) == null) {

? ? ? ? ? ? ? ? ? ? p.next = newNode(hash, key, value, null);

? ? ? ? ? ? ? ? ? ? // 若節(jié)點(diǎn)數(shù)大于等于 8

? ? ? ? ? ? ? ? ? ? if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

? ? ? ? ? ? ? ? ? ? ? ? // 轉(zhuǎn)換為紅黑樹

? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, hash);

? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if (e.hash == hash &&

? ? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k))))

? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? // p 記錄下一個(gè)節(jié)點(diǎn)

? ? ? ? ? ? ? ? p = e;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? if (e != null) { // existing mapping for key

? ? ? ? ? ? V oldValue = e.value;

? ? ? ? ? ? if (!onlyIfAbsent || oldValue == null)

? ? ? ? ? ? ? ? e.value = value;

? ? ? ? ? ? afterNodeAccess(e);

? ? ? ? ? ? return oldValue;

? ? ? ? }

? ? }

? ? ++modCount;

? ? // 判斷是否需要擴(kuò)容

? ? if (++size > threshold)

? ? ? ? resize();

? ? afterNodeInsertion(evict);

? ? return null;

}

0x02、get(Object key)

public V get(Object key) {

? ? Node<K,V> e;

? ? // 經(jīng)過(guò) hash 函數(shù)運(yùn)算父丰，獲取 key 的 hash 值

? ? return (e = getNode(hash(key), key)) == null ? null : e.value;

}

final Node<K,V> getNode(int hash, Object key) {

? ? Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

? ? // 判定三個(gè)條件 table 不為 null && table 的長(zhǎng)度大于 0 && table 指定的索引值不為 null

? ? if ((tab = table) != null && (n = tab.length) > 0 &&

? ? ? ? (first = tab[(n - 1) & hash]) != null) {

? ? ? ? // 判定是否匹配 hash 值 && 匹配 key 值肝谭，成功則返回該值

? ? ? ? if (first.hash == hash && // always check first node

? ? ? ? ? ? ((k = first.key) == key || (key != null && key.equals(k))))

? ? ? ? ? ? return first;

? ? ? ? // 若 first 節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為 null

? ? ? ? if ((e = first.next) != null) {

? ? ? ? ? ? // 若 first 的類型為 TreeNode 紅黑樹

? ? ? ? ? ? if (first instanceof TreeNode)

? ? ? ? ? ? ? ? // 通過(guò)紅黑樹查找匹配值并返回

? ? ? ? ? ? ? ? return ((TreeNode<K,V>)first).getTreeNode(hash, key);

? ? ? ? ? ? // 若上面判定不成功掘宪，則認(rèn)為下一個(gè)節(jié)點(diǎn)為單向鏈表，通過(guò)循環(huán)匹配值

? ? ? ? ? ? do {

? ? ? ? ? ? ? ? if (e.hash == hash &&

? ? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k))))

? ? ? ? ? ? ? ? ? ? // 匹配成功后返回該值

? ? ? ? ? ? ? ? ? ? return e;

? ? ? ? ? ? } while ((e = e.next) != null);

? ? ? ? }

? ? }

? ? return null;

}

0x03攘烛、resize()

// 重新設(shè)置 table 大小/擴(kuò)容魏滚，并返回?cái)U(kuò)容的 Node 數(shù)組即 HashMap 的最新數(shù)據(jù)

final Node<K,V>[] resize() {

? ? // table 賦給 oldTab 作為擴(kuò)充前的 table 數(shù)據(jù)

? ? Node<K,V>[] oldTab = table;

? ? int oldCap = (oldTab == null) ? 0 : oldTab.length;

? ? int oldThr = threshold;

? ? int newCap, newThr = 0;

? ? if (oldCap > 0) {

? ? ? ? // 判定數(shù)組是否已達(dá)到極限大小，若判定成功將不再擴(kuò)容坟漱，直接將舊表返回

? ? ? ? if (oldCap >= MAXIMUM_CAPACITY) {

? ? ? ? ? ? threshold = Integer.MAX_VALUE;

? ? ? ? ? ? return oldTab;

? ? ? ? }

? ? ? ? // 若新表大小(oldCap * 2)小于數(shù)組極限大小鼠次，并且舊表大于等于數(shù)組初始化大小

? ? ? ? else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

? ? ? ? ? ? ? ? oldCap >= DEFAULT_INITIAL_CAPACITY)

? ? ? ? ? ? // 舊數(shù)組大小 oldThr 經(jīng)二進(jìn)制運(yùn)算向左位移 1 個(gè)位置，即 oldThr * 2 當(dāng)作新數(shù)組的大小

? ? ? ? ? ? newThr = oldThr << 1; // double threshold

? ? }

? ? // 若舊表中下次擴(kuò)容大小 oldThr 大于 0

? ? else if (oldThr > 0) // initial capacity was placed in threshold

? ? ? ? // 將 oldThr 賦予控制新表大小的 newCap

? ? ? ? newCap = oldThr;

? ? // 若其他情況則將獲取初始默認(rèn)大小

? ? else {? ? ? ? ? ? ? // zero initial threshold signifies using defaults

? ? ? ? newCap = DEFAULT_INITIAL_CAPACITY;

? ? ? ? newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

? ? }

? ? // 若新表的下表下一次擴(kuò)容大小為 0

? ? if (newThr == 0) {

? ? ? ? // 通過(guò)新表大小 * 負(fù)載因子獲取

? ? ? ? float ft = (float)newCap * loadFactor;

? ? ? ? newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

? ? ? ? ? ? ? ? ? (int)ft : Integer.MAX_VALUE);

? ? }

? ? // 下次擴(kuò)容的大小

? ? threshold = newThr;

? ? @SuppressWarnings({"rawtypes","unchecked"})

? ? ? ? Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

? ? // 將當(dāng)前表賦予 table

? ? table = newTab;

? ? // 若 oldTab 中有值需要通過(guò)循環(huán)將 oldTab 中的值保存到新表中

? ? if (oldTab != null) {

? ? ? ? for (int j = 0; j < oldCap; ++j) {

? ? ? ? ? ? Node<K,V> e;

? ? ? ? ? ? // 獲取舊表中第 j 個(gè)元素芋齿，賦予 e

? ? ? ? ? ? if ((e = oldTab[j]) != null) {

? ? ? ? ? ? ? ? // 并將舊表中的元素?cái)?shù)據(jù)置 null

? ? ? ? ? ? ? ? oldTab[j] = null;

? ? ? ? ? ? ? ? // 若此判定成立腥寇，則代表 e 的下面沒(méi)有節(jié)點(diǎn)了

? ? ? ? ? ? ? ? if (e.next == null)

? ? ? ? ? ? ? ? ? ? // 將 e 直接存于新表的指定位置

? ? ? ? ? ? ? ? ? ? newTab[e.hash & (newCap - 1)] = e;

? ? ? ? ? ? ? ? // 若 e 是 TreeNode 類型

? ? ? ? ? ? ? ? else if (e instanceof TreeNode)

? ? ? ? ? ? ? ? ? ? // 分割樹，將新表和舊表分割成兩個(gè)樹觅捆，并判斷索引處節(jié)點(diǎn)的長(zhǎng)度是否需要轉(zhuǎn)換成紅黑樹放入新表存儲(chǔ)

? ? ? ? ? ? ? ? ? ? ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

? ? ? ? ? ? ? ? else { // preserve order

? ? ? ? ? ? ? ? ? ? // 存儲(chǔ)與舊索引的相同的節(jié)點(diǎn)

? ? ? ? ? ? ? ? ? ? Node<K,V> loHead = null, loTail = null;

? ? ? ? ? ? ? ? ? ? // 存儲(chǔ)與新索引相同的節(jié)點(diǎn)

? ? ? ? ? ? ? ? ? ? Node<K,V> hiHead = null, hiTail = null;

? ? ? ? ? ? ? ? ? ? Node<K,V> next;

? ? ? ? ? ? ? ? ? ? // 通過(guò) do~while 循環(huán)赦役，獲取新舊索引的節(jié)點(diǎn)

? ? ? ? ? ? ? ? ? ? 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);

? ? ? ? ? ? ? ? ? ? // 通過(guò)判定將舊數(shù)據(jù)和新數(shù)據(jù)存儲(chǔ)到新表指定的位置

? ? ? ? ? ? ? ? ? ? if (loTail != null) {

? ? ? ? ? ? ? ? ? ? ? ? loTail.next = null;

? ? ? ? ? ? ? ? ? ? ? ? newTab[j] = loHead;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? if (hiTail != null) {

? ? ? ? ? ? ? ? ? ? ? ? hiTail.next = null;

? ? ? ? ? ? ? ? ? ? ? ? newTab[j + oldCap] = hiHead;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? // 返回新表

? ? return newTab;

}

0x04、treeifyBin(Node<K,V>[] tab, int hash)

final void treeifyBin(Node<K,V>[] tab, int hash) {

? ? int n, index; Node<K,V> e;

? ? // 做判定栅炒，若 tab 為 null 或 tab 的長(zhǎng)度小于紅黑樹最小容量

? ? if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

? ? ? ? // 則通過(guò)擴(kuò)容掂摔，擴(kuò)容 table 數(shù)組大小

? ? ? ? resize();

? ? // 做判定，若 tab 索引位置下數(shù)據(jù)不為空

? ? else if ((e = tab[index = (n - 1) & hash]) != null) {

? ? ? ? // 定義兩個(gè)紅黑樹职辅，分別表示頭部節(jié)點(diǎn)、尾部節(jié)點(diǎn)

? ? ? ? TreeNode<K,V> hd = null, tl = null;

? ? ? ? // 通過(guò)循環(huán)將單向鏈表轉(zhuǎn)換為紅黑樹存儲(chǔ)

? ? ? ? do {

? ? ? ? ? ? // 將單向鏈表轉(zhuǎn)換為紅黑樹

? ? ? ? ? ? TreeNode<K,V> p = replacementTreeNode(e, null);

? ? ? ? ? ? // 若頭部節(jié)點(diǎn)為 null聂示，則說(shuō)明該樹沒(méi)有根節(jié)點(diǎn)

? ? ? ? ? ? if (tl == null)

? ? ? ? ? ? ? ? hd = p;

? ? ? ? ? ? else {

? ? ? ? ? ? ? ? // 指向父節(jié)點(diǎn)

? ? ? ? ? ? ? ? p.prev = tl;

? ? ? ? ? ? ? ? // 指向下一個(gè)節(jié)點(diǎn)

? ? ? ? ? ? ? ? tl.next = p;

? ? ? ? ? ? }

? ? ? ? ? ? // 將當(dāng)前節(jié)點(diǎn)設(shè)尾節(jié)點(diǎn)

? ? ? ? ? ? tl = p;

? ? ? ? } while ((e = e.next) != null); // 若下一個(gè)不為 null域携，則繼續(xù)遍歷

? ? ? ? // 紅黑樹轉(zhuǎn)換后，替代原位置上的單向鏈表

? ? ? ? if ((tab[index] = hd) != null)

? ? ? ? ? ? // 構(gòu)建紅黑樹鱼喉，以頭部節(jié)點(diǎn)為根節(jié)點(diǎn)

? ? ? ? ? ? hd.treeify(tab);

? ? }

}

七秀鞭、HashMap 為什么是線程不安全的？

HashMap 在并發(fā)時(shí)可能出現(xiàn)的問(wèn)題主要是兩方面：

put 的時(shí)候?qū)е碌亩嗑€程數(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ù)不一致的行為。

resize 而引起死循環(huán)

這種情況發(fā)生在 HashMap 自動(dòng)擴(kuò)容時(shí)串塑，當(dāng) 2 個(gè)線程同時(shí)檢測(cè)到元素個(gè)數(shù)超過(guò)數(shù)組大小 * 負(fù)載因子沼琉。此時(shí) 2 個(gè)線程會(huì)在 put() 方法中調(diào)用了 resize()，兩個(gè)線程同時(shí)修改一個(gè)鏈表結(jié)構(gòu)會(huì)產(chǎn)生一個(gè)循環(huán)鏈表（JDK 1.7 中拟赊，會(huì)出現(xiàn) resize 前后元素順序倒置的情況）刺桃。接下來(lái)再想通過(guò) get() 獲取某一個(gè)元素，就會(huì)出現(xiàn)死循環(huán)吸祟。

八瑟慈、1.7 和 1.8 的 HashMap 的不同點(diǎn)

0x01、JDK 1.7 用的是頭插法屋匕，而 JDK 1.8 及之后使用的都是尾插法啸胧，那么為什么要這樣做呢？

因?yàn)?JDK 1.7 是用單鏈表進(jìn)行的縱向延伸逞频，當(dāng)采用頭插法就是能夠提高插入的效率惕稻，但是也會(huì)容易出現(xiàn)逆序且環(huán)形鏈表死循環(huán)問(wèn)題。但是在 JDK 1.8 之后是因?yàn)榧尤肓思t黑樹使用尾插法纤虽，能夠避免出現(xiàn)逆序且鏈表死循環(huán)的問(wèn)題乳绕。

0x02、擴(kuò)容后數(shù)據(jù)存儲(chǔ)位置的計(jì)算方式也不一樣

在 JDK 1.7 的時(shí)候是直接用 Hash 值和需要擴(kuò)容的二進(jìn)制數(shù)進(jìn)行 &（這里就是為什么擴(kuò)容的時(shí)候?yàn)樯兑欢ū仨毷?2 的多少次冪的原因所在逼纸，因?yàn)槿绻挥?2 的 n 次冪的情況時(shí)最后一位二進(jìn)制數(shù)才一定是 1洋措，這樣能最大程度減少 Hash 碰撞）（Hash 值 & length - 1）。

而在 JDK 1.8 的時(shí)候直接用了 JDK 1.7 的時(shí)候計(jì)算的規(guī)律杰刽，也就是擴(kuò)容前的原始位置 + 擴(kuò)容的大小值 = JDK 1.8 的計(jì)算方式菠发，而不再是 JDK 1.7 的那種異或的方法。但是這種方式就相當(dāng)于只需要判斷 Hash 值的新增參與運(yùn)算的位是 0 還是 1 就直接迅速計(jì)算出了擴(kuò)容后的儲(chǔ)存方式贺嫂。

0x03滓鸠、JDK 1.7 的時(shí)候使用的是數(shù)組 + 單鏈表的數(shù)據(jù)結(jié)構(gòu)。但是在 JDK 1.8 及之后第喳，使用的是數(shù)組

+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)（當(dāng)鏈表的深度達(dá)到 8 的時(shí)候糜俗，也就是默認(rèn)閾值，再添加元素就會(huì)自動(dòng)擴(kuò)容曲饱，把鏈表轉(zhuǎn)成紅黑樹的數(shù)據(jù)結(jié)構(gòu)來(lái)把時(shí)間復(fù)雜度從 O(N) 變成O(logN)吩跋，提高了效率）。