这个问题是Jon Skeet对以下问题的回答:"对于被覆盖的System.Object.GetHashCode,最好的算法是什么?"。要计算哈希代码,使用以下算法:
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = 17;
// Suitable nullity checks etc, of course :)
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
hash = hash * 23 + field3.GetHashCode();
return hash;
}
}
我不明白为什么选择数字 17 和 23。我们为什么不选择 3 和 5?这也是质数。有人可以解释一下选择的最佳素数是什么以及为什么吗?
关于您链接到的答案的评论已经简要地尝试解释为什么17
和23
在这里使用不好
许多使用哈希代码的 .NET 类将元素存储在存储桶中。假设有三个存储桶。然后是哈希代码为 0、3、6、9、...存储在存储桶 0 中。哈希代码为 1、4、7、10、...存储在存储桶 1 中。存储桶 2、5、8、11、...存储在存储桶 2 中。
现在假设您的GetHashCode()
使用 hash = hash * 3 + field3.GetHashCode();
。这意味着,除非hash
足够大,可以进行乘法包装,否则在具有三个存储桶的哈希集中,对象最终会进入哪个存储桶仅取决于field3
。
由于对象在存储桶中的分布不均匀,HashSet<T>
无法提供良好的性能。
您需要一个对所有可能的存储桶数共同素数的因子。出于同样的原因,存储桶数量本身将是素数,因此如果您的因子是素数,唯一的风险是它等于桶数。
.NET 使用允许的存储桶数的固定列表:
public static readonly int[] primes = { 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};
你的因素应该是 .NET 不使用的因素,其他自定义实现也同样不太可能使用。这意味着23
是一个坏因素。 31
可以接受.NET 自己的容器,但对于自定义实现可能同样糟糕。
同时,它不应该太低,以至于为常见用途提供大量碰撞。这是3
和5
的风险:假设您有一个包含大量小整数的自定义Tuple<int, int>
实现。请记住,int.GetHashCode()
只是返回该int
本身。假设您的乘法因子为 3
。这意味着(0, 9)
、(1, 6)
、(2, 3)
和(3, 0)
都给出相同的哈希码。
这两个问题都可以通过使用足够大的素数来避免,正如Jon Skeet在他的答案中加入的评论所指出的那样:
编辑:如评论中所述,您可能会发现最好选择一个大的素数乘以。显然486187739很好...
曾几何时,用于乘法的大素数可能很糟糕,因为乘以大整数的速度足够慢,以至于性能差异很明显。在这种情况下,乘以 31
会很好,因为它可以实现为 x * 31
=> x * 32 - x
=> (x << 5) - x
.不过,如今,乘法不太可能导致任何性能问题,然后,一般来说,越大越好。