c# - List 容量增加与 Dictionary 容量增加？

Question

为什么 List<T>将其容量增加 2 倍？

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

为什么 Dictionary<K,V>使用质数作为容量？

private void Resize()
{
    int prime = HashHelpers.GetPrime(this.count * 2);
    int[] numArray = new int[prime];
    for (int i = 0; i < numArray.Length; i++)
    {
        numArray[i] = -1;
    }
    Entry<TKey, TValue>[] destinationArray = new Entry<TKey, TValue>[prime];
    Array.Copy(this.entries, 0, destinationArray, 0, this.count);
    for (int j = 0; j < this.count; j++)
    {
        int index = destinationArray[j].hashCode % prime;
        destinationArray[j].next = numArray[index];
        numArray[index] = j;
    }
    this.buckets = numArray;
    this.entries = destinationArray;
}

为什么它不乘以 2？两者都在寻找继续内存位置……对吗？

Answer 1

哈希表大小通常使用质数，因为它可以降低冲突的可能性。

哈希表通常使用模运算来查找条目所属的桶，如您在代码中所见:

int index = destinationArray[j].hashCode % prime;

假设您的 hashCode 函数产生以下 hashCodes，其中包括 {x , 2x, 3x, 4x, 5x, 6x...}，那么所有这些都将聚集在 m 个桶中，其中 m = table_length/GreatestCommonFactor(table_length, x)。 (验证/推导这个很简单)。现在您可以执行以下操作之一来避免集群:

1. 确保您不会生成太多哈希码，这些哈希码是另一个哈希码的倍数，例如 {x, 2x, 3x, 4x, 5x, 6x...}。但这可能有点困难，如果你的 hashTable 应该有数百万个条目。

2. 或者简单地通过使 GreatestCommonFactor(table_length, x) 等于 1 使 m 等于 table_length，即通过使 table_length 与 x 互质。如果 x 几乎可以是任何数字，那么请确保 table_length 是质数。

(来自 http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html)

HashHelpers.GetPrime(this.count * 2) 

应该返回一个质数。查看 HashHelpers.GetPrime() 的定义。