如何选取质数来计算哈希码？

这个问题是根据乔恩·斯基特（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 and 23在这里使用不是很好的素数。

许多使用哈希码的 .NET 类将元素存储在buckets。假设有三个桶。然后，哈希码为 0, 3, 6, 9, ... 的所有对象都存储在存储桶 0 中。 哈希码为 1, 4, 7, 10, ... 的所有对象都存储在存储桶 1 中。 存储桶 2 的所有对象, 5, 8, 11, ... 存储在存储桶 2 中。

现在假设你的GetHashCode() uses hash = hash * 3 + field3.GetHashCode();。这意味着除非hash在具有三个存储桶的哈希集中，足够大以便乘法能够环绕，对象最终会进入哪个存储桶仅取决于field3.

由于存储桶中的对象分布不均匀，HashSet<T>无法提供良好的性能。

您需要一个与所有可能数量的桶互质的因子。出于同样的原因，桶本身的数量将是素数，因此，如果您的因子是素数，唯一的风险是它是equal到桶的数量。

.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 and 5: 假设你有一个习惯Tuple<int, int>用很多小整数实现。请记住int.GetHashCode()只是返回int本身。假设你的乘数是3。这意味着(0, 9), (1, 6), (2, 3) and (3, 0)都给出相同的哈希码。

通过使用足够大的素数可以避免这两个问题，正如 Jon Skeet 在他的答案中纳入的评论中指出的那样：

编辑：正如评论中所述，您可能会发现最好选择一个大素数来相乘。显然 486187739 不错...

曾几何时，大素数用于乘法可能很糟糕，因为乘以大整数的速度非常慢，以至于性能差异非常明显。乘以31在这种情况下会很好，因为它可以实现为x * 31 => x * 32 - x => (x << 5) - x。但如今，乘法引起任何性能问题的可能性要小得多，而且一般来说，乘法越大越好。