1. JDK 1.7
HashTable 数据结构和 HashMap 相同,桶+链表 ,只不过HashTable 是Entry
而HashMap 是Node
ConcurrentHashMap 1.7的时候 相当于 多个 HashTable 组合在一起,每个 桶单独拥有一个锁;
区别:
【1】put和 get 两次Hash到达指定的HashEntry,第一次hash到达Segment,第二次到达Segment里面的Entry,然后在遍历entry链表
【2】Segment的初始化容量是16;
【3】HashEntry最小的容量为2
2. JDK 1.8
基本数据结构和 HashMap 相同;
【1】数据结构上:
JDK1.7版本的ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑树
【2】JDK1.8的实现降低锁的粒度,JDK1.7版本锁的粒度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是Node(首节点)
JDK1.8版本的数据结构变得更加简单,使得操作也更加清晰流畅,因为已经使用synchronized来进行同步,所以不需要分段锁的概念,也就不需要Segment这种数据结构了,由于粒度的降低,实现的复杂度也增加了
【3】从1.7到1.8版本,由于HashEntry从链表 变成了红黑树所以 concurrentHashMap的时间复杂度从O(n)到O(log(n))
2.1 JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock
【1】JDK1.6后 基于JVM的synchronized优化空间更大,使用内嵌的关键字比使用API更加自然;
在相对而言的低粒度加锁方式,synchronized并不比ReentrantLock差,在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界,更加的灵活,而在低粒度中,Condition的优势就没有了
【2】在大量的数据操作下,对于JVM的内存压力,基于API的ReentrantLock会开销更多的内存,虽然不是瓶颈,但是也是一个选择依据
3.ConcurrentHashMap put 流程
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode()); //两次hash,减少hash冲突,可以均匀分布
int binCount = 0;
for (Node<K,V>[] tab = table;;) { //对这个table进行迭代
Node<K,V> f; int n, i, fh;
//这里就是上面构造方法没有进行初始化,在这里进行判断,为null就调用initTable进行初始化,属于懒汉模式初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果i位置没有数据,就直接无锁插入
if (casTabAt(tab, i, null,
new Node<K,V>(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;
//如果以上条件都不满足,那就要进行加锁操作,也就是存在hash冲突,锁住链表或者红黑树的头结点
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { //表示该节点是链表结构
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
//这里涉及到相同的key进行put就会覆盖原先的value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) { //插入链表尾部
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {//红黑树结构
Node<K,V> p;
binCount = 2;
//红黑树结构旋转插入
if ((p = ((TreeBin<K,V>)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;
}
}
}
addCount(1L, binCount);//统计size,并且检查是否需要扩容
return null;
}
- 如果没有初始化就先调用initTable()方法来进行初始化过程
- 如果没有hash冲突,且链表头部为空,就直接CAS插入。
- 如果还在进行扩容操作就先将次线程参与到扩容中。
- 如果存在hash冲突,就加锁来保证线程安全,这里有两种情况,一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入;
- 最后一个如果该链表的数量大于阈值8,就要先转换成黑红树的结构,break再一次进入循环(阿里面试官问题,默认的链表大小,超过了这个值就会转换为红黑树);
- 如果添加成功就调用addCount()方法统计size,并且检查是否需要扩容;
2.2 ConcurrentHashMap 如何扩容
【1】当一个线程进行put 时,发现正在扩容,那么此线程会参与到扩容中。
ConcurrentHashMap 支持多个线程同时扩容。
【2】扩容之前先生成一个新数组,在转移元素时,先将原数组分组,将每组分给不同的线程来进行元素的转移,每个线程负责一组或多组的元素转移工作。
引用
https://blog.csdn.net/xingxiupaioxue/article/details/88062163