ConcurrentHashMap--原理

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

其他网址

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

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

简介

JDK7与JDK8区别

>

JDK1.7

JDK1.8

机制

ReentrantLock+Segment+HashEntry(数组加链表)

synchronized+CAS+HashEntry(数组加链表)+红黑树

读操作:volatile;写操作:synchronized+CAS

粒度

对需要进行数据操作的Segment加锁

对每个桶(数组项)加锁

JDK7

        在JDK1.7中ConcurrentHashMap采用了ReentrantLock+Segment+HashEntry(数组加链表)的方式实现。

        ConcurrentHashMap中的分段锁称为Segment,它类似于HashMap的结构,即:内部拥有一个Entry数组,数组中的每个元素又是一个链表,同时又是一个ReentrantLock(Segment继承了ReentrantLock)。

        ConcurrentHashMap使用分段锁技术,将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问,能够实现真正的并发访问。 

ConcurrentHashMap的内部结构图

ConcurrentHashMap--原理_第1张图片

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 Nodeimplements Map.Entry

{final int hash;final K key;volatile V val;volatile Node next;//... 省略部分代码}

        在JDK8中ConcurrentHashMap的结构,由于引入了红黑树,使得ConcurrentHashMap的实现非常复杂,我们都知道,红黑树是一种性能非常好的二叉查找树,其查找性能为O(logN),但是其实现过程也非常复杂,而且可读性也非常差,DougLea的思维能力确实不是一般人能比的,早期完全采用链表结构时Map的查找时间复杂度为O(N),JDK8中ConcurrentHashMap在链表的长度大于某个阈值(8)的时候会将链表转换成红黑树进一步提高其查找性能。

ConcurrentHashMap--原理_第2张图片

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[] tab = table;;) {

        Node 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(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

你可能感兴趣的