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?

谢谢 .

卢西恩

回答(3)

2 years ago

先介绍一下背景......

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

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

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

字典是一种非常酷的数据结构,可以换取更高的内存占用量,以换取(或多或少)添加/删除/获取操作的固定成本 . 迭代虽然是一个糟糕的选择 . 在内部,字典包含一个桶数组,其中可以存储值 . 将Key和Value添加到字典时,将在Key上调用GetHashCode方法 . 返回的哈希码用于确定应存储密钥/值对的桶的索引 .

如果要访问“值”,则再次传入密钥 . 在Key上调用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也是如此 . 当两个不同的对象具有相同的键时,我们称之为冲突 .

当我们将两个具有相同哈希码的键/值对添加到字典时,它们都存储在同一个桶中 . 因此,当我们想要检索Value时,在我们的Key上调用GetHashCode方法来定位存储桶 . 由于存储桶中有多个值,因此字典会对存储桶中的所有键/值对进行迭代,调用Keys上的Equals方法以找到正确的值 .

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

TLDR

总而言之,GetHashCode方法用于生成存储对象的地址 . 所以字典不必搜索它 . 它只是计算哈希码并跳转到该位置 . Equals方法是对等式的更好测试,但不能用于将对象映射到地址空间 .

希望有所帮助

2 years ago

GetHashCode 用于Dictionary colections,它创建用于在其中存储对象的哈希 . 这是一篇很好的文章为什么以及如何使用 IEqualtyComparerGetHashCode http://dotnetperls.com/iequalitycomparer

2 years ago

虽然 Dictionary<TKey,TValue> 可以使 GetValue 和类似的方法在每个存储的密钥上调用 Equals 以查看它是否与正在搜索的密钥匹配,但这将非常慢 . 相反,与许多基于散列的集合一样,它依赖于 GetHashCode 来快速排除大多数不匹配的值 . 如果对正在寻找的项目调用 GetHashCode 产生42,而一个集合有53,917个项目,但在53,914个项目上调用 GetHashCode 产生的值不是42,那么只需要将3个项目与正在搜索的项目进行比较 . 其他53,914可以安全地被忽略 .

a GetHashCode 包含在 IEqualityComparer<T> 中的原因是为了允许字典的消费者可能想要视为通常不会将彼此视为相等的相等对象 . 最常见的示例是希望将字符串用作键但使用不区分大小写的比较的调用者 . 为了有效地工作,字典需要具有某种形式的散列函数,它将为"Fox"和"FOX"产生相同的值,但是希望为"box"或"zebra"提供其他产品 . 由于 String 中内置的 GetHashCode 方法不能以这种方式工作,因此字典需要从其他地方获取这样的方法,并且 IEqualityComparer<T> 是最合乎逻辑的地方,因为需要这样的哈希码与 Equals 非常紧密相关 . 认为"Fox"和"FOX"彼此相同但不是"box"或"zebra"的方法 .