algorithm - 对于整数集合(即多集)，什么是好的哈希函数？

Question

我正在寻找一个将多组整数映射到一个整数的函数，希望能提供某种保证，例如成对独立性。

理想情况下，内存使用量是恒定的，并且哈希值可以在插入/删除后的 O(1) 时间内更新。 (这禁止做一些事情，比如对整数进行排序和使用像 h(x) = h_1(x_1, h_2(x_2, h_3(x_3, x_4))) 这样的哈希函数。)

将哈希值异或在一起是行不通的，因为 h({1,1,2}) = h({2})

我认为，如果底层哈希函数具有不切实际的强保证(例如 n 独立性)，则将哈希以素数为模可能会起作用。

Answer 1

我在 cstheory.stackexchange.com 上问过同样的问题并得到了很好的答案:

https://cstheory.stackexchange.com/questions/3390/is-there-a-hash-function-for-a-collection-i-e-multi-set-of-integers-that-has