2

我想知道哈希表在增加容量时如何找到正确的索引。例如，假设我有一个默认容量为 10 的哈希表。现在我们必须添加 (key,value) 对 [14,"hello 1"]

我们将使用下面的索引机制为上面的键 '14' 获得的索引是 '4'。所以 hashtable 会把这个 (key,value) 对保存在索引 4 中。

int index = key.GetHashCode() % 10

现在我们继续将项目添加到哈希表中，它达到了负载因子。所以是时候调整大小了。让我们假设 hastable resize 到 20。

现在我要在这个哈希表中搜索我的旧键“14”。现在根据索引机制，我将得到这个键的索引为 14。所以我将从索引 14 开始搜索哈希表，但理想情况下它在索引 4 中。

所以我的问题是哈希表在调整大小时如何跟踪现有的键索引？或者哈希表在调整大小时是否会重新散列所有现有键？

4

2 回答 2

2

您可能想阅读hash tables，但我认为您缺少的概念是：

  • 对于给定的密钥，比如“asdf”，有一个给定的 32 位 int 哈希码。
  • 要获得索引存储中的位置，您应用模数 ( %) hashCode % length-- 因此如果您将表从 10 增加到 20，结果将更改为新索引。实现当然会确保每个现有条目都在新表的正确存储桶中。
于 2012-12-10T01:58:14.710 回答
1

我查看了 .Net 的共享源 CLI 实现，看起来条目在扩展时重新散列。但是，没有必要使用 .GetHashCode() 重新计算 HashCode。

如果您查看实现，您将看到expand()发生以下步骤的方法：

  1. 创建一个临时存储桶数组，并将其调整为大于其当前大小两倍的最小素数。
  2. 通过从旧存储桶数组重新散列来填充新数组。

.

for (nb = 0; nb < oldhashsize; nb++)
{
    bucket oldb = buckets[nb];
    if ((oldb.key != null) && (oldb.key != buckets))
    {
        putEntry(newBuckets, oldb.key, oldb.val, oldb.hash_coll & 0x7FFFFFFF);
    }
}



private void putEntry (bucket[] newBuckets, Object key, Object nvalue, int hashcode)
{
    BCLDebug.Assert(hashcode >= 0, "hashcode >= 0");  // make sure collision bit (sign bit) wasn't set.

    uint seed = (uint) hashcode;
    uint incr = (uint)(1 + (((seed >> 5) + 1) % ((uint)newBuckets.Length - 1)));

    do 
    {
        int bucketNumber = (int) (seed % (uint)newBuckets.Length);

        if ((newBuckets[bucketNumber].key == null) || (newBuckets[bucketNumber].key == buckets)) 
        {
            newBuckets[bucketNumber].val = nvalue;
            newBuckets[bucketNumber].key = key;
            newBuckets[bucketNumber].hash_coll |= hashcode;
            return;
        }
        newBuckets[bucketNumber].hash_coll |= unchecked((int)0x80000000);
        seed += incr;
        } while (true);
    }
}

新数组已经构建完成，将在后续操作中使用。

此外，来自 MSDN 关于 Hashtable.Add()：

如果 Count 小于 Hashtable 的容量，则此方法是 O(1) 操作。如果需要增加容量以容纳新元素，则此方法变为 O(n) 操作，其中 n 为 Count。

于 2012-12-10T01:57:58.480 回答