哈希表在调整大小时如何跟踪现有密钥索引？

我想知道hashtable在增加容量时如何找到正确的索引。例如，让我们假设我有一个默认容量10哈希表现在，我们必须添加（键，值）对 [14，“你好1”]哈希表在调整大小时如何跟踪现有密钥索引？

，我们将获得上述键“14”使用索引下面的索引机制是'4'。因此，哈希表要拯救这个（键，值）对指数4

int index = key.GetHashCode() % 10

现在我们继续添加项目到哈希表内，并达到客座率。所以是时候调整大小了。假设hastable调整为20.

现在我要在我的旧密钥'14'中搜索这个哈希表。并根据索引机制现在我会得到这个键的索引为14.所以我会开始搜索索引14的哈希表，但理想情况下，它是在索引4.

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

来源

2012-12-10 Pritam Karmakar

@MitchWheat - 他的标记有点......含糊不清，所以我没有声称c＃实现的功能。我将删除那一个并重申：“那么，这取决于它如何实施”。 –

在本文中，有一节“加载因子和扩展哈希表”，阅读完它后，它看起来像C＃哈希表也调整http://msdn.microsoft.com/en-us/library/ms379571%28v=VS.80 ％29.aspx＃datastructures20_2_topic5 –

我删除了Java标记并为此感到抱歉 –

我查看了Shared Source CLI implementation for .Net，它看起来像条目在扩展时重新对齐。但是，没有必要使用.GetHashCode（）重新计算HashCode。

如果你通过实施你会看到expand()方法，其中进行以下步骤：

临时桶阵列创建和尺寸最小质大于两倍现在的规模。
新数组通过重新哈希来自旧桶阵列进行填充。

。

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（）：

If Count is less than the capacity of the Hashtable, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

来源

2012-12-10 01:57:58 JoshVarty

你可能想在hash tables读了，但这个概念我觉得你错过的是：

对于给定的键，说“asdf”，有一个给定的32位int散列码。
获得索引存储中的位置，你申请的hashCode % length模量（%） - 所以，如果你发展你的表从10到20，结果改变的新指标。实施过程当然会进行，并确保每个现有条目都位于新表格的适当桶中。

来源

2012-12-10 01:58:14

哈希表在调整大小时如何跟踪现有密钥索引？

回答

相关问题