[java.util.concurrent 之ConcurrentHashMap 源码分析](http://www.iteye.com/topic/977348)
最近有点想研究下java.util.concurrent 包下的一些类中的实现，在现实中也对这包里的类应用不少，但都没怎么去深入理解，只是听说里面的实现在高并发中有不错的性能。。接下将对里面的几个比较常用的类的源码进行分析。。
**ConcurrentHashMap类**
研究源码时，我一般喜欢从实际的应用中去一步步调试分析。。这样理解起来容易很多。
** 实际应用：**
Java代码 
1. ConcurrentMap map = new ConcurrentHashMap();
2. String oldValue = map.put("zhxing", "value");
3. String oldValue1 = map.put("zhxing", "value1");
4. String oldValue2 = map.putIfAbsent("zhxing", "value2");
5. String value = map.get("zhxing");
6.
7. System.out.println("oldValue:" + oldValue);
8. System.out.println("oldValue1:" + oldValue1);
9. System.out.println("oldValue2:" + oldValue2);
10. System.out.println("value:" + value);
输出结果：
Java代码 
1. oldValue:null
2. oldValue1:value
3. oldValue2:value1
4. value:value1
**先从new 方法开始**
Java代码 
1. /**
2. * Creates a new, empty map with a default initial capacity (16), load
3. * factor (0.75) and concurrencyLevel（也就是锁的个数） (16).
4. *
5. */
6. public ConcurrentHashMap() {
7. this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
8. }
9. // 当都是默认的设置参数
10. public ConcurrentHashMap(int initialCapacity, float loadFactor,
11. int concurrencyLevel) {
12. if (!(loadFactor > 0) || initialCapacity 0 || concurrencyLevel 0)
13. throw new IllegalArgumentException();
14. // MAX_SEGMENTS = 1
15. if (concurrencyLevel > MAX_SEGMENTS)
16. concurrencyLevel = MAX_SEGMENTS;
17.
18. // Find power-of-two sizes best matching arguments
19. // 这里是根据设定的并发数查找最优的并发数
20. int sshift = 0;
21. int ssize = 1;
22. while (ssize
23. ++sshift;
24. ssize 1;// 不断右移
25. }
26. // 到这里，sshift=4，ssize=16.因为concurrencyLevel=16=1
27. segmentShift = 32 - sshift;// =16
28. segmentMask = ssize - 1;// =3
29. // 创建了16个分段（Segment），其实每个分段相当于一个带锁的map
30. this.segments = Segment.newArray(ssize);
31.
32. if (initialCapacity > MAXIMUM_CAPACITY)
33. initialCapacity = MAXIMUM_CAPACITY;
34. // 这里是计算每个分段存储的容量
35. int c = initialCapacity / ssize;// c=16/16=1
36. if (c * ssize // 防止分段的相加的容量小于总容量
37. ++c;
38. int cap = 1;
39. // 如果初始容量比cap的容量小，则已双倍的容量增加
40. while (cap
41. cap 1;
42. // 分别new分段
43. for (int i = 0; i this.segments.length; ++i)
44. this.segments[i] = new Segment(cap, loadFactor);
45. }
这里提到了一个Segment 这个类，其实这个是总map 的分段，就是为了实现分段锁机制。
Java代码 
1. /**
2. * Segments are specialized versions of hash tables. This subclasses from
3. * ReentrantLock opportunistically, just to simplify some locking and avoid
4. * separate construction. map 的分段实现，扩展了锁机制
5. */
6. static final class Segment extends ReentrantLock implements
7. Serializable {
8. //。。。
9. Segment(int initialCapacity, float lf) {
10. loadFactor = lf;
11. // 这个是开始初始化map容器了
12. setTable(HashEntry. newArray(initialCapacity));
13. }
14. /**
15. * Sets table to new HashEntry array. Call only while holding lock or in
16. * constructor.
17. */
18. void setTable(HashEntry[] newTable) {
19. threshold = (int) (newTable.length * loadFactor);
20. table = newTable;
21. }
22. }
23.
24. // 这个是实际保存到map的东西了，如果对HashMap源码有了解的话，是不是觉得很像Hash.Entry，但又没实现Map.Entry接口，它是用另外个类WriteThroughEntry
25. // 来实现这个Map.Entry接口的。
26. static final class HashEntry {
27. final K key;
28. final int hash;
29. volatile V value;
30. final HashEntry next;
31.
32. HashEntry(K key, int hash, HashEntry next, V value) {
33. this.key = key;
34. this.hash = hash;
35. this.next = next;
36. this.value = value;
37. }
38.
39. @SuppressWarnings("unchecked")
40. // 新建数组，保存着map里的键值对
41. static final HashEntry[] newArray(int i) {
42. return new HashEntry[i];
43. }
**get方法实现**
Java代码 
1. //ConcurrentHashMap类
2. // 在这里发现，get操作几乎是不带锁的。。效率提高很多
3. public V get(Object key) {
4. // key不能为null 。。
5. int hash = hash(key); // throws NullPointerException if key null
6. return segmentFor(hash).get(key, hash);
7. }
8.
9. // 这个hash方式不太懂，估计是为了能均匀分布吧
10. static int hash(Object x) {
11. int h = x.hashCode();
12. h += ~(h 9);
13. h ^= (h >>> 14);
14. h += (h 4);
15. h ^= (h >>> 10);
16. return h;
17. }
18.
19. /**
20. * Returns the segment that should be used for key with given hash 这个是寻找所在分段
21. *
22. * @param hash
23. * the hash code for the key
24. * @return the segment
25. */
26. final Segment segmentFor(int hash) {
27. // hash>>>16&3
28. return segments[(hash >>> segmentShift) & segmentMask];
29. }
30.
31. //Segment 类方法
32. /* Specialized implementations of map methods */
33. // 获得值了，和其他map的get的实现其实差不多
34. V get(Object key, int hash) {
35. // count 是每个分段的键值对个数，而且是volatile，保证在内存中只有一份
36. if (count != 0) { // read-volatile
37. // 获得分段中hash链表的第一个值
38. HashEntry e = getFirst(hash);
39. while (e != null) {
40. if (e.hash == hash && key.equals(e.key)) {
41. V v = e.value;
42. if (v != null)
43. return v;
44. // 这个做了一个挺有趣的检查，如果v==null，而key!=null,的时候会等待锁中value的值
45. return readValueUnderLock(e); // recheck
46. }
47. e = e.next;
48. }
49. }
50. return null;
51. }
52.
53. /**
54. * Reads value field of an entry under lock. Called if value field ever
55. * appears to be null. This is possible only if a compiler happens to
56. * reorder a HashEntry initialization with its table assignment, which
57. * is legal under memory model but is not known to ever occur.
58. */
59. V readValueUnderLock(HashEntry e) {
60. lock();
61. try {
62. return e.value;
63. } finally {
64. unlock();
65. }
66. }
**put 方法**
Java代码 
1. //ConcurrentHashMap类
2. // 注意的是key 和value 都不能为空
3. public V put(K key, V value) {
4. if (value == null)
5. throw new NullPointerException();
6. // 和get方式一样的hash 方式
7. int hash = hash(key);
8. return segmentFor(hash).put(key, hash, value, false);
9. }
10.
11. //Segment 类
12.
13. V put(K key, int hash, V value, boolean onlyIfAbsent) {
14. // 这里加锁了
15. lock();
16. try {
17. int c = count;
18. // 如果超过限制，就重新分配
19. if (c++ > threshold) // ensure capacity
20. rehash();
21. HashEntry[] tab = table;
22. int index = hash & (tab.length - 1);
23. HashEntry first = tab[index];
24. HashEntry e = first;
25. // e的值总是在链表的最后一个
26. while (e != null && (e.hash != hash || !key.equals(e.key)))
27. e = e.next;
28.
29. V oldValue;
30. if (e != null) {
31. oldValue = e.value;
32. // 这里就是实现putIfAbsent 的方式
33. if (!onlyIfAbsent)
34. e.value = value;
35. } else {
36. oldValue = null;
37. ++modCount;
38. tab[index] = new HashEntry(key, hash, first, value);
39. count = c; // write-volatile
40. }
41. return oldValue;
42. } finally {
43. unlock();
44. }
45. }
46.
47. // 这中扩容方式应该和其他map 的扩容一样
48. void rehash() {
49. HashEntry[] oldTable = table;
50. int oldCapacity = oldTable.length;
51. // 如果到了最大容量则不能再扩容了，max=1
52. if (oldCapacity >= MAXIMUM_CAPACITY)
53. return;
54.
55. /*
56. * Reclassify nodes in each list to new Map. Because we are using
57. * power-of-two expansion, the elements from each bin must either
58. * stay at same index, or move with a power of two offset. We
59. * eliminate unnecessary node creation by catching cases where old
60. * nodes can be reused because their next fields won't change.
61. * Statistically, at the default threshold, only about one-sixth of
62. * them need cloning when a table doubles. The nodes they replace
63. * will be garbage collectable as soon as they are no longer
64. * referenced by any reader thread that may be in the midst of
65. * traversing table right now.
66. */
67. // 以两倍的方式增长
68. HashEntry[] newTable = HashEntry.newArray(oldCapacity 1);
69. threshold = (int) (newTable.length * loadFactor);
70. int sizeMask = newTable.length - 1;
71. // 下面的数据拷贝就没多少好讲的了
72. for (int i = 0; i
73. // We need to guarantee that any existing reads of old Map can
74. // proceed. So we cannot yet null out each bin.
75. HashEntry e = oldTable[i];
76.
77. if (e != null) {
78. HashEntry next = e.next;
79. int idx = e.hash & sizeMask;
80.
81. // Single node on list
82. if (next == null)
83. newTable[idx] = e;
84.
85. else {
86. // Reuse trailing consecutive sequence at same slot
87. HashEntry lastRun = e;
88. int lastIdx = idx;
89. for (HashEntry last = next; last != null; last = last.next) {
90. int k = last.hash & sizeMask;
91. if (k != lastIdx) {
92. lastIdx = k;
93. lastRun = last;
94. }
95. }
96. newTable[lastIdx] = lastRun;
97.
98. // Clone all remaining nodes
99. for (HashEntry p = e; p != lastRun; p = p.next) {
100. int k = p.hash & sizeMask;
101. HashEntry n = newTable[k];
102. newTable[k] = new HashEntry(p.key, p.hash, n,
103. p.value);
104. }
105. }
106. }
107. }
108. table = newTable;
109. }
**size 方法**
Java代码 
1. /**
2. * Returns the number of key-value mappings in this map. If the map contains
3. * more than Integer.MAX_VALUE elements, returns
4. * Integer.MAX_VALUE. javadoc 上也写明了，返回的数值不能超过Int的最大值，超过也返回最大值
5. * 在下面的分析也可以看出，为了减少锁竞争做了一些性能优化，这种的优化方式在很多方法都有使用
6. *
7. * @return the number of key-value mappings in this map
8. */
9. public int size() {
10. final Segment[] segments = this.segments;
11. long sum = 0;
12. long check = 0;
13. int[] mc = new int[segments.length];
14. // Try a few times to get accurate count. On failure due to
15. // continuous async changes in table, resort to locking.
16. // 这里最多试RETRIES_BEFORE_LOCK=2 次的检查对比
17. for (int k = 0; k
18. check = 0;
19. sum = 0;// size 总数
20. int mcsum = 0;// 修改的总次数
21. // 这里保存了一份对比值，供下次对比时使用
22. for (int i = 0; i
23. sum += segments[i].count;
24. mcsum += mc[i] = segments[i].modCount;
25. }
26. // 只有当map初始化的时候才等于0
27. if (mcsum != 0) {
28. // 在此对比上面保存的修改值
29. for (int i = 0; i
30. check += segments[i].count;
31. if (mc[i] != segments[i].modCount) {
32. check = -1; // force retry
33. break;
34. }
35. }
36. }
37. // 检查和第一次保存值一样则结束循环
38. if (check == sum)
39. break;
40. }
41. // 当不相等的时候，这里就只有用锁来保证正确性了
42. if (check != sum) { // Resort to locking all segments
43. sum = 0;
44. for (int i = 0; i
45. segments[i].lock();
46. for (int i = 0; i
47. sum += segments[i].count;
48. for (int i = 0; i
49. segments[i].unlock();
50. }
51. // 这里也可以看出，如果超过int 的最大值值返回int 最大值
52. if (sum > Integer.MAX_VALUE)
53. return Integer.MAX_VALUE;
54. else
55. return (int) sum;
56. }
**keys 方法**
Java代码 
1. public Enumeration keys() {
2. //这里新建了一个内部Iteraotr 类
3. return new KeyIterator();
4. }
5. //这里主要是继承了HashIterator 方法，基本的实现都在HashIterator 中
6. final class KeyIterator extends HashIterator implements Iterator,
7. Enumeration {
8. public K next() {
9. return super.nextEntry().key;
10. }
11.
12. public K nextElement() {
13. return super.nextEntry().key;
14. }
15. }
16.
17. /* ---------------- Iterator Support -------------- */
18. // 分析代码发现，这个遍历过程没有涉及到锁，查看Javadoc 后可知该视图的 iterator 是一个“弱一致”的迭代器。。
19. abstract class HashIterator {
20. int nextSegmentIndex;// 下一个分段的index
21. int nextTableIndex;// 下一个分段的容器的index
22. HashEntry[] currentTable;// 当前容器
23. HashEntry nextEntry;// 下个键值对
24. HashEntry lastReturned;// 上次返回的键值对
25.
26. HashIterator() {
27. nextSegmentIndex = segments.length - 1;
28. nextTableIndex = -1;
29. advance();
30. }
31.
32. public boolean hasMoreElements() {
33. return hasNext();
34. }
35.
36. // 先变量键值对的链表，再对table 数组的index 遍历，最后遍历分段数组的index。。这样就可以完整的变量完所有的entry了
37. final void advance() {
38. // 先变量键值对的链表
39. if (nextEntry != null && (nextEntry = nextEntry.next) != null)
40. return;
41. // 对table 数组的index 遍历
42. while (nextTableIndex >= 0) {
43. if ((nextEntry = currentTable[nextTableIndex--]) != null)
44. return;
45. }
46. // 遍历分段数组的index
47. while (nextSegmentIndex >= 0) {
48. Segment seg = segments[nextSegmentIndex--];
49. if (seg.count != 0) {
50. currentTable = seg.table;
51. for (int j = currentTable.length - 1; j >= 0; --j) {
52. if ((nextEntry = currentTable[j]) != null) {
53. nextTableIndex = j - 1;
54. return;
55. }
56. }
57. }
58. }
59. }
60.
61. public boolean hasNext() {
62. return nextEntry != null;
63. }
64.
65. HashEntry nextEntry() {
66. if (nextEntry == null)
67. throw new NoSuchElementException();
68. // 把上次的entry换成当前的entry
69. lastReturned = nextEntry;
70. // 这里做一些预操作
71. advance();
72. return lastReturned;
73. }
74.
75. public void remove() {
76. if (lastReturned == null)
77. throw new IllegalStateException();
78. ConcurrentHashMap.this.remove(lastReturned.key);
79. lastReturned = null;
80. }
81. }
**keySet/Values/elements 这几个方法都和keys 方法非常相似** 。。就不解释了。。而entrySet 方法有点特别。。我也有点不是很明白。。
Java代码 
1. //这里没什么好说的，看下就明白，主要在下面
2. public Set> entrySet() {
3. Set> es = entrySet;
4. return (es != null) ? es : (entrySet = new EntrySet());
5. }
6.
7. final class EntrySet extends AbstractSet> {
8. public Iterator> iterator() {
9. return new EntryIterator();
10. }
11. }
12. //主要在这里，新建了一个WriteThroughEntry 这个类
13. final class EntryIterator extends HashIterator implements
14. Iterator> {
15. public Map.Entry next() {
16. HashEntry e = super.nextEntry();
17. return new WriteThroughEntry(e.key, e.value);
18. }
19. }
20.
21. /**
22. * Custom Entry class used by EntryIterator.next(), that relays setValue
23. * changes to the underlying map.
24. * 这个主要是返回一个Entry，但有点不明白的是为什么不在HashEntry中实现Map
25. * .Entry就可以了（HashMap就是这样的），为了减少锁竞争？？
26. */
27. final class WriteThroughEntry extends AbstractMap.SimpleEntry {
28. WriteThroughEntry(K k, V v) {
29. super(k, v);
30. }
31.
32. /**
33. * Set our entry's value and write through to the map. The value to
34. * return is somewhat arbitrary here. Since a WriteThroughEntry does not
35. * necessarily track asynchronous changes, the most recent "previous"
36. * value could be different from what we return (or could even have been
37. * removed in which case the put will re-establish). We do not and
38. * cannot guarantee more.
39. */
40. public V setValue(V value) {
41. if (value == null)
42. throw new NullPointerException();
43. V v = super.setValue(value);
44. ConcurrentHashMap.this.put(getKey(), value);
45. return v;
46. }
47. }
从上面可以看出，ConcurrentHash 也没什么特别的，大概的思路就是采用分段锁机制来实现的，把之前用一个容易EntryTable来装的转换成多个Table来装键值对。而方法里面的也采用了不少为了减少锁竞争而做的一些优化。。从ConcurrentHash类里面可以看出，它里面实现了一大堆的内部类。。比如Segment/KeyIterator/ValueIterator/EntryIterator等等。。个人觉得有些代码好像比较难理解。。比如Segment 类继承ReentrantLock，为什么不用组合呢。。还会有上面提到的，HashEntry 为什么不像HashMap 的Entry一样实现Map.Entry接口。。建立这么多内部类，搞得人头晕晕的。。。。
- JVM
- 深入理解Java内存模型
- 深入理解Java内存模型（一）——基础
- 深入理解Java内存模型（二）——重排序
- 深入理解Java内存模型（三）——顺序一致性
- 深入理解Java内存模型（四）——volatile
- 深入理解Java内存模型（五）——锁
- 深入理解Java内存模型（六）——final
- 深入理解Java内存模型（七）——总结
- Java内存模型
- Java内存模型2
- 堆内内存还是堆外内存？
- JVM内存配置详解
- Java内存分配全面浅析
- 深入Java核心 Java内存分配原理精讲
- jvm常量池
- JVM调优总结
- JVM调优总结（一）-- 一些概念
- JVM调优总结（二）-一些概念
- VM调优总结（三）-基本垃圾回收算法
- JVM调优总结（四）-垃圾回收面临的问题
- JVM调优总结（五）-分代垃圾回收详述1
- JVM调优总结（六）-分代垃圾回收详述2
- JVM调优总结（七）-典型配置举例1
- JVM调优总结（八）-典型配置举例2
- JVM调优总结（九）-新一代的垃圾回收算法
- JVM调优总结（十）-调优方法
- 基础
- Java 征途：行者的地图
- Java程序员应该知道的10个面向对象理论
- Java泛型总结
- 序列化与反序列化
- 通过反编译深入理解Java String及intern
- android 加固防止反编译-重新打包
- volatile
- 正确使用 Volatile 变量
- 异常
- 深入理解java异常处理机制
- Java异常处理的10个最佳实践
- Java异常处理手册和最佳实践
- Java提高篇——对象克隆（复制）
- Java中如何克隆集合——ArrayList和HashSet深拷贝
- Java中hashCode的作用
- Java提高篇之hashCode
- 常见正则表达式
- 类
- 理解java类加载器以及ClassLoader类
- 深入探讨 Java 类加载器
- 类加载器的工作原理
- java反射
- 集合
- HashMap的工作原理
- ConcurrentHashMap之实现细节
- java.util.concurrent 之ConcurrentHashMap 源码分析
- HashMap的实现原理和底层数据结构
- 线程
- 关于Java并发编程的总结和思考
- 40个Java多线程问题总结
- Java中的多线程你只要看这一篇就够了
- Java多线程干货系列（1）：Java多线程基础
- Java非阻塞算法简介
- Java并发的四种风味：Thread、Executor、ForkJoin和Actor
- Java中不同的并发实现的性能比较
- JAVA CAS原理深度分析
- 多个线程之间共享数据的方式
- Java并发编程
- Java并发编程（1）：可重入内置锁
- Java并发编程（2）：线程中断（含代码）
- Java并发编程（3）：线程挂起、恢复与终止的正确方法（含代码）
- Java并发编程（4）：守护线程与线程阻塞的四种情况
- Java并发编程（5）：volatile变量修饰符—意料之外的问题（含代码）
- Java并发编程（6）：Runnable和Thread实现多线程的区别（含代码）
- Java并发编程（7）：使用synchronized获取互斥锁的几点说明
- Java并发编程（8）：多线程环境中安全使用集合API（含代码）
- Java并发编程（9）：死锁（含代码）
- Java并发编程（10）：使用wait/notify/notifyAll实现线程间通信的几点重要说明
- java并发编程-II
- Java多线程基础：进程和线程之由来
- Java并发编程：如何创建线程？
- Java并发编程：Thread类的使用
- Java并发编程：synchronized
- Java并发编程：Lock
- Java并发编程：volatile关键字解析
- Java并发编程：深入剖析ThreadLocal
- Java并发编程：CountDownLatch、CyclicBarrier和Semaphore
- Java并发编程：线程间协作的两种方式：wait、notify、notifyAll和Condition
- Synchronized与Lock
- JVM底层又是如何实现synchronized的
- Java synchronized详解
- synchronized 与 Lock 的那点事
- 深入研究 Java Synchronize 和 Lock 的区别与用法
- JAVA编程中的锁机制详解
- Java中的锁
- TreadLocal
- 深入JDK源码之ThreadLocal类
- 聊一聊ThreadLocal
- ThreadLocal
- ThreadLocal的内存泄露
- 多线程设计模式
- Java多线程编程中Future模式的详解
- 原子操作(CAS)
- [译]Java中Wait、Sleep和Yield方法的区别
- 线程池
- 如何合理地估算线程池大小？
- JAVA线程池中队列与池大小的关系
- Java四种线程池的使用
- 深入理解Java之线程池
- java并发编程III
- Java 8并发工具包漫游指南
- 聊聊并发
- 聊聊并发（一）——深入分析Volatile的实现原理
- 聊聊并发（二）——Java SE1.6中的Synchronized
- 文件
- 网络
- index
- 内存文章索引
- 基础文章索引
- 线程文章索引
- 网络文章索引
- IOC
- 设计模式文章索引
- 面试
- Java常量池详解之一道比较蛋疼的面试题
- 近5年133个Java面试问题列表
- Java工程师成神之路
- Java字符串问题Top10
- 设计模式
- Java：单例模式的七种写法
- Java 利用枚举实现单例模式
- 常用jar
- HttpClient和HtmlUnit的比较总结
- IO
- NIO
- NIO入门
- 注解
- Java Annotation认知(包括框架图、详细介绍、示例说明)