如何选择素数来计算哈希码?
这个问题遵循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
无法提供良好的性能。
您需要一个与所有可能数量的桶共同构成的因子。 由于相同的原因,桶本身的数量将是素数,因此如果您的因子是素数,唯一的风险是它等于桶的数量。
.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.GetHashCode()
只返回int
本身。 假设你的乘法因子是3
。 这意味着(0, 9)
, (1, 6)
, (2, 3)
和(3, 0)
都给出相同的哈希码。
使用足够大的素数可以避免这两个问题,正如Jon Skeet在他的回答中引用的评论中指出的那样:
编辑:正如评论中所指出的,你可能会发现最好选择一个大的素数乘以。 显然486187739很好……
曾几何时,用于乘法的大质数可能是坏的,因为大整数的乘法足够慢,性能差异很明显。 在这种情况下乘以31
会很好,因为它可以实现为x * 31
=> x * 32 - x
=> (x << 5) - x
。 然而,如今,乘法不太可能导致任何性能问题,然后,一般来说,越大越好。