转载

ConcurrentHashMap、HashTable、HashMap三兄弟

ConcurrentHashMap、HashMap、HashTable可以说是师出同门，但却各自“身怀绝技”。他们虽然同为K/V键值对的存储容器，但其内部存储结构却不尽相同，本文针对它们在线程同步中的关系、内部结构进行总结，以便在使用中可以综合比较，选择最适合的工具类。

转载请注明出处： http://www.wangjialong.cc/2018/04/24/map3compare/#more

HashTable

HashTable是三兄弟中最“老”的，从JDK1.0就存在了，它继承了Dictionary类，作为一个哈希表来使用，其key必须包含hashCode方法和equals方法。在JDK1.2之后，为了将其纳入 Java Collections Framework ，使其实现了Map接口，成为了Map家族的一员。

HashTable的内部实现是通过一个Entry数组存放bucket，当Hash冲突时，采用开链法，在对应的bucket之后添加节点，形成链表。其最终形式如下图：

ConcurrentHashMap、HashTable、HashMap三兄弟

HashTable是线程安全的，它实现的方式是将涉及到修改Hashtable的方法使用synchronized进行修饰，是多个线程在调用同步方法时，实际上其按照串行化方式运行。synchronized底层实际上是通过“对象锁”来实现的，也就是说，在调用synchronized修饰的方法时，首先需要获取该对象对应的一个锁，退出该方法时，再释放该对象锁。对象锁是和对象一一对应的，因此调用该方法的不同同步方法时，实际上也是串行化执行的。具体的例子就是，当线程A执行put操作，线程B执行get操作，这两个操作是无法并行的，因此HashTable的线程安全实现方式就是，强制多线程对该对象的访问串行化。

HashMap

HashMap从JDK1.2出现，实现了Map接口，是Map家族中使用最多的一个工具类，它改进了HashTable中很多低性能的方法，提供了相对高效的插入、查询操作。但与此同时，它摒弃了线程安全的实现。HashMap在JDK1.8之后引入了红黑树，当一个bucket对应的链表节点数大于8，将其“树化”，以提高查询性能。其最终形式如下图：

ConcurrentHashMap、HashTable、HashMap三兄弟

如图，当bucket[n]对应的链表节点数>8的时候，将其进行树化，生成对应的红黑树。红黑树是一个平衡二叉查找树，能够保证在O(logN)的时间复杂度内找到对应的k值，此时的N代表的是树中所有节点的个数。由于HashMap有rehash机制，当前节点总数超过阈值时，会进行table数组的扩容，因此单个红黑树的节点数不会太多，可以约等于常数，因此保证了在O(1)

的时间内找到key值，满足Hash表的特性。HashMap不是线程安全的，其在rehash的过程中，可能出现死循环，具体可参考从ConcurrentHashMap的演进看Java多线程核心技术 .

ConcurrentHashMap

ConcurrentHashMap是线程安全的HashMap，其内部的结构和HashMap非常相像，但为了满足线程安全的同时，提高并发度，内部定义了两个静态类HashEntry和Segment。HashEntry 用来封装映射表的键 / 值对；Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。其存储结构如图：

ConcurrentHashMap、HashTable、HashMap三兄弟

当需要获取Map中的某个key值对应的value时，需要首先找到对应的Segment，之后在其内部数组查找key的位置，找到之后，返回即可。ConcurrentHashMap利用volatile的内存可见性，基本实现了读时无锁，除非在读取时发现value为null，此时代表发生了重排序，需要尝试获取Segment的锁，重新获取value值即可获得最新value值。其详细原理可以参考探索 ConcurrentHashMap 高并发性的实现机制

上面的结构是1.8之前的ConcurrentHashMap，在JDK1.8中，已经不再使用两层数组来存储了，而是直接使用数组+开链法，对于数组的每个元素，使用细粒度锁来完成线程安全。其结构如图：

ConcurrentHashMap、HashTable、HashMap三兄弟

如图所示，JDK1.8之后，ConcurrentHashMap改造为在HashMap的基础上，直接对bucket加锁，当需要为对应的bucket中添加一个节点的时候，使用synchronized语句块，对该bucket入口节点进行加锁，实现线程同步。当读某个key对应的value时，仍然是无需加锁的。

总结

ConcurrentHashMap、HashTable、HashMap三兄弟都实现了Map接口，完成K/V对的存储。在使用中，视场景不同，可以选择不同的类实现，如在单线程的情况下，无需考虑线程安全性问题，直接使用HashMap可以获得很好的性能。在多线程情况下，为了达到线程安全，可以选择HashTable或者ConcurrentHashMap来完成，当Map的数据量很少时，为了实现的方便，可以直接使用HashTable；当K/V对很多时，且读请求占比很大，此时可以使用ConcurrentHashMap来实现，可以达到并发的需求。

原文 http://www.wangjialong.cc/2018/04/24/map3compare/

正文到此结束