这个散列函数会异常频繁地发生冲突吗

本文关键字：冲突 散列函数 异常 | 更新日期: 2023-09-27 17:58:47

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

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

也就是说，我添加了所有属性的哈希代码，然后取其哈希值。

在评论中，一位同事表示，这将过于频繁地发生冲突。我不确定这是真的，因为：

  1. 考虑到哈希码是在正数和负数中以相同的频率选择的，并且它们是环绕的，我认为我们没有获得任何关于这些数字求和的可能性的额外信息，而不是数字本身
  2. 在一定程度上，它们的总和是非随机的，哈希码的设计目的是让"靠得很近"的数字变得"相距很远"，因此向函数中输入非均匀分布的值应该不是问题

谁是正确的？

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

这个散列函数会异常频繁地发生冲突吗

是。

假设Prop1、Prop2等属于int类型。通常只使用较低范围的整数。你的求和方法会经常发生冲突。

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

XORing会更好：

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

您可以使用经过修改的FNV HashCode生成器，（我）已经回答了一个非常类似的问题此处

相关文章：