深入解析 ConcurrentHashMap:从 JDK 1.7 到 JDK 1.8

✨探索Java基础 ConcurrentHashMap✨

引言

ConcurrentHashMap 是 Java 中一个线程安全的高效 Map 集合。它在多线程环境下提供了高性能的数据访问和修改能力。本文将详细探讨 ConcurrentHashMap 在 JDK 1.7 和 JDK 1.8 中的不同实现方式,以及它们各自的优缺点。

基本概念

ConcurrentHashMap 是一个线程安全的哈希表实现,适用于高并发场景。它的设计目标是在保证线程安全的同时,提供尽可能高的性能。

JDK 1.7 版本的 ConcurrentHashMap

接下来看一张图片:

数据结构

在 JDK 1.7 中,ConcurrentHashMap 使用 分段锁(Segment) 的设计。每个 Segment 是一个独立的小哈希表,并且每个 Segment 都有自己的锁。这种设计允许多个线程同时访问不同的 Segment,从而提高并发性能。

  • Segment 数组:默认是 16 个 Segment。
  • HashEntry 数组:每个 Segment 内部有一个 HashEntry 数组,用于存储具体的元素。
  • 链表:如果发生哈希冲突,会使用单向链表来存储冲突的节点。

存储流程

  1. 计算 key 的哈希值:通过 key 的哈希值确定 Segment 数组的下标。
  2. 获取 Segment 锁:对对应的 Segment 进行加锁。
  3. 确定 HashEntry 数组下标:再次通过哈希值确定 HashEntry 数组中的下标。
  4. 存储数据:将数据存入 HashEntry 数组中,如果发生冲突,则挂载到单向链表上。
  5. 附图:

扩容机制

  • 基于 Segment:每个 Segment 维护自己的负载因子,当某个 Segment 中的元素数量超过阈值时,该 Segment 会单独进行扩容。
  • 局部扩容:只影响当前 Segment,不会影响其他 Segment。

size 方法

  • 尝试三次不加锁获取 sum:如果三次总数相同,直接返回;否则,加锁计算总和。

JDK 1.8 版本的 ConcurrentHashMap

看图:

数据结构

在 JDK 1.8 中,ConcurrentHashMap 取消了 Segment 设计,采用了与 HashMap 类似的数据结构:数组 + 链表/红黑树。

  • Node 数组:类似于 HashMap 的数组。
  • 链表/红黑树:当链表长度超过一定阈值时,会转换为红黑树以提高查询效率。

存储流程

  1. 计算 key 的哈希值:通过 key 的哈希值确定 Node 数组的下标。
  2. CAS 添加新节点:使用 CAS 操作尝试添加新节点。
  3. 锁定首节点:如果 CAS 失败或需要更新链表/红黑树,使用 synchronized 锁定首节点。
  4. 存储数据:将数据存入链表或红黑树中。

扩容机制

  • 全局扩容:当整个 ConcurrentHashMap 的元素数量超过阈值时,整个数组会进行扩容。
  • 渐进式扩容:多个线程共同参与扩容操作,逐步迁移旧数据到新数组中,降低扩容时的性能开销。

size 方法

  • 类似 LongAdder 的思想:使用 baseCount 和 counterCells 数组来维护计数。
  • 减少竞争:通过分散计数到多个 counterCell 来减少对单个变量的竞争压力。

代码示例

JDK 1.7 版本

// Segment 类
static final class Segment<K,V> extends ReentrantLock implements Serializable {
    private final int threshold;
    transient volatile HashEntry<K,V>[] table;
    transient int count;
    transient int modCount;

    // 构造函数
    Segment(int initialCapacity, float loadFactor) {
        this.threshold = (int) (initialCapacity * loadFactor);
        setTable(HashEntry.<K,V>newArray(initialCapacity));
    }

    // put 方法
    V put(K key, int hash, V value, boolean onlyIfAbsent) {
        lock(); // 加锁
        try {
            int c = count;
            if (c++ > threshold) // 需要扩容
                rehash();
            HashEntry<K,V>[] tab = table;
            int index = hash & (tab.length - 1);
            HashEntry<K,V> first = tab[index];
            HashEntry<K,V> e = first;
            while (e != null && (e.hash != hash || !key.equals(e.key)))
                e = e.next;

            V oldValue;
            if (e != null) {
                oldValue = e.value;
                if (!onlyIfAbsent)
                    e.value = value;
            } else {
                oldValue = null;
                ++modCount;
                tab[index] = new HashEntry<>(key, hash, first, value);
            }
            return oldValue;
        } finally {
            unlock(); // 解锁
        }
    }
}

JDK 1.8 版本

// Node 类
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;

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

    public final K getKey()       { return key; }
    public final V getValue()     { return val; }
    public final String toString() { return key + "=" + val; }
}

// putVal 方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 转换为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // 存在键冲突
            V oldValue = e.val;
            if (!onlyIfAbsent || oldValue == null)
                e.val = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

总结

  • JDK 1.7:使用分段锁(Segment)和 ReentrantLock,每个 Segment 是一个独立的小哈希表,适合中等并发场景。
  • JDK 1.8:采用 CAS 操作和 synchronized 锁定链表或红黑树的首节点,提供了更细粒度的锁,适合高并发场景。

通过这些改进,JDK 1.8 版本的 ConcurrentHashMap 在性能和并发控制方面有了显著的提升。

觉得有用的话可以点点赞 (*/ω\*),支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。

上一篇:《如何高效学习》-第二部分 整体性学习技术


下一篇:求职Leetcode题目(12)