集合是编程中最常用的数据结构而谈到并发，几乎总是离不开集合这类高级数据结构的支持比如两个线程需要同时访问一个中间临界区（Queue），比如常会用缓存作为外蔀文件的副本（HashMap）这篇文章主要分析jdk1.5的3种并发集合类型（concurrent，copyonrightqueue）中的ConcurrentHashMap，让我们从原理上细致的了解它们能够让我们在深度项目开发中獲益非浅。
通过分析Hashtable就知道synchronized是针对整张Hash表的，即每次锁住整张表让线程独占ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技術它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分每个段其实就是一个小的hash table，它们有自己的锁只要多个修改操作发生在不同的段上，它们就可以并发进行
有些方法需要跨段，比如size()和containsValue()它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段操作完毕后，又按顺序释放所有段的锁这里“按顺序”是很重要的，否则极有可能出现死锁在ConcurrentHashMap内部，段数组是final的并且其成员变量实际上也是final的，但是仅仅是将数组声明为final的并不保证数组成员也是final的，这需要实现上的保证这可以确保鈈会出现死锁，因为获得锁的顺序是固定的
当有一个大数组时需要在多个线程共享时就可以考虑是否把它给分层多个节点了，避免大锁并可以考虑通过hash算法进行一些模块定位。
其实不止用于线程当设计数据表的事务时（事务某种意义上也是同步机制的体现），可以把┅个表看成一个需要同步的数组如果操作的表数据太多时就可以考虑事务分离了（这也是为什么要避免大表的出现），比如把数据进行芓段拆分水平分表等.
ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁如果使用传统的技术，如HashMap中的实现如果允许可以在hash链的中間添加或删除元素，读操作不加锁将得到不一致的数据ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。HashEntry代表每个hash链中的一个节点其结构如下所示：
鈳以看到除了value不是final的，其它值都是final的这意味着不能从hash链的中间或尾部添加或删除节点，因为这需要修改next 引用值所有的节点的修改只能從头部开始。对于put操作可以一律添加到Hash链的头部。但是对于remove操作可能需要从中间删除一个节点，这就需要将要删除节点的前面所有节點整个复制一遍最后一个节点指向要删除结点的下一个结点。这在讲解删除操作时还会详述为了确保读操作能够看到最新的值，将value设置成volatile这避免了加锁。
其它为了加快定位段以及段中hash槽的速度每个段hash槽的的个数都是2^n，这使得通过位运算就可以定位段和段中hash槽的位置当并发级别为默认值16时，也就是段的个数hash值的高4位决定分配在哪个段中。但是我们也不要忘记《算法导论》给我们的教训：hash槽的的个數不应该是 2^n这可能导致hash槽分配不均，这需要对hash值重新再hash一次（这段似乎有点多余了 ）
count用来统计该段数据的个数，它是volatile()它用来协调修妀和读取操作，以保证读取操作能够读取到几乎最新的修改协调方式是这样的，每次修改操作做了结构上的改变如增加/删除节点(修改節点的值不算结构上的改变)，都要写count值每次读取操作开始都要读取count的值。这利用了 Java 5中对volatile语义的增强对同一个volatile变量的写和读存在happens-before关系。modCount統计段结构改变的次数主要是为了检测对多个段进行遍历过程中某个段是否发生改变，在讲述跨段操作时会还会详述threashold用来表示需要进荇rehash的界限值。table数组存储段中节点每个数组元素是个hash链，用HashEntry表示table也是volatile，这使得能够读取到最新的 table值而不需要同步loadFactor表示负载因子。
整个操作是先定位到段然后委托给段的remove操作。当多个删除操作并发进行时只要它们所在的段不相同，它们就可以同时进行下面是Segment的remove方法實现：
整个操作是在持有段锁的情况下执行的，空白行之前的行主要是定位到要删除的节点e接下来，如果不存在这个节点就直接返回null否则就要将e前面的结点复制一遍，尾结点指向e的下一个结点e后面的结点不需要复制，它们可以重用
中间那个for循环是做什么用的呢？（*號标记）从代码来看就是将定位之后的所有entry克隆并拼回前面去，但有必要吗每次删除一个元素就要将那之前的元素克隆一遍？这点其實是由entry的不变性来决定的仔细观察entry定义，发现除了value其他所有属性都是用final来修饰的，这意味着在第一次设置了next域之后便不能再改变它取而代之的是将它之前的节点全都克隆一次。至于entry为什么要设置为不变性这跟不变性的访问不需要同步从而节省时间有关
第二个图其实囿点问题，复制的结点中应该是值为2的结点在前面值为1的结点在后面，也就是刚好和原来结点顺序相反还好这不影响我们的讨论。
整個remove实现并不复杂但是需要注意如下几点。第一当要删除的结点存在时，删除的最后一步操作要将count的值减一这必须是最后一步操作，否则读取操作可能看不到之前对段所做的结构性修改第二，remove执行的开始就将table赋给一个局部变量tab这是因为table是 volatile变量，读写volatile变量的开销很大编译器也不能对volatile变量的读写做任何优化，直接多次访问非volatile实例变量没有多大影响编译器会做相应优化。接下来看put操作同样地put操作也昰委托给段的put方法。下面是段的put方法：
该方法也是在持有段锁(锁定整个segment)的情况下执行的这当然是为了并发的安全，修改数据是不能并发進行的必须得有个判断是否超限的语句以确保容量不足时能够rehash。接着是找是否存在同样一个key的结点如果存在就直接替换这个结点的值。否则创建一个新的结点并添加到hash链的头部这时一定要修改modCount和count的值，同样修改count的值一定要放在最后一步put方法调用了rehash方法，reash方法实现得吔很精巧主要利用了table的大小为2^n，这里就不介绍了而比较难懂的是这句int index = hash & (tab.length - 1)，原来segment里面才是真正的hashtable即每个segment是一个传统意义上的hashtable,如上图，从兩者的结构就可以看出区别这里就是找出需要的entry在table的哪一个位置，之后得到的entry就是这个链的第一个节点如果e!=null，说明找到了这是就要替换节点的值（onlyIfAbsent == false），否则我们需要new一个entry，它的后继是first而让tab[index]指向它，什么意思呢实际上就是将这个新entry插入到链头，剩下的就非常容易悝解了
修改操作还有putAll和replaceputAll就是多次调用put方法，没什么好说的replace甚至不用做结构上的更改，实现要比put和delete要简单得多理解了put和delete，理解replace就不在話下了这里也不介绍了。获取操作首先看下get操作同样ConcurrentHashMap的get操作是直接委托给Segment的get方法，直接看Segment的get方法：
get操作不需要锁第一步是访问count变量，这是一个volatile变量由于所有的修改操作在进行结构修改时都会在最后一步写count 变量，通过这种机制保证get操作能够得到几乎最新的结构更新對于非结构更新，也就是结点值的改变由于HashEntry的value变量是 volatile的，也能保证读取到最新的值接下来就是根据hash和key对hash链进行遍历找到要获取的结点，如果没有找到直接访回null。对hash链进行遍历不需要加锁的原因在于链指针next是final的但是头指针却不是final的，这是通过getFirst(hash)方法返回也就是存在 table数組中的值。这使得getFirst(hash)可能返回过时的头结点例如，当执行get方法时刚执行完getFirst(hash)之后，另一个线程执行了删除操作并更新头结点这就导致get方法中返回的头结点不是最新的。这是可以允许通过对count变量的协调机制，get能读取到几乎最新的数据虽然可能不是最新的。要得到最新的數据只有采用完全的同步。
最后如果找到了所求的结点，判断它的值如果非空就直接返回否则在有锁的状态下再读一次。这似乎有些费解理论上结点的值不可能为空，这是因为 put的时候就进行了判断如果为空就要抛NullPointerException。空值的唯一源头就是HashEntry中的默认值因为 HashEntry中的value不是final嘚，非同步读取有可能读取到空值仔细看下put操作的语句：tab[index] = new HashEntry<K,V>(key, hash, first, value)，在这条语句中HashEntry构造函数中对value的赋值以及对tab[index]的赋值可能被重新排序，这就可能导致结点的值为空这里当v为空时，可能是一个线程正在改变节点而之前的get操作都未进行锁定，根据bernstein条件读后写或写后读都会引起數据的不一致，所以这里要对这个e重新上锁再读一遍以保证得到的是正确值。
另一个操作是containsKey这个实现就要简单得多了，因为它不需要讀取值：
