HashTable

HashTable 容器使用 synchronized 来保证线程安全，但在线程竞争激烈的情况下 HashTable 的效率非常低下。因为当一个线程访问 HashTable 的同步方法， 其他线程也访问 HashTable 的同步方法时，会进入阻塞或轮询状态。如线程 1 使 用 put 进行元素添加，线程 2 不但不能使用 put 方法添加元素，也不能使用 get 方法来获取元素，所以竞争越激烈效率越低。

并发下的Map常见面试题汇总

Q：HashMap 和 HashTable 有什么区别？

A：

①、HashMap 是线程不安全的，HashTable 是线程安全的；

②、由于线程安全，所以 HashTable 的效率比不上 HashMap；

③、HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null， 而 HashTable 不允许；

④、HashMap 默认初始化数组的大小为 16，HashTable 为 11，前者扩容时， 扩大两倍，后者扩大两倍+1；

⑤、HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode

Q： Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是 线程安全，它与 HashTable 在线程同步上有什么不同？

A：

ConcurrentHashMap 类（是 Java 并发包 java.util.concurrent 中提供的一 个线程安全且高效的 HashMap 实现）。

HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）；

而针对 ConcurrentHashMap，在 JDK1.7 中采用分段锁的方式；JDK1.8 中 直接采用了 CAS（无锁算法）+synchronized，也采用分段锁的方式并大大缩小了 锁的粒度。

HashMap&ConcurrentHashMap 的区别？

A：

除了加锁，原理上无太大区别。

另外，HashMap 的键值对允许有 null，但是 ConCurrentHashMap 都不允许。 在数据结构上，红黑树相关的节点类

Q：为什么 ConcurrentHashMap 比 HashTable 效率要高？

A：

HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程 竞争一把锁，容易阻塞；

ConcurrentHashMap

JDK1.7 中使用分段锁（ReentrantLock+Segment+HashEntry），相当于把一 个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基 于 Segment，包含多个 HashEntry。

JDK1.8 中使用 CAS+synchronized+Node+ 红黑树。锁粒度：Node（首结 点）（实现 Map.Entry<K,V>）。锁粒度降低了。

Q：针对 ConcurrentHashMap 锁机制具体分析（JDK1.7VSJDK1.8）？

JDK1.7 中，采用分段锁的机制，实现并发的更新操作，底层采用数组+链表 的存储结构，包括两个核心静态内部类 Segment 和 HashEntry。

①、Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶；

②、HashEntry 用来封装映射表的键-值对；

③、每个桶是由若干个 HashEntry 对象链接起来的链表。

JDK1.8 中，采用 Node+CAS+Synchronized 来保证并发安全。取消类 Segment，直接用 table 数组存储键值对；当 HashEntry 对象组成的链表长度超 过 TREEIFY_THRESHOLD 时，链表转换为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树。

Q：ConcurrentHashMap 在 JDK1.8 中，为什么要使用内置synchronized 来代替重入锁 ReentrantLock？

A：

1、JVM 开发团队在 1.8 中对 synchronized 做了大量性能上的优化，而且基 于 JVM 的 synchronized 优化空间更大，更加自然。

2、在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存。

Q：ConcurrentHashMap 简单介绍？

A：

①、重要的常量： privatetransientvolatileintsizeCtl; 当为负数时，-1 表示正在初始化，-N 表示 N-1 个线程正在进行扩容； 当为 0 时，表示 table 还没有初始化； 当为其他正数时，表示初始化或者下一次进行扩容的大小。

②、数据结构： Node 是存储结构的基本单元，继承 HashMap 中的 Entry，用于存储数据； TreeNode 继承 Node，但是数据结构换成了二叉树结构，是红黑树的存储 结构，用于红黑树中存储数据； TreeBin 是封装 TreeNode 的容器，提供转换红黑树的一些条件和锁的控制。

③、存储对象时（put() 方法）：

1.如果没有初始化，就调用 initTable() 方法来进行初始化；

2.如果没有 hash 冲突就直接 CAS 无锁插入；

3.如果需要扩容，就先进行扩容；

4.如果存在 hash 冲突，就加锁来保证线程安全，两种情况：一种是链表形 式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入；

5.如果该链表的数量大于阀值 8，就要先转换成红黑树的结构，break 再一 次进入循环

6.如果添加成功就调用 addCount() 方法统计 size，并且检查是否需要扩容。

④、扩容方法 transfer()：默认容量为 16，扩容时，容量变为原来的两倍。 helpTransfer()：调用多个工作线程一起帮助进行扩容，这样的效率就会更高。

⑤、获取对象时（get()方法）：

1.计算 hash 值，定位到该 table 索引位置，如果是首结点符合就返回；

2.如果遇到扩容时，会调用标记正在扩容结点 ForwardingNode.find()方法， 查找该结点，匹配就返回；

3.以上都不符合的话，就往下遍历结点，匹配就返回，否则最后就返回 null。

Q：ConcurrentHashMap 的并发度是什么？

A：

1.7 中程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16，且可以在构造函数中设置。当用户设置并发度时， ConcurrentHashMap 会使用大于等于该值的最小 2 幂指数作为实际并发度（假如用户设置并发度为 17，实际并发度则为 32）。

1.8 中并发度则无太大的实际意义了，主要用处就是当设置的初始容量小于 并发度，将初始容量提升至并发度大小。