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:
- XOR - Will only work for sets which are guaranteed to not have duplicates as
a XOR a = 0
- Addition - Proposed as a better alternative to XOR since
a + a = a << 1which seems a good fit as long as addition causing integer overflow wraps and equivalently the bit shift is a bitwise rotation
- 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.