原理上来说,ConcurrentHashMap 采纳了分段锁技术,其中 Segment 继承于 ReentrantLock。
不会像 HashTable 那样不论是 put 还是 get 操作都须要做同步解决,实践上 ConcurrentHashMap 反对 CurrencyLevel (Segment 数组数量) 的线程并发。
每当一个线程占用锁拜访一个 Segment 时,不会影响到其余的 Segment。
就是说如果容量大小是 16 他的并发度就是 16,能够同时容许 16 个线程操作 16 个 Segment 而且还是线程平安的。
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();// 这就是为啥他不能够 put null 值的起因
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
他先定位到 Segment,而后再进行 put 操作。
咱们看看他的 put 源代码,你就晓得他是怎么做到线程平安的了,要害句子我正文了。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 将以后 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {if (e != null) {K k;
// 遍历该 HashEntry,如果不为空则判断传入的 key 和以后遍历的 key 是否相等,相等则笼罩旧的 value。
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
// 不为空则须要新建一个 HashEntry 并退出到 Segment 中,同时会先判断是否须要扩容。if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
// 开释锁
unlock();}
return oldValue;
}
首先第一步的时候会尝试获取锁,如果获取失败必定就有其余线程存在竞争,则利用 scanAndLockForPut() 自旋获取锁。
尝试自旋获取锁。
如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取,保障能获取胜利。
get 逻辑比较简单,只须要将 Key 通过 Hash 之后定位到具体的 Segment,再通过一次 Hash 定位到具体的元素上。
因为 HashEntry 中的 value 属性是用 volatile 关键词润饰的,保障了内存可见性,所以每次获取时都是最新值。
ConcurrentHashMap 的 get 办法是十分高效的,因为整个过程都不须要加锁。
1.7 尽管能够反对每个 Segment 并发拜访,然而还是存在一些问题?
因为基本上还是数组加链表的形式,咱们去查问的时候,还得遍历链表,会导致效率很低,这个跟 jdk1.7 的 HashMap 是存在的一样问题,所以他在 jdk1.8 齐全优化了。
jdk1.8 他的数据结构是怎么样子的呢?
其中摈弃了原有的 Segment 分段锁,而采纳了 CAS + synchronized 来保障并发安全性。
跟 HashMap 很像,也把之前的 HashEntry 改成了 Node,然而作用不变,把值和 next 采纳了 volatile 去润饰,保障了可见性,并且也引入了红黑树,在链表大于肯定值的时候会转换(默认是 8)。