c# - 这个hash函数会不会异常频繁的碰撞？

Question

我有以下代码来生成对象的哈希值:

public int GetHashCode(MyType obj)
{
   return (obj.Prop1.GetHashCode() + obj.Prop2.GetHashCode() + obj.Prop3.GetHashCode()).GetHashCode();
}

即我添加了所有属性的哈希码，然后取其哈希值。

在审查中，一位同事建议这会经常发生冲突。我不确定这是真的，因为:

1. 鉴于在正数和负数之间以相同的频率选择哈希码并且它们环绕，我认为我们没有获得任何关于这些数字总和的可能性的额外信息，而不是数字本身
2. 在某种程度上，它们的总和是非随机的，哈希码旨在使“靠近”的数字变得“相距甚远”，因此将非均匀分布的值输入函数不应该是问题

谁是对的？

它在 C# 中，以防答案是特定于语言的。

Answer 1

是的。

假设 Prop1、Prop2 等的类型是 int .通常只使用较低范围的整数。您的 sum 方法会比必要的更频繁地发生冲突。

7的HasCode是 7，这在散列 int 时非常有意义通过它自己。但是对于您的代码，元组 <7, 3> , <3, 7>和 <8, 2>都将具有相同的哈希值。与简单的 XOR 而不是加法相同。

常用的方法是添加一些(质数)数并进行移位:

public int GetHashCode(MyType obj)
{
  int hash = 0;
  unchecked
  {         
     hash += 19 * obj.Prop1.GetHashCode();
     hash += 31 * obj.Prop2.GetHashCode();
     hash += 37 * obj.Prop3.GetHashCode();
  }
  return hash;
}

数字 19、31、37 并不太重要。如果您愿意，可以使用 OR 或 XOR 代替 + .