前言
上篇文章讲解了JDK1.7中的HashMap源码, 主要采用数组+链表来实现, 根据元素的hash计算出来的下标相同时, 也就是发生hash冲突的时候, 就会把这些元素以链表的形式存放在数组中, 当数组比较小, 发生hash冲突比较频繁时, 数组中链表就比较长, 这样查找的效率就比较低.
JDK1.8中的HashMap主要对数据结构进行优化, 引入了红黑树, 当链表长度大于8时把链表转换成红黑树, 红黑树的操作效率远高于链表, 这样就提高了HashMap的效率.
备注: 本人不是计算机专业出身, 对于红黑树也是一知半解, 感兴趣的可以参考这篇文章, 详细介绍了红黑树的特性以及一些基本操作.
源码
JDK1.8源码中增加了这两个参数:
//当链表长度大于8时, 将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
//当红黑树长度小于等于6时, 将红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
构造函数及其他参数基本没变, 不再细说, 下面对一些优化点具体分析.
- hash值计算数组下标
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里通过key的hashcode高16位异或低16位来计算hash值, 这样让hashcode的高位低位都参与到hash计算上, 减少了hash冲突.
然后通过hash&(length-1)来计算数组下标, 我们知道数组长度都是2的N次方, hash&(length-1)相当于hash%length(前者按位与运算效率更高), 这样元素分布更加均匀.
- Node节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
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;
}
}
数组中每一个元素都是Node, 有hash, key, value, next四个属性, 与JDK1.7中的HashMapEntry一样.
- put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//onlyIfAbsent: 如果HashMap中已存在该元素, true:不改变原值, false: 替换原值
//evict: 插入元素之后是否删除
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//数组为空, 通过resize初始化数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通过hash值计算数组下标, 如果tab[i]元素为空, 新建一个元素放在该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//如果tab[i]元素不为空, 说明发生了hash碰撞
Node<K,V> e; K k;
//如果tab[i]元素的 hash key与插入元素相同, 则直接替换
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果tab[i]元素是红黑树, 就在红黑树上插入该元素
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果tab[i]元素是链表, 遍历链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//遍历到链表尾部也没找到hash和key相同的元素, 则创建一个节点放到链表尾部
p.next = newNode(hash, key, value, null);
//如果链表长度大于等于8, 就把链表转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//找到hash和key相同的元素, 退出
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果找到hash和key相同的元素
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent 为false或旧值为空, 则替换旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果容量超过最大容量, 需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
JDK1.8中put操作与JDK1.7中put操作大致相同, 区别就是发生hash碰撞之后, 先判断对应位置是链表还是红黑树, 是红黑树就进行红黑树的插入操作, 链表的话遍历链表插入, 最后再判断链表长度大于等于8时转换成红黑树.
- resize
紧接着来看下数组初始化及扩容的方法resize:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int 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;
}
//当老数组容量大于16时, 数组容量和临界值都扩展为2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果老数组容量为0, 扩容临界值不为0, 则临界值赋给新数组容量
else if (oldThr > 0)
newCap = oldThr;
else { //如果老数组容量和临界值都为0, 则新数组容量为16, 临界值为16*0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//再次判断新数组扩容临界值是否为0, 为0时重新计算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建新容量数组
table = newTab;
// 老数组不为空, 则遍历老数组上每一个元素, 迁移到新数组中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//oldTab[j]上只有一个元素时, 重新计算在新数组中的下标, 放到新数组中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果当前元素是红黑树, 执行split移动到新数组中
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 如果当前元素是单链表
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, 就把当前元素放到低位链表中
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//如果((e.hash & oldCap) == 1, 就把当前元素放到高位链表中
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;
}
//高位链表不为空的话, 把高位链表放到新数组j + oldCap上
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
简单总结一下, 先判断老数组容量, 为空时重新设置容量和扩容临界值, 初始化数组, 如果不为空就对数组容量和临界值扩大2倍, 然后把老数组中所有元素迁移到新数组中, 迁移时先判断数组上元素是红黑树还是链表, 红黑树就进行红黑树的分离操作, 链表的话, 把一个链表分成两个链表, 放到新数组不同位置上.
这里把链表分成两个链表的判断逻辑是e.hash & oldCap是否等于0, 我们知道计算数组下标是通过e.hash & (oldCap-1), 这个链表上所有元素这个下标值是一样的, 但是当数组容量扩充为2倍时, e.hash & oldCap那一位就起了关键作用.
举个例子, 数组初始容量是16,有两个hash值5和21发生了碰撞, 放在一个链表上.
5&(16-1): 0000 0101&0000 1111=0000 0101=5
21&(16-1):0001 0101&0000 1111=0000 0101=5
当数组扩容为32时, 就不会发生hash碰撞了
5&(32-1): 0000 0101&0001 1111=0000 0101=5
21&(32-1):0001 0101&0001 1111=0001 0101=21
通过例子可以看出, 数组扩充为2倍时, 关键看e.hash & oldCap那一位, 要么是0, 要么是1, 通过这一位就可以判断在新数组中的位置, 0的话位置不变, 1的话位置增加了原数组容量.
这里介绍下数组迁移时JDK1.7与1.8的一点区别:
1.7中是对链表上每一个元素通过e.hash & (newCap-1)计算在新数组中的下标, 然后放到新数组对应下标中, 发生hash冲突后, 新加入的元素会放到单链表头部, 这样迁移之后元素发生了倒置.
1.8中数组迁移时(暂不讨论红黑树), 根据e.hash & oldCap等于0或1把一个单链表分成了两个单链表, 最后放到新数组不同位置上. 一方面计算效率更高, 另一方面不会发生元素倒置.
- get
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;
//根据key的hash值计算数组下标, 获取数组对应位置上的首个元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果首个元素hash和key与目标值相等, 则返回
if (first.hash == hash &&
((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;
}
get的方法比较简单, 根据hash值计算出坐标之后, 再判断对应位置元素, 如果是红黑树就在红黑树中查找, 如果是链表, 就循环链表查找.
- remove
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;
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 (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);
}
}
//上面部分跟getNode方法一样, 就是取出hash和key都相等的元素, 如果不为空, 且value与要删除的元素相等
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;
}
remove方法, 根据hash值计算出数组下标之后, 判断对应元素, 是红黑树就从红黑树种查找目标元素并删除, 如果是链表, 就遍历链表查找元素并删除.
- 红黑树
红黑树是整个代码中最难理解的一部分, 如果你看懂了它的原理和算法, 就很好理解了.这里我简单分析下, 有些细节也没看太懂.
- 属性
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 当前节点的父节点
TreeNode<K,V> left;//当前节点的左子节点
TreeNode<K,V> right;//当前节点的右子节点
TreeNode<K,V> prev; // 当前节点的前一个节点
boolean red;//当前节点的颜色: 红/黑
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
这里TreeNode继承的是LinkedHashMap.Entry, 我们知道HashMap的Node是单链表结构, 而LinkedHashMap.Entry是环形链表结构, 所以TreeNode节点既有树状结构又有双链表结构, 对红黑树进行插入查找操作时, 利用树状结构, 分离红黑树时又是利用链表结构.
- root
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
root: 查找当前节点的根节点. 从该节点一直往上查找父节点, 直到父节点为空, 即为根节点.
- find
上面HashMap的getNode方法中, 如果元素是红黑树就通过红黑树的getTreeNode方法查找元素. 这里看下红黑树的getTreeNode方法.
final TreeNode<K,V> getTreeNode(int h, Object k) {
//找到当前节点的根节点, 然后从根节点开始往下查找
return ((parent != null) ? root() : this).find(h, k, null);
}
//从当前节点开始往下查找
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
//获取当前节点的左子节点和右子节点
TreeNode<K,V> pl = p.left, pr = p.right, q;
//当前节点的hash大于目标元素hash, 向左子节点查找
if ((ph = p.hash) > h)
p = pl;
////当前节点的hash小于目标元素hash, 向右子节点查找
else if (ph < h)
p = pr;
//如果当前节点hash和key都与目标元素相同, 返回当前元素
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)//左子节点为空, 向右子节点查找
p = pr;
else if (pr == null)//右子节点为空, 向左子节点查找
p = pl;
//hash值相等, key不等
//如果目标元素的key可比较且与当前节点的key不等价, 如果目标元素key小于当前节点key, 向左查找, 否则向右查找
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
//如果目标key不可比较或者当前节点key与目前key类型不同, 向右子节点查找
else if ((q = pr.find(h, k, kc)) != null)
return q;
else//右子节点查不到再向左子节点查找
p = pl;
} while (p != null);
return null;
}
//比较k和x
static int compareComparables(Class<?> kc, Object k, Object x) {
//如果x为空或x的类型不是kc, 返回0, 否则比较两者, k<x返回负值, k>x返回正值
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
这段代码根据二叉树的性质, 小的在左, 大的在右. 先根据hash值向左查找或向右查找, hash值相等再根据key向左查找或向右查找, 依次向下查找, 直到找到hash和key都相等的节点.
- putTreeVal
上面HashMap的putVal方法中, 如果数组上元素是红黑树就根据红黑树的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;
//先找到当前节点的根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
//从根节点向下查找
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)//向做插入
dir = -1;
else if (ph < h)//向右插入
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))//找到hash和key都相等的元素直接返回
return p;
//hash值相等但key不相等
//如果目标Key不可比较或者当前节点key与目标key类型不同
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
//先向左查找再向右查找, 如果找到则返回
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;
}
//还没找到, 因为目标key与当前节点key类型不同无法比较, 则用另一种方式比较
dir = tieBreakOrder(k, pk);
}
//当前节点保存到xp中
TreeNode<K,V> xp = p;
//dir<0且当前节点左子节点为空, 则向左子节点插入新元素
//dir>0且当前节点右子节点为空, 则向右子节点插入新元素
//否则, 左子节点或右子节点不为空, 则继续向下查找待插入位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
//新建一个节点x
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)//新建节点成为当前节点p的左子节点
xp.left = x;
else//新建节点成为当前节点p的右子节点
xp.right = x;
//指定节点的prev和next, 由此可见, 红黑树中既有树状关系也有双链表关系
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//插入新元素之后红黑树的性质可能打破, 需要进行平衡操作, 最后把红黑树的根放到数组对应位置
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
static int tieBreakOrder(Object a, Object b) {
int d;
//如果a,b为空, 或ab的类名相同, 则通过System.identityHashCode比较
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
总结一下putTreeVal的大致流程, 从根部开始, 根据hash值向左查找或向右查找, 如果hash相等key不等, 就比较key的hash值, 如果找到hash和key都相等的元素就直接返回当前节点, 未找到就新建一个元素作为左子节点或右子节点, 插入元素后可能打破红黑树的性质, 需要进行平衡操作, 平衡操作之后根部元素可能发生变化, 需要把根部节点放到数组对应位置上.
balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)平衡插入操作, 大致是通过左旋右旋, 对节点重新着色来修正红黑树, 是它满足红黑树的所有性质, 具体细节有兴趣的可以研究下.
balanceInsertion平衡操作之后返回的是新的根节点, 然后通过moveRootToFront, 把根节点放到数组对应位置上, 简单看下:
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//根据根节点hash值计算下标
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果数组对应位置上不是这个根节点, 需要替换
if (root != first) {
Node<K,V> rn;
//将root放到数组对应位置上
tab[index] = root;
TreeNode<K,V> rp = root.prev;
//改变root前后节点的指向
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;treeifytreeify
//改变数组对应位置原节点与新的根节点的前后指向
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
- split
上面数组扩容时, 如果元素是红黑树, 就通过split把红黑树分离.
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;//当前节点
// 初始化两个双链表
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//这里利用红黑树节点的链表关系遍历红黑树
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//通过e.hash & bit决定当前元素放到哪个链表上
if ((e.hash & bit) == 0) {//放低位链表
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {//放高位链表
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
//低位链表长度小于等于6, 双链表转换成单链表放到tab[index]上
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {//否则不转换放到tab[index]上
tab[index] = loHead;
//hiHead != null时把loHead转换成红黑树, hiHead =null说明原来的红黑树没有分离, 还是一颗红黑树
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);
}
}
}
扩容时红黑树的分离过程跟链表的分离过程有点类似, 先初始化两个双链表, 然后利用hash&老数组length, 如果是0, 放到低位链表中, 如果是1, 放到高位链表中. 最后判断链表长度, 小于等于6时把双链表转换成单链表存储, 否则, 判断红黑树是否分离, 未分离, 还是一颗红黑树, 经过分离的话再把分离出来的链表转换成红黑树存储, 低位链表存储到相同位置, 高位链表存储到当前位置+老数组长度.
下面看下treeify和untreeify这两个方法:
- treeify
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//根据TreeNode的链表关系遍历
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//链表头元素成为红黑树的根节点
if (root == null) {
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;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
//左子节点或右子节点为空时, 插入新元素
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//插入之后平衡红黑树, 退出, 继续插入下一个元素
root = balanceInsertion(root, x);
break;
}
}
}
}
//所有元素插入红黑树之后再把根节点替换到数组对应位置
moveRootToFront(tab, root);
}
treeify: 把双链表转换成红黑树, 链表头元素成为根节点, 后面的元素根据hash值判断成为当前节点的左子节点或者右子节点, 插入之后平衡红黑树, 等链表上所有元素插入红黑树之后替换数组上的根节点.
- untreeify
final Node<K,V> untreeify(HashMap<K,V> map) {
//初始化链表头尾元素
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
//把当前的TreeNode转换成普通的Node, next为null
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
untreeify: 把每一个TreeNode节点转换成普通的节点, 组成新的单链表, 最终返回单链表头元素.
还有其他几个方法, 左旋rotateLeft, 右旋rotateRight, 插入平衡balanceInsertion, 删除平衡balanceDeletion这些方法具体细节我就不分析了(细节太多太复杂, 没看完), 主要是在红黑树插入元素或删除元素之后通过进行的操作来保证红黑树的性质.
