集合是编程中最常用的数据结构

2019-11-06 09:23:18

字体：大中小

来源：转载

供稿：网友

集合是编程中最常用的数据结构。而谈到并发，几乎总是离不开集合这类高级数据结构的支持。比如两个线程需要同时访问一个中间临界区（Queue），比如常会用缓存作为外部文件的副本（HashMap）。这篇文章主要分析jdk1.5的3种并发集合类型（concurrent，copyonright，queue）中的ConcurrentHashMap，让我们从原理上细致的了解它们，能够让我们在深度项目开发中获益非浅。

通过分析Hashtable就知道，synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的hash table，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”是很重要的，否则极有可能出现死锁，在ConcurrentHashMap内部，段数组是final的，并且其成员变量实际上也是final的，但是，仅仅是将数组声明为final的并不保证数组成员也是final的，这需要实现上的保证。这可以确保不会出现死锁，因为获得锁的顺序是固定的。

一、结构解析

ConcurrentHashMap和Hashtable主要区别就是围绕着锁的粒度以及如何锁,可以简单理解成把一个大的HashTable分解成多个，形成了锁分离。如图:

而Hashtable的实现方式是---锁整个hash表

二、应用场景

当有一个大数组时需要在多个线程共享时就可以考虑是否把它给分层多个节点了，避免大锁。并可以考虑通过hash算法进行一些模块定位。

其实不止用于线程，当设计数据表的事务时（事务某种意义上也是同步机制的体现），可以把一个表看成一个需要同步的数组，如果操作的表数据太多时就可以考虑事务分离了（这也是为什么要避免大表的出现），比如把数据进行字段拆分，水平分表等.

三、源码解读

ConcurrentHashMap中主要实体类就是三个：ConcurrentHashMap（整个Hash表）,Segment（桶），HashEntry（节点），对应上面的图可以看出之间的关系

/** * The segments, each of which is a specialized hash table */  final Segment<K,V>[] segments; 不变(Immutable)和易变(Volatile)ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。如果使用传统的技术，如HashMap中的实现，如果允许可以在hash链的中间添加或删除元素，读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。HashEntry代表每个hash链中的一个节点，其结构如下所示：
 
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，这避免了加锁。其它为了加快定位段以及段中hash槽的速度，每个段hash槽的的个数都是2^n，这使得通过位运算就可以定位段和段中hash槽的位置。当并发级别为默认值16时，也就是段的个数，hash值的高4位决定分配在哪个段中。但是我们也不要忘记《算法导论》给我们的教训：hash槽的的个数不应该是 2^n，这可能导致hash槽分配不均，这需要对hash值重新再hash一次。（这段似乎有点多余了 ）
 
这是定位段的方法：
1. final Segment<K,V> segmentFor(int hash) {  2.     return segments[(hash >>> segmentShift) & segmentMask];  3. } 数据结构关于Hash表的基础数据结构，这里不想做过多的探讨。Hash表的一个很重要方面就是如何解决hash冲突，ConcurrentHashMap 和HashMap使用相同的方式，都是将hash值相同的节点放在一个hash链中。与HashMap不同的是，ConcurrentHashMap使用多个子Hash表，也就是段(Segment)。下面是ConcurrentHashMap的数据成员：
 
1. public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>  2.         implements ConcurrentMap<K, V>, Serializable {  3.     /** 4.      * Mask value for indexing into segments. The upper bits of a 5.      * key's hash code are used to choose the segment. 6.      */  7.     final int segmentMask;  8.   9.     /** 10.      * Shift value for indexing within segments. 11.      */  12.     final int segmentShift;  13.   14.     /** 15.      * The segments, each of which is a specialized hash table 16.      */  17.     final Segment<K,V>[] segments;  18. }  
所有的成员都是final的，其中segmentMask和segmentShift主要是为了定位段，参见上面的segmentFor方法。每个Segment相当于一个子Hash表，它的数据成员如下：
 
1.     static final class Segment<K,V> extends ReentrantLock implements Serializable {  2. PRivate static final long serialVersionUID = 2249069246763182397L;  3.         /** 4.          * The number of elements in this segment's region. 5.          */  6.         transient volatile int count;  7.   8.         /** 9.          * Number of updates that alter the size of the table. This is 10.          * used during bulk-read methods to make sure they see a 11.          * consistent snapshot: If modCounts change during a traversal 12.          * of segments computing size or checking containsValue, then 13.          * we might have an inconsistent view of state so (usually) 14.          * must retry. 15.          */  16.         transient int modCount;  17.   18.         /** 19.          * The table is rehashed when its size exceeds this threshold. 20.          * (The value of this field is always <tt>(int)(capacity * 21.          * loadFactor)</tt>.) 22.          */  23.         transient int threshold;  24.   25.         /** 26.          * The per-segment table. 27.          */  28.         transient volatile HashEntry<K,V>[] table;  29.   http://www.kuaimin.cn/zonghe/20170227/293598.html
http://www.kuaimin.cn/zonghe/20170227/293597.html
http://www.kuaimin.cn/zonghe/20170227/293590.html
30.         /** 31.          * The load factor for the hash table.  Even though this value 32.          * is same for all segments, it is replicated to avoid needing 33.          * links to outer object. 34.          * @serial 35.          */  36.         final float loadFactor;  37. }  
count用来统计该段数据的个数，它是volatile(volatile 变量使用指南)，它用来协调修改和读取操作，以保证读取操作能够读取到几乎最新的修改。协调方式是这样的，每次修改操作做了结构上的改变，如增加/删除节点(修改节点的值不算结构上的改变)，都要写count值，每次读取操作开始都要读取count的值。这利用了 java 5中对volatile语义的增强，对同一个volatile变量的写和读存在happens-before关系。modCount统计段结构改变的次数，主要是为了检测对多个段进行遍历过程中某个段是否发生改变，在讲述跨段操作时会还会详述。threashold用来表示需要进行rehash的界限值。table数组存储段中节点，每个数组元素是个hash链，用HashEntry表示。table也是volatile，这使得能够读取到最新的 table值而不需要同步。loadFactor表示负载因子。