摘要：底層的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組鏈表紅黑樹，紅黑樹是在中加進(jìn)來(lái)的。負(fù)載因子哈希表中的填滿程度。
前言
把 Java 容器的學(xué)習(xí)筆記放到 github 里了，還在更新~
其他的目前不打算抽出來(lái)作為文章寫，感覺(jué)挖的還不夠深，等對(duì)某些東西理解的更深了再寫文章吧
Java 容器
目錄如下：
Java 容器
一、概述
二、源碼學(xué)習(xí)
1. Map
1.1 HashMap
1.2 LinkedHashMap
1.3 TreeMap
1.4 ConcurrentHashMap
2. Set
2.1 HashSet
2.2 LinkedHashSet
2.3 TreeSet
3. List
3.1 ArrayList
3.2 LinkedList
3.3 Vector
4. Queue
4.1 LinkedList
4.2 PriorityQueue
后面還會(huì)對(duì)并發(fā)、和一些 Java 基礎(chǔ)的東西做整理
為啥要做那么多筆記呢？個(gè)人比較喜歡把東西寫出來(lái)~嘻嘻
如果真的有人認(rèn)真看了的話，要是有錯(cuò)誤或者對(duì)我寫的感到迷惑的地方，再或者希望對(duì)哪些知識(shí)再深入了解一些，請(qǐng)盡管說(shuō)出來(lái)，給我的個(gè)人博客留言 or 發(fā)郵件 or 提 issue 都 ok，我會(huì)非常感謝你的~
個(gè)人博客鏈接
一、HashMap簡(jiǎn)介
看一下官方文檔中對(duì)HashMap的描述
* Hash table based implementation of the Map interface. This
* implementation provides all of the optional map operations, and permits
* null values and the null key. (The HashMap
* class is roughly equivalent to Hashtable, except that it is
* unsynchronized and permits nulls.) This class makes no guarantees as to
* the order of the map; in particular, it does not guarantee that the order
* will remain constant over time.
HashMap 是基于哈希表的 Map 接口的實(shí)現(xiàn)。
允許使用 null 值和 null 鍵。
除了不同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。
不保證順序
不保證該順序恒久不變。
HashMap 底層的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組+鏈表+紅黑樹，紅黑樹是在 JDK 1.8 中加進(jìn)來(lái)的。尤其是在 JDK 1.8 對(duì)它優(yōu)化以后，HashMap 變成了一個(gè)更強(qiáng)的容器...嗯...真的很強(qiáng)。
當(dāng)新建一個(gè) HashMap 時(shí)，就會(huì)初始化一個(gè)數(shù)組。在這個(gè)數(shù)組中，存放的是 Node 類，它擁有指向多帶帶的一個(gè)鏈表的頭結(jié)點(diǎn)的引用，這個(gè)鏈表是用來(lái)解決 hash 沖突的（如果不同的 key 被映射到數(shù)組中同一位置的話，就將其放入鏈表中，從而解決沖突）。
大概就是這樣子... ?(? ???ω??? ?)?
數(shù)組
__
|__| 鏈表
__ __ __ __ __
|__|---> |__|->|__|->|__|->|__|->...
__
|__|
__
|__|
__
|__|
__
|__| : Node
但是，在 JDK 1.8 之前的這種做法，即使負(fù)載因子和 Hash 算法設(shè)計(jì)的再合理，也無(wú)法避免會(huì)出現(xiàn)鏈表過(guò)長(zhǎng)的情況， 一旦鏈表過(guò)長(zhǎng)，會(huì)嚴(yán)重影響 HashMap 的性能，所以，在 JDK 1.8 之后，使用了紅黑樹這個(gè)數(shù)據(jù)結(jié)構(gòu)，當(dāng)鏈表長(zhǎng)度大于 8 時(shí)，該鏈表就會(huì)轉(zhuǎn)化成紅黑樹，利用紅黑樹快速增刪查改的特點(diǎn)提高 HashMap 的性能。
因?yàn)?HashMap 是不同步的，如果需要考慮線程安全，需要使用 ConcurrentHashMap，或者可以使用 Collections.synchronizedMap() 方法返回被指定 map 支持的同步的 map。
Map map = Collections.synchronizedMap(new HashMap<>());
二、源碼分析（基于JDK1.8）
1. 成員變量
// 默認(rèn)初始容量是16，必須是2的冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量（必須是2的冪且小于2的30次方，傳入容量過(guò)大會(huì)被這個(gè)值替換）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)加載因子，加載因子就是指哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默認(rèn)的轉(zhuǎn)換成紅黑樹的閾值，即鏈表長(zhǎng)度達(dá)到該值時(shí)，該鏈表將轉(zhuǎn)換成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 存儲(chǔ)Entry的默認(rèn)空數(shù)組
static final Entry[] EMPTY_TABLE = {};
// 存儲(chǔ)Entry的數(shù)組，長(zhǎng)度為2的冪。HashMap采用拉鏈法實(shí)現(xiàn)的，
// 每個(gè)Entry的本質(zhì)是個(gè)單向鏈表
transient Entry[] table = (Entry[]) EMPTY_TABLE;
// HashMap的大小，即HashMap中實(shí)際存在的鍵值對(duì)數(shù)量
transient int size;
// 閾值，表示所能容納的key-value對(duì)的極限，用于判斷是否需要調(diào)整HashMap的容量
// 如果 table 還是空的，那么這個(gè)閾值就是 0 或者是默認(rèn)的容量 16
int threshold;
// 加載因子實(shí)際大小
final float loadFactor;
// HashMap被修改的次數(shù)，用于 fail-fast 機(jī)制
transient int modCount;
其中需要特別注意的是capacity和load factor這兩個(gè)屬性
官方文檔中對(duì)其描述是：
The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.
The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
capacity（容量）：就是buckets的數(shù)目。
load factor（負(fù)載因子）：哈希表中的填滿程度。
若加載因子設(shè)置過(guò)大，則填滿的元素越多，從而提高了空間利用率，但是沖突的機(jī)會(huì)增加了，沖突的越多，鏈表就會(huì)變得越長(zhǎng)，那么查找效率就會(huì)變低；
若加載因子設(shè)置過(guò)小，則填滿的元素越少，那么空間利用率就會(huì)降低，表中數(shù)據(jù)將變得更加稀疏，但是沖突的機(jī)會(huì)減小了，這樣鏈表就不會(huì)太長(zhǎng)，查找效率就會(huì)變高。
一般，如果機(jī)器內(nèi)存足夠，想增加查找速度，可以將load factor設(shè)小一點(diǎn)；相反，如果內(nèi)存不足，并且對(duì)查找速度要求不高，可以將load factor設(shè)大一點(diǎn)。
2. 靜態(tài)內(nèi)部類 Node
Node 實(shí)際上就是一個(gè)單鏈表，它實(shí)現(xiàn)了Map.Entry接口，其中next也是一個(gè)Node對(duì)象，用來(lái)處理hash沖突，形成一個(gè)鏈表。
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next; // 指向下一個(gè)節(jié)點(diǎn)
Node(int hash, K key, V value, Node 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;
}
// 判斷兩個(gè)node是否equal（必須key和value都相等）
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;
}
}
3. 構(gòu)造函數(shù)
HashMap 有四個(gè)構(gòu)造函數(shù)
/**
用指定的初始容量和負(fù)載因子創(chuàng)建HashMap
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
用指定的容量創(chuàng)建HashMap，負(fù)載因子為默認(rèn)的0.75
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
均使用默認(rèn)值(初始容量：16 默認(rèn)負(fù)載因子：0.75)
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
用指定的一個(gè) map 構(gòu)造一個(gè)新HashMap
新的 HashMap 的負(fù)載因子為默認(rèn)值 0.75，容量為足以裝載該 map 的容量，會(huì)在 putMapEntries 中設(shè)置
*/
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
4. 確定哈希桶數(shù)組索引的位置
確定位置這部分是很重要的，無(wú)論增刪查鍵值對(duì)，首先都要定位到哈希桶數(shù)組的位置！理想的情況就是數(shù)組中每個(gè)位置都只有一個(gè)元素，這樣在用算法求得這個(gè)位置后，我們就能直接命中該元素，不用再遍歷鏈表了，這樣可以極大地優(yōu)化查找的效率.
在源碼中，采用的方法就是先根據(jù) hashCode 先計(jì)算出 hash 值，然后根據(jù) hash 值再求得索引，從而找到位置。
求hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
（">>>"為按位右移補(bǔ)零操作符。左操作數(shù)的值按右操作數(shù)指定的位數(shù)右移，移動(dòng)得到的空位以零填充。）
hash 值的計(jì)算主要分三步：
取key的hashCode值
高位運(yùn)算
對(duì)1、2進(jìn)行異或運(yùn)算得到hash值
計(jì)算索引
// 此處取的put方法片段，這里就是用(n - 1) & hash 計(jì)算的索引（n為表的長(zhǎng)度）
if ((p = tab[i = (n - 1) & hash]) == null)
計(jì)算方法其實(shí)就是取模運(yùn)算。
對(duì)于計(jì)算索引的取模運(yùn)算，是一個(gè)非常非常巧妙的運(yùn)算~ ヽ(??▽?)ノ
它是用 hash & (n - 1) 得到索引值，因?yàn)?HashMap 底層數(shù)組的長(zhǎng)度總是 2 的 n 次方（這是 HashMap 在速度上的優(yōu)化），通過(guò)下面這個(gè)函數(shù)去保證 table 的長(zhǎng)度為 2 的次冪。
// 這個(gè)靜態(tài)函數(shù)的作用就是返回一個(gè)比 cap 大但是又最接近 cap 的 2 次冪的整數(shù)
// 原理就是通過(guò)不斷地 位或 和 按位右移補(bǔ)零 操作，
// 將 n 變成 0..0111..111 這種形式，最后 + 1，就變成了 2 的次冪
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è)前提： n 一定為 2 的 n 次方，那么這個(gè)表達(dá)式才能等價(jià)于 hash % n，為什么不直接用 hash % n 呢？因?yàn)?& 比 % 具有更高的效率呀，所以采用的是 hash & (n - 1) 而不是 hash % n。
那么為什么n 為 2 的 n 次方時(shí) hash & (n - 1) 可以等價(jià)于對(duì) n 取模呢？
我是這樣想的
首先，n，即鏈表長(zhǎng)度，為 2 的 n 次方，那么 n 就可以表示成 100...00 的這種樣子，那么 n - 1 就是 01111...11。
如果 hash < n，& 后都是 hash 本身。
如果 hash = n，& 后結(jié)果為 0。
如果 hash > n，& 過(guò)后相當(dāng)于 hash - k*n，即 hash % n。
其次，因?yàn)?n 為 2 的次冪，是偶數(shù)，偶數(shù)最后一位是 0，而 n - 1 肯定是奇數(shù)，奇數(shù)的最后一位是 1，這樣便保證了 hash & (n - 1) 的最后一位可能為 0 也可能為 1，這樣便可以保證散列的均勻性，即均勻分布在數(shù)組 table 中；而如果 n 為奇數(shù)，則 n - 1 肯定是偶數(shù)，那么它的最后一位肯定是 0，這樣 hash & (n - 1) 得到的結(jié)果的最后一位肯定是 0，即只能為偶數(shù)，這樣任何 hash 值都會(huì)被映射到數(shù)組的偶數(shù)下標(biāo)位置上，這就浪費(fèi)了近一半的空間！
因此，HashMap 的作者要求鏈表的長(zhǎng)度必須為 2 的整數(shù)次冪，應(yīng)該就是為了這樣能使不同 hash 值發(fā)生碰撞的概率較小，讓元素在哈希表中均勻的散列。
5. put方法源碼分析
put的過(guò)程大致是：
根據(jù)key計(jì)算hash值
判斷tab是否為空，若為空則進(jìn)行resize()擴(kuò)容
根據(jù)hash值計(jì)算出索引
如果沒(méi)有碰撞就直接放入
如果有碰撞，就先放到鏈表里
若鏈表長(zhǎng)度超過(guò)8（默認(rèn)的TREEIFY_THRESHOLD），則轉(zhuǎn)換成紅黑樹再放
如果key已經(jīng)存在，就覆蓋其oldValue
插入成功后，如果size > threshold，就要擴(kuò)容
public V put(K key, V value) {
// 計(jì)算hash值
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab為哈希表數(shù)組，p為我們要找的那個(gè)插入位置的節(jié)點(diǎn)
Node[] tab; Node p; int n, i;
// 若tab為空，就創(chuàng)建一個(gè)（進(jìn)行擴(kuò)容操作）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根據(jù)key計(jì)算hash值并處理后得到索引，如果表的這個(gè)位置為空，則直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果不為空
else {
Node e; K k;
// 判斷key是否存在，如果存在，則直接覆蓋其value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判斷該鏈表是否為TreeNode，如果是，紅黑樹直接插入鍵值對(duì)
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// 如果不是，則遍歷鏈表，然后插入
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 鏈表長(zhǎng)度大于8，則轉(zhuǎn)換成紅黑樹，并插入鍵值對(duì)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
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)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果超過(guò)閾值，則進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
6. get方法源碼分析
get方法和put方法過(guò)程類似
public V get(Object key) {
Node e;
// 計(jì)算hash值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
// 如果表非空，并且根據(jù)計(jì)算出的索引值對(duì)應(yīng)的值非空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未直接命中
if ((e = first.next) != null) {
// 在紅黑樹中g(shù)et
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
// 在鏈表中g(shù)et
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
7. resize() 的擴(kuò)容機(jī)制
為什么要進(jìn)行 resize?
假設(shè) table 的長(zhǎng)度為 n，總共需要放入 HashMap 的鍵值對(duì)數(shù)量為 m，那么，大約每條鏈表的長(zhǎng)度就是 m / n，查找的時(shí)間復(fù)雜度也就是 O(m / n)，顯然，如果要盡量降低時(shí)間復(fù)雜度，需要加大 n，也就是對(duì) table 擴(kuò)容。
什么時(shí)候進(jìn)行resize?
在 put 過(guò)程中，如果發(fā)現(xiàn)當(dāng)前 HashMap 的 size 已經(jīng)超過(guò)了 load factor 希望占的比例，那么就會(huì)進(jìn)行 resize 操作。
下面是對(duì) resize 源碼的分析，這段我覺(jué)得是最艱難的一段。。這還跳過(guò)了紅黑樹 :(′□`」 ∠):
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果超過(guò)最大值就不再擴(kuò)容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果沒(méi)超過(guò)最大值，并且假設(shè)容量 double 后也不超過(guò)最大值，
// 那就擴(kuò)容為原來(lái)的 2 倍，
// 然后再看原來(lái)的容量是不是還夠
// 如果不夠了，閾值再 double，否則只是擴(kuò)容，不改變閾值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 從閾值中取出 resize 應(yīng)該擴(kuò)容的值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap = 0
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算新的閾值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 創(chuàng)建一個(gè)新的 table
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
// 指向新的 table
table = newTab;
if (oldTab != null) {
// 把每個(gè)bucket都移動(dòng)到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
// 刪除
oldTab[j] = null;
// 如果當(dāng)前結(jié)點(diǎn)是尾結(jié)點(diǎn)
if (e.next == null)
// 重新計(jì)算索引值，然后放入元素
newTab[e.hash & (newCap - 1)] = e;
// 如果當(dāng)前結(jié)點(diǎn)已經(jīng)轉(zhuǎn)換成紅黑樹了
else if (e instanceof TreeNode)
// 將樹上的結(jié)點(diǎn) rehash，然后放到新位置，紅黑樹這塊以后在分析
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
// 進(jìn)行鏈表復(fù)制
// lo鏈的新索引值和以前相同
// hi鏈的新索引值為：原索引值 + oldCap
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
/**
(e.hash & oldCap) == 0 這個(gè)地方比較難理解，但也是擴(kuò)容最關(guān)鍵的地方
假設(shè)現(xiàn)在 (e.hash & oldCap) == 0 為 true
oldCap 和 new Cap 肯定都是 2 的次冪，也就是 100... 這種形式，那么假如現(xiàn)在 oldCap = 16，
那么原索引為
e.hash & (oldCap - 1) = e.hash & 01111 --> index ①
新的索引為
e.hash & (newCap - 1) = e.hash & 11111
同時(shí)我們已知 e.hash & oldCap = 0，
即 e.hash & 10000 = 0 ②
通過(guò) ① ② 就可以推出
e.hash & 11111 --> index
即索引位置不變
*/
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;
}
}
}
}
}
return newTab;
}
擴(kuò)容部分完結(jié)撒花 ★,°:.☆(￣▽￣)/$:.°★
三、關(guān)于 HashMap 的線程安全性
HashMap 不是線程安全的，它在被設(shè)計(jì)的時(shí)候就沒(méi)有考慮線程安全，因?yàn)檫@本來(lái)就不是一個(gè)并發(fā)容器，相應(yīng)的并發(fā)容器是 ConcurrentHashMap，那么，HashMap 的線程不安全性主要體現(xiàn)在哪兒呢？
最著名的一個(gè)就是高并發(fā)環(huán)境下的死循環(huán)問(wèn)題，具體是在 resize 時(shí)產(chǎn)生的。
這種死循環(huán)產(chǎn)生的主要原因是因?yàn)?1.7 的 resize 中，新的 table 采用的插入方式是隊(duì)頭插入（LIFO，后進(jìn)先出），比如元素為 {3,5,7,9}，插入后就是 {9,7,5,9}，會(huì)將鏈表順序逆置，它這樣做主要是為了防止遍歷鏈表尾部，因?yàn)?resize 本來(lái)就是創(chuàng)建了一個(gè)新的 table，所以對(duì)于元素的順序不關(guān)心，因此采用隊(duì)頭插入的方式，如果是正常的從尾部插入的話，還需要先找到尾部的位置，增加了遍歷的消耗，而 resize 又正好不在乎元素順序，所以就使用的隊(duì)頭插入的方式。
但是這種方式帶來(lái)了一個(gè)問(wèn)題，就是死循環(huán)，具體死循環(huán)怎么產(chǎn)生的我就不贅述了，因?yàn)榫W(wǎng)上有很多關(guān)于這個(gè)的具體分析，我要說(shuō)的是，在 JDK 1.8 中，HashMap 除了加入了紅黑樹這個(gè)數(shù)據(jù)結(jié)構(gòu)外還有一些其他的調(diào)整，在 resize 時(shí)對(duì)鏈表的操作，變成了兩對(duì)指針?lè)謩e對(duì) lo鏈 和 hi鏈 操作。
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
因?yàn)樵黾恿藊xTail指針，所以可以隨時(shí)找到尾部，避免遍歷尾部，因此可以直接在尾部插入，因而避免了死循環(huán)問(wèn)題。
不過(guò)這不代表 JDK 1.8 的HashMap就是線程安全了的，因?yàn)楹苊黠@還存在比如并發(fā)時(shí)元素的覆蓋之類的問(wèn)題，所以多線程環(huán)境下還是建議使用 ConcurrentHashMap 或者進(jìn)行同步操作。
