对于整数的集合(即多集),什么是好的散列函数？

Question

我正在寻找一个将多组整数映射到整数的函数,希望它具有成对独立性等某种保证.

理想情况下,内存使用量将保持不变,并且哈希值可以在插入/删除后的O(1)时间内更新.(这禁止执行诸如排序整数和使用哈希函数之类的操作,如h(x)= h_1(x_1,h_2(x_2,h_3(x_3,x_4))).)

XORing哈希值不起作用,因为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-ie-multi-set-of-integers-that-has