↓跳到主要内容
  1. 所有文章/
  2. Java集合相关笔记/

ConcurrentHashMap相关

·📄 3305 字·🍵 7 分钟
技术探索 Java集合 数据结构
目录

实现原理 #

ConcurrentHashMap 在 JDK1.7 和 JDK1.8 的实现方式是不同的。

  • 先来看下JDK1.7

    JDK1.7中的ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即ConcurrentHashMap 把哈希桶切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。

    其中，Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色；HashEntry 用于存储键值对数据。

    ConcurrentHashMap-jdk1.7.png

    首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

  • 再来看下JDK1.8

    在数据结构上， JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用CAS + synchronized实现更加低粒度的锁。

    将锁的级别控制在了更细粒度的哈希桶元素级别，也就是说只需要锁住这个链表头结点（红黑树的根节点），就不会影响其他的哈希桶元素的读写，大大提高了并发度。

    ConcurrentHashMap-jdk1.8.png

put 方法执行逻辑 #

  • 先来看JDK1.7

    首先，会尝试获取锁，如果获取失败，利用自旋获取锁；如果自旋重试的次数超过 64 次，则改为阻塞获取锁。

    获取到锁后：

    1. 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
    2. 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
    3. 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
    4. 释放 Segment 的锁。

  • 再来看JDK1.8

    大致可以分为以下步骤：

    1. 根据 key 计算出 hash值。
    2. 判断是否需要进行初始化。
    3. 定位到 Node，拿到首节点 f，判断首节点 f：
      • 如果为 null ，则通过cas的方式尝试添加。
      • 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容。
      • 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入。
    4. 当在链表长度达到8的时候，数组扩容或者将链表转换为红黑树。 源码分析可看这篇文章：面试 ConcurrentHashMap ，看这一篇就够了！

get 方法是否要加锁？ #

get 方法不需要加锁。因为 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。

这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 安全效率高的原因之一。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    //可以看到这些都用了volatile修饰
    volatile V val;
    volatile Node<K,V> next;
}

get方法不需要加锁与volatile修饰的哈希桶有关吗？ #

没有关系。哈希桶table用volatile修饰主要是保证在数组扩容的时候保证可见性。

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

    // 存放数据的桶
    transient volatile HashEntry<K,V>[] table;

ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？ #

我们先来说value 为什么不能为 null ，因为ConcurrentHashMap 是用于多线程的 ，如果map.get(key)得到了 null ，无法判断，是映射的value是 null ，还是没有找到对应的key而为 null ，这就有了二义性。

而用于单线程状态的HashMap却可以用containsKey(key) 去判断到底是否包含了这个 null 。

我们用反证法来推理：

假设ConcurrentHashMap 允许存放值为 null 的value，这时有A、B两个线程，线程A调用ConcurrentHashMap .get(key)方法，返回为 null ，我们不知道这个 null 是没有映射的 null ，还是存的值就是 null 。

假设此时，返回为 null 的真实情况是没有找到对应的key。那么，我们可以用ConcurrentHashMap .containsKey(key)来验证我们的假设是否成立，我们期望的结果是返回false。

但是在我们调用ConcurrentHashMap .get(key)方法之后，containsKey方法之前，线程B执行了ConcurrentHashMap .put(key, null )的操作。那么我们调用containsKey方法返回的就是true了，这就与我们的假设的真实情况不符合了，这就有了二义性。

总结：key和value都不能为null，因为有两种情况都会导致取到的值为null，因此在多线程情况下无法判断是那种情况导致的。

至于ConcurrentHashMap 中的key为什么也不能为 null 的问题，源码就是这样写的，哈哈。如果面试官不满意，就回答因为作者Doug不喜欢 null ，所以在设计之初就不允许了 null 的key存在。

想要深入了解的小伙伴，可以看这篇文章这道面试题我真不知道面试官想要的回答是什么

并发度 #

在JDK1.7中，并发度默认是16，这个值可以在构造函数中设置。如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度，也就是比如你设置的值是17，那么实际并发度是32。

ConcurrentHashMap 迭代器是强一致性还是弱一致性？ #

与HashMap迭代器是强一致性不同，ConcurrentHashMap 迭代器是弱一致性。

ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。

这样迭代器线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。

想要深入了解的小伙伴，可以看这篇文章[为什么ConcurrentHashMap 是弱一致的](http://ifeve.com/ConcurrentHashMap -weakly-consistent/)

JDK1.7与JDK1.8 中ConcurrentHashMap 的区别 #

  • 数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
  • 保证线程安全机制：JDK1.7采用Segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8 采用CAS+Synchronized保证线程安全。
  • 锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
  • 链表转化为红黑树: 定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
  • 查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

ConcurrentHashMap 和Hashtable的效率哪个更高？为什么？ #

ConcurrentHashMap 的效率要高于Hashtable，因为Hashtable给整个哈希表加了一把大锁从而实现线程安全。而ConcurrentHashMap 的锁粒度更低，在JDK1.7中采用分段锁实现线程安全，在JDK1.8 中采用CAS+Synchronized实现线程安全。

Hashtable的锁机制 #

Hashtable是使用Synchronized来实现线程安全的，给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争激烈的多线程场景中性能就会非常差！

ConcurrentHashMap-hashtable.png

其他多线程安全的Map #

还可以使用Collections.synchronizedMap方法，对方法进行加同步锁

private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize

        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNon null (m);
            mutex = this;
        }

        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }
    // 省略部分代码
    }

如果传入的是 HashMap 对象，其实也是对 HashMap 做的方法做了一层包装，里面使用对象锁来保证多线程场景下，线程安全，本质也是对 HashMap 进行全表锁。在竞争激烈的多线程环境下性能依然也非常差，不推荐使用！

HashSet 和 HashMap #

image-20210403193010949.png

补充HashSet的实现：HashSet的底层其实就是HashMap，只不过我们HashSet是实现了Set接口并且把数据作为K值，而V值一直使用一个相同的虚值来保存。如源码所示：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;// 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
}

由于HashMap的K值本身就不允许重复，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V，那么在HashSet中执行这一句话始终会返回一个false，导致插入失败，这样就保证了数据的不可重复性。

↑ ↓