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 的复杂性。DictionaryHashMap并且每个都具有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 回答