获得k个快速成对独立哈希函数的选项是什么？

Question

我遇到了k个成对独立散列函数的需求，每个散列函数都接受一个整数作为输入，并产生0-N范围内的散列值。count-min sketch需要这个，它类似于Bloom filter。

形式上，我需要h_1，h_2，...，h_k散列函数，成对独立。

(h_i(n) mod N)将给出0-N范围内n的散列值。当我在处理大量数据时，散列需要具有时效性。同时，它们应该尽可能地成对独立。

到目前为止，我尝试了以下几点：

1) xxhash:它是有效的，但在成对独立方面不是很好，这意味着散列函数之间存在散列冲突(即h1(n1)=h1(n2)，然后一些h_k(n1)也= h_k(n2))，因此我得到的结果很糟糕。

2)类似地，著名的整数散列方法((a*n+b) mod p) mod N也具有与xxhash相同的问题。我相信这就是通用散列

3) count-min-sketch中引入的另一种方法产生了很好的结果，但是对于较大的输入来说需要花费太多的时间。

4)在冲突中也尝试了类似问题的Murmur3、sha1。

任何想法都将不胜感激。最好是C/C++，但Java也可以，或者简单的算法。谢谢

Answer 1

我怀疑您使用方法2的问题是您丢弃了相关的a_i和b_i。

对于初学者来说，要确保所有的a_i和b_i都是不同的(即，你得到了2*k个不同的数字)。如果它们均匀地分布在字段中，这也不会有什么坏处:)

在使用SHA的方法4中，您可能会遇到相同的问题。大多数密码学哈希函数(甚至包括损坏的和较旧的)对于数据结构的需求是远远不够的，无论是对于任何合理的k的k-wise独立性，还是几乎任何其他属性。

我会再问一遍--你是怎么使用它的？