`

Java多线程(三)之ConcurrentHashMap深入分析

 
阅读更多

一、Map体系


  1. Hashtable是JDK 5之前Map唯一线程安全的内置实现(Collections.synchronizedMap不算)。Hashtable继承的是Dictionary(Hashtable是其唯一公开的子类),并不继承AbstractMap或者HashMap。尽管Hashtable和HashMap的结构非常类似,但是他们之间并没有多大联系。
  2. ConcurrentHashMap是HashMap的线程安全版本,ConcurrentSkipListMap是TreeMap的线程安全版本。
  3. 最终可用的线程安全版本Map实现是ConcurrentHashMap/ConcurrentSkipListMap/Hashtable/Properties四个,但是Hashtable是过时的类库,因此如果可以的应该尽可能的使用ConcurrentHashMap和ConcurrentSkipListMap。

二、concurrentHashMap的结构

 

我们通过ConcurrentHashMap的类图来分析ConcurrentHashMap的结构。


ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock,在ConcurrentHashMap里扮演锁的角色,HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组,Segment的结构和HashMap类似,是一种数组和链表结构, 一个Segment里包含一个HashEntry数组,每个HashEntry是一个链表结构的元素, 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时,必须首先获得它对应的Segment锁。


ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对;Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。
 

三、ConcurrentHashMap实现原理 

 

锁分离 (Lock Stripping)

 

比如HashTable是一个过时的容器类,通过使用synchronized来保证线程安全,在线程竞争激烈的情况下HashTable的效率非常低下。原因是所有访问HashTable的线程都必须竞争同一把锁。那假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术。

 

ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分,每个段其实就是一个小的hash table,它们有自己的锁。只要多个修改操作发生在不同的段上,它们就可以并发进行。同样当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

 

ConcurrentHashMap有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁。这里“按顺序”是很重要的,否则极有可能出现死锁,在ConcurrentHashMap内部,段数组是final的,并且其成员变量实际上也是final的,但是,仅仅是将数组声明为final的并不保证数组成员也是final的,这需要实现上的保证。这可以确保不会出现死锁,因为获得锁的顺序是固定的。不变性是多线程编程占有很重要的地位,下面还要谈到。

 

[java] view plaincopy
 
  1. /**  
  2.  * The segments, each of which is a specialized hash table  
  3.  */    
  4. final Segment<K,V>[] segments;    

 

 

 不变(Immutable)和易变(Volatile)

 

ConcurrentHashMap完全允许多个读操作并发进行,读操作并不需要加锁。如果使用传统的技术,如HashMap中的实现,如果允许可以在hash链的中间添加或删除元素,读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。HashEntry代表每个hash链中的一个节点,其结构如下所示:

 

 

[java] view plaincopy
 
  1. static final class HashEntry<K,V> {    
  2.     final K key;    
  3.     final int hash;    
  4.     volatile V value;    
  5.     final HashEntry<K,V> next;    
  6. }  


  

 

可以看到除了value不是final的,其它值都是final的,这意味着不能从hash链的中间或尾部添加或删除节点,因为这需要修改next引用值,所有的节点的修改只能从头部开始。对于put操作,可以一律添加到Hash链的头部。但是对于remove操作,可能需要从中间删除一个节点,这就需要将要删除节点的前面所有节点整个复制一遍,最后一个节点指向要删除结点的下一个结点。这在讲解删除操作时还会详述。为了确保读操作能够看到最新的值,将value设置成volatile,这避免了加锁。

 

四、ConcurrentHashMap具体实现

ConcurrentHashMap的初始化

 

ConcurrentHashMap初始化方法是通过initialCapacity,loadFactor, concurrencyLevel几个参数来初始化segments数组,段偏移量segmentShift,段掩码segmentMask和每个segment里的HashEntry数组 。

初始化segments数组。让我们来看一下初始化segmentShift,segmentMask和segments数组的源代码。

 

[java] view plaincopy
 
  1. if (concurrencyLevel > MAX_SEGMENTS)  
  2.     concurrencyLevel = MAX_SEGMENTS;  
  3.   
  4. // Find power-of-two sizes best matching arguments  
  5. int sshift = 0;  
  6. int ssize = 1;  
  7. while (ssize < concurrencyLevel) {  
  8.     ++sshift;  
  9.     ssize <<= 1;  
  10. }  
  11. segmentShift = 32 - sshift;  
  12. segmentMask = ssize - 1;  
  13. this.segments = Segment.newArray(ssize);  


 

由上面的代码可知segments数组的长度ssize通过concurrencyLevel计算得出。为了能通过按位与的哈希算法来定位segments数组的索引,必须保证segments数组的长度是2的N次方(power-of-two size),所以必须计算出一个是大于或等于concurrencyLevel的最小的2的N次方值来作为segments数组的长度。假如concurrencyLevel等于14,15或16,ssize都会等于16,即容器里锁的个数也是16。注意concurrencyLevel的最大大小是65535,意味着segments数组的长度最大为65536,对应的二进制是16位。

 

初始化segmentShift和segmentMask。这两个全局变量在定位segment时的哈希算法里需要使用,sshift等于ssize从1向左移位的次数,在默认情况下concurrencyLevel等于16,1需要向左移位移动4次,所以sshift等于4。segmentShift用于定位参与hash运算的位数,segmentShift等于32减sshift,所以等于28,这里之所以用32是因为ConcurrentHashMap里的hash()方法输出的最大数是32位的,后面的测试中我们可以看到这点。segmentMask是哈希运算的掩码,等于ssize减1,即15,掩码的二进制各个位的值都是1。因为ssize的最大长度是65536,所以segmentShift最大值是16,segmentMask最大值是65535,对应的二进制是16位,每个位都是1。

初始化每个Segment。输入参数initialCapacity是ConcurrentHashMap的初始化容量,loadfactor是每个segment的负载因子,在构造方法里需要通过这两个参数来初始化数组中的每个segment。

 

上面代码中的变量cap就是segment里HashEntry数组的长度,它等于initialCapacity除以ssize的倍数c,如果c大于1,就会取大于等于c的2的N次方值,所以cap不是1,就是2的N次方。segment的容量threshold=(int)cap*loadFactor,默认情况下initialCapacity等于16,loadfactor等于0.75,通过运算cap等于1,threshold等于零。

 

[java] view plaincopy
 
  1. if (initialCapacity > MAXIMUM_CAPACITY)  
  2.     initialCapacity = MAXIMUM_CAPACITY;  
  3. int c = initialCapacity / ssize;  
  4. if (c * ssize < initialCapacity)  
  5.     ++c;  
  6. int cap = 1;  
  7. while (cap < c)  
  8.     cap <<= 1;  
  9. for (int i = 0; i < this.segments.length; ++i)  
  10.     this.segments[i] = new Segment<K,V>(cap, loadFactor);  

 

定位Segment

 

既然ConcurrentHashMap使用分段锁Segment来保护不同段的数据,那么在插入和获取元素的时候,必须先通过哈希算法定位到Segment。可以看到ConcurrentHashMap会首先使用Wang/Jenkins hash的变种算法对元素的hashCode进行一次再哈希。

 

[java] view plaincopy
 
  1. private static int hash(int h) {  
  2.         h += (h << 15) ^ 0xffffcd7d;  
  3.         h ^= (h >>> 10);  
  4.         h += (h << 3);  
  5.         h ^= (h >>> 6);  
  6.         h += (h << 2) + (h << 14);  
  7.         return h ^ (h >>> 16);  
  8.     }  


 

之所以进行再哈希,其目的是为了减少哈希冲突,使元素能够均匀的分布在不同的Segment上,从而提高容器的存取效率。假如哈希的质量差到极点,那么所有的元素都在一个Segment中,不仅存取元素缓慢,分段锁也会失去意义。我做了一个测试,不通过再哈希而直接执行哈希计算。

 

[java] view plaincopy
 
  1. System.out.println(Integer.parseInt("0001111"2) & 15);  
  2. System.out.println(Integer.parseInt("0011111"2) & 15);  
  3. System.out.println(Integer.parseInt("0111111"2) & 15);  
  4. System.out.println(Integer.parseInt("1111111"2) & 15);  

 

计算后输出的哈希值全是15,通过这个例子可以发现如果不进行再哈希,哈希冲突会非常严重,因为只要低位一样,无论高位是什么数,其哈希值总是一样。我们再把上面的二进制数据进行再哈希后结果如下,为了方便阅读,不足32位的高位补了0,每隔四位用竖线分割下。

 

[java] view plaincopy
 
  1. 01000111011001111101101001001110  
  2. 11110111010000110000000110111000  
  3. 01110111011010010100011000111110  
  4. 10000011000000001100100000011010  

 

可以发现每一位的数据都散列开了,通过这种再哈希能让数字的每一位都能参加到哈希运算当中,从而减少哈希冲突。ConcurrentHashMap通过以下哈希算法定位segment。

 

[java] view plaincopy
 
  1. final Segment<K,V> segmentFor(int hash) {  
  2.         return segments[(hash >>> segmentShift) & segmentMask];  
  3.     }  

 

默认情况下segmentShift为28,segmentMask为15,再哈希后的数最大是32位二进制数据,向右无符号移动28位,意思是让高4位参与到hash运算中, (hash >>> segmentShift) & segmentMask的运算结果分别是4,15,7和8,可以看到hash值没有发生冲突。


ConcurrentHashMap的get操作

 

前面提到过ConcurrentHashMap的get操作是不用加锁的,我们这里看一下其实现:

[java] view plaincopy
 
  1. public V get(Object key) {  
  2.     int hash = hash(key.hashCode());  
  3.     return segmentFor(hash).get(key, hash);  
  4. }  

看第三行,segmentFor这个函数用于确定操作应该在哪一个segment中进行,几乎对ConcurrentHashMap的所有操作都需要用到这个函数,我们看下这个函数的实现:

[java] view plaincopy
 
  1. final Segment<K,V> segmentFor(int hash) {  
  2.     return segments[(hash >>> segmentShift) & segmentMask];  
  3. }  

这个函数用了位操作来确定Segment,根据传入的hash值向右无符号右移segmentShift位,然后和segmentMask进行与操作,结合我们之前说的segmentShift和segmentMask的值,就可以得出以下结论:假设Segment的数量是2的n次方,根据元素的hash值的高n位就可以确定元素到底在哪一个Segment中。

在确定了需要在哪一个segment中进行操作以后,接下来的事情就是调用对应的Segment的get方法:

[java] view plaincopy
 
  1. V get(Object key, int hash) {  
  2.     if (count != 0) { // read-volatile  
  3.         HashEntry<K,V> e = getFirst(hash);  
  4.         while (e != null) {  
  5.             if (e.hash == hash && key.equals(e.key)) {  
  6.                 V v = e.value;  
  7.                 if (v != null)  
  8.                     return v;  
  9.                 return readValueUnderLock(e); // recheck  
  10.             }  
  11.             e = e.next;  
  12.         }  
  13.     }  
  14.     return null;  
  15. }  


先看第二行代码,这里对count进行了一次判断,其中count表示Segment中元素的数量,我们可以来看一下count的定义:


[java] view plaincopy
 
  1. transient volatile int count;  

可以看到count是volatile的,实际上这里里面利用了volatile的语义:

 

对volatile字段的写入操作happens-before于每一个后续的同一个字段的读操作。

 

因为实际上put、remove等操作也会更新count的值,所以当竞争发生的时候,volatile的语义可以保证写操作在读操作之前,也就保证了写操作对后续的读操作都是可见的,这样后面get的后续操作就可以拿到完整的元素内容。

然后,在第三行,调用了getFirst()来取得链表的头部:

[java] view plaincopy
 
  1. HashEntry<K,V> getFirst(int hash) {  
  2.     HashEntry<K,V>[] tab = table;  
  3.     return tab[hash & (tab.length - 1)];  
  4. }  

同样,这里也是用位操作来确定链表的头部,hash值和HashTable的长度减一做与操作,最后的结果就是hash值的低n位,其中n是HashTable的长度以2为底的结果。

在确定了链表的头部以后,就可以对整个链表进行遍历,看第4行,取出key对应的value的值,如果拿出的value的值是null,则可能这个key,value对正在put的过程中,如果出现这种情况,那么就加锁来保证取出的value是完整的,如果不是null,则直接返回value。

 

ConcurrentHashMap的put操作

 

看完了get操作,再看下put操作,put操作的前面也是确定Segment的过程,这里不再赘述,直接看关键的segment的put方法:


[java] view plaincopy
 
  1. V put(K key, int hash, V value, boolean onlyIfAbsent) {  
  2.     lock();  
  3.     try {  
  4.         int c = count;  
  5.         if (c++ > threshold) // ensure capacity  
  6.             rehash();  
  7.         HashEntry<K,V>[] tab = table;  
  8.         int index = hash & (tab.length - 1);  
  9.         HashEntry<K,V> first = tab[index];  
  10.         HashEntry<K,V> e = first;  
  11.         while (e != null && (e.hash != hash || !key.equals(e.key)))  
  12.             e = e.next;  
  13.    
  14.         V oldValue;  
  15.         if (e != null) {  
  16.             oldValue = e.value;  
  17.             if (!onlyIfAbsent)  
  18.                 e.value = value;  
  19.         }  
  20.         else {  
  21.             oldValue = null;  
  22.             ++modCount;  
  23.             tab[index] = new HashEntry<K,V>(key, hash, first, value);  
  24.             count = c; // write-volatile  
  25.         }  
  26.         return oldValue;  
  27.     } finally {  
  28.         unlock();  
  29.     }  
  30. }  

首先对Segment的put操作是加锁完成的,然后在第五行,如果Segment中元素的数量超过了阈值(由构造函数中的loadFactor算出)这需要进行对Segment扩容,并且要进行rehash,关于rehash的过程大家可以自己去了解,这里不详细讲了。

第8和第9行的操作就是getFirst的过程,确定链表头部的位置。

第11行这里的这个while循环是在链表中寻找和要put的元素相同key的元素,如果找到,就直接更新更新key的value,如果没有找到,则进入21行这里,生成一个新的HashEntry并且把它加到整个Segment的头部,然后再更新count的值。


ConcurrentHashMap的remove操作

 

Remove操作的前面一部分和前面的get和put操作一样,都是定位Segment的过程,然后再调用Segment的remove方法:


[java] view plaincopy
 
  1. V remove(Object key, int hash, Object value) {  
  2.     lock();  
  3.     try {  
  4.         int c = count - 1;  
  5.         HashEntry<K,V>[] tab = table;  
  6.         int index = hash & (tab.length - 1);  
  7.         HashEntry<K,V> first = tab[index];  
  8.         HashEntry<K,V> e = first;  
  9.         while (e != null && (e.hash != hash || !key.equals(e.key)))  
  10.             e = e.next;  
  11.    
  12.         V oldValue = null;  
  13.         if (e != null) {  
  14.             V v = e.value;  
  15.             if (value == null || value.equals(v)) {  
  16.                 oldValue = v;  
  17.                 // All entries following removed node can stay  
  18.                 // in list, but all preceding ones need to be  
  19.                 // cloned.  
  20.                 ++modCount;  
  21.                 HashEntry<K,V> newFirst = e.next;  
  22.                 for (HashEntry<K,V> p = first; p != e; p = p.next)  
  23.                     newFirst = new HashEntry<K,V>(p.key, p.hash,  
  24.                                                   newFirst, p.value);  
  25.                 tab[index] = newFirst;  
  26.                 count = c; // write-volatile  
  27.             }  
  28.         }  
  29.         return oldValue;  
  30.     } finally {  
  31.         unlock();  
  32.     }  
  33. }  

首先remove操作也是确定需要删除的元素的位置,不过这里删除元素的方法不是简单地把待删除元素的前面的一个元素的next指向后面一个就完事了,我们之前已经说过HashEntry中的next是final的,一经赋值以后就不可修改,在定位到待删除元素的位置以后,程序就将待删除元素前面的那一些元素全部复制一遍,然后再一个一个重新接到链表上去,看一下下面这一幅图来了解这个过程:

假设链表中原来的元素如上图所示,现在要删除元素3,那么删除元素3以后的链表就如下图所示:

 

ConcurrentHashMap的size操作

 

在前面的章节中,我们涉及到的操作都是在单个Segment中进行的,但是ConcurrentHashMap有一些操作是在多个Segment中进行,比如size操作,ConcurrentHashMap的size操作也采用了一种比较巧的方式,来尽量避免对所有的Segment都加锁。

前面我们提到了一个Segment中的有一个modCount变量,代表的是对Segment中元素的数量造成影响的操作的次数,这个值只增不减,size操作就是遍历了两次Segment,每次记录Segment的modCount值,然后将两次的modCount进行比较,如果相同,则表示期间没有发生过写入操作,就将原先遍历的结果返回,如果不相同,则把这个过程再重复做一次,如果再不相同,则就需要将所有的Segment都锁住,然后一个一个遍历了,具体的实现大家可以看ConcurrentHashMap的源码,这里就不贴了。

分享到:
评论

相关推荐

    java 多线程编程实战指南(核心 + 设计模式 完整版)

    《Java多线程编程实战指南》这本书深入浅出地讲解了Java多线程的核心概念和实战技巧,分为核心篇和设计模式篇,旨在帮助开发者掌握并应用多线程技术。 1. **线程基础** - **线程的创建**:Java提供了两种创建线程...

    java多线程并发实战和源码

    Java多线程并发实战与源码分析是Java开发中至关重要的一部分,它涉及到程序性能优化、系统资源高效利用以及复杂逻辑的正确同步。本书主要聚焦于Java多线程的基础理论和实际应用,虽然书中实例和源码相对较少,但仍然...

    JAVA多线程教材

    10. **实战案例分析**:通过分析和解决实际问题,如Web服务器的并发处理、数据库连接池管理等,可以更好地理解和应用Java多线程技术。 以上只是《JAVA多线程教材》可能涵盖的部分内容,实际教材可能会更深入地讨论...

    Java多线程聊天

    Java多线程聊天程序是一种利用Java编程语言实现的并发通信应用,它允许多个用户在同一时间进行交互式的对话。在这个程序中,多线程技术被用来处理并发用户输入和消息传递,确保系统的高效运行和响应性。下面将详细...

    Java多线程聊天室源码

    Java多线程聊天室源码是一个实用的编程示例,它展示了如何在Java环境中实现一个基本的多用户交互系统。这个源代码对于初学者来说是一个很好的学习资源,可以帮助他们理解和应用Java的多线程概念。下面我们将深入探讨...

    java多线程控制的赛跑程序

    在Java编程语言中,多线程是实现并发执行任务的关键技术。这个“java多线程控制的赛跑程序”是一个示例,展示了如何利用多线程来模拟一场赛跑...通过深入研究和分析,你可以进一步提升自己在Java多线程编程方面的技能。

    Java多线程矩阵相乘的代码

    在Java编程语言中,多线程是实现并发执行任务的关键技术。这个压缩包中的内容,"Java多线程矩阵...通过对代码的阅读和分析,我们可以深入理解Java多线程在解决实际问题中的应用,同时也能掌握矩阵运算的并行化策略。

    Java多线程设计模式源代码

    Java多线程设计模式是Java编程中至关重要的一个领域,它涉及到如何在并发环境中高效、稳定地执行多个任务。...通过学习和分析这些源码,开发者能够更好地理解和掌握Java多线程编程,提升并发编程的能力。

    Java系列深入解析Java多线程

    本文将深入探讨Java多线程的各个方面,包括基础知识、创建线程、线程同步与通信、死锁问题以及线程池。 1. **基础知识** - **线程与进程**:线程是操作系统分配CPU时间的基本单位,而进程是系统中运行的程序实例。...

    java多线程基础资料

    Java多线程是Java编程中的一个...以上只是Java多线程基础知识的一部分,深入学习还包括线程池的配置与优化、线程安全的设计模式、并发工具类的使用等。理解和掌握这些知识点对于编写高效、稳定的多线程程序至关重要。

    Java多线程编程全部源码

    Java多线程编程是Java开发中的重要组成部分,它允许程序同时执行多个任务,提升系统效率。这个资源包含的"SimpleThread"源码很可能是对...通过学习和分析这个源码,你可以深入理解Java多线程编程的核心概念和实践技巧。

    深入Java多线程和并发编程

    ### 深入Java多线程与并发编程 在当今高度发展的信息技术领域中,随着硬件技术的进步和软件架构设计的复杂化,多线程与并发编程成为提高程序执行效率、增强系统性能的关键技术之一。本篇文章将围绕Java多线程与并发...

    Java多线程优化百万级数据

    本篇将深入探讨如何利用Java多线程技术来优化这种高负载场景。 首先,理解Java多线程的基础至关重要。在Java中,线程是程序执行的最小单元,可以通过实现`Runnable`接口或继承`Thread`类来创建线程。创建多线程的...

    JAVA线程第三版

    5. **并发集合**:Java提供了并发安全的集合框架,如ConcurrentHashMap、CopyOnWriteArrayList等,它们在多线程环境下能保证数据一致性。 6. **原子变量**:Atomic类提供了一组原子操作,如incrementAndGet(),在多...

    多线程面试题

    在Java编程领域,多线程是面试中常见且重要的知识点,尤其对于系统设计和高并发处理的岗位至关重要。本文将围绕“多线程面试题”这一主题,深入探讨相关概念、技术及其应用。 1. **线程的概念**:线程是程序执行的...

    Java线程-第三版(CHM电子版)

    《Java线程——第三版》是一本专注于Java多线程编程的专业书籍,旨在帮助开发者深入理解和熟练掌握Java中的并发处理技术。多线程是现代软件开发中的重要概念,尤其是在服务器端应用、分布式系统以及高性能计算等领域...

    Java多线程面试题

    以上知识点是Java多线程面试中常见的主题,掌握它们有助于深入理解Java并发编程,并在实际项目中编写高效、稳定的多线程代码。在准备面试时,不仅要理解这些概念,还要通过实践来加深理解,例如编写并发程序,分析和...

    java多线程设计模式

    本文将深入探讨Java多线程的核心概念、开发模式以及如何优化程序的运行效率。 首先,我们了解多线程的基础。Java提供了两种方式创建线程:通过继承`Thread`类或实现`Runnable`接口。当创建一个新的线程时,通常会...

    Java多线程应用练习源代码及相关说明资料

    这个压缩包包含的"Java多线程应用练习源代码及相关说明资料"是一份宝贵的资源,旨在帮助学习者深入理解并实践Java的并发编程。 1. **Java多线程基础** - **线程的概念**:线程是程序执行的最小单位,一个进程可以...

    JAVA多线程设计模式 书和源码

    本书“JAVA多线程设计模式”深入探讨了如何在Java环境中有效地利用多线程,结合源码分析,为开发者提供了宝贵的实践经验。 一、线程基础 Java中的线程是程序执行的最小单元,由Java虚拟机(JVM)管理。通过`Thread`...

Global site tag (gtag.js) - Google Analytics