.NET中IEqualityComparer<T>中的GetHashCode方法的作用是什么？

Question

.NET中IEqualityComparer<T>中的GetHashCode方法的作用是什么？

163

我正在尝试理解接口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方法呢？

谢谢。

Lucian

- Lucian

阅读一下：http://en.wikipedia.org/wiki/Hash_table 然后看看你是否更好地理解了GetHashCode的目的。 - spender

1

请查看这个很棒的答案：https://dev59.com/M3VD5IYBdhLWcg3wE3Xz#3719802 - Mikhail Poda

3个回答

9

GetHashCode被用于字典集合中，它为存储对象创建哈希。以下是一篇很好的文章，介绍了如何使用IEqualtyComparer和GetHashCode：http://dotnetperls.com/iequalitycomparer

- Ash

4

更多：如果你只需要比较是否相等，那么使用"Equals"就足够了，但是当你需要从字典中获取元素时，通过哈希来实现会更容易，而不是使用"Equals"。 - Ash

5

虽然一个Dictionary<TKey,TValue>可能会在其GetValue和类似方法中调用每个存储的键来查看是否匹配正在寻找的键，但这将非常缓慢。与许多基于哈希的集合一样，它依赖于GetHashCode来快速排除大多数不匹配的值。如果在搜索项上调用GetHashCode产生42，并且集合有53,917个项，但在53,914个项上调用GetHashCode产生的值不是42，则只有3个项需要与正在搜索的项进行比较。其他53,914个项可以安全地忽略。 GetHashCode包含在IEqualityComparer<T>中的原因是为了允许字典的使用者将通常不相互视为相等的对象视为相等。最常见的例子是调用方想要使用字符串作为键，但使用不区分大小写的比较。为了使其有效工作，字典将需要某种形式的哈希函数，在其中“Fox”和“FOX”将产生相同的值，但希望对“box”或“zebra”产生其他值。由于内置于String中的GetHashCode方法不起作用，因此字典将需要从其他地方获取此类方法，而IEqualityComparer<T>是最合适的地方，因为需要这样的哈希代码与将“Fox”和“FOX”视为相同但不视为“box”或“zebra”的Equals方法密切相关。

- supercat

问题的正确而简明的答案是：GetHashCode()必须为相关对象的Equals()提供补充。 - Social Developer

@Sumith：许多关于哈希的讨论都涉及到桶，但我认为考虑排除更有用。如果比较很昂贵，即使使用没有组织成桶的集合，哈希也可以提供好处。 - supercat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sheikhjabootie · Accepted Answer

首先了解一些背景......

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

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

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

字典是一种非常酷的数据结构，它为（或多或少）恒定的添加/删除/获取操作成本交换更高的内存占用。但它不适合迭代。在内部，字典包含一个桶数组，其中可以存储值。当向字典添加键和值时，会在键上调用GetHashCode方法。返回的哈希码用于确定应存储键/值对的桶的索引。

当你想要访问值时，再次传入键。在键上调用GetHashCode方法，然后找到包含该值的桶。

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

现在来解释为什么需要两种方法，请考虑以下示例：

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方法以找到正确的键。

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

简而言之

因此，总之，GetHashCode方法用于生成对象存储的地址。所以字典无需搜索它，只需计算哈希码并跳转到该位置。Equals方法是更好的相等性测试，但不能用于将对象映射到地址空间。