c# - Dictionary <,> Size 、GetHashCode 和素数？

Question

我已经阅读了很多关于这个有趣主题 (IMO) 的文章。但我不完全理解一件事:

字典大小正在增加其容量(加倍到最接近的素数)到素数(重新分配时): 因为:

int index = hashCode % [Dictionary Capacity];

• 所以我们可以看到这里使用质数作为[Dictionary Capacity]，因为它们的GreatestCommonFactor是1。这有助于避免碰撞。

此外

我看过很多实现 GetHashCode() 的示例:

这是 Jon Skeet 的示例:

public override int GetHashCode()
{
    unchecked 
    {
        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;
    }
}

我不明白:

问题

Does prime numbers are used both in : Dictionary capacity and in the generation of getHashCode ?

因为在上面的代码中，返回值很有可能不是是质数[如果我错了请纠正我]因为

• 乘以23
• 为每个字段添加 GetHashCode() 值。

例如:(11,17,173 是素数)

        int hash = 17;
        hash = hash * 23 + 11; //402
        hash = hash * 23 + 17; //9263
        hash = hash * 23 + 173 //213222
        return hash;

213222 不是素数。

也没有任何数学规则说明:

(非质数)+(质数)=(质数)

也不

(不是质数)*(质数)=(质数)

也不

(非质数)*(非质数)=(质数)

那么我错过了什么？

Answer 1

GetHashCode 的结果是什么并不重要(它根本不必是质数)，只要两个被认为相等的对象的结果相同即可。但是，让 GetHashCode 为两个被认为不同(但不一定是质数)的对象返回不同的值是很好(但不是必需的)。

给定两个数字 a 和 b，将它们相乘可得到 c = a * b。通常有多个不同的 a 和 b 对产生相同的结果 c。例如 6 * 2 = 12 和 4 * 3 = 12。但是，当 a 是一个素数 时，给出相同结果的对数会少很多。这对于不同对象的散列码应该不同的属性来说很方便。

在字典中，同样的原则适用:对象根据它们的哈希值被放入桶中。由于大多数整数不能很好地除以质数，因此您可以很好地分散桶中的对象。理想情况下，您希望每个桶中只有一个项目以获得最佳词典性能。

---

稍微跑题了:蝉(那是一种昆虫)use prime numbers以确定多少年后他们会再次交配。由于这个交配周期是主要年数，因此交配持续与其任何敌人的生命周期重合的可能性很小。