6

我已经阅读了很多关于这个有趣的话题（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;
    }
}

我不明白 ：

问题

素数是否 同时用于:Dictionary capacity 和?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 不是素数。

也没有任何数学规则表明：

(not a prime number) + (prime number) = (prime number)

也不

(not a prime number) * (prime number) = (prime number)

也不

(not a prime number) * (not a prime number) = (prime number)

那么我错过了什么？

4

1 回答 1

8

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

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

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

稍微偏离主题：蝉（那是一种昆虫）使用素数来确定它们在多少年后再次交配。由于这个交配周期是质数年，因此交配与其任何敌人的生命周期持续一致的可能性很小。

于 2013-02-20T16:09:23.147 回答