hashmap与concurrenthashmap源码解析

hashmap源码解析转载：http://www.cnblogs.com/ITtangtang/p/3948406.html

一、HashMap概述

　　HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

　　值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

 Map map = Collections.synchronizedMap(new HashMap());

二、HashMap的数据结构

　　HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。

hashmap与concurrenthashmap源码解析

图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

我们看看HashMap中Entry类的代码：

    /** Entry是单向链表。 
 * 它是 “HashMap链式存储法”对应的链表。 
 *它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数 
 **/ 
 static class Entry<K,V> implements Map.Entry<K,V> { 
 final K key; 
 V value; 
// 指向下一个节点 
        Entry<K,V> next; 
 final int hash; 

// 构造函数。 
// 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" 
        Entry(int h, K k, V v, Entry<K,V> n) { 
 value = v; 
 next = n; 
 key = k; 
 hash = h; 
 } 

 public final K getKey() { 
 return key; 
 } 

 public final V getValue() { 
 return value; 
 } 

 public final V setValue(V newValue) { 
 V oldValue = value; 
 value = newValue; 
 return oldValue; 
 } 

// 判断两个Entry是否相等 
// 若两个Entry的“key”和“value”都相等，则返回true。 
// 否则，返回false 
 public final boolean equals(Object o) { 
if (!(o instanceof Map.Entry)) 
 return false; 
 Map.Entry e = (Map.Entry)o; 
 Object k1 = getKey(); 
 Object k2 = e.getKey(); 
if (k1 == k2 || (k1 != null && k1.equals(k2))) { 
 Object v1 = getValue(); 
 Object v2 = e.getValue(); 
if (v1 == v2 || (v1 != null && v1.equals(v2))) 
 return true; 
 } 
 return false; 
 } 

// 实现hashCode() 
        public final int hashCode() { 
 return (key==null   ? 0 : key.hashCode()) ^ 
 (value==null ? 0 : value.hashCode()); 
 } 

 public final String toString() { 
 return getKey() + "=" + getValue(); 
 } 

// 当向HashMap中添加元素时，绘调用recordAccess()。 
// 这里不做任何处理 
        void recordAccess(HashMap<K,V> m) { 
 } 

// 当从HashMap中删除元素时，绘调用recordRemoval()。 
// 这里不做任何处理 
        void recordRemoval(HashMap<K,V> m) { 
 } 
 }

HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。

三、HashMap源码分析

1、关键属性

　　先看看HashMap类中的一些关键属性：

1 transient Entry[] table;//存储元素的实体数组
2  
3 transient int size;//存放元素的个数
4  
5 int threshold; //临界值 当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量
6 
7  final float loadFactor; //加载因子
8  
9 transient int modCount;//被修改的次数

其中loadFactor加载因子是表示Hsah表中元素的填满的程度.

若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。

反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了）

冲突的机会越大,则查找的成本越高.

因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.

　　如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它取默认值0.75就好了。

2、构造方法

下面看看HashMap的几个构造方法：

public HashMap(int initialCapacity, float loadFactor) {
2         //确保数字合法
3         if (initialCapacity < 0)
4             throw new IllegalArgumentException("Illegal initial capacity: " +
5 initialCapacity);
6         if (initialCapacity > MAXIMUM_CAPACITY)
7             initialCapacity = MAXIMUM_CAPACITY;
8         if (loadFactor <= 0 || Float.isNaN(loadFactor))
9             throw new IllegalArgumentException("Illegal load factor: " +
10 loadFactor);
11 
12         // Find a power of 2 >= initialCapacity
13         int capacity = 1;   //初始容量
14         while (capacity < initialCapacity)   //确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂
15             capacity <<= 1;
16 
17         this.loadFactor = loadFactor;
18         threshold = (int)(capacity * loadFactor);
19         table = new Entry[capacity];
20 init();
21 }
22 
23     public HashMap(int initialCapacity) {
24         this(initialCapacity, DEFAULT_LOAD_FACTOR);
25 }
26 
27     public HashMap() {
28         this.loadFactor = DEFAULT_LOAD_FACTOR;
29         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
30         table = new Entry[DEFAULT_INITIAL_CAPACITY];
31 init();
32     }

我们可以看到在构造HashMap的时候如果我们指定了加载因子和初始容量的话就调用第一个构造方法，否则的话就是用默认的。默认初始容量为16，默认加载因子为0.75。我们可以看到上面代码中13-15行，这段代码的作用是确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂，至于为什么要把容量设置为2的n次幂，我们等下再看。

重点分析下HashMap中用的最多的两个方法put和get

3、存储数据

　　下面看看HashMap存储数据的过程是怎样的，首先看看HashMap的put方法：

public V put(K key, V value) {
// 若“key为null”，则将该键值对添加到table[0]中。
if (key == null) 
 return putForNullKey(value);
// 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
int hash = hash(key.hashCode());
//搜索指定hash值在对应table中的索引
int i = indexFor(hash, table.length);
// 循环遍历Entry数组,若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
 Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同则覆盖并返回旧值
                  V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
//修改次数+1
         modCount++;
//将key-value添加到table[i]处
 addEntry(hash, key, value, i);
 return null;
}

上面程序中用到了一个重要的内部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。从上面程序中可以看出：当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。这也说明了前面的结论：我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。

我们慢慢的来分析这个函数，第2和3行的作用就是处理key值为null的情况，我们看看putForNullKey(value)方法：

1 private V putForNullKey(V value) {
2         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
3             if (e.key == null) {   //如果有key为null的对象存在，则覆盖掉
4                 V oldValue = e.value;
5                 e.value = value;
6                 e.recordAccess(this);
7                 return oldValue;
8 }
9 }
10         modCount++;
11         addEntry(0, null, value, 0); //如果键为null的话，则hash值为0
12         return null;
13     }

注意：如果key为null的话，hash值为0，对象存储在数组中索引为0的位置。即table[0]

我们再回去看看put方法中第4行，它是通过key的hashCode值计算hash码，下面是计算hash码的函数：

1  //计算hash值的方法 通过键的hashCode来计算
2     static int hash(int h) {
3         // This function ensures that hashCodes that differ only by
4         // constant multiples at each bit position have a bounded
5         // number of collisions (approximately 8 at default load factor).
6         h ^= (h >>> 20) ^ (h >>> 12);
7         return h ^ (h >>> 7) ^ (h >>> 4);
8     }

得到hash码之后就会通过hash码去计算出应该存储在数组中的索引，计算索引的函数如下：

1     static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值
2         return h & (length-1);  //这里不能随便算取，用hash&(length-1)是有原因的，这样可以确保算出来的索引是在数组大小范围内，不会超出
3     }

这个我们要重点说下，我们一般对哈希表的散列很自然地会想到用hash值对length取模（即除法散列法），Hashtable中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是HashMap对Hashtable的一个改进。

接下来，我们分析下为什么哈希表的容量一定要是2的整数次幂。首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。

　　这看上去很简单，其实比较有玄机的，我们举个例子来说明：

　　假设数组长度分别为15和16，优化后的hash码分别为8和9，那么&运算后的结果如下：

       h & (table.length-1)                     hash                             table.length-1
8 & (15-1)：                                 0100                   &              1110                   =                0100
9 & (15-1)：                                 0101                   &              1110                   =                0100
       -----------------------------------------------------------------------------------------------------------------------
8 & (16-1)：                                 0100                   &              1111                   =                0100
9 & (16-1)：                                 0101                   &              1111                   =                0101

从上面的例子中可以看出：当它们和15-1（1110）“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hash值会与15-1（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！而当数组长度为16时，即为2的n次方时，2n-1得到的二进制数的每个位上的值都为1，这使得在低位上&时，得到的和原hash的低位相同，加之hash(int h)方法对key的hashCode的进一步优化，加入了高位计算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。

　　所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

根据上面 put 方法的源代码可以看出，当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

1 void addEntry(int hash, K key, V value, int bucketIndex) {
2         Entry<K,V> e = table[bucketIndex]; //如果要加入的位置有值，将该位置原先的值设置为新entry的next,也就是新entry链表的下一个节点
3         table[bucketIndex] = new Entry<>(hash, key, value, e);
4         if (size++ >= threshold) //如果大于临界值就扩容
5             resize(2 * table.length); //以2的倍数扩容
6     }

参数bucketIndex就是indexFor函数计算出来的索引值，第2行代码是取得数组中索引为bucketIndex的Entry对象，第3行就是用hash、key、value构建一个新的Entry对象放到索引为bucketIndex的位置，并且将该位置原先的对象设置为新对象的next构成链表。

　　第4行和第5行就是判断put后size是否达到了临界值threshold，如果达到了临界值就要进行扩容，HashMap扩容是扩为原来的两倍。

4、调整大小

resize()方法如下：

重新调整HashMap的大小，newCapacity是调整后的单位

 1     void resize(int newCapacity) {
2         Entry[] oldTable = table;
3         int oldCapacity = oldTable.length;
4         if (oldCapacity == MAXIMUM_CAPACITY) {
5             threshold = Integer.MAX_VALUE;
6             return;
7 }
8 
9         Entry[] newTable = new Entry[newCapacity];
10         transfer(newTable);//用来将原先table的元素全部移到newTable里面
11         table = newTable;  //再将newTable赋值给table
12         threshold = (int)(newCapacity * loadFactor);//重新计算临界值
13     }

新建了一个HashMap的底层数组，上面代码中第10行为调用transfer方法，将HashMap的全部元素添加到新的HashMap中,并重新计算元素在新的数组中的索引位置

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，扩容是需要进行数组复制的，复制数组是非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

5、数据读取

1.public V get(Object key) { 
2.    if (key == null) 
3.        return getForNullKey(); 
4.    int hash = hash(key.hashCode()); 
5.    for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
6.        e != null; 
7.        e = e.next) { 
8. Object k; 
9.        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
10.            return e.value; 
11. } 
12.    return null; 
13.}

有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

6、HashMap的性能参数：

HashMap 包含如下几个构造器：

HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。

initialCapacity：HashMap的最大容量，即为底层数组的长度。

loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。

负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。

HashMap的实现中，通过threshold字段来判断HashMap的最大容量：

threshold = (int)(capacity * loadFactor);

结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：

concurrenthashmap转载与文章：http://www.iteye.com/topic/344876

ConcurrentHashMap是Java 5中支持高并发、高吞吐量的线程安全HashMap实现。在这之前我对ConcurrentHashMap只有一些肤浅的理解，仅知道它采用了多个锁，大概也足够了。但是在经过一次惨痛的面试经历之后，我觉得必须深入研究它的实现。面试中被问到读是否要加锁，因为读写会发生冲突，我说必须要加锁，我和面试官也因此发生了冲突，结果可想而知。还是闲话少说，通过仔细阅读源代码，现在总算理解ConcurrentHashMap实现机制了，其实现之精巧，令人叹服，与大家共享之。

实现原理

锁分离 (Lock Stripping)

ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的hash table，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。

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

Java代码

/**
* The segments, each of which is a specialized hash table
*/
final Segment<K,V>[] segments;

不变(Immutable)和易变(Volatile)

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

Java代码

static final class HashEntry<K,V> {
final K key;
final int hash;
volatile V value;
final HashEntry<K,V> next;
}

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

其它

为了加快定位段以及段中hash槽的速度，每个段hash槽的的个数都是2^n，这使得通过位运算就可以定位段和段中hash槽的位置。当并发级别为默认值16时，也就是段的个数，hash值的高4位决定分配在哪个段中。但是我们也不要忘记《算法导论》给我们的教训：hash槽的的个数不应该是2^n，这可能导致hash槽分配不均，这需要对hash值重新再hash一次。（这段似乎有点多余了 hashmap与concurrenthashmap源码解析）

这是重新hash的算法，还比较复杂，我也懒得去理解了。

Java代码

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);
}

这是定位段的方法：

Java代码

final Segment<K,V> segmentFor(int hash) {
return segments[(hash >>> segmentShift) & segmentMask];
}

数据结构

关于Hash表的基础数据结构，这里不想做过多的探讨。Hash表的一个很重要方面就是如何解决hash冲突，ConcurrentHashMap和HashMap使用相同的方式，都是将hash值相同的节点放在一个hash链中。与HashMap不同的是，ConcurrentHashMap使用多个子Hash表，也就是段(Segment)。下面是ConcurrentHashMap的数据成员：

Java代码

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable {
/**
* Mask value for indexing into segments. The upper bits of a
* key's hash code are used to choose the segment.
*/
final int segmentMask;
/**
* Shift value for indexing within segments.
*/
final int segmentShift;
/**
* The segments, each of which is a specialized hash table
*/
final Segment<K,V>[] segments;
}

所有的成员都是final的，其中segmentMask和segmentShift主要是为了定位段，参见上面的segmentFor方法。

每个Segment相当于一个子Hash表，它的数据成员如下：

Java代码

static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
/**
* The number of elements in this segment's region.
*/
transient volatile int count;
/**
* Number of updates that alter the size of the table. This is
* used during bulk-read methods to make sure they see a
* consistent snapshot: If modCounts change during a traversal
* of segments computing size or checking containsValue, then
* we might have an inconsistent view of state so (usually)
* must retry.
*/
transient int modCount;
/**
* The table is rehashed when its size exceeds this threshold.
* (The value of this field is always <tt>(int)(capacity *
* loadFactor)</tt>.)
*/
transient int threshold;
/**
* The per-segment table.
*/
transient volatile HashEntry<K,V>[] table;
/**
* The load factor for the hash table. Even though this value
* is same for all segments, it is replicated to avoid needing
* links to outer object.
* @serial
*/
final float loadFactor;
}

count用来统计该段数据的个数，它是volatile，它用来协调修改和读取操作，以保证读取操作能够读取到几乎最新的修改。协调方式是这样的，每次修改操作做了结构上的改变，如增加/删除节点(修改节点的值不算结构上的改变)，都要写count值，每次读取操作开始都要读取count的值。这利用了Java 5中对volatile语义的增强，对同一个volatile变量的写和读存在happens-before关系。modCount统计段结构改变的次数，主要是为了检测对多个段进行遍历过程中某个段是否发生改变，在讲述跨段操作时会还会详述。threashold用来表示需要进行rehash的界限值。table数组存储段中节点，每个数组元素是个hash链，用HashEntry表示。table也是volatile，这使得能够读取到最新的table值而不需要同步。loadFactor表示负载因子。

实现细节

修改操作

先来看下删除操作remove(key)。

Java代码

public V remove(Object key) {
hash = hash(key.hashCode());
return segmentFor(hash).remove(key, hash, null);
}

整个操作是先定位到段，然后委托给段的remove操作。当多个删除操作并发进行时，只要它们所在的段不相同，它们就可以同时进行。下面是Segment的remove方法实现：

Java代码

V remove(Object key, int hash, Object value) {
lock();
try {
int c = count - 1;
HashEntry<K,V>[] tab = table;
int index = hash & (tab.length - 1);
HashEntry<K,V> first = tab[index];
HashEntry<K,V> e = first;
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue = null;
if (e != null) {
V v = e.value;
if (value == null || value.equals(v)) {
oldValue = v;
// All entries following removed node can stay
// in list, but all preceding ones need to be
// cloned.
++modCount;
HashEntry<K,V> newFirst = e.next;
for (HashEntry<K,V> p = first; p != e; p = p.next)
newFirst = new HashEntry<K,V>(p.key, p.hash,
newFirst, p.value);
tab[index] = newFirst;
count = c; // write-volatile
}
}
return oldValue;
} finally {
unlock();
}
}

整个操作是在持有段锁的情况下执行的，空白行之前的行主要是定位到要删除的节点e。接下来，如果不存在这个节点就直接返回null，否则就要将e前面的结点复制一遍，尾结点指向e的下一个结点。e后面的结点不需要复制，它们可以重用。下面是个示意图，我直接从这个网站上复制的（画这样的图实在是太麻烦了，如果哪位有好的画图工具，可以推荐一下）。

删除元素之前：

hashmap与concurrenthashmap源码解析

删除元素3之后：

hashmap与concurrenthashmap源码解析

第二个图其实有点问题，复制的结点中应该是值为2的结点在前面，值为1的结点在后面，也就是刚好和原来结点顺序相反，还好这不影响我们的讨论。

整个remove实现并不复杂，但是需要注意如下几点。第一，当要删除的结点存在时，删除的最后一步操作要将count的值减一。这必须是最后一步操作，否则读取操作可能看不到之前对段所做的结构性修改。第二，remove执行的开始就将table赋给一个局部变量tab，这是因为table是volatile变量，读写volatile变量的开销很大。编译器也不能对volatile变量的读写做任何优化，直接多次访问非volatile实例变量没有多大影响，编译器会做相应优化。

接下来看put操作，同样地put操作也是委托给段的put方法。下面是段的put方法：

Java代码

V put(K key, int hash, V value, boolean onlyIfAbsent) {
lock();
try {
int c = count;
if (c++ > threshold) // ensure capacity
rehash();
HashEntry<K,V>[] tab = table;
int index = hash & (tab.length - 1);
HashEntry<K,V> first = tab[index];
HashEntry<K,V> e = first;
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue;
if (e != null) {
oldValue = e.value;
if (!onlyIfAbsent)
e.value = value;
}
else {
oldValue = null;
++modCount;
tab[index] = new HashEntry<K,V>(key, hash, first, value);
count = c; // write-volatile
}
return oldValue;
} finally {
unlock();
}
}

该方法也是在持有段锁的情况下执行的，首先判断是否需要rehash，需要就先rehash。接着是找是否存在同样一个key的结点，如果存在就直接替换这个结点的值。否则创建一个新的结点并添加到hash链的头部，这时一定要修改modCount和count的值，同样修改count的值一定要放在最后一步。put方法调用了rehash方法，reash方法实现得也很精巧，主要利用了table的大小为2^n，这里就不介绍了。

修改操作还有putAll和replace。putAll就是多次调用put方法，没什么好说的。replace甚至不用做结构上的更改，实现要比put和delete要简单得多，理解了put和delete，理解replace就不在话下了，这里也不介绍了。

获取操作

首先看下get操作，同样ConcurrentHashMap的get操作是直接委托给Segment的get方法，直接看Segment的get方法：

Java代码

V get(Object key, int hash) {
if (count != 0) { // read-volatile
HashEntry<K,V> e = getFirst(hash);
while (e != null) {
if (e.hash == hash && key.equals(e.key)) {
V v = e.value;
if (v != null)
return v;
return readValueUnderLock(e); // recheck
}
e = e.next;
}
}
return null;
}

get操作不需要锁。第一步是访问count变量，这是一个volatile变量，由于所有的修改操作在进行结构修改时都会在最后一步写count变量，通过这种机制保证get操作能够得到几乎最新的结构更新。对于非结构更新，也就是结点值的改变，由于HashEntry的value变量是volatile的，也能保证读取到最新的值。接下来就是对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]的赋值可能被重新排序，这就可能导致结点的值为空。这种情况应当很罕见，一旦发生这种情况，ConcurrentHashMap采取的方式是在持有锁的情况下再读一遍，这能够保证读到最新的值，并且一定不会为空值。

Java代码

V readValueUnderLock(HashEntry<K,V> e) {
lock();
try {
return e.value;
} finally {
unlock();
}
}

另一个操作是containsKey，这个实现就要简单得多了，因为它不需要读取值：

Java代码

boolean containsKey(Object key, int hash) {
if (count != 0) { // read-volatile
HashEntry<K,V> e = getFirst(hash);
while (e != null) {
if (e.hash == hash && key.equals(e.key))
return true;
e = e.next;
}
}
return false;
}

跨段操作

有些操作需要涉及到多个段，比如说size(), containsValaue()。先来看下size()方法：

Java代码

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;
mcsum += mc[i] = segments[i].modCount;
}
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;
}

size方法主要思路是先在没有锁的情况下对所有段大小求和，如果不能成功（这是因为遍历过程中可能有其它线程正在对已经遍历过的段进行结构性更新），最多执行RETRIES_BEFORE_LOCK次，如果还不成功就在持有所有段锁的情况下再对所有段大小求和。在没有锁的情况下主要是利用Segment中的modCount进行检测，在遍历过程中保存每个Segment的modCount，遍历完成之后再检测每个Segment的modCount有没有改变，如果有改变表示有其它线程正在对Segment进行结构性并发更新，需要重新计算。

Java代码

public boolean containsValue(Object value) {
if (value == null)
throw new NullPointerException();
// See explanation of modCount use above
final Segment<K,V>[] segments = this.segments;
int[] mc = new int[segments.length];
// Try a few times without locking
for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
int sum = 0;
int mcsum = 0;
for (int i = 0; i < segments.length; ++i) {
int c = segments[i].count;
mcsum += mc[i] = segments[i].modCount;
if (segments[i].containsValue(value))
return true;
}
boolean cleanSweep = true;
if (mcsum != 0) {
for (int i = 0; i < segments.length; ++i) {
int c = segments[i].count;
if (mc[i] != segments[i].modCount) {
cleanSweep = false;
break;
}
}
}
if (cleanSweep)
return false;
}
// Resort to locking all segments
for (int i = 0; i < segments.length; ++i)
segments[i].lock();
boolean found = false;
try {
for (int i = 0; i < segments.length; ++i) {
if (segments[i].containsValue(value)) {
found = true;
break;
}
}
} finally {
for (int i = 0; i < segments.length; ++i)
segments[i].unlock();
}
return found;
}

同样注意内层的第一个for循环，里面有语句int c = segments[i].count; 但是c却从来没有被使用过，即使如此，编译器也不能做优化将这条语句去掉，因为存在对volatile变量count的读取，这条语句存在的唯一目的就是保证segments[i].modCount读取到几乎最新的值。关于containsValue方法的其它部分就不分析了，它和size方法差不多。

跨段方法中还有一个isEmpty()方法，其实现比size()方法还要简单，也不介绍了。最后简单地介绍下迭代方法，如keySet(), values(), entrySet()方法，这些方法都返回相应的迭代器，所有迭代器都继承于Hash_Iterator类(提交时居然提醒我不能包含sh It，只得加了下划线)，里实现了主要的方法。其结构是：

Java代码

abstract class Hash_Iterator{
int nextSegmentIndex;
int nextTableIndex;
HashEntry<K,V>[] currentTable;
HashEntry<K, V> nextEntry;
HashEntry<K, V> lastReturned;
}

nextSegmentIndex是段的索引，nextTableIndex是nextSegmentIndex对应段中中hash链的索引，currentTable是nextSegmentIndex对应段的table。调用next方法时主要是调用了advance方法：

Java代码

final void advance() {
if (nextEntry != null && (nextEntry = nextEntry.next) != null)
return;
while (nextTableIndex >= 0) {
if ( (nextEntry = currentTable[nextTableIndex--]) != null)
return;
}
while (nextSegmentIndex >= 0) {
Segment<K,V> seg = segments[nextSegmentIndex--];
if (seg.count != 0) {
currentTable = seg.table;
for (int j = currentTable.length - 1; j >= 0; --j) {
if ( (nextEntry = currentTable[j]) != null) {
nextTableIndex = j - 1;
return;
}
}
}
}
}

不想再多介绍了，唯一需要注意的是跳到下一个段时，一定要先读取下一个段的count变量。

这种迭代方式的主要效果是不会抛出ConcurrentModificationException。一旦获取到下一个段的table，也就意味着这个段的头结点在迭代过程中就确定了，在迭代过程中就不能反映对这个段节点并发的删除和添加，对于节点的更新是能够反映的，因为节点的值是一个volatile变量。

结束语

ConcurrentHashMap是一个支持高并发的高性能的HashMap实现，它支持完全并发的读以及一定程度并发的写。ConcurrentHashMap的实现也是很精巧，充分利用了最新的JMM规范，值得学习，却不值得模仿。最后由于本人水平有限，对大师的作品难免有误解，如果存在，还望大牛们不吝指出。

参考文章：

http://www.ibm.com/developerworks/java/library/j-jtp08223/，这个是讨论的是Doug Lea's util.concurrent包中的ConcurrentHashMap的实现，不过大致思想是一致的。

http://floatingpoint.tinou.com/2008/09/performance-optimization-in-concurrenthashmap.html

// 以下是源博主对疑问的解释：

其实这种方式是存在问题的，在第一个内层for循环中，在这两条语句sum += segments[i].count; mcsum += mc[i] = segments[i].modCount;之间，其它线程可能正在对Segment进行结构性的修改，导致segments[i].count和segments[i].modCount读取的数据并不一致。这可能使size()方法返回任何时候都不曾存在的大小，很奇怪javadoc居然没有明确标出这一点，可能是因为这个时间窗口太小了吧。size()的实现还有一点需要注意，必须要先segments[i].count，才能segments[i].modCount，这是因为segment[i].count是对volatile变量的访问，接下来segments[i].modCount才能得到几乎最新的值（前面我已经说了为什么只是“几乎”了）。

楼主写的非常好，又使我明白的不少东西。这个地方还是不理解，为什么需要首先调用一次volatile变量才使的modCount几乎可以得到最新的值?

写volatile变量和它之前的读写操作是不能reorder的，读volatile变量和它之后的读写操作也是不能reorder的。
修改modCount发生在修改count之前，由于count是volatile变量，修改modCount不能和写count的操作reorder，读取count和它之后的操作，比如读取modCount，不能reorder。有了这两个不能reorder才能保证读取了count之后，能读到线程在写count之前的写入的modCount值，这个modCount值是几乎最新的。
如果在读modCount之前不读count，读modCount甚至可能会reorder到写modCount之前。

用reorder解释总是太复杂了，不如用happens-before来得简洁。当一个线程I对count的读时，它读到的值必定是另一个线程，假设是线程II，最近对count的写。这个两个操作存在happens-before关系，即线程II对count的写happens-before线程I对count的读，记作：II：W(count) < I：R(count)。单线程的happens-before规则，又有II：W(modCount) < II：(count)（查看源代码会发现在写count之前必定有写modCount），以及 I：R(count) < I：R(modCount)，根据传递规则有，II：(modCount) < I：(modCount)，这就是说线程I至少能够读取到线程II写count之前的modCount值。我曾经写了一篇关于happens-before的文章，有些表达可能有误，但大致还是对的，http://www.iteye.com/topic/260515。

不理解的话，也只能告诉你结论了，如果没有对count的写的话（对volatile的写是一种同步操作），读modCount可能读到很久很久很久以前的值（初始值0都有可能）。

期待高人做更简洁的解释吧。

currenthashmap虽然是线程安全的，但是对于安全对象的发布也要注意：

如下问题：

public class TestClass{

private ConcurrentHashMap<String,Integer> map=new ConcurrentHashMap<String,Integer>();

public void add(String key){

Integer value=map.get(key);

if(value==null){

map.put(key,1);

}else{

map.put(key,value+1)

}

秒客网

hashmap与concurrenthashmap源码解析

相关文章