folklore

一个基于 "Concurrent Hash Tables: Fast and General(?)!" 一文中描述的 'folklore' 实现的无锁并发哈希表。

是什么？

与更通用的哈希表实现相比，它有一些主要的限制。具体来说；

• 不能扩展到其初始容量以上。
• 容量限制为 i16::MAX。
• 只能存储正好 2 字节的数据。
• 不支持删除操作（因为墓碑填满映射导致的巨大减速）。

唯一的优点是

• 并发访问/修改速度极快 🔥。
• 可以在线程之间安全共享，无需 Mutex，RwLock 等。

这只是一个有趣的项目，探索了我在学术论文中读到的某些内容的实现。我不太推荐使用它。

如何？

映射条目是一个 16 位键偏移量，一个 16 位值和一个 32 位键哈希。这意味着任何对映射条目的操作都可以通过一个单一的 64 位（1 词）CAS 指令完成。

实际的映射条目存储一个“键偏移量”而不是键，因为键分配在单独的存储中。键存储是一个“ConcurrentArray”，它是无锁的，并且可以安全地进行并发访问，但条目是不可变的，并且只有在它们是最最近添加的情况下才能被删除。

一致性

加载和存储通常分别使用 Ordering::Acquire 和 Ordering::Release。为了性能原因，初始查找条目使用 Ordering::Relaxed，所以有时新插入的键可能会被另一个线程错过。

性能

该仓库包含一些基本基准测试，这些基准测试与 std::collections::HashMap 和 leapfrog::LeapMap 进行比较。有一组针对单线程的基准测试，以及一组针对多线程的基准测试。以下是在 M1 Pro MacBook 上获得的数据：

单线程

多线程（8线程）

每个基准测试的数字本身可能没什么用，但通过比较，我们可以看到民间HashMap的性能略胜一筹。再次强调，这些基准测试非常基础，仅测试插入和更新。

受到couchbase/fleece中ConcurrentMap实现灵感的启发。

robclu/leapfrog在我的理解如何用Rust编写这类代码方面起到了关键作用。跳蛙HashMap也避免了此类HashMap的许多限制，并且在大多数情况下是一个更好的选择。