我试图了解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?
谢谢。
露西安
先来一点背景...
。NET中的每个对象都有一个Equals方法和一个GetHashCode方法。
Equals方法用于将一个对象与另一个对象进行比较-看看两个对象是否等效。
GetHashCode方法生成对象的32位整数表示。由于一个对象可以包含多少信息没有限制,因此某些哈希码可以由多个对象共享-因此哈希码不一定是唯一的。
字典是一个非常酷的数据结构,它以较高的内存占用量为代价来换取(或多或少)添加/删除/获取操作的不变成本。不过,这是一个糟糕的选择。在内部,字典包含一个存储桶数组,可以在其中存储值。将键和值添加到字典时,将在键上调用GetHashCode方法。返回的哈希码用于确定应在其中存储键/值对的存储桶的索引。
[当您要访问值时,请再次输入密钥。在键上调用GetHashCode方法,并找到包含Value的存储桶。
当将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方法,这两个盒子都具有相同的哈希码-100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25-即使它们显然不是同一对象。在这种情况下它们是相同的哈希码的原因是因为您使用的是^(按位异或)运算符,所以100 ^ 100会抵消掉剩余的零,就像1000 ^ 1000一样。当两个不同的对象具有相同的键时,我们称其为碰撞。
当我们将两个具有相同哈希码的键/值对添加到字典时,它们都存储在同一存储桶中。因此,当我们想检索一个值时,将在我们的Key上调用GetHashCode方法以定位存储桶。由于存储桶中有多个值,因此字典会在存储桶中的所有“键/值”对上进行迭代,从而调用“键”上的“等于”方法以找到正确的值。
在您发布的示例中,两个框是等效的,因此Equals方法返回true。在这种情况下,字典具有两个相同的键,因此将引发异常。
TLDR
因此,总而言之,GetHashCode方法用于生成存储对象的地址。因此,词典无需搜索。它只是计算哈希码并跳转到该位置。 Equals方法是对相等性的更好测试,但不能用于将对象映射到地址空间。
GetHashCode用于Dictionary集合,它创建用于在其中存储对象的哈希。这是一篇不错的文章,为什么以及如何使用IEqualtyComparer和GetHashCode http://dotnetperls.com/iequalitycomparer
虽然Dictionary<TKey,TValue>
可能具有其GetValue
,并且类似的方法在每个存储的键上调用Equals
以查看其是否与所寻找的键匹配,但这将非常慢。相反,像许多基于散列的集合一样,它依靠GetHashCode
快速排除大多数不匹配的值。如果在要查找的项目上调用GetHashCode
会产生42,而一个集合有53,917个项目,但是在53914个项目上调用GetHashCode
会产生非42的值,则只需要将3个项目与要比较的项目进行比较寻求。其他53914可以安全地忽略。
GetHashCode
包含在IEqualityComparer<T>
中的原因是为了允许字典的使用者可能希望将其视为相等的对象,而这些对象通常not会认为彼此相等。最常见的示例是一个调用者,该调用者希望使用字符串作为键,但使用不区分大小写的比较。为了使该工作高效,字典将需要具有某种形式的哈希函数,该函数将为“ Fox”和“ FOX”产生相同的值,但希望为“ box”或“ zebra”产生其他值。由于内置在GetHashCode
中的String
方法无法正常工作,因此字典将需要从其他地方获取这种方法,并且IEqualityComparer<T>
是最合逻辑的地方,因为将需要这种哈希码与Equals
方法紧密相关,该方法认为“ Fox”和“ FOX”彼此相同,但与“ box”或“ zebra”不同。