布谷鸟散列

这里有个CPP实现版本附带的文档可以帮助理解

https://github.com/eourcs/LockFreeCuckooHash/blob/master/index.md

基本思路

使用hashA、hashB计算对应的key位置：

1、两个位置均为空，则任选一个插入；
2、两个位置中一个为空，则插入到空的那个位置
3、两个位置均不为空，则踢出一个位置后插入，对被踢出的调用该算法，再执行该算法找其另一个位置，循环直到插入成功。
4、如果被踢出的次数达到一定的阈值，则认为hash表已满，并进行重新哈希rehash

CuckooHash学习 - 图1

rust实现的无锁hashtable

依赖

  1. crossbeam-epoch = "0.9.0"
  2. utilities = {git = "https://github.com/datenlord/utilities"}

依赖crossbeam的EBR无锁

主要用于：释放槽；map扩容后释放老的map

这里把readme中的介绍简单摘出：

Cuckoo 哈希是一种开放寻址解决哈希冲突的哈希算法。基本思路是用两个或者更多哈希函数来解决哈希冲突。在这个实现上，我们用两个哈希函数两个数组。 搜索操作只需查看两个槽，例如 table[0][hash0(key)] 和 table[1][hash1(key)]。如果两个槽不包含key；则哈希表不包含此key。所以搜索最坏的情况下也只需常数时间。 插入操作必须为快速搜索付出代价。插入操作只能放到两个槽中的一个。当两个槽都满了的时候，必须把其他key移动到第二位置（或者移动到第一位置）来给新key让位置，我们称之为重定位（relocation）。如果由于其他槽被占用导致已经移动过的key不能被重定位，则需要再进行一次重定位。如果重定位是很长的链条，或者遇到无限循环，hash表应该被resize或者rehash了。

SharedPtr

  1. pub struct SharedPtr<'g, T: 'g> {
  2.     /// `data` is the value of the pointers.
  3.     /// It will be spilt into three parts:
  4.     /// [higher_u8, raw_pointer, lower_u2]
  5.     ///    8 bits     54 bits     2 bits
  6.     ///
  7.     data: usize,
  8.     /// used for type inference.
  9.     _marker: PhantomData<(&'g (), *const T)>,
  10. }

SharedPtr包装了裸指针，此裸指针低2位用于表示槽状态：

  2. enum SlotState {
  3.     /// `NullOrKey` means a slot is empty(null) or is occupied by a key-value
  4.     /// pair normally without any other flags.
  5.     NullOrKey = 0,
  6.     /// `Reloc` means a slot is being relocated to the other slot.
  7.     Reloc = 1,
  8.     /// `Copied` means a slot is being copied to the new map during resize or
  9.     /// has been copied to the new map.
  10.     Copied = 2,
  11. }

关于CuckooHash的性能

https://developer.aliyun.com/article/563053