Mutable objects and hashcode

Mutable objects can lead to situation wherein it can be put into a hash but never retrieved from it (or rather even worse something else gets returned)...

Even though it is evident in most cases, but its not so evident all the time especially when we have deep hashcode dependencies. Consider the following

 
class Person
{
    public Person(string name, Person parent)
    {
        this.name = name;
        this.parent = parent;
    }

    public string name;
    public Person parent;

    public override int GetHashCode()
    {
        int hashCode = name.GetHashCode();
        if (parent != null)
            hashCode ^= parent.GetHashCode();

        return hashCode;
    }
}

static void Main(string[] args)
{
    Dictionary hash = new Dictionary();

    Person parent = new Person("Beeblebox", null);
    Person zaphod = new Person("Zaphod", parent);

    hash.Add(zaphod, zaphod);
    parent.name = "SomethingElse";

    Console.WriteLine(hash.ContainsKey(zaphod)); // Will print false
}

Here Person is mutable on different levels. Its directly mutable and also deep-mutable as it contains a reference to parent (which in turn is mutable).

Additionally, Person's hashcode depends on it's mutable fields. So in effect if any of the mutable references change then the next GetHashCode will return a different value and hence its lookup inside Dictionary will fail as Dictionary uses the hashcode of the objects place inside it.

Since in the example above the mutation of parent happens inline, it's easy to figure it out. However, it could well be in some obscure corner of the code base.

Comments

• Anonymous
  October 17, 2007
  PingBack from http://www.artofbam.com/wordpress/?p=9912

• Anonymous
  October 18, 2007
  The root of problem here is in custom implementation of equality (and GetHashCode as part of that). Form or Button or List<T> classes don't suffer from that problem, even if they are mutable (obviously). And that's why almost no types override equality in BCL. But there is one interesting thing about that: structs. They've already got that 'special' equality implementation. Luckily, they got away with that, because are being copied all the time, so there is nearly no chance one could push a struct into collection and change the state of the very instance store in collection. Well, there actually is a way, but it's an edge case. Conclusion: implementing value-equality for mutable CLASSES is evil.