东东
发布于 2022-10-18 / 20 阅读 / 0 评论 / 0 点赞

ConcurrentHashMap

实现方式

1.7

JDK1.7中的ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即ConcurrentHashMap 把哈希桶切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。
image-1666079020690
其中，Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色；HashEntry 用于存储键值对数据。

1.8

放弃了Segment，直接用 Node数组+链表+红黑树 的数据结构来实现，并发控制使用Synchronized + CAS来操作，整个看起来就像是优化过且线程安全的HashMap。
image-1666079051521

put方法

1.7

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

然后：获取到锁后：

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

1.8

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

get方法

get方法是否需要枷锁？

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

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

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    // 存放数据的桶
    transient volatile HashEntry<K,V>[] table;

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

其他

为什么不支持key或者value为null？

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

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

我们用反证法来推理：

  1. 假设ConcurrentHashMap 允许存放值为 null 的value，这时有A、B两个线程，线程A调用ConcurrentHashMap .get(key)方法，返回为 null ，我们不知道这个 null 是没有映射的 null ，还是存的值就是 null 。
  2. 假设此时，返回为 null 的真实情况是没有找到对应的key。那么，我们可以用ConcurrentHashMap .containsKey(key)来验证我们的假设是否成立，我们期望的结果是返回false。
  3. 但是在我们调用ConcurrentHashMap .get(key)方法之后，containsKey方法之前，线程B执行了ConcurrentHashMap .put(key, null )的操作。那么我们调用containsKey方法返回的就是true了，这就与我们的假设的真实情况不符合了，这就有了二义性。

ConcurrentHashMap的并发度是多少？

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

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

ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。
这样迭代器线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。

IO
HashSet