问题描述
我在寻找，一个多整数集合映射到一个整数，希望具有某种类似成对的独立保障的功能。
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
这篇关于一个好的哈希函数整数集合（即多集）是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！