List <T>容量增加vs词典<K,V>容量增加？

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(表长度，x)。（验证/推导这一点很简单）。现在您可以执行以下操作之一来避免聚类：

1. 确保您不会生成太多作为另一个 hashCode 的倍数的 hashCode，例如 {x, 2x, 3x, 4x, 5x, 6x...}。但是如果您的 hashTable 应该具有数以百万计的条目。

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

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

HashHelpers.GetPrime(this.count * 2) 

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