ConcurrentHashMap涉及的知识点:HashMap,HashTable,UnSafe,CAS,数组+链表,Segment,ReentrantLock(非公平锁,公平锁),红黑树。
为什么要有ConcurrentHashMap,而不直接使用HashMap和HashTable。
1.因为多线程环境下,使用Hashmap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。
2.HashTable也是线程安全的,因为HashTable在很多方法上加了synchronized,会锁住整个map,所有访问HashTable的线程都必须竞争同一把锁,效率很低。
3.ConcurrentHashMap是线程安全的,在HashMap的基本上,加上了Segment数组(分段锁),假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率。
Segment数组是一种可重入锁ReentrantLock,每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时,必须首先获得它对应的Segment锁。
4.JDK1.8到HashMap和ConCurrentHashMap进行了优化,当链接长度大于8时,会转换为红黑树。
ConcurrentHashMap的缺点:在统计size时,需要获取所有分段锁才能统计。
ReentrantLock原理:
ReentrantLock是基本Unsafe和CAS机制的,需要先对Unsafe和CAS了解。
UnSafe,基本JVM对物理内存直接操作,被认为是不安全的操作,JDK没有对外开放API。
CAS(compare and swap),CAS有3个操作数:内存值V、预期值A、要修改的新值B。当需要把A值修改成B时,只能当V=A时,才能修改成功。
- 非公平锁:如果同时还有另一个线程进来尝试获取,那么有可能会让这个线程抢先获取;(默认为非公平锁)
- 公平锁:如果同时还有另一个线程进来尝试获取,当它发现自己不是在队首的话,就会排到队尾,由队首的线程获取到锁。
a).获取锁流程A
当一个线程获取锁时,先判断锁的状态是不是等于0(0代表可以获取锁),如果等于0,尝试使用CAS进用set写入,一旦成功,表明成功获取锁。
如果锁的状态不等于0,判断获取到锁的线程是否为当前线程,如果是当前线程,将状态+1,直接进入。这也就是可重入锁的实现原理。
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
}
else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
b).获取锁流程B
当一个线程获取锁失败,进入队列队尾,进入队列后,如果前序节点是HEAD(表示列队里没有其它人需要获取锁),则CAS再尝试一次。
否则,则会根据前序节点的状态判断是否需要阻塞。如果需要阻塞,则调用LockSupport的park方法阻塞该线程。
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}