29 面试经典问题——详解Jdk7的ConcurrentHashmap实现
Diego38 82 1

1. 前言

从本章开始我们将要学习并发容器,Java 基础中的 ArrayList、HashSet、HashMap 都是在单线程场景下使用的,在多线程场景下,也有对应的容器类。

并不是所有的容器类都是简单的通过加锁来实现线程安全的,在这里面引入很多能减少锁开销的优化手段,目标只有一个,提升并发性能,更加适用于多线程场景,本节我们就学习 JDK7 中的 ConcurrentHashMap。

2. 为什么要使用 ConcurrentHashMap

在单线程场景下我们使用 HashMap 是没有问题的,但到了多线程场景时,在扩容的过程中甚至会出现环行链表,会引发死循环,导致 CPU 利用率 100%,产生故障。

Java8 的 HashMap 在多线程场景下不会出现环,但依然避免不了线程安全问题。以下脑图罗列了 JDK7 和 JDK8 中 HashMap 的知识要点。 image

HashMap 是基于数组实现的,数组元素存放了 KV 键值对,对 key 做 hash 计算得到数组的下标,如果出现 hash 冲突就通过链表或红黑树来解决,但贯穿始终并未做并发控制。

在 JDK1.5 之前,Collections 提供了静态方法 synchronizedMap 能包装返回一个线程安全的 Map,内部实现是利用代理模式,实现了 Map 接口,对所有对包装对象 Map 的操作都进行加锁控制,以实现线程安全,于此类似的方法还有 SynchronizedList、SynchronizedSet,但现阶段已经不建议使用了,因为性能比较差。

ConcurrentHashmap 就是在这种背景下应运而生的,ConcurrentHashmap 通过降低锁粒度 来提升并发性能的。因此我们在遇到多线程场景下操作 Map 时,一定要选用 ConcurrentHashmap。

3. JDK7 的 ConcurrentHashMap 的实现

相信大家都使用过 ConcurrentHashMap,在下一节会介绍 ConcurrentHashMap 一些特有的 API,比如 computeIfAbsent、putIfAbsent。

3.1 ConcurrentHashMap 的 Jdk7 与 Jdk8 版本对比

JDK7 的 ConcurrentHashMap 核心思想是将数组分成段,一个段包括多个数组元素,默认的段即 segment 默认 16 个,不可扩容,在做 put 操作时只会在分段上进行加锁,而不是整个 map。

那为什么又放弃 JDK7 的 ConcurrentHashMap 呢?

  • 分段锁无法扩容
  • JDK8 只锁数组头结点,比分段锁粒度更小,性能更高

JDK8 的 ConcurrentHashMap 很好的解决了上述两个问题,替代了 JDK7 的 ConcurrentHashMap,即便如此,也是有必要将 JDK7 的 ConcurrentHashMap 的设计思想了解清楚,为今后的举一反三提供帮助。

3.2 ConcurrentHashMap 的实现

image

3.2.1 ConcurrentHashMap 的数据结构

与 HashMap 的纯 Entry 数组不同,ConcurrentHashMap 对 Entry 数组进行二次分组,得到 Segment 数组, 默认的 segment 数组大小是 16,这与在创建 ConcurrentHashMap 时传入的 concurrentLevel 有关系;segment 数组不可扩容,内部是以数组 + 链表组成的。

 static final class Segment<K,V> extends ReentrantLock implements Serializable { 
     ...
 }

Segment 类是继承自 ReentrantLock 的,意味每个 Segment 会被加锁,至于加锁的时机继续下面的分析。

3.2.2 ConcurrentHashMap 的常见 API 分析

通过对常见 API 实现的分析,可以得出 ConcurrentHashMap 分段设计所带来的性能优化的提升,同时注意有些操作是有一定性能开销的。

  • get 整个 get 操作过程中并没有加锁,而是做了两次 hash 外加一次 volatile 读操作。 第一次 hash 是为了定位到 segment 数组下标,第二次 hash 是为了定位到 hashEntry 数组下标。

  • put segment 第一次 hash,然后内部再做一次 hash 定位到 segment 数组下标,由于 segment 元素是延迟初始化的,当发现该下标的 segment 不存在时会进行 CAS 初始化,segment 通过 unsafe.getobjectvolatile 获取和 putobjectVolatile 写入的,使用 CAS 初始化数组。

    private Segment<K,V> ensureSegment(int k) {
       final Segment<K,V>[] ss = this.segments;
       long u = (k << SSHIFT) + SBASE; // raw offset
       Segment<K,V> seg;
       if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
           Segment<K,V> proto = ss[0]; // use segment 0 as prototype
           int cap = proto.table.length;
           float lf = proto.loadFactor;
           int threshold = (int)(cap * lf);
           HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
           if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
               == null) { // recheck
               Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
               //这时有可能其他线程也在进行初始化segment操作,通过CAS抢占式的写入保证一致性
               while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                      == null) {
                   if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                       break;
               }
           }
       }
       return seg;
    }

    定位到下标并且确保当前 segment 元素存在后,并不会马上对 Segment 元素加锁进行 put 操作,而是先自旋尝试获取当前 Segment 锁,达到重试次数再强行 lock 当前 segment。

回忆下 Synchronized 锁的实现一节中,轻量级锁即是先自旋加锁,自旋加锁失败才会升级为重量级锁,当竞争程度比较低时,自旋尝试锁不会进入锁等待,对性能是友好的。

后续的 put 操作和 HashMap 里面的操作差不多,每次 put 都会记录一次修改次数,即当前 segment 的 modCount 加 1。

  • 扩容 扩容是在 put 操作时发现当前 Segment 的容量达到 capacity * loadFactor 触发的,由于 put 操作已经得到了当前 Segment 的独占锁,所以扩容过程不需要额外加锁。扩容的过程是将容量扩容一倍,然后对当前 segment 所有的 kv 重新进行 rehash 操作。

  • containsValue containsValue 有可能会 lock 住所有的 segments:

  1. 先遍历一遍 segment 将 modCount 加起来,如果 modCount 没有发生变化,并且找到了就返回
  2. 找不到并且 modCount 发生了变化,就这样重试几次
  3. 重试次数大于 2,还未找到,就锁住所有的 segments 进行遍历寻找 containsValue 也是利用了乐观锁思想,如果在遍历过程中,数据没有发生变化,则认定当前寻找到的是正确的,否则会重试。

与 containsValue 不同,containsKey 实际是 get (Key) 并没有加锁操作。

  • size

和 containsValue 一样,size 操作也有可能 lock 住所有的 segments 遍历 segments 数组,对 count 属性进行求和,汇总 modCount 求和如果与初始值一致就返回。否则达到重试次数就锁住所有的 segments 数组进行加和。

4. 总结

JDK1.7 版本的 ConcurrentHashMap 已经很少被使用了,但是其中的设计思路是很值得借鉴和学习了,不少面试官在相当长的一段时间都在使用 JDK1.7 的 ConcurrentHashMap,常常拿 JDK1.7 版本和 JDK1.8 版本的 ConcurrentHashMap 做对比,不求 JDK1.7 的 ConcurrentHashMap 源码级剖析,但需要了解其中的设计精髓,在之后的工作可以起到举一反三的作用。 image

预览图
评论区

索引目录