C# - Using references as key in Dictionary

by Fredrik Ljung  

A Dictionaryis used to do quick* lookups of a value using a specific key. Any type can be used as both value and key but if you use your own custom type as a key you need to think of a few things.

*Quicker then say a LINQ-query on a list like MyList.Where(x => x.id == id).Single();

Default GetHashCode() and Equals() are equal if referencing the exact same object

For the following to make sense you need to understand the difference between same object and equal object. The same object is a reference to the exact same object in memory, whereas different objects in memory are only considered equal if you the programmer defines them as such:

Person A = new Person()
{
    FirstName = "Gypsy",
    LastName = "Danger"
};
 
Person B = new Person()
{
    FirstName = "Gypsy",
    LastName = "Danger"
};
 
Person C = B;
 
if (B.Equals(C)) // true
    Console.WriteLine("These references are the same");
 
if (A.Equals(B)) // not true unless Person implements Equals()
    Console.WriteLine("These references are equal");

In the above code Person A and Person B are equal but not the same. They are two different instances of the same type. Person B and Person C on the other hand are the same, they reference the exact same object. Comparison between A and B will not return true unless you override Equals in the Person class. Until then they will only be considered equal if they are also the same. This is because of how comparison works on Object. Object.Equals() will only be equal if the compared Object references the exact same object. The seemingly subtle difference between Object.Equals and Object.GetHashCode() is that GetHashCode() must* return the same value if two Objects are equal.

*With must, I mean should, or you will end up with all sorts of pain trying to use Dictionaries, HashSets, and anything else that relies on GetHashCode() to function properly.

GetHashCode() can return the same value for unequal objects.

Unequal objects usually won?t return the same value for GetHashCode(), but there is no restriction on them to not return the same value. This means that comparison between GetHashCode() can be used to check if an actual equality check needs to performed. If they are unequal it?s safe to assume they are not equal, but if they are the same, an actual equality check needs to be performed. This is why it?s usually good to override Equals in your custom classes, at least if you intend to do any equality comparisons*.

* If you haven?t provided an override for Equals in your objects, if you are using objects you haven?t created, or if you just need a different meaning of equality, you can also use IEqualityComparerwhere it is supported. Dictionary for instance supports equality checks with IEqualityComparer.

Override Equals(Object other) to bring equality to all

So GetHashCode() has returned the same value, now it?s time to prove equality, or inequality if that?s the case. Microsofts guidelines for overriding Equals is to override Equals(), and for added speed bonuses, also define Equals for your specific type:

public Person Class
{
    public string FirstName { get; set; }
    public string LastName { get; set; }
 
    public override bool Equals(object other)
    {
        if (other == null || !(other is Person))
            return false;
 
        return Equals(other as Person);
    }
 
    public bool Equals(Person other)
    {
        return FirstName.Equals(other.FirstName, StringComparison.Ordinal) &&
               LastName.Equals(other.LastName, StringComparison.Ordinal);
    }
 
    // I found the following pattern on StackOverflow. The numbers are
    // prime numbers which magically (or mathematically if you believe
    // in that stuff) creates a fairly good normal distribution of the
    // numbers, which is good for hashing (apparently).
    public override GetHashCode()
    {
        int hash = 17;
        hash = hash * 23 + FirstName.GetHashCode();
        hash = hash * 23 + LastName.GetHashCode();
        return hash;
    }
}

The cost of breaking the guidelines of GetHashCode()

Breaking the rules usually comes with a price. In programming it just about always does. In the case of references as a key, implementing GetHashCode() and then changing the values of the properties used to calculate the has code is a bad thing. However there are a few things you can do to recover. In the case of a Dictionary and HashSet and others I?m sure, you can use IEqualityComparerto work around your proper use of GetHashCode(). If you know your key will change but not how, then perhaps using the object.GetHashCode() is an option as long as you will not try and get values from the Dictionary with a key that?s Equal but not Same.

class PersonComparer : IEqualityComparer
{
    public bool Equals(Person A, Person B)
    {
        if (A.FirstName.Equals("Connor" StringComparison.Ordinal) &&
            A.LastName.Equals("MacLeod, StringComparison.Ordinal))
            return false; // There can be only one
 
        return A.Equals(B);
    }
}

I accidently (this is how I defend that i messed up, an ?accident?) fell into the key change trap recently. I was using Entity Framework entities as keys before I called SaveChanges(). When SaveChanges() was called, all temporary Ids were replaced by the Ids generated in the database. The Dictionary stopped working properly since my override of Equals had the Id as part of the comparison. Since none of the other properties made the object unique, I couldn?t use a IEqualityComparer. The two solutions I came up with was to either wrap the entity in an object and not override GetHashCode(), or to recreate the dictionary using the same references as keys. I decided for the last one since it made the smallest change to my code, and since I was dealing with database calls which are slow, I figured the CPU hit of recreating the Dictionary was small in comparison.

var newMap = new Dictionary();
foreach (var entity in entityMap)
{
    newMap.Add(entity.Key, entity.Value);
}
entityMap = newMap;

No feedback yet