这个哈希函数会不会异常频繁地发生碰撞？

Question

我有以下代码用于生成一个对象的哈希值：

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

即，我将所有属性的哈希码相加，然后对此哈希。在审查中，一位同事认为这样会发生碰撞太频繁。但我不确定这是否正确，因为：

1. 哈希码在正数和负数之间以相等的频率选择，并且它们会循环，所以我认为我们没有获得任何有关这些数字总和可能性的额外信息，而是只能获得数字本身。

2. 在哈希码设计中，为了使“接近”的数字变得“远离”，哈希码被设计成生成非随机分布值时也不应该出现问题。

谁是正确的？

如果答案具有语言特定性，则是C#。

- Xodarap

---

你的同事有什么原因？ - Oliver Charlesworth

Answer 1

是的。

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

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 替代 + 。

- H H

---

质数很好，而且比移位更可取，因为一个简单的分箱算法可能只会取HashCode的低N位；如果属性被移位，它们可能会被完全忽略。 - Dan Bryant

Answer 2

使用异或更好：

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

- Darin Dimitrov

---

请参考Henk Holterman的论述。如果某些属性的GetHashCode没有使用整个范围，则与移位混合应该提供更好的分布... - Alexei Levenkov

Answer 3

你可以使用修改过的FNV HashCode生成器，一个非常相似的问题已经被我回答了这里

- Marcel Valdez Orozco