面试： Hashtable vs ConcurrentHashMap

一、Hashtable和ConcurrentHashMap的不同和相同点

• Hashtable 与 ConcurrentHashMap 都是线程安全的Map 集合。
• Hashtable 并发度低，整个Hashtable对应一把锁，同一时刻，只能有一个线程操作它。
• 1.8之前ConcurrentHashMap使用了Segment +数组＋链表的结构，每个Segment对应一把锁，如果多个线程访问不同的Segment，则不会冲突。
• 1.8 开始ConcurrentHashMap将数组的每个头节点作为锁，如果多个线程访问的头节点不同，则不会冲突。

这是一个还不错的介绍ConcurrentHashMap的博客http://t.csdnimg.cn/WTPtQ

为什么HashTable慢? 它的并发度是什么? 那么ConcurrentHashMap并发度是什么?

Hashtable之所以效率低下主要是因为其实现使用了synchronized关键字对put等操作进行加锁，而synchronized关键字加锁是对整个对象进行加锁，也就是说在进行put等修改Hash表的操作时，锁住了整个Hash表，从而使得其表现的效率低下。

# ConcurrentHashMap在JDK1.7和JDK1.8中实现有什么差别? JDK1.8解決了JDK1.7中什么问题

• HashTable : 使用了synchronized关键字对put等操作进行加锁;
• ConcurrentHashMap JDK1.7: 使用分段锁机制实现;
• ConcurrentHashMap JDK1.8: 则使用数组+链表+红黑树数据结构和CAS原子操作实现;

# ConcurrentHashMap JDK1.7实现的原理是什么?

在JDK1.5~1.7版本，Java使用了分段锁机制实现ConcurrentHashMap.

• 简而言之，ConcurrentHashMap在对象中保存了一个Segment数组，即将整个Hash表划分为多个分段；
• 而每个Segment元素，它通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全；
• 这样，在执行put操作时首先根据hash算法定位到元素属于哪个Segment，然后对该Segment加锁即可。
• 因此，ConcurrentHashMap在多线程并发编程中可是实现多线程put操作。

• concurrencyLevel: Segment 数（并行级别、并发数）。
• 默认是 16，也就是说 ConcurrentHashMap 有 16 个 Segments，所以理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。
• 这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。

# ConcurrentHashMap JDK1.7中Segment数(concurrencyLevel)默认值是多少? 

默认是 16

# ConcurrentHashMap JDK1.7说说其put的机制?

整体流程还是比较简单的，由于有独占锁的保护，所以 segment 内部的操作并不复杂

• 计算 key 的 hash 值
• 根据 hash 值找到 Segment 数组中的位置 j； ensureSegment(j) 对 segment[j] 进行初始化（Segment 内部是由 数组+链表 组成的）
• 插入新值到 槽 s 中

# ConcurrentHashMap JDK1.7是如何扩容的?

• rehash

(注：segment 数组不能扩容，扩容是 segment 数组某个位置内部的数组 HashEntry[] 进行扩容)

# ConcurrentHashMap JDK1.8实现的原理是什么?

• 在JDK1.7之前，ConcurrentHashMap是通过分段锁机制来实现的，所以其最大并发度受Segment的个数限制。
• 因此，在JDK1.8中，ConcurrentHashMap的实现原理摒弃了这种设计，而是选择了与HashMap类似的数组+链表+红黑树的方式实现，而加锁则采用CAS和synchronized实现。
• 简而言之：数组+链表+红黑树，CAS

# ConcurrentHashMap JDK1.8是如何扩容的?

tryPresize, 扩容也是做翻倍扩容的，扩容后数组容量为原来的 2 倍

# ConcurrentHashMap JDK1.8链表转红黑树的时机是什么?

size = 8, log(N)

# ConcurrentHashMap JDK1.8是如何进行数据迁移的?

transfer, 将原来的 tab 数组的元素迁移到新的 nextTab 数组中