javascript - 使用哪些散列函数进行 count-min 草图？

Question

我正在尝试用 JavaScript 实现 count-min 草图。由于我需要一些哈希函数，我无法弄清楚我可以/应该/必须使用哪些。有什么建议么？

如果这个问题很愚蠢，我将不胜感激。谢谢

Answer 1

我认为解决方案是通用散列，您可以从一系列散列函数中选择随机散列函数。什么时候

• m = 宇宙，例如 32 位，即 2^32-1 种可能性
• p = m 以上的下一个素数，例如 4294967311
• a,b = 随机选择 0 < a < p 和 0 <= b < p

然后

• h_a,b(x)=((ax+b)mod p)mod m)

是通用的。

网上有很多信息，从 Wikipedia ( https://en.wikipedia.org/wiki/Universal_hashing ) 开始。