Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 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. –  jonderry 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? –  Mihai 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. –  jonderry Nov 29 '10 at 22:34
add comment

3 Answers

up vote 11 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
Yes, that is the reason for taking the hashes of the individual elements before multiplying them together. –  jonderry 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. –  TonyK Dec 1 '10 at 8:44
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.