按年被提到
20162020 · 2 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:1601.04017 · cs.DS

Concurrent Hash Tables: Fast and General?(!)

并发哈希表:又快又通用?
Tobias Maier, Peter Sanders, Roman Dementiev · 2016

基于线性探测的无锁并发哈希表,支持动态扩容且显著快于主流实现

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2019-01-06 · 最近 2020-05-02
3不同的人
3活跃月份
3讨论串
7被引(OpenAlex)

论文从一个基于线性探测、只支持机器字大小键值且不能动态调整大小的无锁并发哈希表出发,说明如何以可证明可扩展的方式去掉这些限制,并展示动态扩容的开销与顺序哈希表的同类扩展相当。与六种最广泛使用的并发哈希表相比,其实现明显快于受类似限制的最佳算法,比最佳的通用哈希表快一个数量级,极端情形下差距接近四个数量级。

HN 为什么提它

评论者在讨论并发 map 的读取扩展性时引用它,作为并发哈希表性能与可扩展性的研究出处,也有人直接贴出论文的 PDF 链接。

方法难度 4 / 5约 70 分钟经得起时间
读之前最好知道
1哈希表与线性探测
2无锁(lock-free)数据结构
3原子操作与 CAS
4内存模型与缓存一致性
5并发程序性能分析

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用NovaX · 2019-01

“Java and C++ concurrent maps scale reads quite well, both in practice and in research.”

引用它说明并发哈希表的研究,Java 和 C++ 并发 map 读扩展性不错
Rust at speed – building a fast concurrent database [video]原评论 ↗
引用throwaway7281 · 2020-05

“a direct link to a PDF:”

给出这篇并发哈希表论文的 PDF 直链
Concurrent Hash Tables: Fast and General? (2019)原评论 ↗
被提交为 story · 1 次