为包含集合的对象实现GetHashCode()

Question

考虑以下对象:

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关于这个主题的文章,但是找不到我想要的东西.

Answer 1

我认为您的解决方案很好.(很久以后的评论: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;
}

附录(接受答复后):

请记住,如果您在使用哈希表的Routinga Dictionary<Routing, Whatever>,a HashSet<Routing>或其他情况下使用此类型,那么如果有人在将其添加到集合后改变(变异),则您的实例将会丢失Routing.

如果您确定永远不会发生,请使用上面的代码.Dictionary<,>如果确保没有人改变Routing引用的内容,那么仍然有效.

另一个选择就是写

public override int GetHashCode()
{
  return 0;
}

如果您认为永远不会使用哈希码.如果每个instace都返回0哈希码,那么哈希表的性能会非常差,但是你的对象不会丢失.第三种选择是扔一个NotSupportedException.

Answer 2

来自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;
}

随着越来越多的项目被散列,此代码将至少涉及所有位.

Answer 3

作为指导原则,对象的哈希值必须与对象的整个生命周期相同.我会GetHashCode单独留下这个功能,而不是覆盖它.仅当您要将对象放在哈希表中时才使用哈希码.

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

引用该文章:

准则:GetHashCode返回的整数永远不会改变

规则:当对象包含在依赖于哈希代码保持稳定的数据结构中时,GetHashCode返回的整数必须永远不会更改

如果对象的哈希代码在哈希表中变异,那么显然Contains方法就会停止工作.你把对象放在#5桶中,你改变它,当你问集合是否包含变异对象时,它会在#74桶中查找并找不到它.

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