Simple general-purpose hash function for a collection

algorithm, collections, hash

Solution

Be very careful here. If you create a `GetHashCode` method for a `List<T>` (or similar collection), then presumably it'll do something like this:

public override int GetHashCode()
{
    int hash = 13;
    foreach (var t in this)
    {
        // X is an operation (undefined here) that somehow combines
        // the previous hash value and the item's hash value
        hash = hash X t.GetHashCode();
    }
    return hash;
}

(I would suggest something like the Jenkins hash for computing the hash code. Also look into the Wang hash (or bit mixer).)

Unless you compute that value the first time and the cache it, you will end up iterating over all of the items every time `GetHashCode` is called.

So you've created a `GetHashCode` and `Equals` for your collection and you put an instance into a `Dictionary`. Now you have to be very careful not to change the collection (i.e. don't add or remove any items) or any of the items inside the collection. Otherwise the value of `GetHashCode` will change, and the dictionary won't work anymore.

I strongly suggest that if you want to use a collection as the key to a dictionary, you make very sure that the collection is immutable.

One other thing to consider. The concept of list equality isn't as simple as you indicate. For example, are the lists `[1, 2, 3, 4, 5]` and `[5, 1, 3, 4, 2]` equal? It rather depends on your definition of equality. Certainly `A.Union(B) == A.Intersect(B)`, which means that they're equal if your definition of equality is "contain the same items." But if order matters, then the lists aren't equal.

If your definition is "contain the same items," then the hash code calculation I showed above isn't going to work because hash code computations are order dependent. So if you wanted to compute the hash code of those lists, you'd have to sort them first.

If the lists cannot contain duplicates, then computing equality is a matter of creating a hash set of one list and looking up each item from the other list in that hash set. If the lists can contain duplicates, then you either have to sort them to determine equality, or use some kind of dictionary with a count. And both of those imply that the objects contained in the list will implement some form of equality comparer, etc.

And some definitions of equality don't take duplicates into account at all. That is, `[1, 2, 3]` would be equal to `[3, 3, 3, 2, 1, 1]`.

Considering the varying differences of equality and the effort it would have taken to allow for those and more in defining the behavior of `List<T>`, I can understand why whoever designed the collection classes didn't implement value equality. Especially considering that it's pretty uncommon to use a `List<T>` or similar collection as the key in a dictionary or hash table.

Problem

Original source

Related problems

• Why is XOR the default way to combine hashes?
• What is a good Hash Function?