Cuckoo Hash和多级Hash的粗浅认识

Cuckoo Hash和多级Hash的粗浅认识.pdf

通过对Cuckoo Hash、多级Hash和BloomFilter的粗浅了解，感觉它们三者存在类似之处，算是近亲（暂且把普通的Hash称作远亲）。

Cuckoo Hash的思想非常简单，冲突时，重Hash，也就是为Key重新找个新的位置。显然，极端情况下，需要反反复复找位置，效率低。为了减少这个过程，Cuckoo Hash的实现一般引入了两个数组，这样只有在其中一个数组中不存在，就不会重新找位置。

对于Cuckoo Hash的实现有一个小疑问：Google/Baidu出的介绍或实现，都是将已存在的踢出来，但感觉为新插入的找个位置，貌似也没有问题，除非考虑到新插入的可能是热点，暂没能想出更好的理由。

多级Hash弱化了这个问题，它引入了更多的数组，比如20个，第一个位置被占了，就试第二个位置，依次类推，级数够多，最终能找到存放位置的概率就很高。但是也带来了另一个问题：太多级数，也会导致效率下降，因为每次都需要遍历级数次。常规的实现中，一般不同级的桶数会设定不同，一般从1级往后递减。

BloomFilter的用途和Cuckoo Hash、多级Hash明显不同，但同样通过多个数组来降低冲突概率，所以说它们很亲。

总的来说，这些思想都非常简单，而且很实用。而Google的SparseHash则是另一种思想，省内存效率又不错，可以看作是虚拟化的思想，但它不适合用于共享内存这样一次性分配内存的场景。