这个哈希函数会异常频繁地发生冲突吗？

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 类型。通常仅使用较低范围的整数。你的求和方法会发生不必要的冲突。

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

常见的方法是添加一些（质数）数字并进行移位：

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 而不是 + 。

Answer 2

异或会更好：

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

Answer 3

您可以使用修改后的 FNV HashCode 生成器，一个非常相似的问题已被回答（由我）
此处