我在寻找，一个多整数集合映射到一个整数，希望具有某种类似成对的独立保障的功能。

I'm looking for a function that maps a multi-set of integers to an integer, hopefully with some kind of guarantee like pairwise independence.

在理想情况下，内存使用量将保持不变，与哈希值可以在O（1）时间插入后进行更新/删除。 （这禁止做这样的排序整数和使用像h的散列函数（X）= H_1（X_1，H_2（X_2，h_3（x_3，x_4））））

Ideally, memory usage would be constant, and the hash value could be updated in O(1) time after an insert/delete. (This forbids doing something like sorting the integers and using a hash function like h(x) = h_1(x_1, h_2(x_2, h_3(x_3, x_4))).)

异或哈希一起不起作用，因为H（{1,1,2}）= H（{2}）

XORing hashes together doesn't work because h({1,1,2}) = h({2})

我想乘散列一起模的黄金可能会工作，如果底层的散列函数有一个不切实际的有力保障，如正独立性。

I think multiplying hashes together modulo a prime might work if the underlying hash function had an unrealistically strong guarantee, such as n-independence.

推荐答案

我问在cstheory.stackexchange.com同样的问题，并得到了很好的回答：

I asked this same question on cstheory.stackexchange.com and got a good answer:

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