Order-independent Hash Algorithm

Question

I am currently working on a collection library for my custom programming language. I already have several data types (Collection, List, Map, Set) and implementations for them (mutable and immutable), but what I was missing so far was hashCode and equals. While these are no problem for Lists as they are ordered collections, the play a special role for Sets and Maps. Two Sets are considered equal if they have the same size and the same elements, and the order in which the Sets maintain them should not make a difference in their equality. Because of the equals-hashCode-contract, the hashCode implementation also has to reflect this behavior, meaning that two sets with the same elements but different ordering should have the same hash code. (The same applies for Maps, which are technically a Set of Key-Value-Pairs)

Example (Pseudocode):

let set1: Set<String> = [ "a", "b", "c" ]
let set2: Set<String> = [ "b", "c", "a" ]
set1 == set2       // should return true
set1.hashCode == set2.hashCode // should also return true

How would I implement a reasonably good hash algorithm for which the hashCodes in the above example return the same value?

Answer 1

The JDK itself proposes the following solution to this problem. The contract of the java.util.Set interface states:

Returns the hash code value for this set. The hash code of a set is defined to be the sum of the hash codes of the elements in the set, where the hash code of a null element is defined to be zero. This ensures that s1.equals(s2) implies that s1.hashCode()==s2.hashCode() for any two sets s1 and s2, as required by the general contract of Object.hashCode().

An alternative to using the sum of the entries' hash codes would be to use, for example, the ^ (XOR) operator.

The Scala language uses an ordering-invariant version of the Murmurhash algorithm (cf. the private scala.util.hashing.MurmurHash3 class) to implement the hashCode (or ##) method of its immutable sets and similar collections.