☕️【Java 技术之旅】【ConcurrentHashMap】深入浅出核心源码分析（JDK1.7 版本）

李浩宇/Alex

关注

发布于: 56 分钟前

☕️【Java技术之旅】【ConcurrentHashMap】深入浅出核心源码分析（JDK1.7版本）

前提概要

ConcurrentHashMap 是 Java 并发包中提供的一个线程安全且高效的 HashMap 实现，以及被广泛使用，经典的开源框架 Spring 的底层数据结构就是使用 ConcurrentHashMap 实现的。
ConcurrentHashMap 在并发编程的场景中使用频率非常之高，本文就来分析下 ConcurrentHashMap 的实现原理，并对其实现原理进行分析（JDK1.7)。
与同是线程安全的老大哥 HashTable 相比，它已经更胜一筹，因此它的锁更加细化，而不是像 HashTable 一样为几乎每个方法都添加了 synchronized 锁，这样的锁无疑会影响到性能。

实现原理

众所周知，哈希表是中非常高效，复杂度为 O(1)的数据结构，在 Java 开发中，我们最常见到最频繁使用的就是 HashMap 和 HashTable，但是在线程竞争激烈的并发场景中使用都不够合理。

HashMap：先说 HashMap，HashMap 是线程不安全的，在并发环境下，可能会形成环状链表（扩容时可能造成），导致 get 操作时，cpu 空转，所以，在并发环境中使用 HashMap 是非常危险的。
**HashTable：HashTable 和 HashMap 的实现原理几乎一样，差别：
HashTable 不允许 key 和 value 为 null；
HashTable 是线程安全的。
HashTable 线程安全的策略实现代价却太大了，简单粗暴，get/put 所有相关操作都是 synchronized 的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

HashTable 性能差主要是由于所有操作需要竞争同一把锁，而如果容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，这样便可以有效地提高并发效率。这就是 ConcurrentHashMap 所采用的"分段锁"思想。

ConcurrentHashMap 的主干是个 Segment 数组。

 final Segment<K,V>[] segments;

复制代码

Segment 继承 ReentrantLock，所以它就是一种可重入锁 ReentrantLock。
ConcurrentHashMap，一个 Segment 就是一个子哈希表，Segment 里维护了一个 HashEntry 数组，并发环境下，对于不同 Segment 的数据进行操作是不用考虑锁竞争的。

就按默认的 ConcurrentLevel 为 16 来讲，理论上就允许 16 个线程并发执行，有木有很酷

对于同一个 Segment 的操作才需考虑线程同步，不同的 Segment 则无需考虑。

Segment 类似于 HashMap，一个 Segment 维护着一个 HashEntry 数组

transient volatile HashEntry<K,V>[] table;

复制代码

HashEntry 是目前我们提到的最小的逻辑处理单元了。

一个 ConcurrentHashMap 维护一个 Segment 数组，一个 Segment 维护一个 HashEntry 数组。

static final class HashEntry<K,V> {        final int hash;        final K key;        volatile V value;        volatile HashEntry<K,V> next;        //其他省略}

复制代码

Segment 类似哈希表(HashTable)，那么一些属性就跟我们之前提到的 HashMap 差不离，比如负载因子 loadFactor，比如阈值 threshold 等等，看下 Segment 的构造方法

public Segment(float lf, int threshold, HashEntry<K,V>[] tab) {            this.loadFactor = lf;//负载因子            this.threshold = threshold;//阈值            this.table = tab;//主干数组即HashEntry数组}

复制代码

我们来看下 ConcurrentHashMap 的构造方法

public ConcurrentHashMap(int initialCapacity,                               float loadFactor, int concurrencyLevel) {          if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)              throw new IllegalArgumentException();          //MAX_SEGMENTS 为1<<16=65536，也就是最大并发数为65536          if (concurrencyLevel > MAX_SEGMENTS)              concurrencyLevel = MAX_SEGMENTS;          //2的sshif次方等于ssize，例:ssize=16,sshift=4;ssize=32,sshif=5         int sshift = 0;         //ssize 为segments数组长度，根据concurrentLevel计算得出         int ssize = 1;         while (ssize < concurrencyLevel) {             ++sshift;             ssize <<= 1;         }         //segmentShift和segmentMask这两个变量在      //定位segment时会用到，后面会详细讲         this.segmentShift = 32 - sshift;         this.segmentMask = ssize - 1;         if (initialCapacity > MAXIMUM_CAPACITY)             initialCapacity = MAXIMUM_CAPACITY;         // 计算cap的大小，即Segment中HashEntry的数组长度，       // cap也一定为2的n次方.         int c = initialCapacity / ssize;         if (c * ssize < initialCapacity)             ++c;         int cap = MIN_SEGMENT_TABLE_CAPACITY;         while (cap < c)             cap <<= 1;         // 创建segments数组并初始化第一个Segment，      // 其余的Segment延迟初始化         Segment<K,V> s0 =             new Segment<K,V>(loadFactor, (int)(cap * loadFactor),                              (HashEntry<K,V>[])new HashEntry[cap]);         Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];         UNSAFE.putOrderedObject(ss, SBASE, s0);         this.segments = ss;}

复制代码

初始化方法有三个参数，如果用户不指定则会使用默认值，initialCapacity 为 16，loadFactor 为 0.75（负载因子，扩容时需要参考），concurrentLevel 为 16。

Segment 数组的大小 ssize 是由 concurrentLevel 来决定的，但是却不一定等于 concurrentLevel，ssize 一定是大于或等于 concurrentLevel 的最小的 2 的次幂。

比如：默认情况下 concurrentLevel 是 16，则 ssize 为 16；若 concurrentLevel 为 14，ssize 为 16；若 concurrentLevel 为 17，则 ssize 为 32。

为什么 Segment 的数组大小一定是 2 的次幂？其实主要是便于通过按位与的散列算法来定位 Segment 的 index。

重要的属性

首先来看几个重要的属性，与 HashMap 相同的就不再介绍了，这里重点解释一下 sizeCtl 这个属性。可以说它是 ConcurrentHashMap 中出镜率很高的一个属性，因为它是一个控制标识符，在不同的地方有不同用途，而且它的取值不同，也代表不同的含义。

负数代表正在进行初始化或扩容操作

-1 代表正在初始化-N 表示有 N-1 个线程正在进行扩容操作

正数或 0 代表 hash 表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小，这一点类似于扩容阈值的概念。还后面可以看到，它的值始终是当前 ConcurrentHashMap 容量的 0.75 倍，这与 loadfactor 是对应的。

接下来，我们来看看 put 方法

public V put(K key, V value) {        Segment<K,V> s;        //concurrentHashMap不允许key/value为空        if (value == null)            throw new NullPointerException();        //hash函数对key的hashCode重新散列，避免差劲的不合理的hashcode，保证散列均匀        int hash = hash(key);        //返回的hash值无符号右移segmentShift位与段掩码进行位运算，     // 定位segment        int j = (hash >>> segmentShift) & segmentMask;        if ((s = (Segment<K,V>)       // nonvolatile; recheck       UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null)      //  in ensureSegment            s = ensureSegment(j);        return s.put(key, hash, value, false);}

复制代码

put 的主要逻辑也就两步：

定位 segment 并确保定位的 Segment 已初始化
调用 Segment 的 put 方法。

关于 segmentShift 和 segmentMask

segmentShift 和 segmentMask 这两个全局变量的主要作用是用来定位 Segment，int j =(hash >>> segmentShift) & segmentMask。

segmentMask：段掩码，假如 segments 数组长度为 16，则段掩码为 16-1=15；segments 长度为 32，段掩码为 32-1=31。这样得到的所有 bit 位都为 1，可以更好地保证散列的均匀性
segmentShift：2 的 sshift 次方等于 ssize，segmentShift=32-sshift。若 segments 长度为 16，segmentShift=32-4=28;若 segments 长度为 32，segmentShift=32-5=27。而计算得出的 hash 值最大为 32 位，无符号右移 segmentShift，则意味着只保留高几位（其余位是没用的），然后与段掩码 segmentMask 位运算来定位 Segment。

get/put 方法

get 方法

public V get(Object key) {        Segment<K,V> s;        HashEntry<K,V>[] tab;        int h = hash(key);        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;  //先定位Segment，再定位HashEntry        if ((s = (Segment<K,V>)       UNSAFE.getObjectVolatile(segments, u)) != null &&            (tab = s.table) != null) {            for (HashEntry<K,V> e = (HashEntry<K,V>)          UNSAFE.getObjectVolatile                     (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);                 e != null; e = e.next) {                K k;                if ((k = e.key) == key || (e.hash == h && key.equals(k)))                    return e.value;            }        }        return null;    }

复制代码

get 方法无需加锁，由于其中涉及到的共享变量都使用 volatile 修饰，volatile 可以保证内存可见性，所以不会读取到过期数据。

来看下 concurrentHashMap 代理到 Segment 上的 put 方法，Segment 中的 put 方法是要加锁的。只不过是锁粒度细了而已。

final V put(K key, int hash, V value, boolean onlyIfAbsent) {            HashEntry<K,V> node = tryLock() ? null :                scanAndLockForPut(key, hash, value);  //tryLock不成功时会遍历定位到的HashEnry位置的链表（遍历主要是为了使CPU缓存链表），若找不到，则创建HashEntry。  // tryLock一定次数后（MAX_SCAN_RETRIES变量决定），则lock。若遍历过程中，由于其他线程的操作导致链表头结点变化，则需要重新遍历。            V oldValue;            try {                HashEntry<K,V>[] tab = table;                int index = (tab.length - 1) & hash;        //定位HashEntry，可以看到，        //这个hash值在定位Segment时和在Segmen        //t中定位HashEntry都会用到，        //只不过定位Segment时只用到高几位。                HashEntry<K,V> first = entryAt(tab, index);                for (HashEntry<K,V> e = first;;) {                    if (e != null) {                        K k;                        if ((k = e.key) == key ||                            (e.hash == hash && key.equals(k))) {                            oldValue = e.value;                            if (!onlyIfAbsent) {                                e.value = value;                                ++modCount;                            }                            break;                        }                        e = e.next;                    }                    else {                        if (node != null)                            node.setNext(first);                        else                            node = new HashEntry<K,V>(hash, key, value, first);                        int c = count + 1;            //若c超出阈值threshold，需要扩容并rehash。扩容后的容量是当前容量的2倍。这样可以最大程度避免之前散列好的entry重新散列，具体在另一篇文章中有详细分析，不赘述。扩容并rehash的这个过程是比较消耗资源的。                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)                            rehash(node);                        else                            setEntryAt(tab, index, node);                        ++modCount;                        count = c;                        oldValue = null;                        break;                    }                }            } finally {                unlock();            }            return oldValue;        }

复制代码

总结

ConcurrentHashMap 作为一种线程安全且高效的哈希表的解决方案，尤其其中的"分段锁"的方案，相比 HashTable 的全表锁在性能上的提升非常之大。

发布于: 56 分钟前阅读数: 2

原文链接:【http://xie.infoq.cn/article/d45f4ef5bffb6eeb475c35d9b】。文章转载请联系作者。

李浩宇/Alex

关注

我们始于迷惘，终于更高水平的迷惘。 2020.03.25 加入

🏆 【酷爱计算机技术、醉心开发编程、喜爱健身运动、热衷悬疑推理的”极客狂人“】 🏅 【Java技术领域，MySQL技术领域，APM全链路追踪技术及微服务、分布式方向的技术体系等】 🤝未来我们希望可以共同进步🤝

发布

暂无评论

创作场景

☕️【Java 技术之旅】【ConcurrentHashMap】深入浅出核心源码分析（JDK1.7 版本）

前提概要

实现原理

ConcurrentHashMap 的主干是个 Segment 数组。

重要的属性

put 的主要逻辑也就两步：

get/put 方法

get 方法

总结

李浩宇/Alex

评论