列表容量增加与字典容量增加

本文关键字：容量 增加 列表 字典 | 更新日期: 2023-09-27 17:56:49

为什么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？两者都在处理查找继续内存位置...正确？

列表<T>容量增加与字典<K，V>容量增加

通常对

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

哈希表通常使用模数运算来查找条目所属的存储桶，如代码所示：

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...}。但是，如果您的哈希表应该有数百万个条目，这可能会有点困难。

  2. 或者简单地通过使 GreatestCommonFactor（table_length， x） 等于 1 来使 m 等于table_length，即通过使 x 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（） 的定义。

字典根据

其GetHashCode值将其所有对象放入存储桶中，即

Bucket[object.GetHashCode() % DictionarySize] = object;它使用质数表示大小以避免碰撞的机会。据推测，具有许多除数的大小对于设计不佳的哈希码是不利的。

来自 SO 中的一个问题;

字典或哈希表依赖于对键进行哈希处理以获得较小的 索引以查找相应的存储（数组）。所以哈希的选择 功能非常重要。典型的选择是获取哈希代码 key（这样我们得到良好的随机分布），然后划分代码 通过质数并使用提醒索引成固定数 桶。这允许将任意大的哈希代码转换为 有界的小数集，我们可以定义一个数组来查找 上。因此，在质数中具有数组大小很重要，然后 大小的最佳选择成为较大的质数 超过所需容量。这正是字典 实现确实如此。

List<T>使用array来存储数据;增加阵列的容量需要将阵列复制到新的内存位置;这很耗时。我想，为了减少复制数组的发生，列表的容量增加了一倍。

我不是计算机科学家，但是...

最有可能的是，它与HashTable的负载因子有关（最后一个链接只是一个数学定义），并且为了不造成更多的混乱，对于不是数学听觉，定义这一点很重要： 

loadFactor = FreeCells/AllCells

我们可以这样写 

loadFactor = (AllBuckets - UsedBuckets)/AllBuckets

loadFactor 在哈希映射中定义了冲突的概率。因此，通过使用质数，一个

..是大于 1 的自然数 除了 1 和自身之外没有正除数。

我们减少（但不删除）哈希图中的冲突风险。

如果loadFactor趋向于0，我们有更安全的哈希图，因此我们始终必须将其保持在尽可能低的水平。通过MS博客，他们发现该loadFactor（最佳值）的值必须围绕0.72，因此，如果它变大，我们将在最近的素数之后增加容量。

编辑

更清楚地说明这一点：拥有一个素数，可以确保在 .NET 字典中哈希的具体实现中尽可能统一分配哈希。这不是关于检索值的效率，而是关于所用内存的效率和降低碰撞风险。

希望这有帮助。

Dictionary需要一些启发式的，以便存储桶之间的哈希代码分布更加统一。

.NET 的Dictionary使用质数桶来执行此操作，然后像这样计算桶索引：

int num = this.comparer.GetHashCode(key) & 2147483647; // make hash code positive
// get the remainder from division - that's our bucket index
int num2 = this.buckets[num % ((int)this.buckets.Length)];

当它增长时，它会将桶的数量加倍，然后再添加一些桶以使数字再次成为素数。

这不是唯一可能的启发式方法。例如，Java的HashMap采用了另一种方法。那里的存储桶数量始终是 2 的幂，并且在增长时，它只会使存储桶数量翻倍：

resize(2 * table.length);

但是在计算存储桶索引时，它会修改哈希：

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
    return h & (length-1);
}
// from put() method
int hash = hash(key.hashCode()); // get modified hash
int i = indexFor(hash, table.length); // trim the hash to the bucket count

另一方面，List不需要任何启发式方法，所以他们没有打扰。

补充：成长行为根本不影响Add的复杂性。 Dictionary、HashMap和List都摊销了O（1）Add复杂度。

生长操作需要 O（N） 但只发生第 N 次，因此要导致生长操作，我们需要调用 Add N 次。对于 N=8，执行 N Add s 所需的时间具有以下值

O（1）+O（1）+O（1）+O（1）+O（1）+O（1）+O（

1）+O（1）+O（N） = O（N）+O（N） = O（2N） = O（N）

所以，N Add取 O（N），然后一个Add取 O（1）。

当需要调整大小时，按常数增加容量（而不是例如通过加法常数增加容量）以保证一些摊销的运行时间。例如，在基于阵列的列表的末尾添加或删除需要O(1)时间，除非您必须增加或减少复制列表内容所需的容量，因此需要O(n)时间。按常数因子更改容量可确保摊销的运行时间仍O(1)。因子的最佳值取决于预期使用情况。维基百科上的更多信息。

选择哈希表的容量作为素数用于改善项目的分布。 如果hash不是均匀分布的，则bucket[hash % capacity]将产生更均匀的分布，如果capacity是素数。（我不能给出背后的数学，但我正在寻找一个很好的参考。这一点与第一点的结合正是实现所做的 - 将容量增加（至少）2 倍，并确保容量是主要的。

相关文章：