HashMap、Hashtable、ConcurrentHashMap源码解析

ConcurrentHashMap是对Hashtable的改进，ConcurrentHashMap除了拥有Hashtable的操作，还在性能上进行优化，因为Hashtable在同步时锁住整个map，而ConcurrentHashMap采用的分段锁技术，只锁住了要操作的部分。所以在数据量很大的时候，可以感觉到ConcurrentHashMap的处理效率是远高于Hashtable的。

包括两个核心静态内部类 Segment 和 HashEntry。
①、Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶；
②、HashEntry 用来封装映射表的键-值对；
③、每个桶是由若干个 HashEntry 对象链接起来的链表。

JDK1.7存储结构：数组（Segment）+数组（HashEntry）+链表（HashEntry节点）

JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即 ConcurrentHashMap 把哈希桶数组切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。

如上图所示，首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。

Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。Segment 默认为 16，也就是并发度为 16。

存放元素的 HashEntry，也是一个静态内部类，用 volatile 修饰了 HashEntry 的数据 value 和 下一个节点 next，保证了多线程环境下数据获取时的可见性

JDK1.8存储结构：数组（Node）+链表（Node节点）+红黑树

JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的Node数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用 CAS + synchronized实现更加细粒度的锁。将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点（红黑树的根节点），就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。

JDK1.7：put()方法

先通过key找到承载的Segment对象位置，然后竞争操作Segment的独占锁，以确保操作线程。获取锁方式很简单就是tryLock()，如果获取锁失败，执行scanAndLockForPut方法scanAndLockForPut 实现也比较简单，循环调用tryLock，多次获取，如果循环次数retries 次数大于事先设置定好的MAX_SCAN_RETRIES，就执行lock() 方法，此方法会阻塞等待，一直到成功拿到Segment锁为止。

JDK1.7：get()方法

首先根据 key 计算出 hash 值定位到具体的 Segment ，再根据 hash 值获取定位 HashEntry 对象，并对 HashEntry 对象进行链表遍历，找到对应元素。由于HashEntry 涉及到的共享变量都使用 volatile 修饰，volatile 可以保证内存可见性，所以每次获取时都是最新值。

JDK1.8：put()方法

1. 根据 key 计算出 hash 值；

2. 判断是否需要进行初始化；

3. 定位到 Node，拿到首节点 f，判断首节点 f：

• 如果为 null ，则通过 CAS 的方式尝试添加；

• 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容；

• 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入；

JDK1.8：get()方法

1. 根据 key 计算出 hash 值，判断数组是否为空；

2. 如果是首节点，就直接返回；

3. 如果是红黑树结构，就从红黑树里面查询；

4. 如果是链表结构，循环遍历判断

同HashMap的源码解析参考上文