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

Question

这个问题是在 Jon Skeet 对问题“What is the best algorithm for an overridden 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？那也是质数。有人可以解释一下最好的素数是什么以及为什么吗？

Answer 1

您 link 对答案的评论已经简要地尝试解释了为什么 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 使用 a fixed list of allowed numbers of buckets:

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() 只是 returns int 本身。假设你的乘数是3。这意味着 (0, 9)、(1, 6)、(2, 3) 和 (3, 0) 都给出相同的哈希码。

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

EDIT: As noted in comments, you may find it's better to pick a large prime to multiply by instead. Apparently 486187739 is good...

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

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

How to pick prime numbers to calculate the hash code?

.net

c#

hash

primes

gethashcode