Cuckoo Hash和多級Hash的粗淺認識

通過對Cuckoo Hash、多級Hash和BloomFilter的粗淺了解，感覺它們三者存在類似之處，算是近親（暫且把普通的Hash稱作遠親）。

Cuckoo Hash的思想非常簡單，沖突時，重Hash，也就是為Key重新找個新的位置。顯然，極端情況下，需要反反複複找位置，效率低。為了減少這個過程，Cuckoo Hash的實作一般引入了兩個數組，這樣隻有在其中一個數組中不存在，就不會重新找位置。

對于Cuckoo Hash的實作有一個小疑問：Google/Baidu出的介紹或實作，都是将已存在的踢出來，但感覺為新插入的找個位置，貌似也沒有問題，除非考慮到新插入的可能是熱點，暫沒能想出更好的理由。

多級Hash弱化了這個問題，它引入了更多的數組，比如20個，第一個位置被占了，就試第二個位置，依次類推，級數夠多，最終能找到存放位置的機率就很高。但是也帶來了另一個問題：太多級數，也會導緻效率下降，因為每次都需要周遊級數次。正常的實作中，一般不同級的桶數會設定不同，一般從1級往後遞減。

BloomFilter的用途和Cuckoo Hash、多級Hash明顯不同，但同樣通過多個數組來降低沖突機率，是以說它們很親。

總的來說，這些思想都非常簡單，而且很實用。而Google的SparseHash則是另一種思想，省記憶體效率又不錯，可以看作是虛拟化的思想，但它不适合用于共享記憶體這樣一次性配置設定記憶體的場景。