转载

一文带你了解并发 HashMap 的一种简单实现

##前言

java.util.concurrent.ConcurrentHashMap, java.util.concurrent.ConcurrentHashMap 虽然效果不错，但其实现相当复杂。在开发一款工具的过程中，由于无法使用 java.util.concurrent.ConcurrentHashMap (工具的目标之一就是跟踪 ConcurrentHashMap 内部实现) 因此笔者决定自己实现一个 “乞丐版” computeIfAbsent 方法。这样一个简单可扩展的 ConcurrentHashMap 就唾手可得。

##1 算法

算法基于 Jeff Preshing[1] 与 Cliff Click[2] 博士的工作，使用了带线性探测的开放寻址。开放寻址即 key-value 存储在一个数组中。指向 key-value 的 index 等于 hashcode 对数组大小取模。线性探测表示，如果数组元素已占用则使用下一个数组元素。循环往复直到发现一个空的 slot。下面的示例中，在两个已占用的 slot 后面插入新元素：

为了保证算法的并发性，需要使用 compareAndSet 在空 slot 中填入新元素。这样可以保证“检查是否为 null 与填入新元素"是原子(atomic)操作。如果 compareAndSet 顺利执行就成功地插入了一个新元素，返回该元素；如果执行失败，则需要检查是否其他线程使用了相同的 key 进行插入操作。接着寻找下一个空 slot 继续尝试。算法源代码如下：

private static final VarHandle ARRAY = 
复制代码

1 工作原理上述方案之所以可以奏效，当线程读到的数组位置已填充元素则元素不变同时 key 也不变。唯一需要确认是，当前读取元素为 null 时另一个线程是否在这里进行了修改。上面通过使用 compareAndSet 确保了这种意外情况不会发生。由于算法本身不会移除 key 且 key 本身不可变 (immutable) 因此算法成立。

##2 改变大小

在调整大小过程中，需要确保新增元素不丢失即不更新当前数组。具体的做法，会把数组中每个空元素设为特殊值 MOVED_NULL_KEY。看到这个值，线程知道当前正在进行大小调整。待调整结束再插入元素。

HashMap 调整大小步骤如下：

把数组中所有值为 null 的元素设为 MOVED_NULL_KEY；
创建新数组；
拷贝所有当前数组的值到新数组；
设置 currentArray 为新数组。

实现代码：

private static final Object MOVED_NULL_KEY = new Object();  
复制代码

3 基准测试

不同 HashMap 的实现取决于具体负载以及哈希函数，测试结果仅供参考。下面使用 JMH 用随机数 key 调用 computeIfAbsent。基准测试方法的代码如下：

测试环境：Intel Xeon Platinum 8124M CPU @ 3.00GHz, 两个 CPU 插槽 (18核/槽), 每个核心启动2个硬件线程；JVM 使用 Amazon Corretto 11。

新算法的 map 大小与ConcurrentHashMap 类似。500万随机key， java.util.concurrent.ConcurrentHashMap 需要285M字节，新 map 需要253M字节。

##4 差异分析

如果其他线程已更新空 slot，新 map 会进行重试。java.util.concurrent.ConcurrentHashMap 使用 array bin 作为同步块监视器，因此同一时刻只有一个线程修改 bin 中的内容。由此带来了差异：新 map 会多次调用回调函数进行计算，每次更新失败会调用一次方法；而 java.util.concurrent.ConcurrentHashMap 最多只计算一次。