在JDK1.8中，HashMap底層是用數(shù)組Node<K,V>數(shù)組存儲宝恶，數(shù)組中每個元素用鏈表存儲元素，當元素超過8個時趴捅，將鏈表轉化成紅黑樹存儲垫毙。
紅黑樹
紅黑樹本質上是平衡查找二叉樹，用于存儲有序數(shù)據(jù)拱绑，相對于鏈表數(shù)據(jù)查找來說综芥，鏈表的時間復雜度O(n)，紅黑樹的時間復雜度O(lgn)猎拨。
紅黑樹需要滿足一下五種特性：
- 每個節(jié)點是紅色或者黑色
- 根節(jié)點是黑色
- 每一個空葉子節(jié)點必須是黑色
- 紅色節(jié)點的子節(jié)點必須是黑色
- 節(jié)點中到達任意子節(jié)點包含相同數(shù)組的黑節(jié)點
當新增節(jié)點或者減少節(jié)點膀藐，紅黑樹會通過左旋或者右旋操作來調整樹結構屠阻，使其滿足以上特性。
TreeNode 類
HashMap中紅黑樹是通過TreeNode類構造的额各。TreeNode是HashMap的靜態(tài)內(nèi)部類国觉，繼承與LinkedHashMap.Entry<K,V>類
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 父節(jié)點
TreeNode<K,V> parent; // red-black tree links
// 左子節(jié)點
TreeNode<K,V> left;
// 右子節(jié)點
TreeNode<K,V> right;
// 前節(jié)點
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);
}
...
}
treeifyBin 方法
在HashMap中put方法時候，但數(shù)組中某個位置的鏈表長度大于8時虾啦，會調用treeifyBin方法將鏈表轉化為紅黑樹麻诀。
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)
// 數(shù)組大小小于64的，調用resize將數(shù)組大小擴容至2倍大小
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// 遍歷鏈表傲醉，將鏈表元素轉化成TreeNode鏈
do {
// 調用replacementTreeNode構造TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
// TreeNode鏈為空蝇闭，將元素設置為hd的首個節(jié)點
hd = p;
else {
// TreeNode鏈不為空，向TreeNode鏈后面添加元素
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// TreeNode鏈表轉化為紅黑樹
hd.treeify(tab);
}
}
構成紅黑樹--treeify 方法
treeify方法是TreeNode類的方法硬毕，作用是將Treenode鏈轉化成紅黑樹呻引。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
// 遍歷TreeNode鏈
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
// 設置root節(jié)點
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
// 循環(huán)查找當前節(jié)點插入的位置并添加節(jié)點
int dir, ph;
K pk = p.key;
// hashMap元素的hash值用來表示紅黑樹中節(jié)點數(shù)值大小
if ((ph = p.hash) > h)
// 當前節(jié)點值小于根節(jié)點，dir = -1
dir = -1;
else if (ph < h)
// 當前節(jié)點值大于根節(jié)點, dir = 1
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 當前節(jié)點的值等于根節(jié)點值吐咳。
// 如果當前節(jié)點實現(xiàn)Comparable接口逻悠，調用compareTo比較大小并賦值dir
// 如果當前節(jié)點沒有實現(xiàn)Comparable接口，compareTo結果等于0挪丢，則調用tieBreakOrder繼續(xù)比較大小
// tieBreakOrder本質是通過比較k與pk的hashcode
dir = tieBreakOrder(k, pk);
// 當前“根節(jié)點”賦值給xp
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 如果當前節(jié)點小于根節(jié)點且左子節(jié)點為空 或者 當前節(jié)點大于根節(jié)點且右子節(jié)點為空蹂风，直接添加子節(jié)點
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 平衡紅黑樹
root = balanceInsertion(root, x);
// 跳出循環(huán)，繼續(xù)向紅黑樹添加下一個元素
break;
}
}
}
}
// 確保紅黑樹根節(jié)點是數(shù)組中該index的第一個節(jié)點
moveRootToFront(tab, root);
}
新增元素后平衡紅黑樹--balanceInsertion方法
當紅黑樹中新增節(jié)點的時候需要調用balanceInsertion方法來保證紅黑樹的特性乾蓬。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// 新增節(jié)點默認是紅色
x.red = true;
// xp父節(jié)點 xpp祖父節(jié)點 xppl祖父左節(jié)點 xppr 祖父右節(jié)點
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
// x的父節(jié)點為空惠啄，x應為根節(jié)點，應為黑色
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
// 父節(jié)點是黑色任内，祖父節(jié)點為空撵渡，直接返回
return root;
// 父節(jié)點是紅色
if (xp == (xppl = xpp.left)) {
// 父節(jié)點是祖父節(jié)點的左節(jié)點
if ((xppr = xpp.right) != null && xppr.red) {
// 叔父節(jié)點是紅色
// 叔父節(jié)點設為黑色
xppr.red = false;
// 父節(jié)點設為黑色
xp.red = false;
// 祖父節(jié)點設置為紅色
xpp.red = true;
// 將祖父節(jié)點設置為當前節(jié)點，并繼續(xù)循環(huán)操作
x = xpp;
}
else {
// 叔父節(jié)點為黑色或者空
if (x == xp.right) {
// x為父節(jié)點右節(jié)點死嗦，則要進行左旋操作
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 經(jīng)過左旋x為左節(jié)點
if (xp != null) {
// 父節(jié)點涂成黑色
xp.red = false;
if (xpp != null) {
// 祖父節(jié)點不為空
// 祖父節(jié)點設為紅色
xpp.red = true;
// 以租父節(jié)點為支點右旋轉
root = rotateRight(root, xpp);
}
}
}
}
else {
// 父親節(jié)點為右節(jié)點
if (xppl != null && xppl.red) {
// 叔父節(jié)點為紅色
// 將叔父節(jié)點設為黑色
xppl.red = false;
// 父節(jié)點設為黑色
xp.red = false;
// 祖父節(jié)點設為紅色
xpp.red = true;
// 循環(huán)操作
x = xpp;
}
else {
if (x == xp.left) {
// 右旋
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// x為右節(jié)點
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
// 以祖父節(jié)點為支點左旋
root = rotateLeft(root, xpp);
}
}
}
}
}
}
向紅黑樹添加元素 -- putTreeVal 方法
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
// 獲取根節(jié)點
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
// 從root節(jié)點開始遍歷
int dir, ph; K pk;
// 通過比較hash大小確定添加元素的位置
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
// key相同直接返回
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
// 有相同節(jié)點直接返回
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
// 根據(jù)dir大小添加元素
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
// 構建新的treeNode節(jié)點
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 平衡紅黑樹并保證root是index處首節(jié)點
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
TreeNode類還有很多方法如刪除紅黑樹節(jié)點方法removeTreeNode趋距，刪除后平衡二叉樹方法balanceDeletion，查找紅黑樹節(jié)點方法getTreeNode...后續(xù)有精力再來分析越除。
