在內部，散列如何查找獲取值的關鍵？

Question

從內部看，哈希如何查找獲取值的關鍵？

它是垃圾箱排序？

Answer 1

字典使用哈希碼來計算存儲條目的存儲區的數量。桶的數量被選爲質數，並且特定鍵的桶編號被計算爲密鑰的哈希碼以桶數爲模。由於多個對象可以具有相同的哈希代碼，並且多個哈希代碼可以位於同一個存儲桶中，因此當在存儲桶中找到密鑰時，還必須對它們進行比較以確保它是正確的密鑰。如果在存儲桶中找到了錯誤的密鑰，則會使用錯誤條目的next成員查找下一個位置以搜索所需的密鑰。

該算法的結果是，當沒有衝突時，可以非常快速地找到正確的桶 - O（1），但在最糟糕的情況下，它可能需要線性時間存儲在詞典中的條目數。我在這裏假設一個對象的哈希碼可以在不變的時間內計算出來。

在.NET執行的實際代碼可以通過下載參考實現源可以看出，或通過使用.NET反射器：

private int FindEntry(TKey key) 
{ 
    if (key == null) 
    { 
     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 
    } 
    if (this.buckets != null) 
    { 
     int num = this.comparer.GetHashCode(key) & 0x7fffffff; 
     for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next) 
     { 
      if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key)) 
      { 
       return i; 
      } 
     } 
    } 
    return -1; 
} 

Answer 2

散列僅僅是一個針對該創建密鑰算法運行（希望）一個指向哪個桶來存儲項目的唯一值。因此，當您計算值以嘗試檢索該項目時，您的希望是該哈希將指向您先前保存的對象。如果不是，則應該有一個指向哪裏尋找共享此散列值的下一個對象。當你找到你的物品時，它會返回。如果到達鏈條的末端，則無法找到您的物品。

請參閱Hash Tables和Hash Function以更全面地定義哈希。