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

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.

• What is your representation of multisets? I.e., how do you encode a multiset as a bit string? If you really want to get $O(1)$-time operations (independently of the size of the multiset), I think you should make the encoding explicit. Nov 29 '10 at 11:47
• The encoding of the sets is unimportant. The hash function should be independent of the representation of the sets. If I were using a canonical representation of a hash set, then any standard hash on the bit representation of the set would satisfy 3 and probably 1, but not 2. I should add that two equal collections should always hash to the same value. Nov 29 '10 at 18:08
• What exactly do you mean by 2? Do you get the old set, the old hash code, and the new element, and you want to compute the new hash code? Or do you get just the old hash code and the new element? Nov 29 '10 at 21:52
• Ideally, you wouldn't need the old set. You don't even need to be able to perform member queries (important, given the space limits), just equality testing, probably via comparing hash values that have a low probability of a false positive. Nov 29 '10 at 22:34
• Doesn't the sum of the hashes of the elements, modulo N work? Space is constant and unlike the product mod p, it certainly satisfies (3).
– 6005
Sep 21 '20 at 17:50

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.

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).

• I think this only works on sets, not multisets (as the question asked for). From Section 5, at the bottom of page 274: "ADD(x, S)-Adds the element x to the set named S. This operation may not be used if x is already a member of S." Jan 11 '16 at 3:57
• You're right; I missed the "multi" part. It seems likely that a hash function could handle duplicates, though I don't have a citation for it. Jan 11 '16 at 7:56

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.

• Yes, that is the reason for taking the hashes of the individual elements before multiplying them together. Nov 29 '10 at 19:39
• What? The OP's suggestion is simply to multiply them all together, isn't it? I'm saying that if you add a constant to each before you do this, you probably get a better hash. Dec 1 '10 at 8:44
A = 0x4F1BBCDD
B = 0x314EFB75
A*B = 1
N = size of set before addition/removal<P>
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