高薪程序员&面试题精讲系列45之你熟悉ConcurrentHashMap吗？

一. 面试题及剖析

1. 今日面试题

请列举你在java.util.concurrent模块中熟悉的主要并发接口。

请问您对ConcurrentHashMap这一数据结构是否有所了解？

请阐述您所知的ConcurrentHashMap的关键特性。

请问您能否简要说明ConcurrentHashMap实现背后的机制？

在实现过程中，请问您主要依赖哪些基础数据结构？

请问在不使用加锁机制的情况下实现高并发访问，请问这是如何做到的？

您能否比较两者的性能特点与应用场景的不同？

请阐述两者的内存管理策略有何异同。

2. 题目剖析

今天的题目依然繁多，并且主要围绕集合展开。从名称上看,今天所涉及的集合与之前的HashMap存在密切关联,它们之间具有亲缘关系,在使用方法上基本一致[性能]上也相差不大,但在线程安全性方面相比传统的HashMap更具优势。因此,当我们处理多线程并发操作时,常常会用到这种ConcurrentHashMap,而在面试中常被问及它们之间的区别

ConcurrentHashMap是我们工作中常见考点之一，在面试中也经常出现相关问题，请各位务必重视并深入理解这一知识点。接下来 壹哥 就为我们全面解析ConcurrentHashMap的工作原理及相关优化技巧。

二. 背景概述

在复习ConcurrentHashMap之前¹号向大家简要介绍一些相关背景知识, 以便更好地理解为何需要学习这样一个全新的数据结构. 那么, 不使用现有的 HashMap 呢? 为什么还需要学习一个新的集合呢? 接下来让我们回顾一下 HashMap 的常见问题与不足之处.

1. JDK 8之前HashMap存在的问题

HashMap是我们开发过程中应用最广泛的集合容器之一；它通过键值对的形式实现数据存储功能；然而众所周知；在高并发环境下存在安全隐患；

当我们执行put(k,v)操作时，在进行数组扩容的过程中（即当current size等于capacity的时候），首先需要将原数组中的所有元素复制到新扩容的数组中，并对新数组进行rehash处理；然而在上述过程中（即当前容器已经是满的状态），如果其他线程也在执行类似的put()操作，则会出现如下情况：当出现两个元素具有相同哈希值的情况时，在这种情况下，则可以在同一数组下使用链表结构来解决冲突问题。

在JDK 8版本之前的HashMap实现中，在处理链表冲突节点方面采用了头插法策略来应对链表冲突节点的问题。当多线程环境下的高并发操作可能导致同一链表出现闭链情况时，则可能会引发get(k)操作陷入死循环状态。

2. JDK 8之后HashMap的改进

当然，在JDK 8之后对HashMap进行了显著优化。其底层采用了基于数组、链表及红黑树的数据结构来进行数据存储。值得注意的是，在重哈希过程中不再直接操作原链表而是通过复制算法创建了两套独立的链表分别完成对原链表中节点的分离操作。此外该版本采用了尾插法取代了传统的头插法因此即使在多线程环境下也能够保证较高的性能稳定性。

由于其不具备并发访问能力，在不进行较大的源码修改的情况下，默认情况下仍然无法有效处理高并发的应用场景。然而，在实际应用中，在多线程环境下可能会遇到以下问题：例如，在同时进行大量元素的添加操作时会导致数据不一致；而遍历Map时可能会触发异常。

总体而言，在单线程非并发环境中使用传统的HashMap是一种较为理想的状态。然而，在多线程并发环境中确实存在诸多挑战。鉴于此，我们需要采取相应的措施来解决这些问题或采取有效手段来规避潜在风险。

3. 并发安全的集合容器

有哪些解决办法？是否存在更为稳妥的Map集合实例？确实存在多种选择，请您参考以下三种操作方法：分别是...

• HashTable
• Collections.synchronizedMap(map)
• ConcurrentHashMap

针对前面所提及的三种并行集合操作，在处理大量并发请求时表现出较低的性能水平。我们随后将深入分析前两种方法的实际应用情况以及其潜在的问题所在。

Hashtable**：** HashTable是在put()、get()、size()等各种方法上添加 “synchronized” 锁，来保证线程安全，这会导致所有的并发操作都要竞争同一把锁，一个线程在进行同步操作时，其他线程只能等待，大大降低了并发操作的效率。

Collections.synchronizedMap()****： Collections提供了一个同步包装器方法synchronizedMap()，它虽然在方法中没有添加synchronized锁，但是 利用了 “this” 作为互斥的 mutex ，所以严格地说，synchronizedMap跟 HashTable 一样，对性能并没有实际的提升改进。

所以后来Java就提供了另一个专门适合多线程高并发环境中的集合--ConcurrentHashMap！

在本文中, ConcurrentHashMap被选定为主角;相较于前面介绍的两种Map集合的操作方式而言,在设计思想上经历了显著的变化,并显著提升了Map类操作的并发性能.

ConcurrentHashMap基于 Java 内存模型中的原子操作机制，在此基础上增添了多线程支持特性。它通过严格遵守Sun微系统建议的内存模型实现了线程安全性的保证，并且在处理大量并发操作时展现出显著性能优势。相比于传统 HashMap，在高强度并发操作中能够处理更多的任务并保证响应效率。

就其实现而言，在ConcurrentHashMap方面各不相同的JDK版本间存在显著差异。最明显的对比体现在JDK7和JDK8这两个版本之间，这种转变堪称根本性转变。本文将重点分析这两个版本间的具体差异，并着重介绍JDK8这一更为成熟稳定的版本的具体实现机制及其差异所在；由于JDK7已逐渐退出历史舞台，在实际应用中无需对其深入研究只需做基本了解即可

本文聚焦于JDK 8中的ConcurrentHashMap，在其主要属性与特征的基础上，深入分析了其构造方式、put操作流程以及相关的扩容机制、容量变化规律和get操作流程等关键环节。

三. ConcurrentHashMap简介

本节相关面试题:

你能简要说明 ConcurrentHashMap 的主要特性吗？
你能分享一下你对 java.util.concurrent 并发包中哪些API的了解吗？

1. ConcurrentHashMap概念特征

在多线程环境中运行时，默认的HashMap容易在数组扩张与再哈希过程中产生 自环死锁 和 不可见共享 的线程安全问题。然而现有的替代方案如HashTable和Collections.synchronizedMap()尽管能够实现并发操作但它仍依赖于一个 单个全局synchronized锁 来保证多个线程的一致访问从而导致了较低的性能表现。

自JDK 1.5版本起，在该包中引入了高效率的并行操作集合——ConcurrentHashMap（简称CHM）。它在读取数据时不需加锁，在执行write操作时则会施加锁。而内部主要采用了volatile、final以及基于比较算法协议（CAP）等无锁并行技术。这些技术的应用使得系统因互斥竞争导致的影响得到了显著降低，并显著提升了write操作效能的同时降低了对read一致性需求的要求。可以说它的设计与实现都非常巧妙。

在ConcurrentHashMap中(key和value都不允许为空)，如果违反此规定将导致NullPointerException

2. ConcurrentHashMap类关系

ConcurrentHashMap和普通的HashMap都继承自同一个基础抽象类AbstractMap。可以说它们是"亲密兄弟"。因此，在大多数特性及使用场景上，ConcurrentHashMap的表现与普通的HashMap非常接近。此外，在底层实现原理上也存在许多相似之处。

它们所处的包有所不同。具体来说，“ConcurrentHashMap”位于java.util.concurrent包中，“HashMap”则位于标准库中的java.util包内。请参见下图以获取更详细的实现信息。

关于ConcurrentHashMap概念及特征的概述中提到的不同版本之间存在显著差异。值得注意的是，在实际应用中不同版本间的差异显著。因此，在面试过程中通常会遇到需要了解不同版本间差异及各自特点的问题。接下来，壹哥将分别深入探讨JDK 7和JDK 8这两个具有代表性的版本。

四. 不同JDK版本中的ConcurrentHashMap对比

1. JDK 7的ConcurrentHashMap小结

在JDK 7实现的ConcurrentHashMap中，当处理的数据规模较大时（规模较大），哈希冲突的发生频率显著提高（发生频率显著提高）。这会导致链表中的增、删、查等操作的时间开销显著增加（可能导致增、删、查等操作的时间开销显著增加），从而可能会影响系统的运行效率（可能导致系统的运行效率降低）。

JDK 7 中的 ConcurrentHashMap 主要采用 Segment 分段锁机制来实现对 concurrent access 的控制，并将 Map 数据结构划分为多个独立的 Segment 区块以提高内存利用率。具体而言，在 put 操作时需要对该 Segment 区块施加锁定以防止 ConcurrentModificationException；而 get 操作则无需对该 Segment 加锁即可完成数据读取；为了保证操作的一致性和可观察性，在 get 操作前后需使用 volatile 关键字来确保数据可见性。

在统计全局数量的过程中，在如size变量的情况下，首先会通过反复计算modCount值来确定其准确值。随后，在这些尝试期间进行检查以确保没有其他线程正在进行修改操作：如果未发现任何修改动作，则可以直接返回当前的大小值；如果检测到有其他线程进行修改，则必须依次对每个Segment进行锁定以完成正确计数。

2. JDK 8的ConcurrentHashMap小结

改写后的内容：
>
> * 改用Node而非Segment能降低锁的粒度。
> * 设计了一种MOVED状态，在 resize 过程中，在线程2仍试图 put 数据时（即在线等待 resize 完成），线程1会介入协助完成 resize。
> 为了确保Node中某些操作的原子性，我们采用了三个CAS操作来替代传统的锁机制。
> sizeCtl中的不同取值分别代表不同的意义，并起到有效的控制作用。
> 我们选择了synchronized而非ReentrantLock以提升系统的性能。
>

五. 结语

本篇文章,"壹哥"暂且先为您做一下ConcurrentHashMap的基本介绍。具体来说就是围绕它的底层原理,数据结构以及相关的扩容机制和冲突解决方法。鉴于篇幅限制,"壹哥"会分多次为您详细讲解。期待您的持续关注。今天的知识你都掌握了吗？