4
$\begingroup$

I am trying to find out the correct way to hash an unordered collection. In this collection elements may be repeated and the hash needs to reflect how many times an element appears. If we are unable to hash each element, sort the hashes and then hash the result (for example, because the elements are distributed between many machines which are unable to communicate all the data) what is the next best option?

I have seen three possible suggestions for combining the hashes of each element and I am wondering if they are valid in general or just for specific hash functions:

  1. XOR - Will only work for sets which are guaranteed to not have duplicates as a XOR a = 0
  2. Addition - Proposed as a better alternative to XOR since a + a = a << 1 which seems a good fit as long as addition causing integer overflow wraps and equivalently the bit shift is a bitwise rotation
  3. Multiplication - Another proposal which I have seen in this thread: How to hash a set of elements (not sure what benefits this might have over addition)

Are any of these a valid way to combine a collection of hashes without significantly increasing the chance of collision? Are they valid in general or only for cryptographic hash functions? If this isn't something that is supported by most hash functions, are there any specific hash functions which is designed to supports this use case?

Ideally I'd like to use a fast non-cryptographic hash function such as MurmurHash3, but I can't find any good resources that suggest any the above options are a valid way to combine hashes.

|improve this question
$\endgroup$
  • 2
    $\begingroup$ Are you looking to generate a cryptographical hash (e.g. one for which it is infeasible to find preimages or collisions, even given the details of the hash), or a statistical one (e.g. one for which different values are likely to hash differently, assuming that the hash values aren't chosen deliberately to cause collisions)? $\endgroup$ – poncho Feb 20 '17 at 14:09
  • 1
    $\begingroup$ what are your inputs? different length binary strings, fixed length strings, something else? $\endgroup$ – kodlu Feb 20 '17 at 20:01
  • 1
    $\begingroup$ @LVA if collisions are the worst case scenario, you absolutely need to use a cryptographic hash function, and a good one (SHA2-256/512, SHA-3, Blake 2b). The canonical way to do this is with a sort then hash, or use a hash of sorted hashes. A Merkle Tree can be used to reduce communication bandwidth. danieloshea.com/2011/12/07/merkle-tree.html $\endgroup$ – rmalayter Feb 22 '17 at 1:13
  • 2
    $\begingroup$ What is the use case, exactly? For example, if you only need to check whether a set you currently have is equal to some earlier hashed set, you could use a cryptographic accumulator. If either false negatives or false positives are allowed (but not the other) a bloom filter might suffice. Etc. $\endgroup$ – otus Feb 24 '17 at 16:19
  • 1
    $\begingroup$ Having read this more carefully, I'm voting to close this question as off-topic because it is about non-cryptographic hashes. Addition of sufficiently strong hashes will not collide randomly and should work here. $\endgroup$ – otus Feb 24 '17 at 16:26

Browse other questions tagged or ask your own question.