引言
ConcurrentHashMap是线程安全并且高效的HashMap,在并发编程中经常可见它的使用,在开始分析它的高并发实现机制前,先讲讲废话,看看它是如何被引入jdk的。
为什么引入ConcurrentHashMap?
-
HashMap线程不安全,它的线程不安全主要发生在put等对HashEntry有直接写操作的地方:
从put操作的源码不难看出,线程不安全主要可能发生在这两个地方:-
key已经存在,需要修改HashEntry对应的value;
-
key不存在,在HashEntry中做插入。
-
-
Hashtable线程安全,但是效率低下:
从Hashtable示例的源码可以看出,Hashtable是用synchronized关键字来保证线程安全的,由于synchronized的机制是在同一时刻只能有一个线程操作,其他的线程阻塞或者轮询等待,在线程竞争激烈的情况下,这种方式的效率会非常的低下。注:小小的多嘴一句,Hashtable扩容的时候newSize = 2 * oldSize + 1,这个是常识性的点,但是由于整个jdk源码封装比较好,而且Hashtable效率低下,使用较少,貌似好多程序员都不太知道这一点。
ConcurrentHashMap的为什么高效?
Hashtable低效主要是因为所有访问Hashtable的线程都争夺一把锁。如果容器有很多把锁,每一把锁控制容器中的一部分数据,那么当多个线程访问容器里的不同部分的数据时,线程之前就不会存在锁的竞争,这样就可以有效的提高并发的访问效率。这也正是ConcurrentHashMap使用的分段锁技术。将ConcurrentHashMap容器的数据分段存储,每一段数据分配一个Segment(锁),当线程占用其中一个Segment时,其他线程可正常访问其他段数据。
ConcurrentHashMap实现分析
在分析ConcurrentHashMap的源码之前先来看看它的结构:
从类图可以看出:ConcurrentHashMap由Segment和HashEntry组成。
-
Segment是可重入锁,它在ConcurrentHashMap中扮演分离锁的角色;
-
HashEntry主要存储键值对;
-
CurrentHashMap包含一个Segment数组,每个Segment包含一个HashEntry数组并且守护它,当修改HashEntry数组数据时,需要先获取它对应的Segment锁;而HashEntry数组采用开链法处理冲突,所以它的每个HashEntry元素又是链表结构的元素。
由此可以得出ConcurrentHashMap的结构图如下:
初始化ConcurrentHashMap
可以看出,ConcurrentHashMap的构造方法都调用了public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
,初始化部分都由它来完成,我们来看一看它是怎么来初始化ConcurrentHashMap的。
ConcurrentHashMap初始化具体实现
整个初始化是通过参数initialCapacity,loadFactor和concurrencyLevel来初始化segmentShift(段偏移量)、segmentMask(段掩码)和segment数组。
-
计算segment数组长度
segment数组长度ssize是由concurrencyLevel计算得出,当ssize < concurrencyLevel时,ssize *= 2,至于为什么一定要保证ssize是2的N次方是为了可以通过按位与来定位segment;注:concurrencyLevel的最大值是65535,那么,ssize的最大值就为65536,对应到二进制就是16位。
-
初始化segmentShift、segmentMask
segmentShift和segmentMask在定位segment使用,segmentShift = 32 - ssize向左移位的次数,segmentMask = ssize - 1。ssize的最大长度是65536,对应的 segmentShift最大值为16,segmentMask最大值是65535,对应的二进制16位全1; -
初始化segment
- 初始化每个segment的HashEntry长度;
- 创建segment数组和segment[0]。
注:HashEntry长度cap同样也是2的N次方,默认情况,ssize = 16,initialCapacity = 16,loadFactor = 0.75f,那么cap = 1,threshold = (int) cap * loadFactor = 0。
Segment定位
-
Hash算法
ConcurrentHashMap使用分段锁segment来保护数据,也就是说,在插入和读取元素,需要先通过hash算法定位segment。ConcurrentHashMap使用了变种hash算法对元素的hashCode再散列。注:为什么需要再散列?
再散列的目的是为了减少冲突,让元素可以近似均匀的分布在不同的Segment上,从而提升存储效率。如果hash算法不好,最差的情况是所有的元素都在一个Segment中,这时候hash表将退化成链表,查询插入的时间复杂度都会从理想的o(1)退化成o(n^2),同时,分段锁也会失去存在的意义。 -
Segment定位
ConcurrentHashMap将hashCode进行位运算来定位具体的segment:
默认情况下,segmentShift = 28, segmentMask = 15,hashCode最大是32位的二进制数,向右无符号移动28位,让高4位参与位运算(& segmentMask)。
ConcurrentHashMap相关操作实现分析
主要分析ConcurrentHashMap常用的三个操作:get/put/size的具体实现。
-
get操作
- 根据key,计算出hashCode;
- 根据步骤1计算出的hashCode定位segment,如果segment不为null && segment.table也不为null,跳转到步骤3,否则,返回null,该key所对应的value不存在;
- 根据hashCode定位table中对应的hashEntry,遍历hashEntry,如果key存在,返回key对应的value;
- 步骤3结束仍未找到key所对应的value,返回null,该key锁对应的value不存在。
比起Hashtable,ConcurrentHashMap的get操作高效之处在于整个get操作不需要加锁。如果不加锁,ConcurrentHashMap的get操作是如何做到线程安全的呢?原因是volatile,所有的value都定义成了volatile类型,volatile可以保证线程之间的可见性,这也是用volatile替换锁的经典应用场景。
-
put操作
ConcurrentHashMap提供两个方法put和putIfAbsent来完成put操作,它们之间的区别在于put方法做插入时key存在会更新key所对应的value,而putIfAbsent不会更新。-
put实现
- 参数校验,value不能为null,为null时抛出NPE;
- 计算key的hashCode;
- 定位segment,如果segment不存在,创建新的segment;
- 调用segment的put方法在对应的segment做插入操作。
-
putIfAbsent实现
putIfAbsent的执行过程与put方法是一致的,除了最后调用的segment的put方法参数onlyIfAbsent传参不一样。
segment的put方法实现
segment的put方法是整个put操作的核心,它实现了在segment的HashEntry数组中做插入(segment的HashEntry数组采用开链法来处理冲突)。
具体的执行流程如下:- 获取锁,保证put操作的线程安全;
- 定位到HashEntry数组中具体的HashEntry;
- 遍历HashEntry链表,假若待插入key已存在:
- 需要更新key所对应value(!onlyIfAbsent),更新oldValue -> newValue,跳转到步骤5;
- 否则,直接跳转到步骤5;
- 遍历完HashEntry链表,key不存在,插入HashEntry节点,oldValue = null,跳转到步骤5;
- 释放锁,返回oldValue。
步骤4在做插入的时候实际上经历了两个步骤:
- 第一:HashEntry数组扩容;
- 是否需要扩容
在插入元素前会先判断Segment的HashEntry数组是否超过threshold,如果超过阀值,则需要对HashEntry数组扩容; - 如何扩容
在扩容的时候,首先创建一个容量是原来容量两倍的数组,将原数组的元素再散列后插入到新的数组里。为了高效,ConcurrentHashMap只对某个Segment进行扩容,不会对整个容器扩容。 - 第二:定位添加元素对应的位置,然后将其放到HashEntry数组中。
-
-
size实现
如果需要统计整个ConcurrentHashMap的容量,需要统计所有Segment容量然后求和,Segment提供全局volatile变量count用于存储当前Segment的容量。但是ConcurrentHashMap为了保证线程安全,并不是直接把所有的Segment的count相加来得到整个容器的大小,我们来看看ConcurrentHashMap是怎么来统计容量的。
由于在累加count的操作的过程中之前累加过的count发生变化的几率非常小,所以ConcurrentHashMap先尝试2次不锁住Segment的方式来统计每个Segment的大小,如果在统计的过程中Segment的count发生了变化,这时候再加锁统计Segment的count。ConcurrentHashMap如何判断统计过程中Segment的cout发生了变化?
Segment使用变量modCount来表示Segment大小是否发生变化,在put/remove/clean操作里都会将modCount加1,那么在统计size的前后只需要比较modCount是否发生了变化,如果发生变化,Segment的大小肯定发生了变化。
http://blog.csdn.net/u010185262/article/details/54614456
相关推荐
### Java并发编程之ConcurrentHashMap #### 一、概述 `ConcurrentHashMap`是Java并发编程中的一个重要组件,它提供了一种线程安全的哈希表实现方式。与传统的`Hashtable`或`synchronized`关键字相比,`...
ConcurrentHashMap为了提高本身的并发能力,在内部采用了一个叫做Segment的结构,一个Segment其实就是一个类HashTable的结构,Segment内部维护了一个链表数组,我们用下面这一幅图来看下ConcurrentHashMap的内部结构...
《Java并发编程实战》是Java并发编程领域的一本经典著作,它深入浅出地介绍了如何在Java平台上进行高效的多线程编程。这本书的源码提供了丰富的示例,可以帮助读者更好地理解书中的理论知识并将其应用到实际项目中。...
《Java并发编程实战》这本书是关于Java语言中并发编程技术的经典著作。它详细介绍了如何在Java环境中有效地实现多线程程序和并发控制机制。在Java平台上,由于其本身提供了强大的并发编程支持,因此,掌握并发编程...
并发集合是Java并发编程中的重要组成部分,如`ConcurrentHashMap`, `CopyOnWriteArrayList`, `ConcurrentLinkedQueue`等,它们设计为线程安全,能够在并发环境中高效地工作。书中的章节可能会详细解释这些集合的设计...
在Java并发编程中,多线程是核心概念之一。多线程允许程序同时执行多个任务,从而充分利用系统资源,提高程序性能。然而,多线程编程也带来了同步和竞态条件等问题,这需要开发者具备良好的线程管理和同步机制的知识...
Java并发编程是Java开发中的重要领域,特别是在多核处理器和分布式系统中,高效地利用并发可以极大地提升程序的性能和响应速度。以下是对标题和描述中所提及的几个知识点的详细解释: 1. **线程与并发** - **线程*...
《JAVA并发编程实践》这本书是Java开发者深入理解并发编程的重要参考资料。它涵盖了Java并发的核心概念、工具和最佳实践,旨在帮助读者在多线程环境下编写高效、安全的代码。 并发编程是现代软件开发中的关键技能,...
Java并发编程中的ConcurrentHashMap是HashMap的一个线程安全版本,设计目标是在高并发场景下提供高效的数据访问。相比HashTable,ConcurrentHashMap通过采用锁分离技术和更细粒度的锁定策略来提升性能。HashTable...
《Java并发编程实践》是一本深入探讨Java多线程编程的经典著作,由Brian Goetz、Tim Peierls、Joshua Bloch、Joseph Bowles和David Holmes等专家共同编写。这本书全面介绍了Java平台上的并发编程技术,是Java开发...
Java并发编程还包括对并发容器的使用,如ArrayList、LinkedList、HashSet、HashMap等基础容器在并发环境下可能存在问题,Java提供了一些线程安全的容器,如Vector、HashTable以及java.util.concurrent包下的...
《JAVA并发编程艺术》是Java开发者深入理解和掌握并发编程的一本重要著作,它涵盖了Java并发领域的核心概念和技术。这本书详细阐述了如何在多线程环境下有效地编写高效、可靠的代码,对于提升Java程序员的技能水平...
《Java并发编程从入门到精通》是一本专为Java开发者设计的深度学习并发编程的书籍。作者韩剑锋,凭借其12年的IT行业经验,曾担任多家IT公司的研发总监和技术总监,以其丰富的实战经验和深厚的理论知识,为读者提供了...
《Java 并发编程实战》是一本专注于Java并发编程的权威指南,对于任何希望深入了解Java多线程和并发控制机制的开发者来说,都是不可或缺的参考资料。这本书深入浅出地介绍了如何在Java环境中有效地管理和控制并发...
Java并发编程是软件开发中的一个关键领域,尤其是在大型企业级应用和分布式系统中。通过学习相关的书籍,开发者可以深入理解如何有效地设计和实现高效的多线程应用程序,避免并发问题,如竞态条件、死锁、活锁等。...
Java并发编程实践是Java开发中不可或缺的一个领域,它涉及到如何高效、正确地处理多线程环境中的任务。这本书的读书笔记涵盖了多个关键知识点,旨在帮助读者深入理解Java并发编程的核心概念。 1. **线程和进程的...
"Java并发编程与实践"文档深入剖析了这一主题,旨在帮助开发者理解和掌握如何在Java环境中有效地实现并发。 并发是指在单个执行单元(如CPU)中同时执行两个或更多任务的能力。在Java中,这主要通过线程来实现,...