C# Dictionary & GetHashCode() & Equals()

• Download source - 3.2 KB

Introduction

This is a note on C# Dictionary<TKey,TValue> and GetHashCode() and Equals() methods.

Background

This is a note on C# Dictionary<TKey,TValue> and GetHashCode() and Equals() methods. The C# Dictionary<TKey,TValue> class is a generic type.

• TKey - The type of the keys in the dictionary
• TValue - The type of the values in the dictionary

The keys in a dictionary can be a reference type, i.e., objects. When an object is used as the key, the virtual methods GetHashCode() and Equals() can change how the dictionary search for the entries depending on if they are overridden, and how they are overridden.

The Dictionary<TKey,TValue> class is implemented as a hash table.

• The hash code of the key object is obtained by calling the instance method GetHashCode().
• In case of hash collisions, the colliding entries are placed in the same hash slot, and the instance method Equals() on the object is used to find the exact dictionary entry in the slot.

This note is a unit test experiment helping us to better understand the GetHashCode() and Equals() methods and their roles when objects are used as dictionary keys.

The Dictionary<TKey,TValue> & GetHashCode() & Equals()

Test No. 1 - The Basics - Add & Lookup Entries

As test No.1, let us take a look at the basic example to use objects as the dictionary keys.

[Test]
public void Test_Object_As_Key()
{
    const int Count = 100;
    var rand = new Random();
    
    var objects = new List<object>();
    var values = new List<double>();
    
    for (var i = 0; i < Count; i++)
    {
        objects.Add(new object());
        values.Add(rand.NextDouble());
    }
    
    this.DictionaryOperations(objects, values);
}
    
private void DictionaryOperations(List<object> objects, List<double> values)
{
    Assert.AreEqual(objects.Count, values.Count);
    
    // Add the values to the dictionary with the object key
    var dictionary = new Dictionary<object, double>();
    for (var i = 0; i < objects.Count; i++)
    {
        dictionary.Add(objects[i], values[i]);
    }
    
    // Check all the keys are added and retrievable
    Assert.AreEqual(objects.Count, dictionary.Count);
    for (var i = 0; i < objects.Count; i++)
    {
        Assert.AreEqual(values[i], dictionary[objects[i]]);
    }
}

The goal of test No.1 is trivial. It simply verifies that the instances of an object type can be used as the keys of a dictionary.

• The DictionaryOperations(List<object> objects, List<double> values) method takes a list of objects and a list of values. It performs the test to add each value to a dictionary and retrieve it back with the object key.
• The Test_Object_As_Key() methods prepares the lists of objects and values. It then passes the lists to the DictionaryOperations() method to test the dictionary operations.

If you run the test Test_Object_As_Key, you can find that all the entries are added nicely, and every entry is retrievable by the corresponding object instance.

Test No. 2 - GetHashCode() & Hash Collision

When an entry is added to a dictionary, the instance method GetHashCode() of the key object is called for the hash code. In test No. 2, we use Mocks to alter the GetHashCode() method to artificially create hash collisions. All the Mock objects return 100 when the GetHashCode() is called.

[Test]
public void Test_Overridden_Gethashcode()
{
    const int Count = 100;
    var rand = new Random();
    
    var objects = new List<object>();
    var values = new List<double>();
    
    for (var i = 0; i < Count; i++)
    {
        var oMock = new Mock<object>();
        oMock.Setup(x => x.GetHashCode()).Returns(100);
        
        objects.Add(oMock.Object);
        values.Add(rand.NextDouble());
    }
    
    this.DictionaryOperations(objects, values);
}

It may be of little surprise that this test runs successfully, but it is totally expected.

The C# Dictionary is well designed to handle the hash collisions with the cost of the performance. In case of hash collisions, the instance method Equals() will be called to check if two instances are the same. By default, the implementation of the Equals() method is Object.ReferenceEquals(), so the dictionary can retrieve the exact entry from the list of the colliding entries.

Test No. 3 - GetHashCode() & Equals()

In test No. 3, let us modify both GetHashCode() and Equals() methods.

[Test]
public void Test_Overridden_Gethashcode_And_Equals()
{
    const int Count = 100;
    var rand = new Random();
    
    var objects = new List<object>();
    var values = new List<double>();
    
    for (var i = 0; i < Count; i++)
    {
        var oMock = new Mock<object>();
        oMock.Setup(x => x.GetHashCode()).Returns(100);
        oMock.Setup(x => x.Equals(It.IsAny<object>())).Returns(true);
    
        objects.Add(oMock.Object);
        values.Add(rand.NextDouble());
    }
    
    bool exceptionFired = false;
    try
    {
        this.DictionaryOperations(objects, values);
    }
    catch (Exception e)
    {
        Console.WriteLine(e.Message);
        exceptionFired = true;
    }
    
    Assert.IsTrue(exceptionFired, "exception is expected");
}

• In this test, all the object instances return the same hash code.
• All the object instances return true when the Equals() method is called.

When we try to add the second entry to the dictionary, because a hash collision is encountered, the Equals() method is called. Because we modified the Equals() method to always return true even when comparing different object instances, an exception is expected because the dictionary falsely recognizes that we are trying to add the same key to the dictionary twice.

The following is the message from the exception:

Test No. 4 - The Default Implementations of GetHashCode() & Equals()

The virtual methods GetHashCode() and Equals() are important for the dictionary operations. Because they are instance methods, you may want to know the default implementations in the System.Object class.

• The default GetHashCode() method computes a hash code based on the object's reference, which is equivalent to the RuntimeHelpers.GetHashCode() method.
• The default Equals() method of a reference type is equivalent to calling the Object.ReferenceEquals() method.

[Test]
public void Test_Default_Gethashcode_And_Equals()
{
    const int Count = 100;
    var rand = new Random();
    
    var objects = new List<object>();
    var values = new List<double>();
    
    for (var i = 0; i < Count; i++)
    {
        var oMock = new Mock<object>();
        oMock.Setup(x => x.GetHashCode())
            .Returns(RuntimeHelpers.GetHashCode(oMock.Object));
        oMock.Setup(x => x.Equals(It.IsAny<object>()))
            .Returns<object>(o => object.ReferenceEquals(o, oMock.Object));
        
        objects.Add(oMock.Object);
        values.Add(rand.NextDouble());
    }
    
    this.DictionaryOperations(objects, values);
}

In this test, although we altered the GetHashCode() and Equals() methods, the supplements are equivalent to the default implementations. We should expect the same test result as test No. 1.

The Method Override & Reflection & "DeclaringType"

When objects are used as dictionary keys, it is important to find out if the GetHashCode() and Equals() methods have been overridden.

namespace dictionary_gethashcode_equals
{
    using System;
    using System.Runtime.CompilerServices;
    
    using NUnit.Framework;
    
    [TestFixture]
    class Method_Override_Test
    {
        [Test]
        public void TestImplementationClass()
        {
            var className = typeof(TestClass)
                .GetMethod("GetHashCode")?.DeclaringType?.Name;
            Assert.AreEqual("TestClass", className);
    
            className = typeof(TestClass).GetMethod("Equals")?.DeclaringType?.Name;
            Assert.AreEqual("Object", className);
        }
    
        private class TestClass : object
        {
            public override int GetHashCode()
            {
                return RuntimeHelpers.GetHashCode(this);
            }
        }
    }
}

It is not difficult to find if the methods are overridden using reflection by checking the DeclaringType.

• In the Method_Override_Test, I created a TestClass, and only overrode the GetHashCode() method.
• The test shows that the implementation class of the GetHashCode() method is the TestClass, but the implementation class of the Equals() method is the Object class.

This experiment shows us that we can find out the implementation class by reflection if we are not sure if a virtual method has been overridden. If you download the attachment, you can run all the tests in the Visual Studio and experiment with the tests.

Discussions

The Dictionary is implemented as a hash table. Hopefully with the above experiments, we are convinced about the following.

• The hash code to determine the hash slot of the dictionary entry is obtained by calling the virtual method GetHashCode() on the key object.
• With the possibility of hash collisions, the Equals() method on the key object is used to identify the exact dictionary entry.

The default implementations of the two methods on the System.Object are equivalent to the following:

• GetHashCode() - RuntimeHelpers.GetHashCode(). It returns identical hash codes for identical object references. Although there is no guarantee, the chance for a hash collision is very small, which makes it ideal to serve as the hash code for a dictionary entry;
• Equals() - Object.ReferenceEquals(), which determines whether the objects are the same instance.

The GetHashCode() and Equals() methods are virtual methods that can be overridden. To check if they are overridden, we can use reflection and check the DeclaringType of the methods. In case they are overridden, you need to find out how they are overridden if you want to use the objects as dictionary keys. In this note, I only talked about reference types. In case of value types, the idea is the same, but the default implementations of the two methods are totally different.

Points of Interest

• This is a note on C# Dictionary and GetHashCode() and Equals() methods.
• I hope you like my posts and I hope this note can help you in one way or the other.

History

• 8^th March, 2019: First revision