20

为什么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？两者都在处理寻找持续的内存位置......对吗？

4

6 回答 6

2

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

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

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

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

  1. 确保您不会生成太多的 hashCodes，这些 hashCodes 是另一个 hashCode 的倍数，例如 {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() 的定义。

于 2013-01-30T08:20:40.790 回答
1

Dictionary需要一些启发式方法，以便桶之间的哈希码分布更加均匀。

.NETDictionary使用质数的桶来做到这一点，然后像这样计算桶索引：

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)];

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

这不是唯一可能的启发式方法。HashMap例如，Java采用了另一种方法。桶的数量总是 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's 的复杂性。Dictionary，HashMap并且每个都具有O(1) 的List摊销复杂度。Add

增长操作需要 O(N) 但只发生第 N 次，因此要进行增长操作，我们需要调用AddN 次。对于 N=8，执行 N Adds 所需的时间具有值

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 Adds 取 O(N)，然后一个Add取 O(1)。

于 2013-01-30T08:41:26.737 回答
1

来自SO中的一个问题；

字典或散列表依赖于散列键以获得较小的索引来查找相应的存储（数组）。所以哈希函数的选择非常重要。典型的选择是获取一个键的哈希码（这样我们得到良好的随机分布），然后将代码除以一个素数，并使用提醒索引到固定数量的桶中。这允许将任意大的哈希码转换为一组有界的小数字，我们可以为其定义一个要查找的数组。因此，将数组大小设为素数很重要，然后大小的最佳选择成为大于所需容量的素数。这正是字典实现所做的。

List<T>使用arrays 存储数据；并且增加数组的容量需要将数组复制到新的内存位置；这很耗时。我想，为了降低复制数组的发生率，list 的容量会增加一倍。

于 2013-01-30T08:28:05.637 回答
1

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

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

loadFactor = FreeCells/AllCells

这我们可以写成 

loadFactor = (AllBuckets - UsedBuckets)/AllBuckets

loadFactor定义哈希映射中的碰撞概率。因此，通过使用质数，一个数字

..是一个大于 1 的自然数，除了 1 和它本身之外没有正除数。

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

如果loadFactor趋于0，我们有更安全的哈希图，所以我们总是必须保持它尽可能低。通过 MS博客，他们发现那个loadFactor（最佳值）的值必须是 arround 0.72，所以如果它变大，我们会增加最接近素数的容量。

编辑

为了更清楚地说明这一点：拥有一个质数，尽可能确保在我们在 .NET 字典中的哈希的具体实现中均匀分布哈希。这与检索值的效率无关，而是与内存使用效率和碰撞风险降低有关。

希望这可以帮助。

于 2013-01-30T08:28:09.210 回答
1

Dictionary 根据其 GetHashCode 值将其所有对象放入桶中，即
Bucket[object.GetHashCode() % DictionarySize] = object;
它使用质数作为大小以避免发生冲突的机会。据推测，具有许多除数的大小对于设计不佳的哈希码是不利的。

于 2013-01-30T08:17:25.357 回答
0

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

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

于 2013-01-30T09:36:32.387 回答