HashMap 源碼分析
1.結(jié)構(gòu)
1. 繼承
??該類繼承自 AbstractMap 這個類似于 ArrayList
2. 實(shí)現(xiàn)
具體如下：
- 首先這個類是一個 Map 自然有 Map 接口
- 然后就是兩個集合框架肯定會實(shí)現(xiàn)的兩個接口 Cloneable, Serializable 割坠。
3. 主要字段
1. 屬性字段
// 默認(rèn)大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 鏈表轉(zhuǎn)成樹礁凡，鏈表的長度 8
static final int TREEIFY_THRESHOLD = 8;
// 樹轉(zhuǎn)成鏈表時樹大節(jié)點(diǎn)數(shù) 6
static final int UNTREEIFY_THRESHOLD = 6;
// Node 數(shù)組
transient Node<K,V>[] table;
// 大小
transient int size;
// 閾值 他等于容量乘以負(fù)載因子
int threshold;
2. Node
??? 這個其實(shí)就是在 JDK1.7 中我們常說的 Entry ，但是在 Java8 把 Entry 更進(jìn)一步抽象了孽亲，放到了 Map 接口里面坎穿，那里面的內(nèi)部接口。里面并沒有定義任何的字段返劲，只有一些公共的方法玲昧。
??? 然后這個 Node 是實(shí)現(xiàn)了 Entry 接口，里面定義了四個屬性篮绿，這幾個屬性也就是 HashMap 的關(guān)鍵了孵延，分別就是 hash 、key亲配、value 尘应、next 。下面具體的看下代碼吼虎。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
3. TreeNode
?? TreeNode 著很明顯犬钢，我們在上面的屬性字段提到了關(guān)于鏈表轉(zhuǎn)成樹的操作，那么我們就需要把 Node 節(jié)點(diǎn)包裝成 TreeNode 鲸睛。這里有一個比較有意思的事情就是這個 TreeNode 是繼承自 LinkedHashMap 的 Entry 但是他又繼承自 HashMap 的 Node 娜饵，而 那個 Entery 在 Node 基礎(chǔ)上添加了屬性就是 before 和 after 。有點(diǎn)繞官辈，那么簡單來說就是 TreeNode 在 Node 里面添加了 before 箱舞、after 還有其他的紅黑樹的信息。來具體看一下結(jié)構(gòu)拳亿。
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;
//before after inhert from Entry
}
4. 主要方法概覽
- cotr-4
- put/putVal
- resize
- putAll/putMapEntries
- get/getNode/containsKey
- remove/removeNode/clear
- containsValue
- read/writeObject
2. 主要方法分析
1. cotr-4
?? 首先介紹一下構(gòu)造方法晴股，這里我們會看到四個構(gòu)造方法，他們在里面做的事情都差不多肺魁，主要是設(shè)置容器的 容量 和閾值 电湘。其中在上面的字段中我們看到了一些常量，其中就有說明初始大小就是 16 鹅经，然后負(fù)載因子是 0.75 寂呛，還有提到最大容量 2^32 。
?? 在進(jìn)行數(shù)組大小設(shè)置的時候有一個比較有意思的方法瘾晃，tableSizeFor(int size) 這個方法能夠保證最后返回出來的值是一個比 size 大的最小的 2^n 這樣一個數(shù)贷痪。這樣說可能有點(diǎn)不好理解，舉個例子吧蹦误。 假如我們傳入一個 18 那么返回的就是 32 劫拢，因為 32 是 2 的 n 次方 這類的數(shù)肉津，然后他是最接近 18 的 2 的 n 次方 。
?? 然后你可能會發(fā)現(xiàn)為什么沒有初始化 Node 數(shù)組舱沧， 這是因為在 jdk1.8 里面 HashMap 的實(shí)現(xiàn)他的空間是延時分配的妹沙，也就是在我們真正往里面 put 值的時候才會真的創(chuàng)建 Node數(shù)組 ，這個到我們分析 put方法 的時候我們會看到這一機(jī)制熟吏。
?
// 設(shè)置負(fù)載因子和初始大小
public HashMap(int initialCapacity, float loadFactor) {
// 參數(shù)判斷
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;
// 這個方法就是把一個不是 2 的次冪的數(shù)轉(zhuǎn)換成一個大于當(dāng)前數(shù)的最小的 2 的次冪的數(shù)
this.threshold = tableSizeFor(initialCapacity);
}
// 大小設(shè)置一下距糖，負(fù)載因子默認(rèn)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 設(shè)置負(fù)載因子為默認(rèn)的 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// putMapEntries 這個方法就是 new 新數(shù)組然后 foreach 拷貝
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
?
2. put/putVal
? put 方法是今天的重頭戲，因為大部分的代碼其實(shí)都集中在這里分俯，put 方法直接調(diào)用了 putVal 這個方法里面就進(jìn)行了真正的存放元素的操作肾筐。
? 我先大概說一下 putVal 的邏輯，然后再看代碼就不會那么頭疼了缸剪。
一開始判斷當(dāng)前的
Node 數(shù)組是否是空，如果是空則進(jìn)行初始化东亦，也就是分配空間（這里就是啊前面提到的延時分配空間）接著需要計算這個插入的值在數(shù)組中的位置杏节，計算的方法就是
hash % capacity，但是你可能看到的代碼不是這樣而是采用的hash & (capacity-1)典阵，但是他們是等價的７苡妗！壮啊！不過這個等價是有條件的嫉鲸，那就是capacity的值必須是2 ^ n。所以你現(xiàn)在可能理解為什么HashMap的大小一直需要為2 ^ n以及tableSizeFor的作用歹啼。這個等價是可以證明的玄渗，比較簡單不再贅述。找到需要插入元素的位置以后狸眼，如果說這個位置沒有元素那好藤树，我們直接把這個元素插入即可。
但是如果這個地方的元素并不是空的拓萌，那么我們要么就是插入了完全一樣的
key要么就是key不一樣但是hash函數(shù)發(fā)生了沖突岁钓。如果是完全一樣的
key那我們就用新的value替換掉原來的value返回老值即可。但是如果是發(fā)生了 hash 沖突我們就需要解決沖突微王。在
jdk1.8里面采用的解決沖突的方法就是在這個節(jié)點(diǎn)上生成一個鏈表或紅黑樹屡限。至于具體生成哪種據(jù)坎節(jié)點(diǎn)的數(shù)量了，節(jié)點(diǎn)數(shù)量少鏈表就很快多了的話我們肯定采用平衡二叉樹（紅黑樹）炕倘。這個分水嶺的節(jié)點(diǎn)數(shù)是 8 钧大，在上面的數(shù)據(jù)域可以看到他是一個常量。對紅黑樹直接調(diào)用紅黑樹的
putTreeVal方法插入激才，而鏈表的話我們直接插入到鏈表的尾部即可拓型。對鏈表插入完成以后需要檢測一下是不是需要轉(zhuǎn)成紅黑樹额嘿。最后進(jìn)行一下擴(kuò)容判斷，畢竟有新的節(jié)點(diǎn)加入劣挫。
? 以上就是 putVal 的全部過程册养， 其中有一個擴(kuò)容操作沒有說，一會會單獨(dú)講這個方法压固。下面看看這個方法的源碼球拦。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 第三個參數(shù) onlyIfAbsent 如果是 true，那么只有在不存在該 key 時才會進(jìn)行 put 操作
// 第四個參數(shù) evict 我們這里不關(guān)心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次 put 值的時候帐我，會觸發(fā)下面的 resize()坎炼。這是因為我們調(diào)用了默認(rèn)的無參的構(gòu)造方法導(dǎo)致的，無參的里面只設(shè)置了負(fù)載因子
// 第一次 resize 和后續(xù)的擴(kuò)容有些不一樣拦键，因為這次是數(shù)組從 null 初始化到默認(rèn)的 16 或自定義的初始容量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 找到具體的數(shù)組下標(biāo)谣光，如果此位置沒有值，那么直接初始化一下 Node 并放置在這個位置就可以了
// 這個地方采用的 (n - 1) & hash 來尋找數(shù)組的下標(biāo)芬为，他和 hash%n 的效果一樣的 但是僅僅限制在 n 是 2 的次冪
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//newNode 方法不用看 就直接 new
else {// 數(shù)組該位置有數(shù)據(jù)
Node<K,V> e; K k;
// 首先萄金，判斷該位置的第一個數(shù)據(jù)和我們要插入的數(shù)據(jù)，key 是不是"相等"媚朦，如果是氧敢，把這個節(jié)點(diǎn)放到 e 里面
// 最后還有一個判斷 e 是不是 null 然后對這個節(jié)點(diǎn)的 value 進(jìn)行替換也就是說，如果 key 一樣的話直接替換 vaule key 不一樣說明是碰撞
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 下面兩種情況都是碰撞處理
// 如果該節(jié)點(diǎn)是代表紅黑樹的節(jié)點(diǎn)询张，調(diào)用紅黑樹的插值方法孙乖，本文不展開說紅黑樹
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 數(shù)組該位置上是一個鏈表
else {
// 循環(huán)找鏈表的最后一個節(jié)點(diǎn)
for (int binCount = 0; ; ++binCount) {
// 找到尾部就插入尾部 (Java7 是插入到鏈表的最前面)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD 為 8，所以份氧，如果新插入的值是鏈表中的第 9 個唯袄，會觸發(fā)下面的 treeifyBin，也就是將鏈表轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 不可能發(fā)生半火，所以直接 break 了 越妈，這個條件在前面就過濾掉了，也就是 key 相同的情況應(yīng)該進(jìn)行 value 的替換
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e!=null 說明存在舊值的key與要插入的key"相等"钮糖，不是碰撞情況而是一致的 key 需替換返回老值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //這個操作是空操作 模板設(shè)計模式 是給 LinkedHashMap 使用的
return oldValue;
}
}
++modCount;
// 如果 HashMap 由于新插入這個值導(dǎo)致 size 已經(jīng)超過了閾值梅掠，需要進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 同 afterNodeAccess
return null;
}
3. resize
? 擴(kuò)容方法也有點(diǎn)復(fù)雜，方法體有點(diǎn)長店归，沒關(guān)系我們慢慢分析阎抒，先了解思路在看源碼。
雖然這個方法是擴(kuò)容方法消痛，但是他也承擔(dān)著初始化的任務(wù)且叁。前面我們提到在
putVal方法中有為Node 數(shù)組分配空間的事情，但是這個分配空間是委托給了 這個方法進(jìn)行的秩伞。所以開始確認(rèn)當(dāng)前是分配空間還是在擴(kuò)容逞带，如果是擴(kuò)容我們要判斷當(dāng)前的容量是不是已經(jīng)到達(dá)極限了也就是最大容量
2^32欺矫，如果大于等于這個值我們不進(jìn)行擴(kuò)容把閾值設(shè)置為最大的整數(shù)，防止下次再進(jìn)行擴(kuò)容操作展氓。否則的話我們正常擴(kuò)容把容量調(diào)整為原來的二倍穆趴，這樣做的原因很明顯容量要是2 ^ n。接下來我們就可以 new 一個新數(shù)組了遇汞，當(dāng)然如果是這個操作是初始化那么我們的工作就完成了未妹，但是如果是擴(kuò)容操作我們還需要把原來的數(shù)組中的元素遷移到新的數(shù)組中。
接下來的操作就是數(shù)據(jù)遷移工作空入。遷移就是遍歷原來的數(shù)組络它，然后如果這個位置只有一個元素那直接遷移，如果不是的話就只能是紅黑樹或者單鏈表了歪赢。
遇到紅黑樹我們就調(diào)用紅黑樹的遷移方法化戳，單鏈表就把原來的鏈表拆成兩部分。掛在新的數(shù)組的位置埋凯，拆分的方法也很巧妙源碼中會看到迂烁。
?? 所以流程大概清楚了就看源碼，源碼注釋的比較清楚递鹉。
final Node<K,V>[] resize() {
//前面這一大堆都是關(guān)于計算擴(kuò)容的操作 不管他
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 對應(yīng)數(shù)組擴(kuò)容
if (oldCap > 0) {
//到極限了不擴(kuò)容 修改閾值防止下一次又進(jìn)入擴(kuò)容操作
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 將數(shù)組大小擴(kuò)大一倍 將閾值擴(kuò)大一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 對應(yīng)使用兩個有參的構(gòu)造方法初始化后，第一次 put 的時候 也就是說 HashMap 在初始化的時候沒有分配數(shù)組藏斩，空間是延時分配的
else if (oldThr > 0)
newCap = oldThr;
// 對應(yīng)使用 new HashMap() 初始化后躏结，第一次 put 的時候
else {
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;
// 用新的數(shù)組大小初始化新的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 如果是初始化數(shù)組，到這里就結(jié)束了狰域，返回 newTab 即可 接下來的操作就是數(shù)據(jù)遷移
table = newTab;
if (oldTab != null) {
// 開始遍歷原數(shù)組媳拴，進(jìn)行數(shù)據(jù)遷移。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果該數(shù)組位置上只有單個元素兆览，那就簡單了屈溉，簡單遷移這個元素就可以了
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是紅黑樹，就進(jìn)行分裂操作
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 鏈表的話就要把這些數(shù)據(jù)遷移到對應(yīng)的位置 抬探，注意不是直接把整個鏈表放到數(shù)組的新位置 而是拆成兩個鏈表
else {
// 這塊是處理鏈表的情況子巾，需要將此鏈表拆成兩個鏈表，放到新的數(shù)組中小压，并且保留原來的先后順序
// loHead线梗、loTail 對應(yīng)一條鏈表，hiHead怠益、hiTail 對應(yīng)另一條鏈表仪搔，代碼還是比較簡單的
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//一條鏈表拆成兩條
do {
next = e.next;
//這里就是用了一個條件拆分成了兩條鏈表
//他代碼這樣寫的原因在于：oldCap 是一個2的次冪，那么也就是說 他是形如 "100000000...000" 這個格式的
//那么任何一個數(shù)和他相與必然只有兩種結(jié)果 0 / 非0 就看最高位蜻牢，其他位出來肯定是0 這樣就區(qū)分了兩個鏈表 巧妙烤咧！
if ((e.hash & oldCap) == 0) {
//這里面的邏輯其實(shí)就是鏈表按照原來的順序連接 也就是說原來 a 在 c 前面只要 ac 在同一條鏈表上 a 就在 c 前面
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);
//用來把兩條鏈表分別掛在正確的數(shù)組位置
if (loTail != null) {
loTail.next = null;
// 第一條鏈表新位置就是原來的位置
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 第二條鏈表的新的位置是 j + oldCap偏陪，這個很好理解
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
4. putAll/putMapEntries
?? 前面分析完比較困難的 putVal 和 resize 方法后接下來的方法都很輕松了。
?? 這個 putAll 方法調(diào)用了 putMapEntries 煮嫌，在構(gòu)造函數(shù)中也調(diào)用了這個方法的朴恳。其具體的就是 foreach 拷貝元素寸认。
5. get/getNode/containsKey
? 這幾個方法底層調(diào)用的都是 getNode 方法，它的原理就是判斷第一個元素是不是，然后看是紅黑樹還是單鏈表再遍歷得到結(jié)果蠢莺。
public V get(Object key) {
Node<K,V> e;
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判斷第一個節(jié)點(diǎn)是不是就是需要的
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判斷是否是紅黑樹
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 鏈表遍歷
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
5. remove/removeNode/clear
這幾個方法也很簡單，remove 就是底層依賴的 removeNode 就是先遍歷找到對應(yīng)的節(jié)點(diǎn)丛肮，然后在遍歷去刪除洲守。
? clear 方法和前面介紹的 ArrayList 一樣就是把數(shù)組元素設(shè)置為 null 讓他去 gc
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//首先 hash 對應(yīng)的位置是有東西的 否則直接返回 null
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//這個 if else 是用來尋找那個要刪除的節(jié)點(diǎn)的
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//這個 if 是用來刪除上面找到的那個節(jié)點(diǎn)
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
6. containsValue
? 這個方法還是采用遍歷的方法，他沒有區(qū)分是樹還是鏈表統(tǒng)一的采用了 next 指針儿奶，這是因為 key 是作為紅黑樹的索引條件但是 value 并不是框往，并且在 TreeNode 中是有 next 的因為他間接繼承了 Node。
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
7. read/writeObject
? 最后還是序列化的問題闯捎，Node數(shù)組 并沒有采用默認(rèn)的序列化可以看到他加了 transient 關(guān)鍵字椰弊。這里手動序列化只是序列化了 key value 其他的一概不存儲。原因還是節(jié)省空間瓤鼻。
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
int buckets = capacity();
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
s.writeInt(buckets);
s.writeInt(size);
internalWriteEntries(s);
}
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
Node<K,V>[] tab;
if (size > 0 && (tab = table) != null) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
}
3. Hashtable
? ?? 就像是 ArrayList 和 Vector 一樣我們需要討論一下 Hashtable 和 HashMap 之間的異同秉版。
繼承結(jié)構(gòu)他們的實(shí)現(xiàn)接口一致，繼承的類卻不同茬祷，
Hashtable繼承的是Dictionary里面采用的結(jié)構(gòu)是
Entry 數(shù)組,沒有采用延時空間分配清焕，默認(rèn)大有采用延時空間. 迭代接口也有Enumeration確定數(shù)組的下標(biāo)采用的直接
(hash & 0x7FFFFFFF) % tab.length不允許 null 的鍵值
擴(kuò)容遷移采用鏈表倒敘插入，只有鏈表沒有紅黑樹祭犯。
?? 關(guān)于為什么 &0x7ffffffff 這里提一下秸妥，關(guān)鍵在于一個對象的 HashCode可以為負(fù)數(shù)，這樣操作后可以保證它為一個正整數(shù)0x7FFFFFFF is 0111 1111 1111 1111 1111 1111 1111 1111(hash & 0x7FFFFFFF) 將會得到一個正整數(shù)沃粗。因為hash是要作為數(shù)組的index的粥惧，這樣可以避免出現(xiàn)下標(biāo)為負(fù)數(shù)而出現(xiàn)異常。
