Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

Question

I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally:

1. It uses O(1) space
2. It can be updated to reflect an insertion or deletion in O(1) time
3. Two identical collections (i.e., collections that have the same elements with the same multiplicities) should always hash to the same value, and two distinct collections should hash to different values with high probability (i.e., the function is independent or pairwise independent)

One initial attempt at this would be to store the product modulo a random prime of the hashes of the individual elements. This satisfies 1 and 2 but it's not clear whether it, or a close variation, would satisfy 3.

I originally posted this on StackOverflow.

*Properties 1 and 2 could be relaxed a little to, say, O(log n), or a small sublinear polynomial. The point is to see whether we can identify multi-sets and reliably test equality without storing the elements themselves.

Answer 1

If you think of sets as living in universe $[u]$, it is quite easy to solve your problem with $O(\lg u)$ update time. All you need is a fast hash function for a vector of $u$ numbers, with fast "local updates".

Wikipedia/Universal hashing suggests $h(\vec{x}) = \big(\sum_{i=1}^{u} x_i a^i \big) \bmod{p}$, where $p$ is a large enough prime and $a$ is uniformly drawn from $[p]$. When you add or remove element $i$, you have to add/subtract $a^i$ from the hash code, which takes $O(\lg i)$ time using divide and conquer for the exponentiation. Since a polynomial of degree $u$ can only have $u$ roots, the probability of collision for two distinct sets is $O(u/p)$. This can be made very small by taking $p$ to be large enough (for instance, $p=u^2$ and you work in "double precision"). If the sets are much smaller than $[u]$, you can of course begin by hashing the universe down to a smaller universe.

Does anybody know a solution with $O(1/p)$ collision probability when hashing to range $[p]$? This ought to be possible.

Answer 2

Carter and Wegman cover this in New hash functions and their use in authentication and set equality; it's very similar to what you describe. Essentially a commutative hash function can be updated one element at a time for insertions and deletions, and high probability matches, in O(1).

Answer 3

The quality of a hash function will always depend on the properties of the elements that it has to hash. Can you say something about this? For instance, your product suggestion is probably a poor hash function if the elements x_i of your multiset typically have many small prime factors. But you can improve it in this case simply by taking the product of all x_i + p mod q for some primes p and q.

Answer 4

A = 0x4F1BBCDD
B = 0x314EFB75
A*B = 1 
N = size of set before addition/removal<P>
Add X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U+X)&M)<<16) + ((V^X)&M)
H *= A
H += N+1

Remove X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U-X)&M)<<16) + ((V^X)&M)
H *= A
H += N-1

the sum allows us to have multiple occurrences of the same value
the xor allows us to have sets that sum to the same amount