之前的文章中介紹了JDK1.7中的HashMap的實(shí)現(xiàn)和JDK1.8中HashMap的紅黑樹的內(nèi)容株依，但是沒有介紹1.8中HashMap實(shí)現(xiàn)的具體細(xì)節(jié)部分茎辐，本章開始介紹一下JDK1.8中HashMap的具體實(shí)現(xiàn)搔课。
首先在1.8中的一些常量需要介紹一下泌枪，因?yàn)樵趖able擴(kuò)充過程中多了一些步驟，所以自然也多了一些內(nèi)部的常量值峭跳。
- static final int TREEIFY_THRESHOLD = 8; 當(dāng)tables數(shù)組中一個(gè)格子的元素?cái)?shù)量超過這個(gè)值得時(shí)候才可以進(jìn)行鏈表-》紅黑樹的轉(zhuǎn)換排拷。需要注意的是侧漓，這個(gè)限制只是轉(zhuǎn)換的條件之一，也就是說不是到了8就一定會(huì)發(fā)生轉(zhuǎn)換监氢。
- static final int UNTREEIFY_THRESHOLD = 6;當(dāng)table數(shù)組進(jìn)行resize的時(shí)候布蔗，如果一個(gè)格子里面的節(jié)點(diǎn)數(shù)量少于這個(gè)值的話就會(huì)從紅黑樹退化為普通的鏈表。
- static final int MIN_TREEIFY_CAPACITY = 64;只有在table數(shù)組的長(zhǎng)度大于這個(gè)數(shù)值的時(shí)候才能進(jìn)行鏈表到紅黑樹的轉(zhuǎn)換操作（如果數(shù)組長(zhǎng)度沒有達(dá)到這個(gè)長(zhǎng)度的話浪腐，會(huì)在格子元素?cái)?shù)量過多的時(shí)候進(jìn)行resize操作）纵揍，這個(gè)長(zhǎng)度至少應(yīng)該是TREEIFY_THRESHOLD的四倍。
在一些正常的初始化操作中這里的實(shí)現(xiàn)與1.7中的實(shí)現(xiàn)沒有太多差異牛欢，我們重點(diǎn)來看看不同的地方骡男。
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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //在resize方法中初始化table數(shù)組
if ((p = tab[i = (n - 1) & hash]) == null) //如果在指定的格子中沒有元素，則直接進(jìn)行元素插入
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //如果新插入的元素的key跟p（格子中第一個(gè)元素）的key一致
e = p;
else if (p instanceof TreeNode) //如果當(dāng)前的格子中是一棵紅黑樹的話就直接進(jìn)行紅黑樹的插入(紅黑樹的插入細(xì)節(jié)見之前的文章)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //說明此時(shí)的格子中存在的是一個(gè)鏈表傍睹，并且插入的元素的位置在鏈表非頭部
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) //如果插入前這個(gè)格子中的元素?cái)?shù)量已經(jīng)達(dá)到了樹化閾值-1就進(jìn)行樹化
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 存在key值相同的節(jié)點(diǎn)
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //這個(gè)判斷就保證了樹化對(duì)于table數(shù)組長(zhǎng)度的限制，為什么對(duì)這個(gè)長(zhǎng)度進(jìn)行限制呢犹菱？
//因?yàn)槿绻跀?shù)組長(zhǎng)度比較小的時(shí)候拾稳，橫向的擴(kuò)展成本并不大，也能進(jìn)行保證訪問元素的時(shí)間復(fù)雜度在常量范圍腊脱。隨著數(shù)組長(zhǎng)度的逐漸增加访得，訪問resize的成本會(huì)逐漸升高，這時(shí)候才會(huì)選擇對(duì)鏈表進(jìn)行樹化陕凹。
//但是為什么是到達(dá)MIN_TREEIFY_CAPACITY之后才進(jìn)行樹化呢悍抑？這個(gè)道理就相當(dāng)于loadFactor的取值一樣，都是經(jīng)過JDK開發(fā)人員測(cè)試的(我并沒有測(cè)試過)杜耙。
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null); //這個(gè)過程中是將所有的Node節(jié)點(diǎn)轉(zhuǎn)換為TreeNode節(jié)點(diǎn)并做好前后連接工作
if ((tab[index] = hd) != null)
hd.treeify(tab); //將鏈表轉(zhuǎn)為紅黑樹
}
}
從整個(gè)插入過程中來看搜骡，這里的做法普遍多的步驟就是針對(duì)于紅黑樹的特定處理，考慮了鏈表與紅黑樹之間的轉(zhuǎn)換佑女。接下來记靡，我們看看get方法主要有哪些區(qū)別
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) {
if (first.hash == hash && //每次總是首先檢查第一個(gè)節(jié)點(diǎn)是否為需要查找的節(jié)點(diǎn)
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) { //判斷邏輯就是作一下紅黑樹于鏈表的區(qū)分就行
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;
}
其他的包括移除一些的對(duì)于整個(gè)結(jié)構(gòu)有變化的操作都會(huì)考慮到關(guān)于紅黑樹的特殊處理谈竿，但是因?yàn)榍闆r跟上面兩種有些類似，所以就不多說了摸吠。
