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;
}
目录
相关文章
|
20天前
|
人工智能 自然语言处理 Java
FastExcel:开源的 JAVA 解析 Excel 工具,集成 AI 通过自然语言处理 Excel 文件,完全兼容 EasyExcel
FastExcel 是一款基于 Java 的高性能 Excel 处理工具,专注于优化大规模数据处理,提供简洁易用的 API 和流式操作能力,支持从 EasyExcel 无缝迁移。
96 9
FastExcel:开源的 JAVA 解析 Excel 工具,集成 AI 通过自然语言处理 Excel 文件,完全兼容 EasyExcel
|
1天前
|
存储 Java 计算机视觉
Java二维数组的使用技巧与实例解析
本文详细介绍了Java中二维数组的使用方法
24 15
|
1天前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
23 6
|
7天前
|
SQL Java 数据库连接
如何在 Java 代码中使用 JSqlParser 解析复杂的 SQL 语句?
大家好,我是 V 哥。JSqlParser 是一个用于解析 SQL 语句的 Java 库,可将 SQL 解析为 Java 对象树,支持多种 SQL 类型(如 `SELECT`、`INSERT` 等)。它适用于 SQL 分析、修改、生成和验证等场景。通过 Maven 或 Gradle 安装后,可以方便地在 Java 代码中使用。
98 11
|
1天前
|
存储 算法 搜索推荐
【潜意识Java】期末考试可能考的高质量大题及答案解析
Java 期末考试大题整理:设计一个学生信息管理系统,涵盖面向对象编程、集合类、文件操作、异常处理和多线程等知识点。系统功能包括添加、查询、删除、显示所有学生信息、按成绩排序及文件存储。通过本题,考生可以巩固 Java 基础知识并掌握综合应用技能。代码解析详细,适合复习备考。
10 4
|
1天前
|
存储 Java
【潜意识Java】期末考试可能考的选择题(附带答案解析)
本文整理了 Java 期末考试中常见的选择题,涵盖数据类型、控制结构、面向对象编程、集合框架、异常处理、方法、流程控制和字符串等知识点。每道题目附有详细解析,帮助考生巩固基础,加深理解。通过这些练习,考生可以更好地准备考试,掌握 Java 的核心概念和语法。
|
6天前
|
存储 分布式计算 Hadoop
基于Java的Hadoop文件处理系统:高效分布式数据解析与存储
本文介绍了如何借鉴Hadoop的设计思想,使用Java实现其核心功能MapReduce,解决海量数据处理问题。通过类比图书馆管理系统,详细解释了Hadoop的两大组件:HDFS(分布式文件系统)和MapReduce(分布式计算模型)。具体实现了单词统计任务,并扩展支持CSV和JSON格式的数据解析。为了提升性能,引入了Combiner减少中间数据传输,以及自定义Partitioner解决数据倾斜问题。最后总结了Hadoop在大数据处理中的重要性,鼓励Java开发者学习Hadoop以拓展技术边界。
30 7
|
1天前
|
Java 编译器 程序员
【潜意识Java】期末考试可能考的简答题及答案解析
为了帮助同学们更好地准备 Java 期末考试,本文列举了一些常见的简答题,并附上详细的答案解析。内容包括类与对象的区别、多态的实现、异常处理、接口与抽象类的区别以及垃圾回收机制。通过这些题目,同学们可以深入理解 Java 的核心概念,从而在考试中更加得心应手。每道题都配有代码示例和详细解释,帮助大家巩固知识点。希望这些内容能助力大家顺利通过考试!
|
25天前
|
Java 数据库连接 Spring
反射-----浅解析(Java)
在java中,我们可以通过反射机制,知道任何一个类的成员变量(成员属性)和成员方法,也可以堆任何一个对象,调用这个对象的任何属性和方法,更进一步我们还可以修改部分信息和。
|
3天前
|
自然语言处理 数据处理 索引
mindspeed-llm源码解析(一)preprocess_data
mindspeed-llm是昇腾模型套件代码仓,原来叫"modelLink"。这篇文章带大家阅读一下数据处理脚本preprocess_data.py(基于1.0.0分支),数据处理是模型训练的第一步,经常会用到。
12 0

热门文章

最新文章

推荐镜像

更多