Hashtable、ConcurrentHashMap源码分析

为什么把这两个数据结构对比分析呢，相信大家都明白。首先二者都是线程安全的，但是二者保证线程安全的方式却是不同的。废话不多说了，从源码的角度分析一下两者的异同，首先给出二者的继承关系图。

 Hashtable类属性和方法源码分析

　　我们还是先给出一张Hashtable类的属性和方法图，其中Entry<K,V>是Hashtable类的静态内部类，该类继承自Map.Entry<K,V>接口。如下将会详细讲解Hashtable类中属性和方法的含义。

• 属性

1. Entry<?,?>[] table ：Entry类型的数组，用于存储Hashtable中的键值对；

2. int count ：存储hashtable中有多少个键值对

3. int threshold ：当count值大于该值是，哈希表扩大容量，进行rehash()

4. float loadFactor ：threshold=哈希表的初始大小*loadFactor，初始容量默认为11，loadFactor值默认为0.75

5. int modCount ：实现"fail-fast"机制，在并发集合中对Hashtable进行迭代操作时，若其他线程对Hashtable进行结构性的修改，迭代器会通过比较expectedModCount和modCount是否一致，如果不一致则抛出ConcurrentModificationException异常。如下通过一个抛出ConcurrentModificationException异常的例子说明。

    ConcurrentModificationException异常

   Hashtable的remove(Object key)方法见如下方法5，每一次修改hashtable中的数据都更新modCount的值。Hashtable内部类Enumerator<T>的相关部分代码如下：

    Enumerator类

• 方法

1. contains(Object value)，该方法是判断该hashtable中是否含有值为value的键值对，执行该方法需要加锁（synchronized）。hashtable中不允许存储空的value，所以当查找value为空时，直接抛出空指针异常。接下来是两个for循环遍历table。由如上的Entry实体类中的属性可以看出，next属性是指向与该实体拥有相同hashcode的下一个实体。

2. containsKey(Object key)，该方法是判断该hashtable中是否含有键为key的键值对，执行该方法也需要对整张table加锁（synchronized）。首先根据当前给出的key值计算hashcode，并有hashcode值计算该key所在table数组中的下标，依次遍历该下标中的每一个Entry对象e。由于不同的hashcode映射到数组中下标的位置可能相同，因此首先判断e的hashcode值和所查询key的hashcode值是否相同，如果相同在判断key是否相等。

3. get(Object key)，获取当前键key所对应的value值，本方法和containsKey(Object key)方法除了返回值其它都相同，如果能找到该key对应的value，则返回value的值，如果不能则返回null。

4.  put(K key, V value)，将该键值对加入table中。首先插入的value不能为空。其次如果当前插入的key值已经在table中存在，则用新的value替换掉原来的value值，并将原来的value值作为该方法的返回值返回。如果当前插入的key不在table中，则将该键值对插入。

   插入的方法首先判断当前table中的值是否大于阈值(threshold)，如果大于该阈值，首先对该表扩容，再将新的键值对插入table[index]的链表的第一个Entry的位置上。

5. remove(Object key)，将键为key的Entry从table表中移除。同样该方法也需要锁定整个table表。如果该table中存在该键，则返回删除的key的value值，如果当前table中不存在该key，则该方法的返回值为null。

6. replace(K key, V value)，将键为key的Entry对象值更新为value，并将原来的value最为该方法的返回值。

ConcurrentHashMap类属性和方法源码分析

　　ConcurrentHashMap在JDK1.8中改动还是挺大的。它摒弃了Segment（段锁）的概念，在实现上采用了CAS算法。底层使用数组+链表+红黑树的方式，但是为了做到并发，同时也增加了大量的辅助类。如下是ConcurrentHashMap的类图。

• 属性

//ConcurrentHashMap最大容量private static final int MAXIMUM_CAPACITY = 1 << 30;//ConcurrentHashMap初始默认容量private static final int DEFAULT_CAPACITY = 16;//最大table数组的大小static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//默认并行级别，主体代码并未使用private static final int DEFAULT_CONCURRENCY_LEVEL = 16;//加载因子，默认为0.75private static final float LOAD_FACTOR = 0.75f;//当hash桶中hash冲突的数目大于此值时，将链表转化为红黑树，加快hash的查找速度static final int TREEIFY_THRESHOLD = 8;//当hash桶中hash冲突小于等于此值时，会把红黑树转化为链表static final int UNTREEIFY_THRESHOLD = 6;//当table数组的长度大于该值时，同时满足hash桶中hash冲突大于TREEIFY_THRESHOLD时，才会把链表转化为红黑树static final int MIN_TREEIFY_CAPACITY = 64;//扩容操作中，transfer()方法允许多线程，该值表示一个线程执行transfer时，至少对连续的多少个hash桶进行transferprivate static final int MIN_TRANSFER_STRIDE = 16;//ForwardingNode的hash值，ForwardingNode是一种临时节点，在扩容中才会出现，不存储实际的数据static final int MOVED     = -1;//TreeBin的hash值，TreeBin是用于代理TreeNode的特殊节点，存储红黑树的根节点static final int TREEBIN   = -2;//用于和负数hash进行&运算，将其转化为正数static final int HASH_BITS = 0x7fffffff;

•  基本类
  

1. Node<K,V>：基本结点/普通节点。当table中的Entry以链表形式存储时才使用，存储实际数据。此类不会在ConcurrentHashMap以外被修改，而且该类的key和value永远不为null（其子类可为null，随后会介绍）。

    Node<K,V>

2. TreeNode：红黑树结点。当table中的Entry以红黑树的形式存储时才会使用，存储实际数据。ConcurrentHashMap中对TreeNode结点的操作都会由TreeBin代理执行。当满足条件时hash会由链表变为红黑树，但是TreeNode中通过属性prev依然保留链表的指针。

    TreeNode<K,V>

3. ForwardingNode：转发结点。该节点是一种临时结点，只有在扩容进行中才会出现，其为Node的子类，该节点的hash值固定为-1，并且他不存储实际数据。如果旧table的一个hash桶中全部结点都迁移到新的数组中，旧table就在桶中放置一个ForwardingNode。当读操作或者迭代操作遇到ForwardingNode时，将操作转发到扩容后新的table数组中去执行，当写操作遇见ForwardingNode时，则尝试帮助扩容。

    ForwardingNode<K,V>

   补充图一张说明扩容下是如何遍历结点的。

4. TreeBin：代理操作TreeNode结点。该节点的hash值固定为-2，存储实际数据的红黑树的根节点。因为红黑树进行写入操作整个树的结构可能发生很大变化，会影响到读线程。因此TreeBin需要维护一个简单的读写锁，不用考虑写-写竞争的情况。当然并不是全部的写操作都需要加写锁，只有部分put/remove需要加写锁。

    TreeBin<K,V>

5. ReservationNode：保留结点，也被称为空节点。该节点的hash值固定为-3，不保存实际数据。正常的写操作都需要对hash桶的第一个节点进行加锁，如果hash桶的第一个节点为null时是无法加锁的，因此需要new一个ReservationNode节点，作为hash桶的第一个节点，对该节点进行加锁。

    ReservationNode<K,V>

• ConcurrentHashMap方法

　　首先介绍一些基本的方法，这些方法不会直接用到，但却是理解ConcurrentHashMap常见方法前提，因为这些方法被ConcurrentHashMap常见的方法调用。然后在介绍完这些基本方法的基础上，再分析常见的containsValue、put、remove等常见方法。

1. Node<K,V>[] initTable()：初始化table的方法。初始化这个工作不是在构造函数中执行的，而是在put方法中执行，put方法中发现table为null时，调用该方法。

    initTable方法

2. 如下几个方法是用于读取table数组，使用Unsafe提供更强的功能代替普通的读写。

    View Code

3. 扩容方法：扩容分为两个步骤：第一步新建一个2倍大小的数组（单线程完成），第二步是rehash，把旧数组中的数据重新计算hash值放入新数组中。ConcurrentHashMap在第二步中处理旧table[index]中的节点时，这些节点要么在新table[index]处，要么在新table[index]和table[index+n]处，因此旧table各hash桶中的节点迁移不相互影响。ConcurrentHashMap扩容可以在多线程下完成，因此就需要计算每个线程需要负责处理多少个hash桶。

    计算每个transfer处理桶的个数

   计算完成之后每个transfer按照计算的值处理相应下标位置的桶，扩容操作从旧数组的末尾向前一次对hash桶进行处理。从末尾向前处理主要是减少和遍历数据时的锁冲突。从旧数组的末尾向前代码如下：

    计算每个transfer处理hash桶的区域

   

   扩容部分的完整代码如下：

    扩容代码

   如下是一个链表扩容的示意图，第一张是一个hash桶中的一条链表，其中蓝色节点表示第X位为0，而红色表示第X位为1，扩容后旧table[i]的桶中为一个ForwardingNode节点，而新nextTab[i]和nextTable[i+n]的桶中分别为第二张和第三张图。

   

   

4. Traverser只读遍历器：确切的说它不是方法，而是一个内部类。ConcurrentHashMap的多线程扩容增加了对ConcurrentHashMap遍历的困难。当遍历旧table时，如果遇到某个hash桶中为ForwardingNode节点，则遍历顺序参考基本类中ForwardingNode中的介绍。

    Traverser

5. containsValue(Object value)：遍历ConcurrentHashMap看是否存在值为value的Node。

    containsValue(Object value)

6. containsKey(Object key)：遍历ConcurrentHashMap看是否存在键为key的Node。

    containsKey(Object key)

7. put(K key, V value)：将该键值对插入ConcurrentHashMap中。

    put(K key, V value)

8. remove(Object key)：删除键为key的Node。同样其中也包含了对replace(Object key, V value, Object cv)的介绍。

    remove(Object key)

　　至此ConcurrentHashMap的主要方法也就介绍完了，综合比较Hashtable和ConcurrentHashMap，两者都是线程安全的，但是Hashtable是表级锁，而ConcurrentHashMap是段级锁，锁住的单个Node，而且ConcurrentHashMap可以并发读取。对整张表进行迭代时，ConcurrentHashMap使用了不同于Hashtable的迭代方式，而是一种弱一致性的迭代器。