乐趣区

关于java:ConcurrentHashMap原理

jiezi

原文网址：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><p>项 </p></td><td><p>JDK1.7</p></td><td><p>JDK1.8</p></td></tr><tr><td><p> 机制 </p></td><td><p>ReentrantLock+Segment+HashEntry（数组加链表）</p></td><td><p>synchronized+CAS+HashEntry（数组加链表）+ 红黑树 </p><p> 读操作：volatile；写操作：synchronized+CAS</p></td></tr><tr><td><p> 粒度</p></td><td><p> 对须要进行数据操作的 Segment 加锁 </p></td><td><p> 对每个桶（数组项）加锁 </p></td></tr></tbody></table>

JDK7

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

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

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

ConcurrentHashMap 的外部结构图

put 过程

  1. 对 key 进行 第 1 次 hash，通过 hash 值确定 Segment 的地位
  2. 在 Segment 内进行操作，获取锁
  3. 获取以后 Segment 的 HashEntry 数组后对 key 进行 第 2 次 hash，通过 hash 值确定在 HashEntry 数组的索引地位（头部）
  4. 通过继承 ReentrantLock 的 tryLock 办法尝试去获取锁，如果获取胜利就直接插入相应的地位，如果曾经有线程获取该 Segment 的锁，那以后线程会以自旋的形式去持续的调用 tryLock 办法去获取锁，超过指定次数就挂起，期待唤醒
  5. 而后对以后索引的 HashEntry 链进行遍历，如果有反复的 key，则替换；如果没有反复的，则插入到链头
  6. 开释锁 

get 操作

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

size 操作

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

  • 如果雷同，则示意期间没有产生过写入操作，就将原先遍历的后果返回。
  • 如果经判断发现两次统计出的 modCount 并不统一，要全副 Segment 加锁来进行 count 的获取和统计。在此期间每个 Segement 都被锁住，无奈进行其余操作，统计出的 count 天然很精确。

此构造优缺点

长处

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

毛病

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

JDK8

概述

        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 怎么确定数组的大小？

JDK8

初始化

put

        应用 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

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

size

退出移动版