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是怎么处理的
Java代码
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
我们从上面的代码不难看出，在HashTable中的处理十分简单，数组下标的值仅仅是放入元素Key的hashCode()函数与数组长度取余。Object的hashCode()函数是一个native方法。方法说明做出了一下三条保证：
Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the java.lang.Object.equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
做一个假设，Object的hashCode()方法返回一个常数在HashTable中会出现什么情况。没错！此时我们存储在tab中的数据将呈现一个链表的结构。原因就是我们的hashCode与表长度求余的结果是一个常数，所以要不断的解决hash冲突。
我们再来看看HashMap中的hash算法：
Java代码
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
从代码和说明中，我们不难发现。HashMap的hash算法比HashTable的要略微复杂了一点。目的也是使结果在目标空间竟可能分散。
HashMap是比HashTable要快的key-value容器，原因很简单，在访问HashMap的时候比访问HashTable的数据少了同步的性能消耗。但带来的问题则是该数据容器在多线程环境下会导致数据不安全。它是一个非线程安全的键值对容器。在高并发的环境要禁止使用它。但key-value的访问方式又是必不可少的。所以在JDK 1.5引入了一个并发的HashMap，它几乎是在并发环境下使用key-value容器的必选对象。我们先来看看它的内部结构。
首先还是hash算法：
Java代码
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because ConcurrentHashMap uses power-of-two length hash tables,
* that otherwise encounter collisions for hashCodes that do not
* differ in lower or upper bits.
*/
private static int hash(int h) {
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}
又复杂了，没错！ 目的只有一个使结果在目标空间均匀。相关文章请参考这里
除了hash算法的改进，还有就是在并发HashMap中使用了锁，而且这把锁是分离的锁。目的就是绕过访问必须加锁的技术障碍，当然又要保护数据的安全。这样比HashTable中方法级别的synchronized更加细粒度的Segment诞生了。该类自身就是继承自ReentrantLock可重入锁对象，目的是方便加锁操作。
Java代码
/**
* Segments are specialized versions of hash tables. This
* subclasses from ReentrantLock opportunistically, just to
* simplify some locking and avoid separate construction.
*/
static final class Segment<K,V> extends ReentrantLock implements Serializable {
并发HashMap中默认使用16个Segment对HashMap的数据进行分段，读取方法如下：
Java代码
public V get(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
}
读取方法使用了二次hash操作，第一次时命中一个Segment，第二次调用Segment的get方法：
Java代码
/* Specialized implementations of map methods */
V get(Object key, int hash) {
&n
补充：软件开发 , Java ,
