简介
前面一篇我们介绍了ConcurrentHashMap一些重要的内部类Node 、TreeNode、TreeBin、ForwardingNode，以及ConcurrentMap接口和ConcurrentHashMap的构造函数，本篇主要介绍ConcurrentHashMap的主干方法。
ConcurrentHashMap 的hash算法
static final int spread(int h) {
// 混合高低位，并控制范围
return (h ^ (h >>> 16)) & HASH_BITS;
}
在HashMap中hash算法是return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 而spread方法其实就是hash算法，最后和int最大值取位与只是为了控制结果在int范围内。
ConcurrentHashMap 数组长度计算
private static final int tableSizeFor(int c) {
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
此方法请看HashMap篇，里面有详细推导
ConcurrentHashMap 操作数组头节点
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
// ((long)i << ASHIFT) + ABASE 元素位置
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
// 修改槽中元素从c改成v
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
// v放到对应槽中
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
ConcurrentHashMap 添加
public V put(K key, V value) {
// 添加
return putVal(key, value, false);
}
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;
// 遍历table
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// tab为空（第一次添加）
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 查找hash所在的槽是否为空
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 创建新节点并放入对应槽中(失败重新来过)
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
// 正在扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
// 原值
V oldVal = null;
// 锁定头节点
synchronized (f) {
// 头节点没有改变过
if (tabAt(tab, i) == f) {
// 头节点hash 大于 0
if (fh >= 0) {
// 链表添加初始为1
binCount = 1;
// 从头节点开始遍历（每次binCount加1）
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 键是否一样
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 获取原值
oldVal = e.val;
// 不覆盖开关是否打开，false就覆盖
if (!onlyIfAbsent)
e.val = value;
break;
}
// 键不一样e下移
Node<K,V> pred = e;
// 后面节点为空
if ((e = e.next) == null) {
// 追加元素
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// hash 小于 0 说明是TreeBin（hash为-2）
else if (f instanceof TreeBin) {
Node<K,V> p;
// 树添加设置为2
binCount = 2;
// 调用树结构添加
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
// 原值
oldVal = p.val;
if (!onlyIfAbsent)
// 覆盖原值
p.val = value;
}
}
}
}
if (binCount != 0) {
// binCount 大于8，链表转树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
// 原值不为空，要么覆盖要么忽略
if (oldVal != null)
return oldVal;
break;
}
}
}
// 能到这儿一定添加成功（需不需要扩容）
addCount(1L, binCount);
return null;
}
如果只看putVal方法ConcurrentHashMap 跟HashMap差不多，就把头元素锁了，但是如果你真这么认为，只能说明没有看第三篇。
ConcurrentHashMap 初始化数组
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// table 不为空退出循环
while ((tab = table) == null || tab.length == 0) {
// 判断扩容阈值是否小于0
if ((sc = sizeCtl) < 0)
// 让出cpu
Thread.yield();
// 修改扩容阈值为-1
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// 判处table是否还没被初始化
if ((tab = table) == null || tab.length == 0) {
// sc > 0 使用sc，否则使用默认初始长度
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 创建数组
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
// 赋值
table = tab = nt;
// 计算下次扩容阈值
// n - n/4 等价于 n*0.75
sc = n - (n >>> 2);
}
} finally {
// 设置新的扩容阈值
sizeCtl = sc;
}
break;
}
}
return tab;
}
ConcurrentHashMap 链表转树
// binCount（链表长度）大于8会调用这个方法
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
// 数组不能为空
if (tab != null) {
// 判断是在是否小于64
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// 扩容第三篇会讲
tryPresize(n << 1);
// 大于64，获取头节点，判断是否已经是TreeBin
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
// 锁住头节点
synchronized (b) {
// 再取一次头节点判断跟b是否一样
if (tabAt(tab, index) == b) {
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);
// 构建树节点的链表结构，
// 初始化TreeBin时才转树结构
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
// 构建TreeBin，并把它放入当前槽
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
ConcurrentHashMap 树转链表
static <K,V> Node<K,V> untreeify(Node<K,V> b) {
Node<K,V> hd = null, tl = null;
// 遍历节点
for (Node<K,V> q = b; q != null; q = q.next) {
// 构建普通节点
Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
ConcurrentHashMap 键取值
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 计算hash
int h = spread(key.hashCode());
// 判断数组是否为空，然后判断槽中头节点是否为空
// (n - 1) & h 就是取余，请看HashMap篇推导过程
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 头节点hash是否一样
if ((eh = e.hash) == h) {
// hash一样看key是否一样
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
// key一样返回节点中的值
return e.val;
}
// hash不一样，判断hash是否小于0
// TreeBin 的hash为-2
else if (eh < 0)
// 在红黑树中查找
return (p = e.find(h, key)) != null ? p.val : null;
// 能到这说明一定是链表，通过遍历链表查找
while ((e = e.next) != null) {
// 判断key是否一样，并节点下移
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
ConcurrentHashMap 删除
public V remove(Object key) {
return replaceNode(key, null, null);
}
final V replaceNode(Object key, V value, Object cv) {
// 计算hash
int hash = spread(key.hashCode());
// 自旋
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 判断数组或头节点为空
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
// 直接退出
break;
// 判断hash是否为移动状态
else if ((fh = f.hash) == MOVED)
// 如果是就帮忙移动，移动完自旋删除
tab = helpTransfer(tab, f);
else {
// 能到这儿，说明不是再移动
V oldVal = null;
boolean validated = false;
// 锁住头节点
synchronized (f) {
// 判断头节点是否变动
if (tabAt(tab, i) == f) {
// 链表删除
if (fh >= 0) {
validated = true;
// 遍历链表
for (Node<K,V> e = f, pred = null;;) {
K ek;
// 判断key是否一样
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
V ev = e.val;
// 判断值是否一样
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
// 原值
oldVal = ev;
// value不为空，使用value覆盖原值，
// 否则移除节点，
// 如果移除的是头节点，需要把设置新头节点
if (value != null)
e.val = value;
else if (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
// 节点下移
pred = e;
if ((e = e.next) == null)
break;
}
}
// 树结构中删除
else if (f instanceof TreeBin) {
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
// 在树结构中查找
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
// 判断值是否一样
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
oldVal = pv;
// value不为空，使用value覆盖原值，
// 否则，在树结构中删除
// 如果移除的是头节点，需要设置新头节点
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
// 是否查找过
if (validated) {
// 原值是否为空
if (oldVal != null) {
// value是否为空，不为空只覆盖不删除
if (value == null)
// 长度减一
addCount(-1L, -1);
// 返回原值
return oldVal;
}
break;
}
}
}
return null;
}
ConcurrentHashMap 清空
public void clear() {
long delta = 0L;
int i = 0;
Node<K,V>[] tab = table;
// 遍历数组所有元素
while (tab != null && i < tab.length) {
int fh;
// 获取头节点
Node<K,V> f = tabAt(tab, i);
// 头节点为空，数组下标加1
if (f == null)
++i;
// 判断头节点状态
else if ((fh = f.hash) == MOVED) {
// 帮忙移动
tab = helpTransfer(tab, f);
// 移动完成，重置数组下标
i = 0;
}
// 正常删除
else {
// 锁住头节点
synchronized (f) {
// 判断头节点是否变化
if (tabAt(tab, i) == f) {
// 获取链表或树的头节点
Node<K,V> p = (fh >= 0 ? f :
(f instanceof TreeBin) ?
((TreeBin<K,V>)f).first : null);
// 遍历个数
while (p != null) {
--delta;
p = p.next;
}
// 清空当前槽
setTabAt(tab, i++, null);
}
}
}
}
// 修改总长度
if (delta != 0L)
addCount(delta, -1);
}
ConcurrentHashMap 在修改链表或者树时都会锁住头元素，其他修改操作就拿不到锁，他们就会等待。
