关于java:ConcurrentHashMap原理

4次阅读

共计 2980 个字符，预计需要花费 8 分钟才能阅读完成。

原文网址：ConcurrentHashMap– 原理 \_IT 利刃出鞘的博客 -CSDN 博客

ConcurrentHashMap 源码解析 JDK8\_沈世钧的博客 -CSDN 博客
详解 ConcurrentHashMap 及 JDK8 的优化 \_全菜工程师小辉的博客 -CSDN 博客
ConcurrentHashMap 源码剖析（JDK8 版本）\_惟愿无事 -CSDN 博客

Hashmap1.7 和 1.8 区别 +ConcurrentHashmap1.7 和 1.8 区别 \_hellodake 的博客 -CSDN 博客

JDK7 与 JDK8 区别

> <table align=”center”><tbody><tr><td>项 </td><td>JDK1.7</td><td>JDK1.8</td></tr><tr><td> 机制 </td><td>ReentrantLock+Segment+HashEntry（数组加链表）</td><td>synchronized+CAS+HashEntry（数组加链表）+ 红黑树 读操作：volatile；写操作：synchronized+CAS</td></tr><tr><td> 粒度</td><td> 对须要进行数据操作的 Segment 加锁 </td><td> 对每个桶（数组项）加锁 </td></tr></tbody></table>

在 JDK1.7 中 ConcurrentHashMap 采纳了ReentrantLock+Segment+HashEntry（数组加链表）的形式实现。

ConcurrentHashMap 中的分段锁称为 Segment，它相似于 HashMap 的构造，即：外部领有一个 Entry 数组，数组中的每个元素又是一个链表，同时又是一个 ReentrantLock（Segment 继承了 ReentrantLock）。

ConcurrentHashMap 应用分段锁技术，将数据分成一段一段的存储，而后给每一段数据配一把锁，当一个线程占用锁拜访其中一个段数据的时候，其余段的数据也能被其余线程拜访，可能实现真正的并发拜访。

ConcurrentHashMap 的外部结构图

put 过程

对 key 进行 第 1 次 hash，通过 hash 值确定 Segment 的地位

在 Segment 内进行操作，获取锁

获取以后 Segment 的 HashEntry 数组后对 key 进行 第 2 次 hash，通过 hash 值确定在 HashEntry 数组的索引地位（头部）

通过继承 ReentrantLock 的 tryLock 办法尝试去获取锁，如果获取胜利就直接插入相应的地位，如果曾经有线程获取该 Segment 的锁，那以后线程会以自旋的形式去持续的调用 tryLock 办法去获取锁，超过指定次数就挂起，期待唤醒

而后对以后索引的 HashEntry 链进行遍历，如果有反复的 key，则替换；如果没有反复的，则插入到链头

开释锁

get 操作

和 put 操作相似，也是要两次 hash。然而 get 操作的 Concurrenthashmap 不须要加锁，起因是存储元素都标记了 volatile。

size 操作

size 操作就是遍历两次所有的 Segments，每次记录 Segment 的 modCount 值，而后将两次的 modCount 进行比拟

如果雷同，则示意期间没有产生过写入操作，就将原先遍历的后果返回。

如果经判断发现两次统计出的 modCount 并不统一，要全副 Segment 加锁来进行 count 的获取和统计。在此期间每个 Segement 都被锁住，无奈进行其余操作，统计出的 count 天然很精确。

此构造优缺点

长处

写操作的时候能够只对元素所在的 Segment 进行加锁即可，不会影响到其余的 Segment。

毛病

Hash 的过程要比一般的 HashMap 要长

概述

JDK8 中 ConcurrentHashMap 构造基本上和 HashMap 一样，采纳了（synchronized+CAS+HashEntry（数组加链表）+ 红黑树） 的实现形式来设计。读操作应用 CAS，写操作应用 synchronized。

JDK8 中彻底放弃了 Segment 转而采纳的是 Node，其设计思维也不再是 JDK1.7 中的分段锁思维。

Node：保留 key，value 及 key 的 hash 值的数据结构。其中 value 和 next 都用 volatile 润饰，保障并发的可见性。
class Node<K,V>implements Map.Entry<K,V>

{final int hash;final K key;volatile V val;volatile Node<K,V> next;//... 省略局部代码}
在 JDK8 中 ConcurrentHashMap 的构造，因为引入了红黑树，使得 ConcurrentHashMap 的实现非常复杂，咱们都晓得，红黑树是一种性能十分好的二叉查找树，其查找性能为 O（logN），然而其实现过程也非常复杂，而且可读性也十分差，DougLea 的思维能力的确不是个别人能比的，晚期齐全采纳链表构造时 Map 的查找时间复杂度为 O（N），JDK8 中 ConcurrentHashMap 在链表的长度大于某个阈值（8）的时候会将链表转换成红黑树进一步提高其查找性能。

size 办法

ConcurrentHashMap 怎么确定数组的大小？

应用 CAS 操作，…….。

线程拜访哈希表的 bucket 时，应用 sychronizeded 关键字，避免多个线程同时操作同一个 bucket(即锁住 bucket)。如果该结点的 hash 值不少于 0，则遍历链表更新节点或插入新节点；如果该节点是 TreeBin 类型的节点，阐明是红黑树结构，则通过 putTreeVal 办法往红黑树中插入节点；更新了节点数量，还要思考扩容和链表转红黑树。
final V putVal(K key, V value, boolean onlyIfAbsent) {if (key == null || value == null) throw new NullPointerException();

 int hash = spread(key.hashCode());

 for (Node<K,V>[] tab = table;;) {

 Node<K,V> f; int n, i, fh;

 if (tab == null || (n = tab.length) == 0)

 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {

 if (casTabAt(tab, i, null,

 new Node<K,V>(hash, key, value, null)))

 break; // no lock when adding to empty bin

 else if ((fh = f.hash) == MOVED)

 tab = helpTransfer(tab, f);

 if (binCount >= TREEIFY_THRESHOLD)

get 操作能够无锁 (不加锁) 是因为 Node 元素的 val 指针和 next 指针用 volatile 润饰的，在多线程环境下，线程 A 批改结点的 val 或者新增结点的时候，对线程 B 都是可见的。

正文完