3
$\begingroup$

I'm searching an hash function for integer set equality that must be fast. It must support update (adding an element already in the set must not change the hash) and union. MinHash has these 2 properties but it is too expensive and I do not need all the feature of MinHash, in fact I don't need set similarity but only equality. Do you know something that can satisfy my needs? Thanks :)

P.S. I have to implement it in C for an high performance software

Improve this question
$\endgroup$
11
  • $\begingroup$ How do you represent a set? Adding a value that is already present doesn’t change the set, so why would it change the hash? $\endgroup$ – gnasher729 May 15 '19 at 10:53
  • $\begingroup$ I do not represent the set, this is the problem. For each new item (an int16_t) I call hash.update(item). I am considering a bloom filter but it seems to expensive in space. $\endgroup$ – Andrea Fioraldi May 15 '19 at 11:52
  • $\begingroup$ The answer depends very much on the nature of the integer sets you will encounter. It would be nice if you can share a few hundreds or more such such sets. $\endgroup$ – John L. May 15 '19 at 16:57
  • 2
    $\begingroup$ Is "adding a new item" the only modifying operation on the set? $\endgroup$ – John L. May 15 '19 at 16:59
  • $\begingroup$ @Apass.Jack I really don't see how adding a few hundred examples to the question would help. That's an absurd amount of data to demand: it could be a huge amount of work for the asker and I don't see how it would be useful to most answerers. $\endgroup$ – David Richerby May 17 '19 at 12:58
3
$\begingroup$

MinHash already is super-fast. I suggest you check whether you understand correctly how MinHash works.

Take any standard hash function $H$; then all you have to do is compute $H$ once on each element of the set. You can implement $H$ with as fast a hash algorithm as you want. The update operation requires one call to $H$ (namely, if your set's hash is currently $y$, and you add element $x$, the new hash is $\min(y, H(x))$), and the union operation is super fast (namely, the union of two sets with hashes $y_1,y_2$ is $\min(y_1,y_2)$). Notice that these operation have the property you want (adding an element already in the set does not change the hash).

I have a hard time imagining how you could get much faster than that.

If you want this to be faster, a reasonable way is to choose a $H$ that is faster.

I've described a variant where the hash of a set is the smallest of the element-hashes. The only downside is that the number of hash collisions might higher than you like. Measure and see if that is actually a problem in practice. If it is, you can consider variants that keep the $k$ distinct smallest element hashes. If $k$ is large, you can store those $k$ hashes in a heap of size $k$ to make the update and union operations faster.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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