GetHashCode 在.NET 的 IEqualityComparer < T > 中扮演什么角色？

我试图理解 IEqualityComparer 接口的 GetHashCode 方法的作用。

下面的例子取自 MSDN:

using System;
using System.Collections.Generic;
class Example {
static void Main() {
try {


BoxEqualityComparer boxEqC = new BoxEqualityComparer();


Dictionary<Box, String> boxes = new Dictionary<Box,
string>(boxEqC);


Box redBox = new Box(4, 3, 4);
Box blueBox = new Box(4, 3, 4);


boxes.Add(redBox, "red");
boxes.Add(blueBox, "blue");


Console.WriteLine(redBox.GetHashCode());
Console.WriteLine(blueBox.GetHashCode());
}
catch (ArgumentException argEx) {


Console.WriteLine(argEx.Message);
}
}
}


public class Box {
public Box(int h, int l, int w) {
this.Height = h;
this.Length = l;
this.Width = w;
}
public int Height { get; set; }
public int Length { get; set; }
public int Width { get; set; }
}


class BoxEqualityComparer : IEqualityComparer<Box> {


public bool Equals(Box b1, Box b2) {
if (b1.Height == b2.Height & b1.Length == b2.Length
& b1.Width == b2.Width) {
return true;
}
else {
return false;
}
}


public int GetHashCode(Box bx) {
int hCode = bx.Height ^ bx.Length ^ bx.Width;
return hCode.GetHashCode();
}
}

Equals 方法实现难道不足以比较两个 Box 对象吗？这就是我们告诉框架用来比较对象的规则的地方。为什么需要 GetHashCode？

谢谢。

卢西恩

38367 次浏览
小开

GetHashCode 用于 Dictionary 集合，它创建哈希来在其中存储对象。这里有一篇很好的文章，告诉你为什么以及如何使用 IEqualtyComparer和 GetHashCode的 http://dotnetperls.com/iequalitycomparer

小开
最佳答案

先介绍一下背景。

NET 中的每个对象都有一个 Equals 方法和一个 GetHashCode 方法。

Equals 方法用于将一个对象与另一个对象进行比较，以查看这两个对象是否相等。

GetHashCode 方法生成对象的32位整数表示形式。由于对象可以包含的信息量没有限制，因此某些哈希代码由多个对象共享-所以哈希代码不一定是唯一的。

Dictionary 是一种非常酷的数据结构，它可以用更高的内存占用来交换(或多或少)用于添加/删除/获取操作的不变成本。不过，对于迭代来说，这是一个糟糕的选择。在内部，dictionary 包含一个存储值的桶数组。向字典中添加 Key 和 Value 时，将对 Key 调用 GetHashCode 方法。返回的散列码用于确定存储 Key/Value 对的 bucket 的索引。

当要访问 Value 时，再次传入 Key。在 Key 上调用 GetHashCode 方法，并找到包含 Value 的 bucket。

当将 IEqualityComparer 传递到字典的构造函数中时，IEqualityComparer。Equals 和 IEqualityComparer。使用 GetHashCode 方法而不是 Key 对象上的方法。

现在，为了解释为什么这两种方法都是必要的，考虑一下这个例子:

BoxEqualityComparer boxEqC = new BoxEqualityComparer();


Dictionary<Box, String> boxes = new Dictionary<Box, string>(boxEqC);


Box redBox = new Box(100, 100, 25);
Box blueBox = new Box(1000, 1000, 25);


boxes.Add(redBox, "red");
boxes.Add(blueBox, "blue");

使用 BoxEqualityComparer。在你的例子中，GetHashCode 方法，这两个框有相同的 hashcode-100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25-即使它们显然不是同一个对象。在本例中它们是相同的哈希码的原因是因为您使用了 ^ (按位排斥 -OR)运算符，所以100 ^ 100相互抵消，留下零，1000 ^ 1000也相互抵消。当两个不同的对象有相同的键时，我们称之为碰撞。

当我们将两个具有相同散列码的 Key/Value 对添加到一个 dictionary 时，它们都存储在同一个 bucket 中。因此，当我们想要检索 Value 时，在 Key 上调用 GetHashCode 方法来定位 bucket。因为 bucket 中有不止一个值，所以字典会遍历 bucket 中的所有 Key/Value 对，调用 Keys 上的 Equals 方法来查找正确的值。

在您发布的示例中，这两个框是等效的，因此 Equals 方法返回 true。在这种情况下，字典有两个相同的键，因此它抛出一个异常。

TLDR

总之，GetHashCode 方法用于生成存储对象的地址。所以字典不需要搜索它。它只是计算散列码然后跳到那个位置。Equals 方法是一种更好的相等性测试，但不能用于将对象映射到地址空间。

小开

虽然 Dictionary<TKey,TValue>可以让它的 GetValue和类似的方法对每个存储的密钥调用 Equals，以查看它是否匹配所寻找的密钥，但这将是非常缓慢的。相反，像许多基于散列的集合一样，它依赖于 GetHashCode来快速地从考虑中排除大多数不匹配的值。如果对一个被寻找的项目调用 GetHashCode得到42个项目，并且一个集合有53,917个项目，但是对其中53,914个项目调用 GetHashCode得到42个项目以外的值，那么只有3个项目需要与被寻找的项目进行比较。其余的53,914可以安全地被忽略。

GetHashCode包含在 IEqualityComparer<T>中的原因是考虑到字典的使用者可能希望将通常 没有将彼此视为相等的对象视为相等对象的可能性。最常见的例子是调用者希望使用字符串作为键，但是使用不区分大小写的比较。为了有效地实现这一点，字典将需要某种形式的散列函数，它将为“ FOX”和“ FOX”产生相同的值，但希望为“ box”或“ zebra”产生其他值。由于 String内置的 GetHashCode方法不是这样工作的，字典需要从其他地方获得这样一个方法，而 IEqualityComparer<T>是最符合逻辑的地方，因为对这样一个散列码的需求将与 Equals方法紧密联系在一起，这个方法认为“ FOX”和“ FOX”是相同的，但不是“ box”或“ zebra”。


提交答案