HashMap線程不安全，底層數(shù)組+鏈表+紅黑樹
面試重點(diǎn)是put方法，擴(kuò)容

總結(jié)

put方法

HashMap的put方法，首先通過(guò)key去生成一個(gè)hash值，第一次進(jìn)來(lái)是null，此時(shí)初始化大小為16，i = (n - 1) & hash計(jì)算下標(biāo)值，第一次獲取是null，直接放入一個(gè)Node節(jié)點(diǎn)，如果不是null，分成下面三種情況
1）如果發(fā)現(xiàn)hash和key相等，將原來(lái)的覆蓋
2）不相等，就要用到鏈表，通過(guò)尾插法插入到尾部。超過(guò)8轉(zhuǎn)成紅黑樹
3）如果是TreeNode，插入即可

擴(kuò)容

首先，上面put方法每次都會(huì)計(jì)算大小
如果超過(guò)16*0.75，即12就會(huì)r調(diào)用resize方法
這里主要是老數(shù)組上面元素轉(zhuǎn)到新數(shù)組上面去的邏輯
遍歷，如果老數(shù)組上面元素不是null
這里又是幾種情況
1）如果next下標(biāo)是null，
說(shuō)明只有一個(gè)元素，直接重新計(jì)算下標(biāo)放入新數(shù)組
2）判斷是否是TreeNode
對(duì)TreeNode樹進(jìn)行拆分，轉(zhuǎn)到新數(shù)組，不一定在一起。拆分后不一定還是樹，這里各種情況，看節(jié)點(diǎn)對(duì)應(yīng)的是高位還是低位。判斷低位個(gè)數(shù)如果不超過(guò)6，轉(zhuǎn)成鏈表（TreeNode轉(zhuǎn)成Node）。高位也一樣。否則重新生成紅黑樹（根據(jù)是否有高地位判斷是否需要重新生成紅黑樹）
3）否則說(shuō)明是個(gè)鏈表，
將鏈表轉(zhuǎn)到新數(shù)組上面去，擴(kuò)容后重新計(jì)算hash后下標(biāo)不一定還是相同的，所以不能直接轉(zhuǎn)到新數(shù)組，但是擴(kuò)容后下標(biāo)是有規(guī)律的。擴(kuò)容后只有兩種情況，低位和高位。 哪些節(jié)點(diǎn)是在低位鏈表上面，哪些節(jié)點(diǎn)是在高位鏈表上面。然后放到新數(shù)組即可。

源碼如下：

/*** 默認(rèn)的初始容量-必須是二的冪。2的4次方=16，*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** 如果隱式指定了更高的值，則使用最大容量由帶有參數(shù)的構(gòu)造函數(shù)中的任何一個(gè)執(zhí)行。必須是二次方<=1<<30。*/
static final int MAXIMUM_CAPACITY = 1 << 30;/*** 在構(gòu)造函數(shù)中未指定時(shí)使用的負(fù)載系數(shù)。*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** 使用樹而不是列表作為存儲(chǔ)箱的存儲(chǔ)箱計(jì)數(shù)閾值。當(dāng)向至少有這么多節(jié)點(diǎn)的bin添加元素時(shí)，bin會(huì)轉(zhuǎn)換為樹。該值必須大于2，并且應(yīng)至少為8，以符合樹木移除中關(guān)于收縮后轉(zhuǎn)換回普通垃圾箱的假設(shè)。*/
static final int TREEIFY_THRESHOLD = 8;/*** 在調(diào)整大小操作期間取消嘗試（拆分）垃圾箱的垃圾箱計(jì)數(shù)閾值。應(yīng)小于TREEIFY_THRESHOLD，并且最多6個(gè)，以便在去除時(shí)進(jìn)行收縮檢測(cè)。*/
static final int UNTREEIFY_THRESHOLD = 6;/*** 可以將垃圾箱樹化的最小桌子容量。（否則，如果一個(gè)bin中的節(jié)點(diǎn)太多，則會(huì)調(diào)整表的大小。）應(yīng)至少為4*TREEIFY_THRESHOLD，以避免調(diào)整大小閾值和樹化閾值之間的沖突。*/
static final int MIN_TREEIFY_CAPACITY = 64;/*** 基本hash bin節(jié)點(diǎn)，用于大多數(shù)條目。（TreeNode子類見下文，Entry子類見LinkedHashMap。）*/
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;//鏈表的實(shí)現(xiàn)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;}
}

new HashMap，默認(rèn)無(wú)參構(gòu)造，負(fù)載因子0.75

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // 這個(gè)是0.75f}/*** The number of times this HashMap has been structurally modified* Structural modifications are those that change the number of mappings in* the HashMap or otherwise modify its internal structure (e.g.,* rehash).  This field is used to make iterators on Collection-views of* the HashMap fail-fast.  (See ConcurrentModificationException).*/transient int modCount;//記錄修改次數(shù)

put方法

//put方法
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}
/*** 計(jì)算key.hashCode（）并將哈希的高位擴(kuò)展（XOR）到低位。因?yàn)樵摫硎褂昧藘蓚€(gè)掩碼的冪，所以僅在當(dāng)前掩碼之上以位為單位變化的哈希集總是會(huì)發(fā)生沖突。（已知的例子包括在小表中保存連續(xù)整數(shù)的浮點(diǎn)鍵集。）因此，我們應(yīng)用了一種變換，將高位的影響向下擴(kuò)展。比特?cái)U(kuò)展的速度、效用和質(zhì)量之間存在權(quán)衡。由于許多常見的哈希集已經(jīng)合理分布（因此不會(huì)從擴(kuò)展中受益），并且因?yàn)槲覀兪褂脴鋪?lái)處理箱中的大型沖突集，所以我們只需以最便宜的方式對(duì)一些移位的比特進(jìn)行異或，以減少系統(tǒng)損失，并將最高比特的影響納入其中，否則由于表綁定，這些比特將永遠(yuǎn)不會(huì)用于索引計(jì)算*/
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

首先通過(guò)hash方法，傳入key計(jì)算出一個(gè)int類型的hash值。

這里為什么不直接用key.hashCode()的值呢？

key.hashCode()計(jì)算出一個(gè)hash值，然后賦值給h，h右移16位，然后兩個(gè)做異或運(yùn)算
計(jì)算的值右移16位，右移之前和右移之后的值進(jìn)行異或^運(yùn)算，得到最終的hashcode，這個(gè)最終的值時(shí)通過(guò)低位和高位一起異或運(yùn)算算出來(lái)的。這樣高位也參加到了計(jì)算中，高位都是0.

下面還有計(jì)算數(shù)組下標(biāo)的
i = (n - 1) & hash，第一次n=16，做&運(yùn)算，何為&運(yùn)算，即都為1則為1。
比方15的二進(jìn)制時(shí)是 0000 1111 而上面計(jì)算得到的hash值和這個(gè)做&運(yùn)算，值在0-15之間。這樣(n - 1) & hash計(jì)算是為了使均勻分布。0-15出現(xiàn)頻率都差不多。hash值比較均勻，最后計(jì)算的i就比較均勻。為啥要n-1，如果16的話，做&運(yùn)算得到結(jié)果就兩種

然后調(diào)用putVal方法，入?yún)⑹耴ey的hash值，key，value，false，true

這里是put的核心方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//定義tab，p，n，i，初始化一些變量Node<K,V>[] tab; Node<K,V> p; int n, i;//這里為啥不直接用table？性能問(wèn)題，我們自己初始化變量是屬于棧中，而table是堆中，不用每次從堆中去拿table。//第一次進(jìn)來(lái)是nullif ((tab = table) == null || (n = tab.length) == 0)//這里調(diào)用resize，初始化及擴(kuò)容，第一次返回16n = (tab = resize()).length;//那=16//下面這個(gè)i是如何來(lái)的？i = (n - 1) & hash，算出數(shù)組下標(biāo)，如果沒(méi)有值，是null，就放到這里。if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);//如果這個(gè)位置不是null，這里就涉及到鏈表else {//如果這個(gè)位置上不是null，說(shuō)明這個(gè)位置有東西Node<K,V> e; K k;//如果發(fā)現(xiàn)hash和key相等if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//直接賦值到e，下面不會(huì)走了e = p;//如果這個(gè)位置上的是TreeNode類型else if (p instanceof TreeNode)//進(jìn)行紅黑樹的插入e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//不相等，就要用到鏈表，這里for循環(huán)，//如何加？通過(guò)Node對(duì)象的next屬性for (int binCount = 0; ; ++binCount) {//binCount=0，有一個(gè)節(jié)點(diǎn)，所以下面要8-1=7，binCount=8//尾插法，找到尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的next==nullif ((e = p.next) == null) {//將新的節(jié)點(diǎn)給到next屬性，完成鏈表插入p.next = newNode(hash, key, value, null);//如果bincount的大小>=8-1=7，binCount=7，鏈表有8個(gè)節(jié)點(diǎn)，但是你自己上面newNode還新增了一個(gè)，其實(shí)現(xiàn)在有9個(gè)節(jié)點(diǎn)//為啥超過(guò)8個(gè)轉(zhuǎn)紅黑樹，這個(gè)和紅黑樹的性能有關(guān)if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//如果發(fā)現(xiàn)鏈表中有相等的，也是無(wú)需做什么了，直接覆蓋值if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//如果e不是null，if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)更新valuee.value = value;afterNodeAccess(e);//將原來(lái)老的value返回return oldValue;}}++modCount;//統(tǒng)計(jì)++size，hashmap大小，和域值threshold（16*0.75）比較//不停往集合put，如果大于12（threshold）個(gè)，就會(huì)調(diào)用resize擴(kuò)容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}/*** 初始化或加倍表大小。如果為null，則根據(jù)字段閾值中的初始容量目標(biāo)進(jìn)行分配。否則，因?yàn)槲覀兪褂玫氖嵌蝺缯归_，所以每個(gè)bin中的元素必須保持在同一索引，或者在新表中以二次冪偏移量移動(dòng)。** @return the table*/transient Node<K,V>[] table;int threshold;final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//一開始時(shí)nullint oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)//左移1位，翻倍newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaults//一開始0，走到這里執(zhí)行newCap = DEFAULT_INITIAL_CAPACITY;//默認(rèn)16（1>>4）newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16*0.75=12這個(gè)和擴(kuò)容有關(guān)系，擴(kuò)容的一個(gè)域值}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;//第一次將12賦值給threshold@SuppressWarnings({"rawtypes","unchecked"})//這里開始創(chuàng)建Node，第一次newCap=16，這里創(chuàng)建出一個(gè)16大小的node數(shù)組Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//將16給到table，table=16table = newTab;//老數(shù)組上面元素轉(zhuǎn)到新數(shù)組上面去if (oldTab != null) {//遍歷老數(shù)組for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//如果老數(shù)組這個(gè)元素不是nullif ((e = oldTab[j]) != null) {oldTab[j] = null;//如果為null，說(shuō)明只有一個(gè)元素if (e.next == null)//重新計(jì)算放到新數(shù)組中newTab[e.hash & (newCap - 1)] = e;//判斷是不是TreeNodeelse if (e instanceof TreeNode)//對(duì)TreeNode樹進(jìn)行拆分，轉(zhuǎn)到新數(shù)組，不一定在一起。拆分后不一定還是樹，這里各種情況，看節(jié)點(diǎn)對(duì)應(yīng)的是高位還是低位。判斷低位個(gè)數(shù)如果不超過(guò)6，轉(zhuǎn)成鏈表（TreeNode轉(zhuǎn)成Node）。否則還是TreeNode，然后判斷高位低位，如果低位，不用動(dòng)，如果有高位，說(shuō)明樹進(jìn)行了拆分，重新生成紅黑樹。((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order//是個(gè)鏈表，將鏈表轉(zhuǎn)到新數(shù)組上面去，擴(kuò)容后重新計(jì)算hash后下標(biāo)不一定還是相同的，所以不能直接轉(zhuǎn)到新數(shù)組，但是擴(kuò)容后下標(biāo)是有規(guī)律的。只有兩種情況，低位和高位//哪些節(jié)點(diǎn)是在低位鏈表上面，哪些節(jié)點(diǎn)是在高位鏈表上面Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;//e.hash & oldCap==0判斷在低位還是高位，等于0在低位if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//低位鏈表放到newTabif (loTail != null) {loTail.next = null;newTab[j] = loHead;}//高位鏈表放到newTabif (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;//第一次調(diào)用的最后返回16}

轉(zhuǎn)紅黑樹的方法

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;//MIN_TREEIFY_CAPACITY=64，判斷數(shù)組長(zhǎng)度是否小于64if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {//將這個(gè)鏈表上面的Node節(jié)點(diǎn)遍歷變成TreeNode節(jié)點(diǎn)，完成轉(zhuǎn)換TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {//將prev也賦值，改成雙向鏈表，方便去拿前一個(gè)節(jié)點(diǎn)p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)//將TreeNode節(jié)點(diǎn)轉(zhuǎn)成紅黑樹hd.treeify(tab);}}

紅黑樹查詢刪除等時(shí)間復(fù)雜度都是log（n），要快一點(diǎn)，提升查詢性能
并不是超過(guò)8就一定轉(zhuǎn)成紅黑樹，而是還要判斷數(shù)組長(zhǎng)度，64比較，小于64擴(kuò)容
為啥要判斷數(shù)組長(zhǎng)度？和擴(kuò)容有關(guān)，resize擴(kuò)容，將鏈表拆分成兩個(gè)短鏈表。

擴(kuò)容，兩個(gè)地方進(jìn)行擴(kuò)容
一個(gè)是計(jì)算hashmap大小大于12進(jìn)行擴(kuò)容
一個(gè)是鏈表長(zhǎng)度大于8，不一定轉(zhuǎn)成紅黑樹，而是通過(guò)判斷數(shù)組長(zhǎng)度是否小于64進(jìn)行擴(kuò)容

擴(kuò)容先生成新數(shù)組，再把老數(shù)組上面元素放到新數(shù)組位置上

擴(kuò)容，如果是TreeNode情況

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {TreeNode<K,V> b = this;// Relink into lo and hi lists, preserving order//低位TreeNode<K,V> loHead = null, loTail = null;//高位TreeNode<K,V> hiHead = null, hiTail = null;int lc = 0, hc = 0;//低位和高位數(shù)量for (TreeNode<K,V> e = b, next; e != null; e = next) {next = (TreeNode<K,V>)e.next;e.next = null;if ((e.hash & bit) == 0) {if ((e.prev = loTail) == null)loHead = e;elseloTail.next = e;loTail = e;++lc;}else {if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.next = e;hiTail = e;++hc;}}
//如果低位不是nullif (loHead != null) {//如果低位數(shù)量不超過(guò)6if (lc <= UNTREEIFY_THRESHOLD)//將TreeNode轉(zhuǎn)成Node，轉(zhuǎn)成了鏈表tab[index] = loHead.untreeify(map);else {//如果超過(guò)，說(shuō)明要用紅黑樹，tab[index] = loHead;//如果高位不是null，說(shuō)明有高位，此時(shí)需要重新生成紅黑樹，如果沒(méi)有高位，就不用走到treeify方法，用之前的就行。不需要重新再生成紅黑樹。if (hiHead != null) // (else is already treeified)loHead.treeify(tab);}}if (hiHead != null) {if (hc <= UNTREEIFY_THRESHOLD)tab[index + bit] = hiHead.untreeify(map);else {tab[index + bit] = hiHead;if (loHead != null)hiHead.treeify(tab);}}}

紅黑樹

1. 根節(jié)點(diǎn)是黑色的；

2. 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL），也就是說(shuō)，葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)；

3. 任何相鄰的節(jié)點(diǎn)都不能同時(shí)為紅色，紅色節(jié)點(diǎn)是被黑色節(jié)點(diǎn)隔開的；

4. 每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到達(dá)其可達(dá)葉子節(jié)點(diǎn)的所有路徑，都包含相同數(shù)目的黑色節(jié)點(diǎn)

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {x.red = true;for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {//如果是null，父節(jié)點(diǎn)，返回if ((xp = x.parent) == null) {x.red = false;return x;}//如果父節(jié)點(diǎn)是黑色，不用調(diào)整，返回rootelse if (!xp.red || (xpp = xp.parent) == null)return root;//父節(jié)點(diǎn)是紅色的情況，//父節(jié)點(diǎn)正好是xpp的左節(jié)點(diǎn)if (xp == (xppl = xpp.left)) {//開始變色if ((xppr = xpp.right) != null && xppr.red) {//父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)變黑，祖父節(jié)點(diǎn)變紅，xppr.red = false;xp.red = false;xpp.red = true;//最上面節(jié)點(diǎn)顏色變化，再次遞歸，繼續(xù)進(jìn)行調(diào)整x = xpp;}else {if (x == xp.right) {root = rotateLeft(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}if (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;root = rotateRight(root, xpp);}}}}else {if (xppl != null && xppl.red) {xppl.red = false;xp.red = false;xpp.red = true;x = xpp;}else {if (x == xp.left) {root = rotateRight(root, x = xp);xpp = (xp = x.parent) == null ? null : xp.parent;}if (xp != null) {xp.red = false;if (xpp != null) {xpp.red = true;root = rotateLeft(root, xpp);}}}}}}

HashMap為什么用紅黑樹

R-B Tree。它是一種不嚴(yán)格的平衡二叉查找樹
引入RB-Tree是功能、性能、空間開銷的折中結(jié)果。
紅黑是用非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決，而AVL是嚴(yán)格平衡樹，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹要多。
就插入節(jié)點(diǎn)導(dǎo)致樹失衡的情況，AVL和RB-Tree都是最多兩次樹旋轉(zhuǎn)來(lái)實(shí)現(xiàn)復(fù)衡rebalance，旋轉(zhuǎn)的量級(jí)是O(1)
刪除節(jié)點(diǎn)導(dǎo)致失衡，AVL需要維護(hù)從被刪除節(jié)點(diǎn)到根節(jié)點(diǎn)root這條路徑上所有節(jié)點(diǎn)的平衡，旋轉(zhuǎn)的量級(jí)為O(logN)，而RB-Tree最多只需要旋轉(zhuǎn)3次實(shí)現(xiàn)復(fù)衡，只需O(1)，所以說(shuō)RB-Tree刪除節(jié)點(diǎn)的rebalance的效率更高，開銷更小！

hashmap使用紅黑樹的原因是：這樣可以利用鏈表對(duì)內(nèi)存的使用率以及紅黑樹的高效檢索，是一種很有效率的數(shù)據(jù)結(jié)構(gòu)。AVL樹是一種高度平衡的二叉樹，所以查找的效率非常高，但是，有利就有弊，AVL樹為了維持這種高度的平衡，就要付出更多代價(jià)。每次插入、刪除都要做調(diào)整，復(fù)雜、耗時(shí)。對(duì)于有頻繁的插入、刪除操作的數(shù)據(jù)集合，使用AVL樹的代價(jià)就有點(diǎn)高了。而且紅黑樹只是做到了近似平衡，并不嚴(yán)格的平衡，所以在維護(hù)的成本上，要比AVL樹要低。所以，hashmap用紅黑樹。

紅黑樹相比avl樹，在檢索的時(shí)候效率其實(shí)差不多，都是通過(guò)平衡來(lái)二分查找。但對(duì)于插入刪除等操作效率提高很多。紅黑樹不像avl樹一樣追求絕對(duì)的平衡，他允許局部很少的不完全平衡，這樣對(duì)于效率影響不大，但省去了很多沒(méi)有必要的調(diào)平衡操作，avl樹調(diào)平衡有時(shí)候代價(jià)較大，所以效率不如紅黑樹，在現(xiàn)在很多地方都是底層都是紅黑樹的天下啦。

java8不是用紅黑樹來(lái)管理hashmap，而是在hash值相同的情況下（且重復(fù)數(shù)量大于8），用紅黑樹來(lái)管理數(shù)據(jù)。 紅黑樹相當(dāng)于排序數(shù)據(jù)，可以自動(dòng)的使用二分法進(jìn)行定位，性能較高。一般情況下，hash值做的比較好的話基本上用不到紅黑樹。

AVL樹用于自平衡的計(jì)算犧牲了插入刪除性能，但是因?yàn)樽疃嘀挥幸粚拥母叨炔?#xff0c;查詢效率會(huì)高一些。紅黑樹的高度只比高度平衡的AVL樹的高度（log2n）僅僅大了一倍，在性能上卻好很多。

HashMap為什么要轉(zhuǎn)成樹？為什么閾值是8？

當(dāng)鏈表長(zhǎng)度不斷變長(zhǎng)，肯定會(huì)對(duì)查詢性能有一定的影響，所以才需要轉(zhuǎn)成樹。
選擇8，是根據(jù)概率統(tǒng)計(jì)決定。

HashMap源碼里有一段注解，大概意思是：
理想情況下使用隨機(jī)的哈希碼，容器中節(jié)點(diǎn)分布在hash桶中的頻率遵循泊松分布(具體可以查看http://en.wikipedia.org/wiki/Poisson_distribution)，按照泊松分布的計(jì)算公式計(jì)算出了桶中元素個(gè)數(shù)和概率的對(duì)照表，可以看到鏈表中元素個(gè)數(shù)為8時(shí)的概率已經(jīng)非常小，再多的就更少了，所以原作者在選擇鏈表元素個(gè)數(shù)時(shí)選擇了8，是根據(jù)概率統(tǒng)計(jì)而選擇的。

這里看到8的時(shí)候概率小的可憐了。

空間和時(shí)間的權(quán)衡
TreeNodes占用空間是普通Nodes的兩倍，所以只有當(dāng)bin包含足夠多的節(jié)點(diǎn)時(shí)才會(huì)轉(zhuǎn)成TreeNodes，而是否足夠多就是由TREEIFY_THRESHOLD的值決定的。當(dāng)bin中節(jié)點(diǎn)數(shù)變少時(shí)，又會(huì)轉(zhuǎn)成普通的bin。并且我們查看源碼的時(shí)候發(fā)現(xiàn)，鏈表長(zhǎng)度達(dá)到8就轉(zhuǎn)成紅黑樹，當(dāng)長(zhǎng)度降到6就轉(zhuǎn)成普通bin。

為什么不用B+Tree

B+樹在數(shù)據(jù)庫(kù)中被應(yīng)用的原因是其“矮胖”的特點(diǎn)，B+樹的非葉子結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，所以每個(gè)結(jié)點(diǎn)能存儲(chǔ)的關(guān)鍵字更多。所以B+樹更能應(yīng)對(duì)大量數(shù)據(jù)的情況。Mysql就是用的B+Tree。
jdk1.7中的HashMap本來(lái)是數(shù)組+鏈表的形式，鏈表由于其查找慢的特點(diǎn)，所以需要被查找效率更高的樹結(jié)構(gòu)來(lái)替換。如果用B+樹的話，在數(shù)據(jù)量不是很多的情況下，數(shù)據(jù)都會(huì)“擠在”一個(gè)結(jié)點(diǎn)里面。這個(gè)時(shí)候遍歷效率就退化成了鏈表。

結(jié)論：b+樹不屬于二叉樹，因?yàn)槎娌檎覙涞牟檎倚适亲罡叩?如果內(nèi)存能裝下完整的樹,最好使用二叉查找樹，b+樹是退而求其次的方式。

所以就是根據(jù)數(shù)據(jù)量去選擇，HashMap數(shù)據(jù)量不大，，沒(méi)有必要用B+Tree。