Java并发包探秘 (二) ConcurrentHashMap
本文是Java并发包探秘的第二篇，旨在介绍一下Java并发容器中用的一些思路和技巧，帮助大家更好的理解Java并发容器，让我们更好的使用并发容器打造更高效的程序。本人能力有限，错误难免。希望及时指出。
Java并发包中有很多精心设计的高并发容器。有ConcurrentLinkedQueue、ConcurrentSkipListMap 、ConcurrentHashMap等。ConcurrentHashMap就是其中设计独特，受到开发者一致好评的key-value高并发容器，现在就让我们来一步一步揭开他们神秘的面纱。
正文开始：
为了照顾到所有读者，本文在分析ConcurrentHashMap之前先从HashMap开始介绍。为了叙述方便ConcurrentHashMap简称为并发HashMap，而HashMap就称之为HashMap。
一说到HashMap，我们首先需要明白什么是Hash。Hash其实是数学中的一个“散列”算法，可以把这个算法理解成 ： address = hash(key) 其中 key 是输入参数，address 是我们关心的地址。那么hash()就是“散列”函数或者称之为hash函数。什么是输入参数呢？在HashMap中是指关系映射的键、address就是用来存储数据的数组下标。采用这个方法来算地址在时间复杂度上是最快的。否则我们要一一比对容器中的内容和我们要的数据是否满足。链表的时间复杂度是O(n)，B+Tree的时间复杂度是O(log2n)，相关知识请点击。Hash算法的种类非常多。我们理解只需要明确。Hash()函数的计算结果要在目标空间竟可能的分散和均匀，当计算结果相同时如何解决好冲突。在理解HashMap之前让我们来看看HashTable是怎么处理的
public int size() { final Segment<K,V>[] segments = this.segments; long sum = 0; long check = 0; int[] mc = new int[segments.length]; // Try a few times to get accurate count. On failure due to // continuous async changes in table, resort to locking. for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) { check = 0; sum = 0; int mcsum = 0; for (int i = 0; i < segments.length; ++i) { sum += segments[i].count;//1.注意这语句 mcsum += mc[i] = segments[i].modCount;//2.还有这一句。//以上两句是不能调换位置的，还是JSR166 happens-before原则。count之前修改的内容一定会被读取到，jdk 1.5 volatile 关键字的语意增强。 } if (mcsum != 0) { for (int i = 0; i < segments.length; ++i) { check += segments[i].count; if (mc[i] != segments[i].modCount) { check = -1; // force retry break; } } } if (check == sum) break; } if (check != sum) { // Resort to locking all segments sum = 0; for (int i = 0; i < segments.length; ++i) segments[i].lock();//全部加锁 for (int i = 0; i < segments.length; ++i) sum += segments[i].count; for (int i = 0; i < segments.length; ++i) segments[i].unlock();//全部解锁 } if (sum > Integer.MAX_VALUE) return Integer.MAX_VALUE; else return (int)sum; }