ConcurrentHashMap是一个兼具高并发和并发安全的一个 Map 类，主要依赖于 Unsafe 类，闲话不多说了，直接上代码吧
put 方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//计算hash
int hash = spread(key.hashCode());
int binCount = 0;
//自旋，知道操作成功
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
//初始化操作
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//判断i的位置是否已经有值，使用的CAS保证多线程，如果没有就直接放入
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)//说明其他线程正在扩容，帮助一起扩容
tab = helpTransfer(tab, f);
else {//发生碰撞
V oldVal = null;
synchronized (f) {//获取链表第一个的对象锁。这里使用synchronized，是防止在扩容或remove时发生错误（扩容和remove时也加了synchronized）。假设 synchronized 不加并且此时正在扩容，可能发生错误
if (tabAt(tab, i) == f) {//判断是否相等，防止被别的线程修改，比如被移除，扩容
if (fh >= 0) {
binCount = 1;//链表的数量
//遍历整个链表，要么替换旧值，要么把值放到链表的最后
for (Node<K,V> e = f;; ++binCount) {
K ek;
//如果hash值相同，而且value也相同，则新值替换旧值，后面回返回
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {//把值放到链表的最后
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//如果是红黑树操作
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
//binCount != 0，说明成功放入
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)//链表数量 >= 8 转红黑树
treeifyBin(tab, i);
if (oldVal != null)//就像前所说的旧值替换新值，返回旧值
return oldVal;
break;
}
}
}
//计数（计算map中的总数量，如果数量大于容量的3/4则扩容）
addCount(1L, binCount);
return null;
}
为什么链表转红黑树时时 >= TREEIFY_THRESHOL，而不是=TREEIFY_THRESHOLD？
因为转换还需要一个条件 tab > 64
初始化 initTable 方法
/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)//sizeCtl < 0，说明正在扩容或初始化，让出此次cpu ，自旋，如果其他线程已经初始化则退出
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//cas，把 sizeCtl 设置为 -1
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;//不想HashMap，ConcurrentHashMap的容量默认值在初始化时设置，即16
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2); //等同于 sc = sc * 0.75，初始化后 sc 代表的是下一次扩容阈值
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
addCount 容器中的元素数量 + 1，并扩容（如果大于阈值）
/**
* Adds to count, and if table is too small and not already
* resizing, initiates transfer. If already resizing, helps
* perform transfer if work is available. Rechecks occupancy
* after a transfer to see if another resize is already needed
* because resizings are lagging additions.
*
* @param x the count to add
* @param check if <0, don't check resize, if <= 1 only check if uncontended
*/
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {//只要 counterCell != null 或 出现竞争失败 则进入。
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 || //这里注意，如果 counterCells == null 而且 竞争失败，也可能出现 as != null 的情况
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
if (check >= 0) {// 是否需要检查，putVal 方法调用时，默认就是要检查的。
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) { //判断是否需要扩容， 如果 s (容器中的总数量） >= 扩容点（默认是容器容量的 0.75）
int rs = resizeStamp(n);//这个rs肯定是一个正数
if (sc < 0) {//sc 小于0，说明正在扩容
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0) //判断是否扩容结束，这里有bug，已在给出连接中说明
//(sc >>> RESIZE_STAMP_SHIFT) != rs 说明n的值变化了，说明这一轮的扩容结束了，(sc >>> RESIZE_STAMP_SHIFT) != rs的原因是因为，transfer 时 table = nextTab 在sizeCtl = (n << 1) - (n >>> 1) 之前，所以n被改变，导致rs也改变
//(nt = nextTable) == null，说明别的线程正在扩容，但还未初始化 nextTable
//nextTable已经初始化，但transferIndex <= 0 ，说明没有可分配的段供此线程转移
break;
//上面的条件都不满足，也就是说，nextTable != null，transferIndex > 0(有可分配的段)，就帮助转移，并且sizeCtl + 1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))//rs << RESIZE_STAMP_SHIFT 之后 sizeCtl变成一个非常小的负数，RESIZE_STAMP_SHIFT + RESIZE_STAMP_BITS 正好是32，正好是将1左移的32位
//首次进入转移，sizeCtl变为一个非常小的负数
//这里 + 2 不太明白，因为transfer时会-2，给我的感觉好像这里不加2，后面不减2应该也没问题
transfer(tab, null);
s = sumCount();
}
}
}
这里 baseCount 只是在没有竞争时使用的，这里有可能出现 baseCount 和 size() 数量不一致。这里的 CounterCell 的作用 和 LongAdder 几乎一摸一样。有兴趣可以看下我的另一篇文章LongAdder。
这里有个bug，jdk12才修好 请看https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8214427
这边文章特别好，该文章作者也是上面bug的修复者 https://blog.csdn.net/lengxiao1993/article/details/84029155#_1
jdk12中已修复的代码：
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT; // 位移操作挪到了这里， bug 被修复了
if (sc < 0) {
if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
(nt = nextTable) == null || transferIndex <= 0)
// sc == rs + 1，这里为什么是 rs + 1
break;
if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
transfer(tab, null);
s = sumCount();
}
}
这里为什么是rs + 1?
因为首次进入是 sc = rs + 2，后面transfer完成时(即最后一个扩容线程退出时)对sc减1即sc = rs + 2 - 1 = rs + 1
transfer 扩容
扩容时，ConcurrentHashMap 采用分段转移，一个线程负责一个或多个段，当一个段转移完毕后，就尝试获取下一分段，如果有则继续转移，直到所有的数据都被转移到nextTable
无论时获取分段还是转移都是从尾部开始的
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
*/
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)//根据CPU数量计算步长，用于多线程扩容，没来一个线程分类一个stride
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n; //transferIndex 表示剩下未分段的数组的末尾（并不是下标）
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;//nextIndex 当前已分配桶段的末尾元素的下标，当前桶分配的边界（即第一个元素，用于判断是否已经到达当前桶的边界）
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {//如果transferIndex<=0，说明桶段分配完毕，当前线程可以不需要再转移
i = -1;
advance = false;
}
else if (U.compareAndSwapInt//当前线程分配桶段未分配的一段桶段，并把 transferIndex 向前移动一个桶段的距离
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
// 所有的迁移操作已经完成
nextTable = null;
table = nextTab;
//将阈值设置未新数组的0.75倍，sizeCtl = 2n - 0.5n = 0.75(2n)
//也可以这么理解，
sizeCtl = (n << 1) - (n >>> 1);
return;
}
//进入transfer时 + 1，现在当前线程转移完毕时 - 1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)//判断是否时最后一个扩容中的线程，如果不是则直接退出
return;
//由最后一个扩容中的线程执行以下代码
finishing = advance = true;
//// i 设置为 n， 让当前线程再重复检查一遍旧数组的桶结点是不是都迁移完毕， 变成了 ForwardingNode
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null)//此处 == null 直接放入ForwardingNode
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)//已被迁移
advance = true; // already processed
else {
// 对桶的头结点加锁，独占式地完成该桶的迁移工作，防止 remove 和 insert 操作对转移的影响
synchronized (f) {
if (tabAt(tab, i) == f) {
//ln : 和原位置相同的链表，hn：原位置 + oldCap的链表
Node<K,V> ln, hn;
if (fh >= 0) {//头结点的 hash 大于 0，说明是链表的 Node 节点
int runBit = fh & n;//这里不是求余，这里的作用时判断 fh 第 n 位上的值是0还是1，如果是0的话说明该值的对newCap(新数组的容量)求余和对oldCap（旧数组的容量）求余不变，所以还是在原来的桶中，如果是1，则把它放到oldIndex + oldCap(原来的容量)。这里太66666
Node<K,V> lastRun = f;
//这个循环的作用是找出最后一段在同一位置的元素连续链表（会包括最后一个元素）
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {//runBit变化了，说明这个链表中的元素有些在<n的桶中，有些在>n的桶中
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {//这里假设所有的hash值对新数组的求余都小于n，则把链表头部放入临时变量ln中，接着它会跳过下面的for循环
ln = lastRun;
hn = null;
}
else {
hn = lastRun;//这里假设所有的hash值对新数组的求余都大于n
ln = null;
}
//这个 for 循环只有在 p != lastRun 才会进入，也就是说最后一段连续的链表的头部不是整个链表的首元素，并且说明 runBit 变化了，重新遍历整个链表，并对其进行分组
//这个很好理解，假设 oldCap = 16，链表中有一个hash fh = 50 的元素，50 % 16 = 2，扩容后newCap = 32, 50 % 32 = 18。这时候就要把它放入 i + oldCap 的桶中
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);//对旧的table设置ForwardingNode，告诉别的线程该处已经被处理了
advance = true;
}
else if (f instanceof TreeBin) {//红黑树迁移
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 如果一分为二后，节点数少于 8，那么将红黑树转换回链表
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
sizeCtl的意义：
- sizeCtl = -1： 正在初始化
- sizeCtl =0.75n ：扩容阈值
- sizeCtl < -1：正在扩容
treeifyBin 链表转红黑树
先说下红黑树的概念，红黑树首先是一种二叉树，满足二叉树的所有条件，其次它是一种二叉查找树，最后它是自平衡二叉查找树的一种实现：
它满足：
- 节点不是黑色就是红色
- 根节点是黑色
- 所有的叶子节点（nil节点）都是黑色
- 如果节点是红色，则它的子节点都是黑色
- 从任意节点到其叶子节点的路径上经过的黑色节点数量相同
这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不大于最短的可能路径的两倍长。
为什么从根到叶子的最长的可能路径不大于最短的可能路径的两倍长？
假设深度为 k 的树，那么最坏的情况（即黑色最少的情况）就是红色和黑色交替出现（因为性质4，红色不能相邻），这样黑色就是k/2，又因为性质5，这就有可能创建一颗从根到叶子的最长的可能路径等于最短的可能路径的两倍长。因为前面说了这也是最坏的情况，所以不可能大于2倍。
这里安利一个在线演示网站https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
/**
* Replaces all linked nodes in bin at given index unless table is
* too small, in which case resizes instead.
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)//table的容量小于64，尝试扩容
tryPresize(n << 1);
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {// i 的节点不为null，且hash>=0则转为红黑树，为什么判断 != null 因为有可能被别的线程修改
//对链表第一个元素换取锁
synchronized (b) {
if (tabAt(tab, index) == b) {//重新比较第一个元素，防止被其他线程修改，remove || 扩容等
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {//将Node单向链表转换为TreeNode双向链表
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));//根据上面的双向链表生成红黑树，并把根节点放入 TreeBin，最后把 TreeBin 放入对应的位置
}
}
}
}
}
链表转红黑树的条件？
- bitCont >= 8(链表数量达到9)
- 容量 >= 64
tryPresize：
/**
* Tries to presize table to accommodate the given number of elements.
*
* @param size number of elements (doesn't need to be perfectly accurate)
*/
private final void tryPresize(int size) {
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);//把size调整未比size大的2的倍数
int sc;
while ((sc = sizeCtl) >= 0) {//>0说明没有初始化和扩容操作
Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {//初始化，由putAll方法调用（也就是说new 未插入其他元素，直接调用了 putAll 方法）
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)//进入while前被别的线程扩容到大于c了
break;
else if (tab == table) {//未扩容，则进行扩容，和addCount中的逻辑一样
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
TreeBin 构造方法方法
/**
* Creates bin with initial set of nodes headed by b.
*/
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null, null, null);//将根节点的hash值置为-2
this.first = b;
TreeNode<K,V> r = null;//父节点
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (r == null) {//r == null，说明是根节点
x.parent = null;
x.red = false;//红黑树根节点是黑色
r = x;//初始化时，根节点就是父节点
}
else {
K k = x.key;//当前节点的key值
int h = x.hash;//当前节点的hash值
Class<?> kc = null;
for (TreeNode<K,V> p = r;;) {//循环遍历插入，知道插入合适的位置
int dir, ph;
K pk = p.key;//父节点的key值
if ((ph = p.hash) > h)// ph父节点的hash值
//父节点的hash值 > 当前节点的hash值
dir = -1;
else if (ph < h)
//父节点的hash值 < 当前节点的hash值
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//父节点的hash值 = 当前节点的hash值，通过别的方法计算
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;//xp 父节点的临时节点
if ((p = (dir <= 0) ? p.left : p.right) == null) {//判断父节点的左右节点是否为空，为空则插入，否则，把父节点的子节点当作父节点往下找，知道找到合适的位置
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
r = balanceInsertion(r, x);
break;
}
}
}
}
this.root = r;
assert checkInvariants(root);
}
TreeBin 维护了链表的第一个元素 first 和 树的根节点 root。
红黑树的插入(和构造方法类似)
/**
* Finds or adds a node.
* @return null if added
*/
final TreeNode<K,V> putTreeVal(int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if (p == null) {
first = root = new TreeNode<K,V>(h, k, v, null, null);
break;
}
else if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (pk != 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.findTreeNode(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.findTreeNode(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
TreeNode<K,V> x, f = first;
first = x = new TreeNode<K,V>(h, k, v, f, xp);
if (f != null)
f.prev = x;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
if (!xp.red)
x.red = true;
else {
lockRoot();
try {
root = balanceInsertion(root, x);
} finally {
unlockRoot();
}
}
break;
}
}
assert checkInvariants(root);
return null;
}
balanceInsertion 这个方法用于插入后的找平
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;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {//父节点是祖父节点的左节点
//为什么要在叔父节点和父节点都是红色的情况下才进行变色？
//因为如果单独给父节点变色的话会导致不满足性质5
if ((xppr = xpp.right) != null && xppr.red) {//叔父节点是黑色
xppr.red = false;
xp.red = false;
xpp.red = true;
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);
}
}
}
}
}
}
左旋
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {//左旋时，旋转节点 p 的右子节点 r 不能为空
if ((rl = p.right = r.left) != null)//如果右子节点 r 的左子节点 rl 不为null，则把它挂到旋转节点 p 的右节点上
rl.parent = p;
if ((pp = r.parent = p.parent) == null)//祖父节点为 null 说明 p 是根节点，此时把根节点变为 r，并且把 r 的颜色变为黑色
(root = r).red = false;
else if (pp.left == p)//p 是祖父节点的左子节点
pp.left = r;
else //p 是祖父节点的右子节点
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
找平的逻辑：假设插入的节点是 x
- 判断父节点是否为空，如果是说明是根节点，把此节点颜色设置为黑色，并返回
- 父节点 != null，且父节点的颜色为黑色，则说明是平衡的，因为插入的颜色是红色，返回
- 父节点 != null，且父节点的颜色是红色，分两种情况（主要是判断是需要左旋还是右旋，其实这两中情况正好成镜面，可以理解为一种）：
3.1. 父节点是祖父节点的左节点，分为两种情况：
3.1.1. 叔父节点是红色，则把父节点和叔父节点变为黑色，祖父节点变为红色，这里变色之后可能会造成祖父节点的和祖父节点的父节点的冲突（即，两个红色节点连在一起），这时把祖父节点当作 x，重复 1，2，3操作直到平衡（即，在1，2步骤中返回）
3.1.2. 叔父节点是黑色（null 可以堪称是黑色），需要对祖父节点右旋，右旋的前提是 x 是父节点的左节点，如果不是先对父节点进行左旋，然后在对调父节点和祖父节点的颜色，最后对祖父节点右旋，重复 1，2，3操作直到平衡（即，在1，2步骤中返回）
3.2 父节点是祖父节点的右节点，和3.1一样，就不废话了
3.2.1. ...
3.2.2. ...
红黑树的删除
/**
* Removes the given node, that must be present before this
* call. This is messier than typical red-black deletion code
* because we cannot swap the contents of an interior node
* with a leaf successor that is pinned by "next" pointers
* that are accessible independently of lock. So instead we
* swap the tree linkages.
*
* @return true if now too small, so should be untreeified
*/
final boolean removeTreeNode(TreeNode<K,V> p) {
TreeNode<K,V> next = (TreeNode<K,V>)p.next;
TreeNode<K,V> pred = p.prev; // unlink traversal pointers
TreeNode<K,V> r, rl;
if (pred == null)//处理链表
first = next;
else
pred.next = next;
if (next != null)
next.prev = pred;
if (first == null) {//只有一个根节点的情况
root = null;
return true;
}
if ((r = root) == null || r.right == null || // too small
(rl = r.left) == null || rl.left == null)
return true;
lockRoot();
try {
TreeNode<K,V> replacement;
TreeNode<K,V> pl = p.left;
TreeNode<K,V> pr = p.right;
if (pl != null && pr != null) {//被删除的节点有两个子节点，这种情况下，用了一种很巧妙的思想，即只要对调被删除节点和被删除节点的右子节点的最左叶子节点（后继节点），这里包括对调颜色，就可以把这种情况转换为下面的 pr != null 或无子节点的情况，这里真的想了很久
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor//找到后继节点，其实找前继节点也一样
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent 后继节点就是删除节点的右节点
//交换 s p的位置
p.parent = s;
s.right = p;
}
else {
//交换s p 的位置
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
r = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)//被删除节点的左子节点 != null && 被删除节点的右子节点 == null
replacement = pl;
else if (pr != null)//被删除节点的右子节点 != null && 被删除节点的左子节点 == null
replacement = pr;
else //被删除节点没有子节点
replacement = p;
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)//被删除节点是根节点
r = replacement;
else if (p == pp.left)//被删除节点是祖父节点的左子节点，并替换它
pp.left = replacement;
else//被删除节点是祖父节点的右子节点，并替换它
pp.right = replacement;
p.left = p.right = p.parent = null;
}
root = (p.red) ? r : balanceDeletion(r, replacement);//如果替换节点是红色，则不需要进行自平衡，因为少一个红色，不影响路径上黑色节点的数量
if (p == replacement) { // detach pointers
TreeNode<K,V> pp;
if ((pp = p.parent) != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
p.parent = null;
}
}
} finally {
unlockRoot();
}
assert checkInvariants(root);
return false;
}
balanceDeletion 这个方法主要是用于删除节点后的找平
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (x.red) {
x.red = false;
return root;
}
else if ((xpl = xp.left) == x) {
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;
else {
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
}
else {
if (sr == null || !sr.red) {
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
}
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
这里注意下两个子节点的情况，这种情况下，用了一种很巧妙的思想来处理。即，只要对调被删除节点和被删除节点的右子节点的最左叶子节点（后继节点），这里包括对调颜色，就可以把这种情况转换为下面的 pr != null 或无子节点的情况，这里真的想了很久
get 获取元素
读取元素不需要加锁
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {//桶中的第一个元素的hash值 == key的hash值
if ((ek = e.key) == key || (ek != null && key.equals(ek)))//如果key值也相同，说明e就是要找的元素。有可能存在hash值完全相同，但key不相同的情况。
return e.val;
}
else if (eh < 0)//第一个元素的hash小于 0，注意此时有可能正在扩容，eh = -1，Node为ForwardingNode
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
注意，获取时有可能正在扩容，也就是说，当前节点时一个ForwardingNode，ForwardingNode有一个重写方法 find ，循环的在 nextTable 上查找，看下源码：
如果当前获取节点是ForwardingNode，也说明该节点在新节点上已经转移完毕
ForwardingNode
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
outer: for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; int n;
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
for (;;) {//循环遍历链表
int eh; K ek;
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
if (eh < 0) {//说明是 ForwardingNode 或 红黑树
if (e instanceof ForwardingNode) {//发生大于一次的扩容，可能会出现这种情况
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
else
return e.find(h, k);//e是红黑树，则由相应的 find 方法处理
}
if ((e = e.next) == null)//e是链表
return null;
}
}
}
}
网友评论