乐趣区

关于java:3秒搞定ConcurrentHashMap

jiezi

jdk8

总结

1、ConcurrentHashMap, 是 Java 并发包中自 JDK1.5 后 提供的一个 线程平安且高效的 HashMap 实现，能够用来代替 HashTable。间接实现了 ConcurrentMap 接口，同时继承了 AbstractMap 抽象类。

2、JDK1.8 后，ConcurrentHashMap 应用 CAS 算法联合 synchronized 同步锁的形式保障线程平安。

3、ConcurrentHashMap 的存储构造与 HashMap 基本一致，应用外部子类 Node 作为根本单元，存储链表节点数据，应用外部子类 TreeNode 存储树节点数据。同时减少了几个子类节点对象：ForwardingNode（转发节点）、TreeBin(红黑树根节点)、ReservationNode（保留节点）

UML

性能介绍

根本信息

包门路：java.util.concurrent
**
阐明：ConcurrentHashMap, 是 Java 并发包中自 JDK1.5 后 提供的一个 线程平安且高效的 HashMap 实现，能够用来代替 HashTable。间接实现了 ConcurrentMap 接口，同时继承了 AbstractMap 抽象类。

它沿用了与它同期间的 HashMap 版本的思维，（jdk1.8）底层仍然由“数组”+ 链表 + 红黑树的形式。然而为了做到并发，又减少了很多辅助的类，例如 TreeBin，Traverser 等对象外部类。

特点：1、线程平安 【JDK1.7 之前应用分段锁实现，JDK1.8 开始应用 CAS 算法实现】
           2、 不反对 null 的 key 和 value

ConcurrentMap 是如何保障线程平安的？

咱们晓得，HashTable 通过 synchronized 同步锁保障线程平安 ，同一时间只有有一个线程操作某个数据，就会锁定整个哈希表，其余线程就无奈对 HashTable 进行任何操作，只能期待该线程执行结束或开释锁，那这种形式其实是很不敌对且 效率很低 的。

分段锁

于是 ConcurrentHashMap 在 JDK1.7 应用了“分段锁” 这种机制，线程拜访数据时锁定一段范畴的数据，这样在容器内就会存在多个锁定区间的锁（相似数据库的“间隙锁”），每一把锁锁一段数据，这样在多线程拜访时不同段的数据时，就不会存在锁竞争了，这样便能够无效地进步并发效率

在 ConcurrentHashMap 中，Segment 是一个类，实际上每一个 segment 都是一个 HashEntry<K,V>[] table，table 中的每一个元素实质上都是一个 HashEntry 的单向队列。

每一个 Segment 都领有一个锁，当进行写操作时，只须要锁定一个 Segment，而其它 Segment 中的数据是能够拜访的。实质上 Segment 类 就是一个小的 hashmap，外面 table 数组存储了各个节点的数据

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

CAS+synchonized

JDK1.8 版本 则做了 2 点批改

1、将原先 table 数组+单向链表的数据结构，变更为 table 数组+单向链表+红黑树的构造.（与 HashMap 的变动基本一致）

2、勾销 segments 字段，间接采纳 transient volatile HashEntry<K,V>[] table 保留数据，采纳 table 数组元素作为锁，从而实现了 对每一行数据进行加锁 ， 并发管制应用 synchronized 和 CAS 来操作

synchronized 只锁定以后链表或红黑树的首节点，这样只有哈希不抵触（不操作同一地位元素），就不会产生并发，效率又晋升很多。

CAS（Compare And Swap，比拟替换 ）算法，它蕴含三个参数 CAS(V, E, N): V 示意要更新的变量, E 示意预期值, N 示意新值。根本思维就是 一直地去比拟以后内存中的变量值与你指定的一个变量值（预期值）是否相等，如果相等，则承受你指定的批改的值（新值），否则证实曾经有别的线程批改过该变量的值，回绝你的操作。因为以后线程中的值曾经不是最新的值，你的批改很可能会笼罩掉其余线程批改的后果。这一点与乐观锁，SVN 的思维是比拟相似的。

本文基于 JDK1.8 进行编写

简略应用

package com.java.map;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @description
 * @date: 2021-05-29 23:07
 */
public class ConcurrentHashMapCode {public static void main(String[] args) {Map<String,Object> concurrentHashMap = new ConcurrentHashMap<>();
        concurrentHashMap.put("one",1);
        concurrentHashMap.put("two", 2);
        System.out.println(concurrentHashMap);
        // 如果传入 key 对应的 value 曾经存在，就返回存在的 value，不进行替换
        concurrentHashMap.putIfAbsent("one", 2);
        concurrentHashMap.putIfAbsent("three", 3);
        System.out.println(concurrentHashMap);
    }
}

输入：

{one=1, two=2}
{one=1, two=2, three=3}

思考

ConcurrentHashMap 与 HashMap 的比拟

线程安全性

  • HashMap 不是线程平安的，多线程并发下扩容可能会导致数据笼罩的状况。
  • ConcurrentHashMap 线程平安，在 ConcurrentHashMap 中，大量应用了 U.compareAndSwapXXX 的办法，这个办法是利用一个 CAS 算法实现无锁化的批改值的操作，他能够大大降低锁代理的性能耗费。同时，在 ConcurrentHashMap 中还定义了三个原子操作，用于对指定地位的节点进行操作。这三种原子操作被宽泛的应用在 ConcurrentHashMap 的 get 和 put 等办法中。
  • 咱们能够发现 JDK8 中 ConcurrentHashMap 的实现应用的是锁拆散思维，只是锁住的是一个 node，而锁住 Node 之前的操作是基于在 volatile 和 CAS 之上无锁并且线程平安的。

null 值

  • HashMap 容许 key 和 value 为空
  • ConcurrentHashMap 不容许

迭代

  • HashMap 在用 iterator 遍历的同时，不容许批改 HashMap；
  • ConcurrentHashMap 容许该行为，并且更新对后续的遍历是可见的；

扩容机制不同

HashMap 的扩容机制

HashMap 的扩容，个别都蕴含两个步骤：
① table 数组的扩容
table 数组的扩容，个别就是新建一个 2 倍大小的槽数组，这个过程通过由一个单线程实现，且不容许呈现并发。

② 数据迁徙
所谓数据迁徙，就是把旧 table 中的各个槽中的结点重新分配到新 table 中。比方，单线程状况下，能够遍历原来的 table，而后 put 到新 table 中。

这一过程通常波及到槽中 key 的rehash，因为 key 映射到桶的地位与 table 的大小无关，新 table 的大小变了，key 映射的地位个别也会变动。

ConcurrentHashMap 的扩容机制

ConcurrentHashMap 在解决 rehash 的时候，并不会从新计算每个 key 的 hash 值 ，而是利用了一种很奇妙的办法。
ConcurrentHashMap 外部的 table 数组的大小必须为 2 的幂次，起因是让 key 均匀分布，缩小抵触，这只是其中一个起因。
另一个起因就是：当 table 数组的大小为 2 的幂次时，通过 key.hash & table.length-1 这种形式计算出的索引i，当 table 扩容后（2 倍），新的索引要么在原来的地位i，要么是i+n。

咱们来看个例子：

上图中：
扩容前，table 数组大小为 16，key1 和 key2 映射到同一个索引 5；
扩容后，table 数组的大小变成 2*16=32，key1 的索引不变，key2 的索引变成 5+16=21。

而且还有一个特点，扩容后 key 对应的索引如果产生了变动，那么其变动后的索引最高位肯定是 1 （见扩容后 key2 的最高位）。

   这种解决形式十分利于扩容时多个线程同时进行的数据迁徙操作，因为旧 table 的各个桶中的结点迁徙不会相互影响，所以就能够用“分治”的形式，将整个 table 数组划分为很多局部，每一部分蕴含肯定区间的桶，每个数据迁徙线程解决各自区间中的结点，对多线程同时进行数据迁徙十分无利。

                                    看到这里就点个赞吧👇分享更多技术文章, 去帮忙更多的人, 这里有我所有知识库哟~ 🐌   https://www.yuque.com/yingwenerjie  

退出移动版