字典<,>大小,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;
    }
}

我不明白:

题

难道素数使用 两种在: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)

那么什么我缺少什么？

Answer 1

结果GetHashCode是什么并不重要(它根本不必是素数),只要结果对于被认为是相等的两个对象是相同的.但是,对于被认为是不同的(但仍然不一定是素数)的两个对象,返回不同的值是很好的(但不是必需的GetHashCode).

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

在字典中,相同的原则适用:对象根据其哈希值放入存储桶中.由于大多数整数不能很好地除以素数,因此您可以在桶中很好地传播对象.理想情况下,您只需要每个存储桶中的一个项目以获得最佳字典性能.

稍微偏离主题:蝉(这是一种昆虫)使用素数来确定他们去多少年后再次交配.由于这个交配周期是素数年,因此交配的机会与其任何敌人的生命周期不断重合.