前言:
本篇文章主要讲解结合底层源码介绍ConcurrentHashMap如何保证线程安全的知识。该专栏比较适合刚入坑Java的小白以及准备秋招的大佬阅读。
如果文章有什么需要改进的地方欢迎大佬提出,对大佬有帮助希望可以支持下哦~
小威在此先感谢各位小伙伴儿了😁
以下正文开始
JDK1.7保证线程安全
ConcurrentHashMap在JDK 1.7和JDK 1.8版本保证线程安全及其底层数据结构是不一样的,这一块是面试中的重点,接下来详细介绍一下它们。
在JDK 1.7中,ConcurrentHashMap采用了分段锁(Segment)的设计来保证线程安全。下面我们将通过详细解读其底层源码,来介绍其线程安全实现原理。
ConcurrentHashMap的主要类是Segment。每个Segment是一个独立的锁,并且维护着一个HashEntry数组。HashEntry是链表节点,存储了键值对。
首先,我们来看一下ConcurrentHashMap的基本数据结构:
static final class HashEntry<K, V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K, V> next;
HashEntry(int hash, K key, V value, HashEntry<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
static final class Segment<K, V> extends ReentrantLock implements Serializable {
static final float LOAD_FACTOR = 0.75f;
transient volatile HashEntry<K, V>[] table;
transient int count;
transient int modCount;
transient int threshold;
final float loadFactor;
}
每个Segment都是一个继承自ReentrantLock的可重入锁,具备独立的线程安全性。table是Segment内部的HashEntry数组,用于存储键值对。count表示当前Segment中的元素数量,modCount用于记录修改次数,threshold表示扩容的阈值,loadFactor表示加载因子。
接下来,我们看一下ConcurrentHashMap的put操作:
public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
int hash = hash(key.hashCode());
int segmentIndex = getSegmentIndex(hash);
return segments[segmentIndex].put(key, hash, value, false);
}
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
lock(); // 获取当前Segment的锁
try {
int c = count;
if (c++ > threshold) // 判断是否需要扩容
rehash();
HashEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
HashEntry<K, V> first = tab[index];
HashEntry<K, V> e = first;
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue;
if (e != null) { // 键存在,更新值
oldValue = e.value;
if (!onlyIfAbsent)
e.value = value;
} else { // 键不存在,创建新节点并添加到链表头部
oldValue = null;
++modCount;
tab[index] = new HashEntry<K, V>(hash, key, value, first);
count = c; // 更新元素数量
}
return oldValue;
} finally {
unlock(); // 释放当前Segment的锁
}
}
在put操作中,首先通过hash函数计算键的散列值hash,然后根据散列值获取对应的Segment。接着,通过Segment的锁保证了当前操作的线程安全。
在获取到Segment的锁之后,首先判断当前Segment中的元素数量count是否超过了阈值threshold,如果超过了则进行扩容。然后通过散列值和数组长度计算出键对应的索引位置index,并从对应的链表开始遍历,寻找是否存在相同的键。
如果找到了相同的键,则更新对应的值;如果没有找到相同的键,则创建一个新的HashEntry节点,并将其添加到链表的头部。
在完成操作后,释放Segment的锁。
通过分段锁的设计,JDK 1.7的ConcurrentHashMap允许多个线程同时操作不同的Segment,从而提高了并发性能。虽然在高并发情况下仍可能存在竞争问题,但通过细粒度的锁设计,可以减少锁竞争的概率,提升整体性能。
JDK1.8保证线程安全
在JDK 1.8中,ConcurrentHashMap进行了重大改进,采用了更加高效的并发控制机制来保证线程安全。相较于JDK 1.7的分段锁设计,JDK 1.8引入了基于CAS(Compare and Swap)操作和链表/红黑树结构的锁机制以及其他优化,大大提高了并发性能。
底层数据结构:
JDK 1.8中的ConcurrentHashMap采用了数组+链表/红黑树的结构。具体来说,它将整个哈希桶(Hash Bucket)划分为若干个节点(Node)。每个节点代表一个存储键值对的单元,可以是链表节点(普通节点)或红黑树节点(树节点),这取决于节点内的键值对数量是否达到阈值。使用红黑树结构可以提高查找、插入、删除等操作的效率。
主要类和数据结构如下:
static final class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
volatile V value;
volatile Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
static final class TreeNode<K, V> extends Node<K, V> {
TreeNode(int hash, K key, V value, Node<K, V> next) {
super(hash, key, value, next);
}
// 省略了红黑树相关的操作代码
}
static final class ConcurrentHashMap<K, V> {
transient volatile Node<K, V>[] table;
transient volatile int sizeCtl;
transient volatile int baseCount;
transient volatile int modCount;
}
ConcurrentHashMap的线程安全实现原理:
初始状态:在初始状态下,table为null,sizeCtl为0。当第一个元素被插入时,会根据并发级别(Concurrency Level)计算出数组的长度,并使用CAS操作将数组初始化为对应长度的桶。
插入操作
put方法:当进行插入操作时,ConcurrentHashMap首先计算键的散列值,然后根据散列值和数组长度计算出对应的桶位置。接着使用CAS操作尝试插入新节点,如果成功则插入完成;如果失败,则进入下一步。
resize方法:插入节点时,若发现链表中的节点数量已经达到阈值(默认为8),则将链表转化为红黑树,提高查找、插入、删除等操作的效率。在转化过程中,利用synchronized锁住链表或红黑树所在的桶,并进行相应的操作。
forwardTable方法:若节点数量超过阈值(默认为64)且table未被初始化,则使用CAS操作将table指向扩容后的桶数组,并根据需要将链表或红黑树进行分割,以减小线程之间的冲突。
查询操作
get方法:当进行查询操作时,首先计算键的散列值,然后根据散列值和数组长度计算出对应的桶位置。接着从桶位置的链表或红黑树中查找对应的节点。
其他操作
remove方法:当进行删除操作时,首先计算键的散列值,然后根据散列值和数组长度计算出对应的桶位置。接着使用synchronized锁住桶,并进行相应的操作。
综上所述,JDK 1.8的ConcurrentHashMap通过CAS操作、锁机制(synchronized)以及链表/红黑树结构来保证线程安全。CAS操作用于插入新节点和初始化桶数组,锁机制用于链表/红黑树的转化和删除操作,链表/红黑树结构用于提高查找、插入、删除操作的效率。这些优化措施使得ConcurrentHashMap在高并发环境下具有较好的性能表现。
JDK1.7和JDK1.8对比总结
在JDK 1.7和JDK 1.8中,ConcurrentHashMap有以下主要区别:
JDK 1.7中的实现方式:
- JDK 1.7中的ConcurrentHashMap使用分段锁(Segment Locking)的设计。它将整个哈希表分成多个段(Segment),每个段都有自己的锁。这样可以降低并发操作时锁的争用范围,提高并发性能。
- 每个段中包含一个HashEntry数组,每个HashEntry是一个链表结构,用于解决哈希冲突。
- 由于每个段都有自己的锁,不同的线程可以同时访问不同的段,从而提高了并发度。
JDK 1.8中的改进:
JDK 1.8中的ConcurrentHashMap采用了CAS操作、锁机制以及链表/红黑树结构的改进。
- 数据结构改进:JDK 1.8中使用数组+链表/红黑树的结构,代替了JDK 1.7中的段+链表结构。数组用于存储桶,链表/红黑树用于解决哈希冲突。
- CAS操作:JDK 1.8使用CAS(Compare and Swap)操作来插入新节点和初始化桶数组。CAS操作是一种乐观锁机制,通过原子操作比较并交换的方式进行,并发安全性更好。
- 锁的改进:JDK 1.8中引入了基于CAS操作和链表/红黑树结构的锁机制。对于链表/红黑树上的操作,使用synchronized锁住桶,以保证操作的原子性。
- 链表转化为红黑树:JDK 1.8在插入操作时,当链表中的节点数量达到一定阈值时,会将链表转化为红黑树,提高查找、插入、删除等操作的效率。
- resize操作的改进:JDK 1.8中的resize操作(扩容)采用了分割链表/红黑树的方式,减小了线程冲突的概率。
总的来说,JDK 1.8中的ConcurrentHashMap在数据结构、CAS操作、锁机制和链表/红黑树结构等方面进行了改进,相较于JDK 1.7,性能更好且并发度更高。这些改进使得JDK 1.8中的ConcurrentHashMap在高并发环境下表现更优秀。
文章到这里就先结束了,感兴趣的可以订阅专栏哈,后续会继续分享相关的知识点。文章来源:https://www.toymoban.com/news/detail-505037.html
文章来源地址https://www.toymoban.com/news/detail-505037.html
到了这里,关于结合底层源码介绍ConcurrentHashMap如何保证线程安全,佬会爱上这篇文章嘛的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!