Java集合源码解析-ConcurrentHashMap(JDK8)(上)

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: Java集合源码解析-ConcurrentHashMap(JDK8)

为并发而生的 ConcurrentHashMap

数据结构


Java 7为实现并发访问,引入了Segment这一结构,实现了分段锁,理论上最大并发度与Segment个数相等。


Java 8取消了基于 Segment 的分段锁思想,改用CAS + synchronized 控制并发操作,在某些方面提升了性能。并且追随 1.8 版本的 HashMap 底层实现,使用数组+链表+红黑树进行数据存储。


image.png


和 HashMap 中的语义一样,代表整个哈希表。在第一次插入时才懒加载初始化。大小永远是 2 的次幂。被迭代器直接访问。


image.png


一个连接表,用于哈希表扩容,扩容完成后会被重置为 null


image.png


保存着整个哈希表中存储的所有的结点的个数总和,类似于 HashMap 的 size 属性。主要用于当没有线程竞争时使用,也会作为哈希表初始化过程中的反馈。通过CAS 更新。

image.png


这是一个重要的属性,无论是初始化哈希表,还是扩容 rehash,都需要该依赖。有如下取值:

  • >0:相当于 HashMap 中的 threshold,表示阈值
  • 0:默认值
  • -1:代表哈希表正在进行初始化
  • <-1:代表有多个线程正在进行扩容


image.png


构造函数的实现也和HashMap类似


image.png



若传入 32,实际大小 64。即最接近1.5n+1的 2的次幂。因为如果你想存入 15 个元素,那么 16 是存不下的,需要扩容,所以直接给你初始化为 32 的容量。


image.png



寻址方式

同样是通过Key的哈希值与数组长度取模确定该Key在数组中的索引;

同样为了避免不太好的Key的hashCode设计,它通过如下方法计算得到Key的最终哈希值.

// usable bits of normal node hash
static final int HASH_BITS = 0x7fffffff;

不同的是,Java 8的ConcurrentHashMap作者认为引入红黑树后,即使哈希冲突比较严重,寻址效率也足够高,所以作者并未在哈希值的计算上做过多设计,只是将Key的hashCode值与其高16位作异或并保证最高位为0(从而保证最终结果为正整数)


image.png



8.3 同步方式

对于put操作,如果Key对应的数组元素为null,则通过CAS操作将其设置为当前值;

如果Key对应的数组元素(也即链表表头或者树的根元素)不为null,则对该元素使用synchronized关键字申请锁,然后进行操作;

如果该put操作使得当前链表长度超过一定阈值,则将该链表转换为树,从而提高寻址效率.


对于读操作,由于数组被volatile修饰,因此不用担心数组的可见性问题;

同时每个元素是一个Node实例(Java 7中每个元素是一个HashEntry),它的Key值和hash值都由final修饰,不可变更,无须关心它们被修改后的可见性问题;

而其Value及对下一个元素的引用由volatile修饰,可见性也有保障.


8.4 操作


put方法和remove方法都会通过addCount方法维护Map的size;

size方法通过sumCount获取由addCount方法维护的Map的size.


下面我们主要来分析下 ConcurrentHashMap 的一个核心方法 put,我们也会一并解决掉该方法中涉及到的扩容、辅助扩容,初始化哈希表等方法。



8.4.1 put

HashMap多线程并发添加元素会导致数据丢失等并发问题,那么 ConcurrentHashMap 又是如何做到并发添加的呢?

final V putVal(K key, V value, boolean onlyIfAbsent) {
    //对传入的参数进行合法性判断
    if (key == null || value == null) throw new NullPointerException();
    //计算键所对应的 hash 值
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //如果哈希表还未初始化,那么初始化它
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        //根据键的 hash 值找到哈希数组相应的索引位置
        //如果为空,那么以CAS无锁式向该位置添加一个节点
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   
        }

这里需要详细说明的只有initTable 方法:初始化哈希表,它同时只允许一个线程进行初始化操作。

/**
  * Initializes table, using the size recorded in sizeCtl.
  */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    // 如果表为空才进行初始化操作
    while ((tab = table) == null || tab.length == 0) {
        // sizeCtl 小于零说明已经有线程正在进行初始化操作
        // 当前线程应该放弃 CPU 的使用
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        // 否则说明尚未有线程对表进行初始化,那么本线程就来做这个工作
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            //保险起见,再次判断下表是否为空
            try {
                if ((tab = table) == null || tab.length == 0) {
                    //至此, sc 大于零说明容量已经初始化了,否则使用默认容量,其他线程再也无法初始化!!!
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    //根据容量构建数组
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    //计算阈值,等效于 n*0.75
                    sc = n - (n >>> 2);
                }
            } finally {
                //设置阈值
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}
目录
相关文章
|
2月前
|
存储 安全 Java
Java 集合框架中的老炮与新秀:HashTable 和 HashMap 谁更胜一筹?
嗨,大家好,我是技术伙伴小米。今天通过讲故事的方式,详细介绍 Java 中 HashMap 和 HashTable 的区别。从版本、线程安全、null 值支持、性能及迭代器行为等方面对比,帮助你轻松应对面试中的经典问题。HashMap 更高效灵活,适合单线程或需手动处理线程安全的场景;HashTable 较古老,线程安全但性能不佳。现代项目推荐使用 ConcurrentHashMap。关注我的公众号“软件求生”,获取更多技术干货!
52 3
|
2月前
|
存储 缓存 安全
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
60 5
|
3月前
|
存储 缓存 安全
Java 集合框架优化:从基础到高级应用
《Java集合框架优化:从基础到高级应用》深入解析Java集合框架的核心原理与优化技巧,涵盖列表、集合、映射等常用数据结构,结合实际案例,指导开发者高效使用和优化Java集合。
72 4
|
3月前
|
安全 Java
Java多线程集合类
本文介绍了Java中线程安全的问题及解决方案。通过示例代码展示了使用`CopyOnWriteArrayList`、`CopyOnWriteArraySet`和`ConcurrentHashMap`来解决多线程环境下集合操作的线程安全问题。这些类通过不同的机制确保了线程安全,提高了并发性能。
|
9月前
|
存储 Java Windows
Java21 JDK下载安装及Windows环境变量配置
JDK是Java的开发工具包,要进行Java学习或开发之前,需先下载安装,下载地址如下:提示:这网址里面有三个扩展名的文件,分别是“.zip”、“.exe”和“.msi”,鄙人选择的是.exe的文件,下方的安装和环境的配置也是安装该文件的安装程序进行的。
1077 2
Java JDK的安装
首先我们先去下载jdk。
|
6月前
|
Java 关系型数据库 MySQL
"解锁Java Web传奇之旅:从JDK1.8到Tomcat,再到MariaDB,一场跨越数据库的冒险安装盛宴,挑战你的技术极限!"
【8月更文挑战第19天】在Linux上搭建Java Web应用环境,需安装JDK 1.8、Tomcat及MariaDB。本指南详述了使用apt-get安装OpenJDK 1.8的方法,并验证其版本。接着下载与解压Tomcat至`/usr/local/`目录,并启动服务。最后,通过apt-get安装MariaDB,设置基本安全配置。完成这些步骤后,即可验证各组件的状态,为部署Java Web应用打下基础。
77 1
|
5月前
|
关系型数据库 Java MySQL
"解锁Java Web传奇之旅:从JDK1.8到Tomcat,再到MariaDB,一场跨越数据库的冒险安装盛宴,挑战你的技术极限!"
【9月更文挑战第6天】在Linux环境下安装JDK 1.8、Tomcat和MariaDB是搭建Java Web应用的关键步骤。本文详细介绍了使用apt-get安装OpenJDK 1.8、下载并配置Tomcat,以及安装和安全设置MariaDB(MySQL的开源分支)的方法。通过这些步骤,您可以快速构建一个稳定、高效的开发和部署环境,并验证各组件是否正确安装和运行。这为您的Java Web应用提供了一个坚实的基础。
76 0
|
6月前
|
IDE Java 测试技术
Java零基础(4) - JDK、IntelliJ IDEA的安装和环境变量配置
【8月更文挑战第4天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
181 0
Java零基础(4) - JDK、IntelliJ IDEA的安装和环境变量配置
WXM
|
7月前
|
Oracle Java 关系型数据库
Java JDK下载安装及环境配置超详细图文教程
Java JDK下载安装及环境配置超详细图文教程
WXM
1854 3

热门文章

最新文章