C# Dictionary & GetHashCode() & Equals()

• 下载源代码 - 3.2 KB

引言

这是一篇关于 C# Dictionary<TKey,TValue>、GetHashCode() 和 Equals() 方法的笔记。

背景

这是一篇关于 C# Dictionary<TKey,TValue>、GetHashCode() 和 Equals() 方法的笔记。C# Dictionary<TKey,TValue> 类是一个泛型类型。

• TKey - 字典中键的类型
• TValue - 字典中值的类型

字典中的键可以是引用类型，即对象。当对象被用作键时，虚方法 GetHashCode() 和 Equals() 是否被重写以及如何被重写，会改变字典搜索条目的方式。

Dictionary<TKey,TValue> 类是作为哈希表实现的。

• 键对象的哈希码是通过调用实例方法 GetHashCode() 获得的。
• 在发生哈希冲突时，冲突的条目会被放置在同一个哈希槽中，然后使用对象上的实例方法 Equals() 来在该槽中查找确切的字典条目。

这篇笔记是一个单元测试实验，帮助我们更好地理解 GetHashCode() 和 Equals() 方法，以及当对象被用作字典键时它们所扮演的角色。

Dictionary<TKey,TValue>、GetHashCode() 和 Equals()

测试 1 - 基础 - 添加和查找条目

作为测试 1，让我们来看一个使用对象作为字典键的基本示例。

[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]]);
    }
}

测试 1 的目标很简单。它只是验证一个对象类型的实例可以用作字典的键。

• DictionaryOperations(List<object> objects, List<double> values) 方法接收一个对象列表和一个值列表。它执行测试，将每个值添加到字典中，并使用对象键将其取回。
• Test_Object_As_Key() 方法准备对象和值的列表。然后它将这些列表传递给 DictionaryOperations() 方法来测试字典操作。

如果你运行 Test_Object_As_Key 测试，你会发现所有条目都已成功添加，并且每个条目都可以通过相应的对象实例来检索。

测试 2 - GetHashCode() 与哈希冲突

当一个条目被添加到字典中时，会调用键对象的实例方法 GetHashCode() 来获取哈希码。在测试 2 中，我们使用 Mocks 来修改 GetHashCode() 方法，以人为地制造哈希冲突。所有 Mock 对象在 GetHashCode() 被调用时都返回 100。

[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);
}

这个测试能够成功运行可能并不令人意外，但这完全在预料之中。

C# 的 Dictionary 经过精心设计，能够以性能为代价来处理哈希冲突。在发生哈希冲突时，会调用实例方法 Equals() 来检查两个实例是否相同。默认情况下，Equals() 方法的实现是 Object.ReferenceEquals()，所以字典可以从冲突条目的列表中检索出确切的条目。

测试 3 - GetHashCode() 和 Equals()

在测试 3 中，让我们同时修改 GetHashCode() 和 Equals() 方法。

[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");
}

• 在这个测试中，所有对象实例都返回相同的哈希码。
• 当 Equals() 方法被调用时，所有对象实例都返回 true。

当我们尝试向字典中添加第二个条目时，因为遇到了哈希冲突，Equals() 方法会被调用。由于我们将 Equals() 方法修改为即使在比较不同对象实例时也总是返回 true，字典会错误地认为我们试图向字典中两次添加相同的键，因此预计会抛出异常。

以下是异常信息

测试 4 - GetHashCode() 和 Equals() 的默认实现

虚方法 GetHashCode() 和 Equals() 对字典操作非常重要。因为它们是实例方法，你可能想知道它们在 System.Object 类中的默认实现。

• 默认的 GetHashCode() 方法会根据对象的引用计算一个哈希码，这等同于 RuntimeHelpers.GetHashCode() 方法。
• 引用类型的默认 Equals() 方法等同于调用 Object.ReferenceEquals() 方法。

[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);
}

在这个测试中，虽然我们修改了 GetHashCode() 和 Equals() 方法，但补充的实现等同于默认实现。我们应该期望得到与测试 1 相同的结果。

方法重写、反射和 "DeclaringType"

当对象被用作字典键时，弄清楚 GetHashCode() 和 Equals() 方法是否被重写非常重要。

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);
            }
        }
    }
}

通过检查 DeclaringType，使用反射来判断方法是否被重写并不困难。

• 在 Method_Override_Test 中，我创建了一个 TestClass，并且只重写了 GetHashCode() 方法。
• 测试显示 GetHashCode() 方法的实现类是 TestClass，而 Equals() 方法的实现类是 Object 类。

这个实验告诉我们，如果我们不确定一个虚方法是否被重写，可以通过反射来找出其实现类。如果你下载附件，可以在 Visual Studio 中运行所有测试并进行实验。

讨论

Dictionary 是作为哈希表实现的。希望通过以上实验，我们对以下几点深信不疑。

• 用于确定字典条目哈希槽的哈希码是通过调用键对象上的 virtual 方法 GetHashCode() 获得的。
• 由于存在哈希冲突的可能性，键对象上的 Equals() 方法被用来识别确切的字典条目。

System.Object 上这两个方法的默认实现等同于以下

• GetHashCode() - RuntimeHelpers.GetHashCode()。它为相同的对象引用返回相同的哈希码。虽然没有绝对保证，但哈希冲突的几率非常小，这使其非常适合作为字典条目的哈希码；
• Equals() - Object.ReferenceEquals()，它判断对象是否为同一个实例。

GetHashCode() 和 Equals() 方法是可被重写的 virtual 方法。要检查它们是否被重写，我们可以使用反射并检查方法的 DeclaringType。如果它们被重写了，而你又想用这些对象作为字典键，就需要弄清楚它们是如何被重写的。在这篇笔记中，我只讨论了引用类型。对于值类型，原理是相同的，但这两个方法的默认实现则完全不同。

关注点

• 这是一篇关于 C# Dictionary、GetHashCode() 和 Equals() 方法的笔记。
• 希望您喜欢我的帖子，也希望这篇笔记能以某种方式帮助到您。

历史

• 2019年3月8日：初版