对一组整数进行哈希处理

Question

我正在寻找一个基于集合的哈希函数H(.)和一个关系R(.,.)，使得如果A包含在B中，则有R(H(A), H(B))成立。当然，R(.,.)必须易于验证（常数时间），而且H(A)应该能在线性时间内计算出来。

其中一个H和R的例子如下：

H(A) = 对于A中的每个x，将1 << (h(x) % k)进行或运算，k是固定整数，h(x)是整数哈希函数。

R(H(A), H(B)) = ((H(A) & H(B)) == H(A))

是否有其他好的例子？（好很难定义，但直观上如果R(H(A), H(B))则A很可能被包含在B中）。

- Alexandru

---

我已将此问题转移到cstheory。 http://cstheory.stackexchange.com/questions/1786/hashing-sets-of-integers - Alexandru

Answer 1

• 经过思考，我得出了你所给的例子。即B中的每个元素设置哈希中的一个位，只有在H（B）中设置了H（A）中设置的每个位时，A才包含在B中。
• 也许布隆过滤器适用于您的情况。它似乎使用相同的位技巧，但具有多个哈希函数。

- Sjoerd

---

今天我一直在思考如何利用布隆过滤器。当你进行极端集合搜索时，小的k非常有用，因为你可以将集合分成2^k个子集，并减少总测试次数。我的想法是从布隆过滤器中选择k位。 - Alexandru