28

考虑以下对象：

class Route
{
   public int Origin { get; set; }
   public int Destination { get; set; }
}

Route 实现了相等运算符。

class Routing
{
   public List<Route> Paths { get; set; }
}

我使用下面的代码为 Routing 对象实现 GetHashCode 方法，它似乎有效，但我想知道这是否是正确的方法？我依靠平等检查，因为我不确定，我想我会问你们。我可以只对哈希码求和还是需要做更多的魔术才能保证达到预期的效果？

public override int GetHashCode() =>
{
    return (Paths != null 
                ? (Paths.Select(p => p.GetHashCode())
                        .Sum()) 
                : 0);
}

我在这里检查了几个GetHashCode()问题以及 MSDN 和 Eric Lippert 关于此主题的文章，但找不到我要查找的内容。

4

4 回答 4

18

我认为你的解决方案很好。（稍后会说：LINQ 的Sum方法将在上下文中起作用checked，因此您可以很容易地得到一个OverflowException，这意味着它毕竟不是那么好。）但是更常见的是进行 XOR（不带进位的加法）。所以它可能是这样的

public override int GetHashCode()
{
  int hc = 0;
  if (Paths != null)
    foreach (var p in Paths)
      hc ^= p.GetHashCode();
  return hc;
}

附录（答案被接受后）：

请记住，如果您曾经Routing在 a Dictionary<Routing, Whatever>、 a或其他使用哈希表的情况下使用此类型，那么如果有人在将其添加到集合后更改（变异）HashSet<Routing>您的实例，那么您的实例将丢失。Routing

如果您确定这永远不会发生，请使用我上面的代码。Dictionary<,>如果您确保没有人更改所Routing引用的内容，依此类推。

另一种选择是只写

public override int GetHashCode()
{
  return 0;
}

如果您认为永远不会使用哈希码。如果每个实例都返回0哈希码，则哈希表的性能会很差，但您的对象不会丢失。第三种选择是抛出NotSupportedException.

于 2012-05-12T21:24:17.913 回答
10

Jeppe Stig Nielsen 的答案中的代码有效，但它可能导致大量重复的哈希码值。假设您正在对 0-100 范围内的整数列表进行哈希处理，那么您的哈希码将保证在 0 到 255 之间。这在字典中使用时会产生很多冲突。这是一个改进的版本：

public override int GetHashCode()
{
  int hc = 0;
  if (Paths != null)
    foreach (var p in Paths) {
        hc ^= p.GetHashCode();
        hc = (hc << 7) | (hc >> (32 - 7)); //rotale hc to the left to swipe over all bits
    }
  return hc;
}

随着越来越多的项目被散列进来，这段代码至少会随着时间的推移涉及所有位。

于 2012-05-12T21:30:04.123 回答
6

作为准则，对象的哈希在对象的整个生命周期内必须相同。我会GetHashCode单独保留该功能，而不是覆盖它。仅当您想将对象放在哈希表中时才使用哈希码。

您应该阅读 Eric Lippert 关于 .NET 中哈希码的精彩文章：GetHashCode 的指南和规则。

引用那篇文章：

准则：GetHashCode 返回的整数永远不应该改变

规则：当对象包含在依赖于哈希码保持稳定的数据结构中时，GetHashCode 返回的整数永远不能改变

如果对象的哈希码在哈希表中时可能会发生变异，那么显然 Contains 方法将停止工作。您将对象放入存储桶#5，对其进行变异，当您询问集合是否包含变异对象时，它在存储桶#74 中查找并没有找到它。

您实现的GetHashCode函数在对象的生命周期内不会返回相同的哈希码。如果使用此函数，如果将这些对象添加到哈希表中，就会遇到麻烦：该Contains方法将不起作用。

于 2012-05-12T21:25:44.137 回答
0

我认为这不是正确的做法，因为要确定最终hashcode它对于指定对象必须是唯一的。在您的情况下，您执行 a Sum()，它可以在集合中使用不同的哈希码产生相同的结果（最后哈希码只是整数）。

如果您的意图是根据集合的内容确定相等性，此时只需比较两个对象之间的这些 cillections。顺便说一句，这可能是一项耗时的操作。

于 2012-05-12T21:22:03.197 回答