布隆過濾器的「快速」散列函數是什麼？

Question

假設我正在研究和調整布隆過濾器的哈希函數，使用可能被廣泛接受爲「快速」的函數來計算哈希所花費的最大週期數是多少？

Answer 1

這取決於你想要做什麼。

如果您使用bloom過濾器來避免磁盤I/O，那麼在散列函數中花費更多時間可能是有意義的，以便儘可能少地發生散列衝突。布隆過濾器用於例如避免log structured merge tree的磁盤I/O。通常使用cryptographically secure hash function是沒有意義的，但是類似的，例如xxhash或MurmurHash。

如果您想使用布隆過濾器來避免內存查找，那麼您可能希望使用更快的哈希函數，例如只是輸入的異或，或者使用Fletcher checksum。

快速與慢速哈希函數的優缺點和一些測試are available here的一個很好的解釋。