java ConcurrentHashMap实现机制转自developerWorks 中文社区?注意：由于只能在表头插入，所以链表中节点的
java ConcurrentHashMap实现机制
转自 developerWorks 中文社区
?
注意：由于只能在表头插入，所以链表中节点的顺序和插入的顺序相反。
图 5. 执行删除之后的新链表
从上图可以看出，删除节点 C 之后的所有节点原样保留到新链表中；删除节点 C 之前的每个节点被克隆到新链表中，注意：它们在新链表中的链接顺序被反转了。
在执行 remove 操作时，原始链表并没有被修改，也就是说：读线程不会受同时执行 remove 操作的并发写线程的干扰。
综合上面的分析我们可以看出，写线程对某个链表的结构性修改不会影响其他的并发读线程对这个链表的遍历访问。
假设线程 M 在写入了 volatile 型变量 count 后，线程 N 读取了这个 volatile 型变量 count。
根据 happens-before 关系法则中的程序次序法则，A appens-before 于 B，C happens-before D。
根据 Volatile 变量法则，B happens-before C。
根据传递性，连接上面三个 happens-before 关系得到：A appens-before 于 B； B appens-before C；C happens-before D。也就是说：写线程 M 对链表做的结构性修改，在读线程 N 读取了同一个 volatile 变量后，对线程 N 也是可见的了。
虽然线程 N 是在未加锁的情况下访问链表。Java 的内存模型可以保证：只要之前对链表做结构性修改操作的写线程 M 在退出写方法前写 volatile 型变量 count，读线程 N 在读取这个 volatile 型变量 count 后，就一定能“看到”这些修改。
ConcurrentHashMap 中，每个 Segment 都有一个变量 count。它用来统计 Segment 中的 HashEntry 的个数。这个变量被声明为 volatile。
清单 8.Count 变量的声明
package com.zx.collection;import java.util.concurrent.*;import java.util.*;public class T { static final int threads = 5000; static final int NUMBER = 20000; public static void main(String[] args) throws Exception { Map<String, Integer> hashmapSync = Collections .synchronizedMap(new HashMap<String, Integer>()); Map<String, Integer> concurrentHashMap = new ConcurrentHashMap<String, Integer>(); Map<String, Integer> hashtable = new Hashtable<String, Integer>(); long totalA = 0; long totalB = 0; long totalC = 0; for (int i = 0; i <= 10; i++) { totalA += testPut(hashmapSync); totalB += testPut(concurrentHashMap); totalC += testPut(hashtable); } System.out.println("Put time HashMapSync=" + totalA + "ms."); System.out.println("Put time ConcurrentHashMap=" + totalB + "ms."); System.out.println("Put time Hashtable=" + totalC + "ms."); totalA = 0; totalB = 0; totalC = 0; for (int i = 0; i <= 10; i++) { totalA += testGet(hashmapSync); totalB += testGet(concurrentHashMap); totalC += testGet(hashtable); } System.out.println("Get time HashMapSync=" + totalA + "ms."); System.out.println("Get time ConcurrentHashMap=" + totalB + "ms."); System.out.println("Get time Hashtable=" + totalC + "ms."); } public static long testPut(Map<String, Integer> map) throws Exception { long start = System.currentTimeMillis(); for (int i = 0; i < threads; i++) { new MapPutThread(map).start(); } while (MapPutThread.counter > 0) { Thread.sleep(1); } return System.currentTimeMillis() - start; } public static long testGet(Map<String, Integer> map) throws Exception { long start = System.currentTimeMillis(); for (int i = 0; i < threads; i++) { new MapPutThread(map).start(); } while (MapPutThread.counter > 0) { Thread.sleep(1); } return System.currentTimeMillis() - start; } } class MapPutThread extends Thread { static int counter = 0; static Object lock = new Object(); private Map<String, Integer> map; private String key = this.getId() + ""; MapPutThread(Map<String, Integer> map) { synchronized (lock) { counter++; } this.map = map; } public void run() { for (int i = 1; i <= T.NUMBER; i++) { map.put(key, i); } synchronized (lock) { counter--; } } } class MapGetThread extends Thread { static int counter = 0; static Object lock = new Object(); private Map<String, Integer> map; private String key = this.getId() + ""; MapGetThread(Map<String, Integer> map) { synchronized (lock) { counter++; } this.map = map; } public void run() { for (int i = 1; i <= T.NUMBER; i++) { map.get(key); } synchronized (lock) { counter--; } } }
?
测试结果如下：
?
1、插入和获取1千万次static final int threads = 1000;static final int NUMBER = 1000;Put time HashMapSync=2859ms.Put time ConcurrentHashMap=1439ms.Put time Hashtable=2702ms.Get time HashMapSync=2781ms.Get time ConcurrentHashMap=1392ms.Get time Hashtable=2718ms.2、插入和获取1亿次static final int threads = 1000;static final int NUMBER = 10000;Put time HashMapSync=23078ms.Put time ConcurrentHashMap=8219ms.Put time Hashtable=22235ms.Get time HashMapSync=22889ms.Get time ConcurrentHashMap=8514ms.Get time Hashtable=22159ms.3、插入和获取5亿次static final int threads = 5000;static final int NUMBER = 10000;Put time HashMapSync=113501ms.Put time ConcurrentHashMap=38249ms.Put time Hashtable=109657ms.Get time HashMapSync=113498ms.Get time ConcurrentHashMap=38158ms.Get time Hashtable=106422ms.4、插入和获取10亿次static final int threads = 5000;static final int NUMBER = 20000;Put time HashMapSync=225376ms.Put time ConcurrentHashMap=77563ms.Put time Hashtable=211296ms.Get time HashMapSync=230001ms.Get time ConcurrentHashMap=77562ms.Get time Hashtable=218749ms.
?
?
?? 结果可以比较得知：在高并发的情况下，ConcurrentHashMap完胜其它同步Map
?
?
?
参考资料
学习
Java 语言规范（第 3 版）：Java 程序设计语言最权威的技术参考书。17.4 章探讨了 Java 内存模型。
Java 并发编程实践：本书作者系 Java 标准化组织 JSR 166 专家组的主要成员，本书是近年来 Java 并发编程图书中最值得一读的力作。5.2 章探讨了并发容器， 11.4 探讨了如何减少锁的竞争，11.5 比较了各种 Map 的性能，16 章探讨了 Java 内存模型。
Java 并发编程—设计原则与模式（第二版）：Java 并发编程领域的先驱 --Doug Lea 先生的经典著作。Doug Lea 先生是 JDK 中 util.concurrent 包的实现者。
多核系统的 Java 并发缺陷模式（bug patterns）：本文通过对 6 个鲜为人知的并发缺陷问题的讲解，阐述了威胁运行在多核系统上的 Java 应用程序线程安全和性能的原因，同时带领您研究并发缺陷模式（bug patterns），让您既能够提高对并发编程的理解，还能够了解如何发现无效或可能无效的编程方法。
Java 多线程与并发编程专题：本专题汇集了与 Java 多线程与并发编程相关的文章和教程，帮助读者理解 Java 并发编程的模式及其利弊，向读者展示了如何更精确地使用 Java 平台的线程模型。
developerWorks Java 技术专区：这里有数百篇关于 Java 编程各个方面的文章。
