Click here to Skip to main content
13,900,697 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

2.4K views
35 downloads
11 bookmarked
Posted 15 Mar 2019
Licenced CPOL

C# Dictionary & GetHashCode() & Equals()

, 15 Mar 2019
Rate this:
Please Sign up or sign in to vote.
This is a note on C# Dictionary & GetHashCode() & Equals() methods

Introduction

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

Background

This is a note on C# "Dictionary<TKey,TValue>" & GetHashCode() & 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()" & "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()" & "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() & 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() & 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 & GetHashCode() & Equals() methods.
  • I hope you like my postings and I hope this note can help you in one way or the other.

History

  • 3/8/2019: First revision

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Dr. Song Li
United States United States
I have been working in the IT industry for some time. It is still exciting and I am still learning. I am a happy and honest person, and I want to be your friend.

You may also be interested in...

Comments and Discussions

 
GeneralMy vote of 5 Pin
David Pierson17-Mar-19 20:12
memberDavid Pierson17-Mar-19 20:12 
QuestionMessage Closed Pin
15-Mar-19 0:48
memberMember 1418351315-Mar-19 0:48 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01 | 2.8.190306.1 | Last Updated 15 Mar 2019
Article Copyright 2019 by Dr. Song Li
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid