oihash

(O)rder-(I)ndependent Hash

A definitely-not-cryptographically-secure hash algorithm designed to
allow you to answer the following question:

Do these two enormous lists of []bytes have the same elements in the
same numbers? i.e. if you have a pair of multisets represented as
lists, are they the same?

It's assumed that it's infeasible to sort the two input lists, which
means that we want a hash function into which you can mix the elements
in any order, and the result will be the same regardless of mixing
order. One helpful construction for this is to select two functions
with the following signatures:

Hash: MultiSet<[]byte> -> HashType
Combine: HashType x HashType -> HashType

that satisfy the following property:

Combine(Hash(A), Hash(B)) == Hash(Union(A, B))


Then you can compute incrementally as follows:

var combinedHash HashType
for _, x := range items {
  itemHash := Hash({x})
  combinedHash = Combine(combinedHash, itemHash)
}