<p>Carter and Wegman cover this in <a href="http://www.sciencedirect.com/science/article/pii/0022000081900337" rel="nofollow">New hash functions and their use in authentication and set equality</a>; 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).  </p>

CC BY-SA 3.0
2016-01-11T03:57:50.717Z
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."
jbapple
CC BY-SA 3.0
2016-01-11T07:56:21.420Z
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.
KWillets
CC BY-SA 3.0
2016-01-05T18:22:41.707Z
2016-01-05T18:22:41.707Z
KWillets
<p>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.</p>

CC BY-SA 2.5
2010-11-29T19:39:46.467Z
Yes, that is the reason for taking the hashes of the individual elements before multiplying them together.
jonderry
CC BY-SA 2.5
2010-12-01T08:44:03.633Z
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.
TonyK
CC BY-SA 2.5
2010-11-29T18:35:31.657Z
2010-11-29T18:35:31.657Z
TonyK
<pre><code>A = 0x4F1BBCDD
B = 0x314EFB75
A*B = 1 
N = size of set before addition/removal&lt;P&gt;
Add X
H = (H-N)*B
U = H &gt;&gt; 16
V = H &amp; 0xFFFF
H = (((U+X)&amp;M)&lt;&lt;16) + ((V^X)&amp;M)
H *= A
H += N+1

Remove X
H = (H-N)*B
U = H &gt;&gt; 16
V = H &amp; 0xFFFF
H = (((U-X)&amp;M)&lt;&lt;16) + ((V^X)&amp;M)
H *= A
H += N-1
</code></pre>

<p>the sum allows us to have multiple occurrences of the same value<br>
 the xor allows us to have sets that sum to the same amount</p>

CC BY-SA 3.0
2011-06-04T02:17:06.743Z
2017-01-19T22:37:14.970Z
2017-01-19T22:37:14.970Z
Louis Reinitz
<p>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". </p>

<p>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.</p>

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

CC BY-SA 2.5
2010-11-29T22:07:54.627Z
2010-11-29T22:07:54.627Z
Mihai
<p>I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally:</p>

<ol>
<li>It uses O(1) space</li>
<li>It can be updated to reflect an insertion or deletion in O(1) time</li>
<li>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)</li>
</ol>

<p>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.</p>

<p>I originally posted this on <a href="https://stackoverflow.com/questions/4175951/what-is-a-good-hash-function-for-a-collection-i-e-multi-set-of-integers">StackOverflow</a>.</p>

<p>*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.</p>

CC BY-SA 2.5
2010-11-29T11:47:18.403Z
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.
Jukka Suomela
CC BY-SA 2.5
2010-11-29T18:08:50.380Z
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.
jonderry
CC BY-SA 2.5
2010-11-29T21:52:32.177Z
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?
Mihai
CC BY-SA 2.5
2010-11-29T22:34:48.557Z
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.
jonderry
CC BY-SA 4.0
2020-09-21T17:50:50.113Z
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).
Caleb Stanford
<ds.algorithms><ds.data-structures><hash-function>
Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?
jonderry
# Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

(Asked by: username_0 on 2010-11-29)

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](https://stackoverflow.com/questions/4175951/what-is-a-good-hash-function-for-a-collection-i-e-multi-set-of-integers).

\*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.

**Tags:** ds.algorithms, ds.data-structures, hash-function

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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?  
> **username_0**: 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.  
> **username_3**: 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).  

---

## 4 answers

### Answer by username_2 on 2010-11-29. Score: 21 | Accepted answer

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 by username_4 on 2016-01-05. Score: 3

Carter and Wegman cover this in [New hash functions and their use in authentication and set equality](http://www.sciencedirect.com/science/article/pii/0022000081900337); 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).

> **Comments:**
> **username_5**: 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."  
> **username_4**: 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.  

---

### Answer by username_6 on 2010-11-29. Score: -2

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.

> **Comments:**
> **username_0**: Yes, that is the reason for taking the hashes of the individual elements before multiplying them together.  
> **username_6**: 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.  

---

### Answer by username_7 on 2011-06-04. Score: -5

A = 0x4F1BBCDD
B = 0x314EFB75
A*B = 1 
N = size of set before addition/removal
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


---

