一文带你了解并发 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 后面插入新元素:

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

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

private static final VarHandle ARRAY = 
复制代码

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

##2 改变大小

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

HashMap 调整大小步骤如下:

  1. 把数组中所有值为 null 的元素设为 MOVED_NULL_KEY;
  2. 创建新数组;
  3. 拷贝所有当前数组的值到新数组;
  4. 设置 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。

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

新算法的 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 最多只计算一次。

总结

自己实现的 computeIfAbsent 比 java.util.concurrent.ConcurrentHashMap 扩展性更好。文中的算法之所以简单,因为没有涉及元素删除以及 key 的改变。可以用来存储 class 以及相关元数据

原文 

https://juejin.im/post/5ef843a96fb9a07eb20c0b8f

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 一文带你了解并发 HashMap 的一种简单实现

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址