lockfree-cuckoohash

这是一个无锁Cuckoo哈希表的Rust实现。

简介

Cuckoo哈希是一种开放寻址的哈希冲突解决方案。Cuckoo哈希的基本思想是通过使用两个或更多的哈希函数来解决冲突，而不是仅使用一个。在这个实现中，我们使用了两个哈希函数和两个数组（或表）。

搜索操作只查找两个槽位，即table[0][hash0(key)]和table[1][hash1(key)]。如果这两个槽位不包含键，则哈希表不包含键。因此，搜索操作在最坏情况下只需要常数时间。

插入操作必须为快速搜索付出代价。插入操作只能将键放入两个槽位之一。然而，当两个槽位都已满时，需要移动其他键到它们的第二个位置（或回到第一个位置）为新键腾出空间，这称为迁移。如果移动的键不能迁移，因为它的另一个槽位也被占用，则需要另一个迁移。如果迁移是一个非常长的链或遇到无限循环，则应该调整表的大小或重新散列。

测试 & 基准测试

单元测试

cargo test

简单基准测试

cargo test --test benchmark bench_read_write --release -- --ignored --nocapture

参考文献

• Nguyen, N., & Tsigas, P. (2014). Lock-Free Cuckoo Hashing. 2014 IEEE 34th International Conference on Distributed Computing Systems, 627-636.