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

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>都会有相同的哈希.与简单的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代替+.