ConcurrentHashMap和HashMap原理基本类似,只是在HashMap的基础上需要支持并发操作,保证多线程情况下对HashMap操作的安全性。当某个线程对集合内的元素进行数据操作时,会锁定这个元素,如果其他线程操作的数据hash得到相同的位置,就必须等到这个线程释放锁之后才能进行操作。
HashMap --> 非线程安全的:多线程同时访问一个HashMap实例会存在线程安全问题。
HashTable --> 线程安全的:方法上都加了synchronized锁,能保证线程安全,但是锁的粒度太大,性能低。
为了去优化,在性能和线程安全方面做个平衡,所以引入ConcurrentHashMap,在方法内部代码块上加了synchronized锁。
使用方法computeIfAbsent:如果不存在则修改值
computeIfPresent:如果存在则修改值
compute:computeIfAbsent和computeIfPresent的结合
merge:数据合并
jdk 1.7:使用segment分段锁,锁的粒度大
jdk 1.8:使用链表 + 红黑树
ConcurrentHashMap和HashMap原理基本类似,只是在HashMap的基础上需要支持并发操作,保证多线程情况下对HashMap操作的安全性。当某个线程对集合内的元素进行数据操作时,会锁定这个元素,如果其他线程操作的数据hash得到相同的位置,就必须等到这个线程释放锁之后才能进行操作。
数据结构- 最外层是初始16位长度的数组,数据达到阈值(16 * 0.75)时会自动扩容(16 >> 1 = 32)
- 插入数据时,先对key进行hash计算得到数据将要插入到数组的位置下标,如果此位置为空,则插入;
- 如果此位置有数据,并且key相同,则替换做修改操作;
- 如果此位置有数据,但key不同,则追加到此下标位置;
- 初始情况下标位置是以单向链表结构存储数据,后续数据追加到链表尾部;
- 当数组长度扩容到64,且某个位置链表长度达到8时,会将单向链表转换为红黑树结构
- 做删除操作时,如果某个位置元素小于8时,会将红黑树转换为单向链表
为什么扩容因子设置为0.75,链表长度阈值为8?
遵循泊松分布(Poisson Distribution),这样可以让链表转红黑树的几率很小,链表转红黑树会有性能损耗。
扩容过程(满足两种情况会扩容):
- 当新增节点后,所在位置链表元素个数达到阈值8,并且数组长度小于64;
- 当增加集合元素后,当前数组内元素个数达到扩容阈值(16 * 0.75)时就会触发扩容;
- 当线程处于扩容状态下,其他线程对集合进行操作时会参与帮助扩容;
默认是16位长度的数组,如果扩容就会新创建一个32位长度的数组,并对数据进行迁移,采用高低位迁移;
高低位迁移原理扩容之后,数据迁移,有些数据需要迁移,有些数据不需要,低位不变,高位迁移;
数据扩容,但是计算存储位置下标的公式不变:i = (n - 1) & hash,所以有些key在扩容前后得到的下标位置相同,而有些key在扩容后hash得到的下标位置发生了改变;
假设:某个key的hash为9,数组长度为16,扩容到32,hash后得到的位置依然是9
假设:某个key,数组长度为16时hash值为4,而扩容为32长度时hash值变成了20
所以,table长度发生变化之后,获取同一个key在集合数组中的位置发生了变化,那么就需要迁移
链表转红黑树当数组长度大于等于64,且某个数组位置的链表长度大于等于8,会把该位置链表转化为红黑树
hash冲突在ConcurrentHashMap中,通过链式寻址解决hash冲突问题。
源码分析 put()方法// 存储数据元素的容器 transient volatile Node[] table; public V put(K key, V value) { return putVal(key, value, false); // 是否只有当不存在时才put }
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
// 自旋(;;)去保证数据存储成功,通过cas保证线程安全
for (ConcurrentHashMap.Node[] tab = table;;) {
ConcurrentHashMap.Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); //初始化table
// (n - 1) & hash --> hash取模计算数组下标位置
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果当前位置为空,直接存储到该位置
// 通过cas保证原子性操作
if (casTabAt(tab, i, null,
new ConcurrentHashMap.Node(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) {
if (tabAt(tab, i) == f) {
// 针对链表结构
if (fh >= 0) {
binCount = 1;
// 此处f代表链表中的头节点,循环整个链表所有元素
for (ConcurrentHashMap.Node e = f;; ++binCount) {
K ek;
// 判断是否存在相同的key,如果存在则覆盖
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
// 如果不存在则通过尾插法插入到链表尾部
ConcurrentHashMap.Node pred = e;
// 说明到了最后一个节点,插入到尾部
if ((e = e.next) == null) {
pred.next = new ConcurrentHashMap.Node(hash, key,
value, null);
break;
}
}
}
// 针对红黑树结构
else if (f instanceof ConcurrentHashMap.TreeBin) {
ConcurrentHashMap.Node p;
binCount = 2;
if ((p = ((ConcurrentHashMap.TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
// 如果链表长度大于8,则判断是否转换红黑树还是扩容
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 统计ConcurrentHashMap数组元素个数
addCount(1L, binCount);
return null;
}
initTable()
有可能多个线程同时进入此方法去初始化数组,但是这里没有加锁,而是使用CAS保证原子性操作,因为CAS方法里面用到了Lock锁
private final ConcurrentHashMap.Node[] initTable() { ConcurrentHashMap.Node [] tab; int sc; // 如果table没有初始化,不停循环 while ((tab = table) == null || tab.length == 0) { if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin // 通过cas自旋,占用一个锁的标记,保证原子性操作 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 说明当前线程抢占了锁 try { if ((tab = table) == null || tab.length == 0) { int n = (sc > 0) ? sc : DEFAULT_CAPACITY; @SuppressWarnings("unchecked") ConcurrentHashMap.Node [] nt = (ConcurrentHashMap.Node [])new ConcurrentHashMap.Node,?>[n]; table = tab = nt; sc = n - (n >>> 2); // 扩容的阈值 } } finally { sizeCtl = sc; } break; } } return tab; }
casTabAt()
static finaltreeifyBin(tab, index)boolean casTabAt(Node [] tab, int i, Node c, Node v) { return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); }
根据阈值判断是否需要链表转红黑树,还是进行扩容
private final void treeifyBin(ConcurrentHashMap.NodetryPresize(size)扩容[] tab, int index) { ConcurrentHashMap.Node b; int n, sc; if (tab != null) { // 如果数组长度小于64,扩容 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); // 否则链表转红黑树 else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { synchronized (b) { if (tabAt(tab, index) == b) { ConcurrentHashMap.TreeNode hd = null, tl = null; for (ConcurrentHashMap.Node e = b; e != null; e = e.next) { ConcurrentHashMap.TreeNode p = new ConcurrentHashMap.TreeNode (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 ConcurrentHashMap.TreeBin (hd)); } } } } }
多线程并发扩容(允许其他线程来协助扩容):多个线程对数据进行分段迁移
扩容的本质是创建一个新的数组,数组大小是之前的两倍
private final void tryPresize(int size) {
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
ConcurrentHashMap.Node[] tab = table; int n;
// 如果没有初始化table, 在此做初始化,putAll方法可能在此做初始化
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
ConcurrentHashMap.Node[] nt = (ConcurrentHashMap.Node[])new ConcurrentHashMap.Node,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
// 如果已经是最大容量,不能扩容
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
int rs = resizeStamp(n);
if (sc < 0) {
ConcurrentHashMap.Node[] 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);
}
}
}
transfer(tab, nextTab)数据迁移
支持多线程协助做数据扩容,记录线程的数量(sizeCtl),对数据进行分段,每个线程负责一段数据的迁移,当每个线程完成数据迁移之后,退出的时候减掉协助扩容的线程数量。
对数组数据进行迁移:
- 可能数组节点是链表
(n - 1) & hash取模运算后可能得到不同的结果:
比如n为16时:15 & 4 = 4;15 & 20 = 4;15 & 52 = 4;
如果n为32时:31 & 4 = 4;31 & 20 = 20;31 & 52 = 20;
我们可以发现hash值为4时hash取模的结果是相同的,而其他hash值取模后结果不同,所以:
○ 可能数组位置不变:数据不需要迁移
○ 可能数据位置变了:数据需要迁移
- 可能数组节点是红黑树
private final void transfer(ConcurrentHashMap.NodeConcurrentHashMap如何统计元素个数?[] tab, ConcurrentHashMap.Node [] nextTab) { int n = tab.length, stride; // 计算每个线程处理的数据区间大小,最小是16 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range if (nextTab == null) { // initiating try { // 初始化扩容之后的数组,向左位移一位表示扩大两倍 @SuppressWarnings("unchecked") ConcurrentHashMap.Node [] nt = (ConcurrentHashMap.Node [])new ConcurrentHashMap.Node,?>[n << 1]; nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; // 迁移的索引 transferIndex = n; } int nextn = nextTab.length; // 表示已经迁移完的状态,如果old数组迁移完成,则更改成fwd ConcurrentHashMap.ForwardingNode fwd = new ConcurrentHashMap.ForwardingNode (nextTab); boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { ConcurrentHashMap.Node f; int fh; while (advance) { int nextIndex, nextBound; if (--i >= bound || finishing) advance = false; else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } else if (U.compareAndSwapInt (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; sizeCtl = (n << 1) - (n >>> 1); return; } if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) return; finishing = advance = true; i = n; // recheck before commit } } else if ((f = tabAt(tab, i)) == null) //如果数组位置节点为空,代表已经迁移过了 advance = casTabAt(tab, i, null, fwd); //改成fwd,代表迁移完成 else if ((fh = f.hash) == MOVED) //元素已经被迁移过了 advance = true; // already processed else { // 加锁--> 针对当前要迁移的节点 synchronized (f) { //保证迁移过程中,其他线程在此节点put数据,必须要等待 if (tabAt(tab, i) == f) { ConcurrentHashMap.Node ln, hn; if (fh >= 0) { int runBit = fh & n; //f的hash值与n取模运算 ConcurrentHashMap.Node lastRun = f; for (ConcurrentHashMap.Node p = f.next; p != null; p = p.next) { int b = p.hash & n; if (b != runBit) { runBit = b; lastRun = p; } } if (runBit == 0) { // hash取模结果为0代表不需要迁移 ln = lastRun; // 存入低位链表 hn = null; } else { //需要迁移 hn = lastRun; // 存入高位链表 ln = null; } for (ConcurrentHashMap.Node 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 ConcurrentHashMap.Node (ph, pk, pv, ln); else hn = new ConcurrentHashMap.Node (ph, pk, pv, hn); } setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } // 针对红黑树节点 else if (f instanceof ConcurrentHashMap.TreeBin) { ConcurrentHashMap.TreeBin t = (ConcurrentHashMap.TreeBin )f; ConcurrentHashMap.TreeNode lo = null, loTail = null; ConcurrentHashMap.TreeNode hi = null, hiTail = null; int lc = 0, hc = 0; for (ConcurrentHashMap.Node e = t.first; e != null; e = e.next) { int h = e.hash; ConcurrentHashMap.TreeNode p = new ConcurrentHashMap.TreeNode (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; } } ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new ConcurrentHashMap.TreeBin (lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new ConcurrentHashMap.TreeBin (hi) : t; setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } } } } } }
private transient volatile long baseCount; private transient volatile CounterCell[] counterCells;
private final void addCount(long x, int check) {
ConcurrentHashMap.CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
// 如果竞争不激烈,那么baseCount直接成功计数
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// 如果baseCount计数失败代表竞争激烈,接下来通过CounterCell[]数组方式计数
ConcurrentHashMap.CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
// 完成CounterCell的初始化和元素的累加
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
// 判断是否需要扩容
if (check >= 0) {
ConcurrentHashMap.Node[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
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);
s = sumCount();
}
}
}
// 通过@sun.misc.Contended解决伪共享问题
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
1) 如果竞争不激烈的情况下,通过cas使用baseCount + 1计数;
2) 如果竞争激烈,采用数组counterCells的方式计数;默认长度为2的数组,如果不够可以扩容,然后每次计数的时候随机负载到数组某个位置去修改元素的值,最后把数组所有元素的值累加;
那么ConcurrentHashMap元素的个数就是baseCount的值与counterCells数组元素值之和。
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
boolean collide = false; // True if last slot nonempty
for (;;) {
ConcurrentHashMap.CounterCell[] as; ConcurrentHashMap.CounterCell a; int n; long v;
if ((as = counterCells) != null && (n = as.length) > 0) {
if ((a = as[(n - 1) & h]) == null) {
if (cellsBusy == 0) { // Try to attach new Cell
ConcurrentHashMap.CounterCell r = new ConcurrentHashMap.CounterCell(x); // Optimistic create
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { //通过CAS抢占锁
boolean created = false;
try { // Recheck under lock
ConcurrentHashMap.CounterCell[] rs; int m, j;
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
// 添加一个CounterCell
rs[j] = r;
created = true;
}
} finally {
cellsBusy = 0;
}
if (created)
break;
continue; // Slot is now non-empty
}
}
collide = false;
}
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;
else if (counterCells != as || n >= NCPU)
collide = false; // At max size or stale
else if (!collide)
collide = true;
// 扩容部分
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { //通过CAS抢占锁
try {
if (counterCells == as) {// Expand table unless stale
// 对CounterCell[]数组长度扩容一倍
ConcurrentHashMap.CounterCell[] rs = new ConcurrentHashMap.CounterCell[n << 1];
// 扩容后做数据迁移,将旧数组元素添加到新数组中
for (int i = 0; i < n; ++i)
rs[i] = as[i];
counterCells = rs;
}
} finally {
cellsBusy = 0;
}
collide = false;
continue; // Retry with expanded table
}
h = ThreadLocalRandom.advanceProbe(h);
}
// 如果CounterCell[]数组为空,保证初始化过程的线程安全性,通过CAS操作
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// 如果CAS操作修改cellsBusy值成功,代表抢占到锁
boolean init = false;
try { // Initialize table
if (counterCells == as) {
ConcurrentHashMap.CounterCell[] rs = new ConcurrentHashMap.CounterCell[2];
rs[h & 1] = new ConcurrentHashMap.CounterCell(x); //把x保存到数组某个位置
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0; //最后释放锁
}
if (init)
break;
}
// 修改baseCount
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
统计元素个数
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
ConcurrentHashMap.CounterCell[] as = counterCells; ConcurrentHashMap.CounterCell a;
long sum = baseCount; //先拿到baseCount
if (as != null) { //遍历CounterCell[]数组元素,将所有元素值累加
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}



