Combining hashes for an ordered set

Question

An accepted way of combining two hashes from different objects is to use XOR. This makes sense, but as mentioned in the second comment by Thomas Pornin in the below post, XOR is commutative, which means that if you hash each element in a set and combine them with XOR, any order that you do it will always result in the same hash:

Why is XOR the default way to combine hashes?

What is a good way to combine hashes that you want to be order dependent? If it is specific to the size, what are some known techniques for 32 bit and for 64 bit?

Answer 1

To make the resulting hash order dependent, there has to be some sequential (i.e. non-static) aspect in the algorithm. The most common technique probably is that of Cyclic Redundancy Checks (CRC).

CRC can be implemented in hardware as a shift-register with XOR-ed feedback. Such a shift-register acts as deterministic random number generator. Provided the initial state is the same, it will always go through the same sequence of states. These states are used in CRC signature computation to XOR the data in a repeatable fashion.

To combine two hash values, you'd XOR them together with a third value from a CRC algorithm. This might be calculated or taken from a look-up table.-

Popular CRC codes:

09 bits (CRC-8)
17 bits (CRC-16)
33 bits (CRC-32)
65 bits (CRC-64)

Classless.Hasher provides more details.

C# implementations can be found in HashLib.