目录
读取TreeBin节点 使用共享锁
写 TreeBin节点 使用独占锁（排它锁 synchronize）
- 共享锁（读锁）
- 排它锁 又称为写锁、独占锁
- 互斥锁 是 独占锁的一种
- 独占锁：指该锁一次只能被一个线程所持有。对ReentrantLock和Synchronized而言都是独占锁
- 共享锁：指该锁可以被多个线程锁持有
- 对ReentrantReadWriteLock其读锁是共享，其写锁是独占
在putVal 方法中有一段判断是否树化链表的代码：
// 当前桶位不为null，可能是链表，可能是红黑树
if (binCount != 0) {
//如果binCount >= 8 表示处理的桶位一定是链表
if (binCount >= TREEIFY_THRESHOLD)
//调用转化链表为红黑树的方法
treeifyBin(tab, i);
//不等于null 代表与原数据发生冲突，返回原来的值
if (oldVal != null)
return oldVal;
break;
}
里面树化红黑树使用treeifyBin 方法，里面分两种情况：
- 扩容数组 tryPresize(n<<1)
- 树化链表
treeifyBin方法（包括tryPresize方法）
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
// 条件成立：说明当前table数组长度 未达到64，此时不进行树化操作，进行扩容操作
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// 扩容
tryPresize(n << 1);
// 条件成立：说明当前桶位 有数据，且是普通node数据
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
// 给头节点加锁
synchronized (b) {
// 加锁没有问题
if (tabAt(tab, index) == b) {
// TreeNode链表是双向链表
// hd 代表代表头节点，tl代表前一个节点
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
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;
}
// 把TreeBin放到对应的桶位中
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
里面用到的方法 tryPresize
* 传进来的 size=len<<1
* 假如len=16，size=32
*/
private final void tryPresize(int size) {
// size=32 , c=tableSizeFor(32 + 16 + 1) = 64
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
// sizeCtl > 0
// 1.如果table 未初始化，表示初始化大小
// 2.如果已经初始化，表示下次扩容时的 触发条件（阈值）
// sizeCtl = 0
// 表示创建table数组时，使用 DEFAULT_CAPACITY 为大小
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table;
// n 代表扩容的大小
int n;
// 说明table 还未初始化
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
// 设置sizeCtl 为-1，告诉其它线程，table正在初始化
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;
}
}
}
// 条件成立：说明sizeCtl > 0 ，因为c一定是一个正数，sc就是sizeCtl
// 扩容大小还没有达到扩容阈值
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
// 前置条件：table已经初始化，c 已达到扩容阈值
else if (tab == table) {
// rs 代表当前长度的版本戳
int rs = resizeStamp(n);
// sc 如果 小于 0
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))
/** 因为我们的 rs 最终都是要赋值给 sizeCtl 的，而 sizeCtl 负数才代表扩容，
* 而将 rs 左移 16 位就刚好使得最高位为 1，此时低 16 位全部是 0，而因为低 16 位要记录扩容线程数，
* 按常理 +1 即可，但是 sizeCtl 中 -1 这个数值已经被使用了，用来代替当前有线程准备扩容，所以只好 +2
*/
//当前线程扩容
transfer(tab, null);
}
}
}
TreeBin源码
TreeBin中的变量
部分变量：
static final class TreeBin<K,V> extends Node<K,V> {
// 红黑树 根节点
TreeNode<K,V> root;
// 链表的头节点
volatile TreeNode<K,V> first;
// 等待者线程 （当前lockState是读锁状态）
volatile Thread waiter;
* 1.写锁状态 写是独占状态，以散列表来看，真正进入到TreeBin 中的写线程 同一时刻 只有一个线程
* 2.读锁状态，读锁是共享，同一时刻可以有多个线程，同时进入到TreeBin对象中获取数据，每一个线程 都会给 lockStat + 4
* 3.等待者状态（写线程在等待），当TreeBin 中有读线程目前正在读取数据时，写线程无法修改数据，那么就将lockState的最低2位 设置为 0b 10
*/
volatile int lockState;
// values for lockState
//在持有写锁时设置
static final int WRITER = 1;
//在等待写锁时设置
static final int WAITER = 2;
//设置读锁的增量值
static final int READER = 4;
TreeBin的构造方法
* b 链表的头元素
*/
TreeBin(TreeNode<K,V> b) {
// 设置节点hash 为-2，此节点是TreeBin节点
super(TREEBIN, null, null, null);
// 使用first 引用 TreeNode 链表
this.first = b;
// r 红黑树的根节点
TreeNode<K,V> r = null;
// x 表示遍历的当前节点
// 插入链表：这个for循环是把 以b开头的链表插入到 红黑树中
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
// 强制设置当前插入节点的左右子树 为null
x.left = x.right = null;
// 条件成立：说明当前红黑树 是一个空树，那么设置插入元素 为根节点
//根节点
if (r == null) {
// 根节点的父节点 一定为null
x.parent = null;
// 颜色改为黑色
x.red = false;
// 让r引用x所指向的对象
r = x;
}
// 非根节点
else {
// 非第一次循环，此时根节点已经有元素了
// k 表示 插入节点的key
K k = x.key;
// h 表示插入节点的hash
int h = x.hash;
// kc 表示插入节点key的class类型
Class<?> kc = null;
//p 表示查找插入节点的父节点的一个临时节点
// 插入节点：这个for循环是把 x节点插入到 红黑树中
for (TreeNode<K,V> p = r;;) {
// dir
// 1:表示插入节点的hash值大于 当前p节点的hash
// -1：表示插入节点的hash值小于 当前p节点的hash
// ph：表示临时父节点的hash值
int dir, ph;
// 临时节点 key
K pk = p.key;
//插入节点的hash值 小于 临时父节点
if ((ph = p.hash) > h)
// 插入节点可能需要插入到 当前节点 的左子节点 或者 继续在左子树查找
dir = -1;
//插入节点的hash值 大于 临时父节点
else if (ph < h)
// 插入节点可能需要插入到 当前节点 的右子节点 或者 继续在右子树查找
dir = 1;
// 自定义类型比较，比较的对象是实现了Comparable 接口
// 如果执行到CASE3：说明当前插入节点的hash 与 当前节点的hash一致，会在case3 做出最终排序
// 最终拿到的dir 一定不是0，而是（1，或 -1）
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// xp 表示 插入节点的父节点
TreeNode<K,V> xp = p;
// dir<=0 说明 x 应该在 p 的左边
// 条件成立：p==null 说明当前来到了叶子节点
// 条件不成立： 说明p下面还有层数，还可以继续向下查找
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 设置插入节点为 xp
x.parent = xp;
//dir<=0 说明插入节点是父节点的左子树
if (dir <= 0)
xp.left = x;
//dir>0 说明插入节点是父节点的右子树
else
xp.right = x;
// 插入节点后 红黑树的性质可能会被破坏，所以需要调用 平衡方法
r = balanceInsertion(r, x);
break;
}
}
}
}
// 将r 赋值给 TreeBin对象的 root引用
this.root = r;
assert checkInvariants(root);
}
TreeBin的find方法
final Node<K,V> find(int h, Object k) {
if (k != null) {
//e 表示 循环迭代的当前节点 迭代的是first引用的链表
for (Node<K,V> e = first; e != null; ) {
// s 保存的是lock 临时状态
// ek 链表当前节点 的key
int s; K ek;
// (WAITER|WRITER) =》 0010 | 0001 = 0011
//等待者状态（写线程在等待），当TreeBin 中有读线程目前正在读取数据时，写线程无法修改数据，那么就将lockState的最低2位 设置为 0b 10
// lockState & 0011 != 0 条件成立：说明当前TreeBin 有等待线程 或者 目前有写操作线程正在加载
if (((s = lockState) & (WAITER|WRITER)) != 0) {
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
e = e.next;
}
//前置条件：说明上面是等于0的，当前treeBin中，等待者线程 或者 写线程 都没有
// 说明添加读锁成功 lockStat + 4
else if (U.compareAndSwapInt(this, LOCKSTATE, s,
s + READER)) {
TreeNode<K,V> r, p;
try {
//查询操作
// r是红黑树 根节点
// TreeBin 的find 里面调用的是 TreeNode 的findTreeNode
p = ((r = root) == null ? null :
r.findTreeNode(h, k, null));
} finally {
// w 表示等待者线程
Thread w;
//查询完后，释放读锁
// U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER)
// getAndAddInt 返回的值是未修改前的值
//1.当前线程查询红黑树结束，释放当前线程的读锁，就是让lockstate - 4
// (READER|WAITER) = （4 | 2） = 0110 => 表示当前只有一个线程在读，且有一个线程在等待
// 当前读线程未TreeBin 中的最后一个读线程
//2.(w = waiter) != null 说明有一个写线程在等待读操作全部结束
if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
(READER|WAITER) && (w = waiter) != null)
// 使用unpark 让写线程 恢复运行状态
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}
putTreeVal方法
* 查找或添加节点。
* 如果添加则返回null
*/
final TreeNode<K,V> putTreeVal(int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
for (TreeNode<K,V> p = root;;) {
// dir
// 1:表示插入节点的hash值大于 当前p节点的hash
// -1：表示插入节点的hash值小于 当前p节点的hash
// ph：表示临时父节点的hash值
int dir, ph; K pk;
// 当根节点为null，插入节点就是根节点
if (p == null) {
first = root = new TreeNode<K,V>(h, k, v, null, null);
break;
}
// 插入节点 比 当前节点小 dir<0
else if ((ph = p.hash) > h)
dir = -1;
// 插入节点 比 当前节点大 dir>0
else if (ph < h)
dir = 1;
// 插入节点 比 当前节点一样（key一样）
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
// 插入失败返回当前TreeNode
return p;
// 自定义类型比较，比较的对象是实现了Comparable 接口
// 如果执行到CASE3：说明当前插入节点的hash 与 当前节点的hash一致，会在case3 做出最终排序
// 最终拿到的dir 一定不是0，而是（1，或 -1）
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);
}
// xp 父节点
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 当前循环节点p 即为x节点的爸爸
// x 表示插入节点
// f 表示链表之前的 链表的头节点
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;
// 如果xp 父节点是黑色的，则x当前节点为红色
if (!xp.red)
x.red = true;
else {
// 表示当前新插入节点后，新插入节点 与父节点 形成“红红相连”
lockRoot();
try {
// 平衡红黑树，使其再次符合规范
root = balanceInsertion(root, x);
} finally {
unlockRoot();
}
}
break;
}
}
assert checkInvariants(root);
return null;
}
lockRoot方法和unlockRoot方法：
* 为树结构重组获取写锁。
*/
private final void lockRoot() {
// 只有一个写线程可以存在于TreeBin中
// 条件成立：说明lockState 并不是0，说明此时有其它线程在TreeBin红黑树中读取数据
// !false = true 说明我们已经加锁成功了
if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
contendedLock(); // offload to separate method 卸载到分离方法
}
* 为树结构调整释放写锁。
*/
private final void unlockRoot() {
lockState = 0;
}
contendedLock()方法
* 可能阻塞等待根锁。
*/
private final void contendedLock() {
boolean waiting = false;
// s 表示lock值
for (int s;;) {
// ~WAITER = 11111....10
//条件成立：说明目前TreeBin中没有读线程在访问 红黑树
// 因为读的时候lockState 后两位是 10，所以等于0时，lockState没有读线程
// 条件不成立：有线程访问红黑树
if (((s = lockState) & ~WAITER) == 0) {
// 条件成立：说明写线程 抢占成功
// 把LOCKSTATE 改为 1
if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
if (waiting)
// 设置TreeBin 对象waiter 引用为null
waiter = null;
return;
}
}
// lock & 0000...10 = 0 ：说明lock 中waiter 标志位为0，此时当前线程可以设置为 1了，然后将当前线程挂起
else if ((s & WAITER) == 0) {
// 设置LOCKSTATE 的低两位为 01，让线程等待
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
waiting = true;
// 设置等待线程就是当前线程
waiter = Thread.currentThread();
}
}
//条件成立：说明当前线程在CASE2 中，已经将waiter设置为了当前线程，并且将lockState 中表示 等待者标记位的地方 设置为了1
// 这个时候，就是让当前线程挂起
else if (waiting)
LockSupport.park(this);
}
}