c# - 这个哈希函数会异常频繁地碰撞吗？

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. 通常只使用较低的整数范围。您的求和方法将比必要的更频繁地发生冲突。

HasCode 的7值为 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 生成器，一个非常相似的问题已被回答（由我） here