哈希表在調整大小時如何跟蹤現有密鑰索引？

我想知道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

哈希表在調整大小時如何跟蹤現有密鑰索引？

回答

相關問題