lockfree-cuckoohash

这是一个lock-free cuckoo hash表的Rust实现。

简介

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

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

插入操作必须为快速搜索付出代价。插入操作只能将键放入两个槽位中的一个。然而，当两个槽位都已满时，必须移动其他键到它们的位置以为新键腾出空间，这称为relocation。如果移动的键无法重新定位，因为它的另一个槽位也被占用，则需要另一个relocation。如果重新定位是一个很长的链或者遇到无限循环，则应该调整表的大小或重新哈希。

测试 & 基准测试

单元测试

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.