ConcurrentHashMap 实现原理

ConcurrentHashMap 实现原理

Posted by wenfengSAT on April 25, 2018

ConcurrentHashMap 实现原理

ConcurrentHashMap 实现原理

由于 HashMap 是一个线程不安全的容器,主要体现在容量大于总量*负载因子发生扩容时会出现环形链表从而导致死循环。

因此需要支持线程安全的并发容器 ConcurrentHashMap

JDK1.7 实现

数据结构

如图所示,是由 Segment 数组、HashEntry 数组组成,和 HashMap 一样,仍然是数组加链表组成。

ConcurrentHashMap 采用了分段锁技术,其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理,理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时,不会影响到其他的 Segment

get 方法

ConcurrentHashMapget 方法是非常高效的,因为整个过程都不需要加锁。

只需要将 Key 通过 Hash 之后定位到具体的 Segment ,再通过一次 Hash 定位到具体的元素上。由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的,保证了内存可见性,所以每次获取时都是最新值(volatile 相关知识点)。

put 方法

内部 HashEntry 类 :

    static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;

        HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

虽然 HashEntry 中的 value 是用 volatile 关键词修饰的,但是并不能保证并发的原子性,所以 put 操作时仍然需要加锁处理。

首先也是通过 Key 的 Hash 定位到具体的 Segment,在 put 之前会进行一次扩容校验。这里比 HashMap 要好的一点是:HashMap 是插入元素之后再看是否需要扩容,有可能扩容之后后续就没有插入就浪费了本次扩容(扩容非常消耗性能)。

而 ConcurrentHashMap 不一样,它是在将数据插入之前检查是否需要扩容,之后再做插入操作。

size 方法

每个 Segment 都有一个 volatile 修饰的全局变量 count ,求整个 ConcurrentHashMapsize 时很明显就是将所有的 count 累加即可。但是 volatile 修饰的变量却不能保证多线程的原子性,所有直接累加很容易出现并发问题。

但如果每次调用 size 方法将其余的修改操作加锁效率也很低。所以做法是先尝试两次将 count 累加,如果容器的 count 发生了变化再加锁来统计 size

至于 ConcurrentHashMap 是如何知道在统计时大小发生了变化呢,每个 Segment 都有一个 modCount 变量,每当进行一次 put remove 等操作,modCount 将会 +1。只要 modCount 发生了变化就认为容器的大小也在发生变化。

JDK1.8 实现

1.8 中的 ConcurrentHashMap 数据结构和实现与 1.7 还是有着明显的差异。

其中抛弃了原有的 Segment 分段锁,而采用了 CAS + synchronized 来保证并发安全性。

也将 1.7 中存放数据的 HashEntry 改为 Node,但作用都是相同的。

其中的 val next 都用了 volatile 修饰,保证了可见性。

put 方法

重点来看看 put 函数:

  • 根据 key 计算出 hashcode 。
  • 判断是否需要进行初始化。
  • f 即为当前 key 定位出的 Node,如果为空表示当前位置可以写入数据,利用 CAS 尝试写入,失败则自旋保证成功。
  • 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
  • 如果都不满足,则利用 synchronized 锁写入数据。
  • 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

get 方法

  • 根据计算出来的 hashcode 寻址,如果就在桶上那么直接返回值。
  • 如果是红黑树那就按照树的方式获取值。
  • 都不满足那就按照链表的方式遍历获取值。

总结

1.8 在 1.7 的数据结构上做了大的改动,采用红黑树之后可以保证查询效率(O(logn)),甚至取消了 ReentrantLock 改为了 synchronized,这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。