什么是布隆过滤器的“快速”哈希函数？

Question

假设我正在研究和调整布隆过滤器的散列函数，使用一个可能被广泛接受为“快速”的函数来计算散列所需的最大周期数是多少？

Answer 1

这取决于你想做什么。

如果您使用bloom filter来避免磁盘I/O，那么在散列函数中花费更多的时间可能是有意义的，这样您就会有尽可能少的散列冲突。例如，布隆过滤器用于避免log structured merge tree的磁盘I/O。通常，使用cryptographically secure hash function是没有意义的，但是使用类似的东西，例如xxhash或MurmurHash。

如果您希望使用bloom filter来避免在内存中查找，那么您可能希望使用更快的散列函数，例如，仅对输入进行异或，或者使用Fletcher checksum。

关于快速哈希函数与慢速哈希函数的优缺点的很好的解释，以及一些测试，are available here。