如有转载请注明出处 https://www.jianshu.com/p/2c2d145ffa86
插入
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)))
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;
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;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
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;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
向树中插入节点首先需要找到根节点，调用了root方法
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
通过for循环寻找根节点，如果没有根节点则我们就视它为整个树的根节点。
找到根节点之后需要去根据树的规则向树中存入数据
- key的hash大于当前节点的hash值
那么应该放在树的右侧节点 - key的hash小于当前节点的hash值
那么应该放在树的左侧节点 - key等于当前key
说明已经有当前节点，返回当前节点 -
key为null，hash值相同但是key不同
遍历左侧节点树或者右侧节点树，寻找key是否已经在树中存在，如果存在则替换，如果不存在就插入
最后始终要保证树的根节点是在第一个节点
保证树在首节点.png
查找
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
查找就比较简单了，直接拿到树的根节点然后再去根据hash值查找，如果hash大于节点的hash值，那么应该在右侧树中接着找，如果找不到返回null，如果找到则返回node，在获取value，如果hash小于节点的hash值，那么就在树的左侧节点找，如果hash值相同则用equals进行比较key，如果key相同，则返回节点
当链表长度大于8时转换成红黑树
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
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);
}
其中的操作也比较简单，如果树的根节点为null，那么就把链表的第一个节点作为树的节点，然后在根据hash值进行判断，是放在该节点的左侧还是右侧
将红黑树转换成链表
当红黑树的节点不超过6时会将红黑树转换成链表
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) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
如果tl节点不存在，也就是这个链表没有值，那么就把root节点设置为链表的第一个节点，如果链表中已经存在节点，那么就把树中的节点指向，链表的最后一个节点。
对红黑树进行切割
在扩容的时候当我们扩容完之后需要将老的数组中的数据重新放入新的数组中，红黑树的扩容和链表的扩容原理是一样的，计算出位置没有改变的节点(hash&oldCap==0)，放入新的数组中和老数组一样的位置，如果有改变的节点还是放在index+oldCap位置。
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;
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;
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) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
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);
}
}
}
网友评论