爲什麼我們在HashTable中使用哈希代碼而不是索引？

GetHashCode（）函數如何生成整數哈希值？這是一個不是唯一的隨機值嗎？爲什麼我們在HashTable中使用哈希代碼而不是索引？
在字符串中，它被覆蓋以確保只存在一個特定字符串的哈希碼。如何做到這一點？
如何使用哈希碼加快哈希表中的特定鍵的搜索速度？
使用哈希碼直接在集合中使用索引（如數組中）有什麼優點？

有人可以幫忙嗎？

2009-05-23 Jaywith.7

基本上，哈希函數使用一些泛型函數來消化數據併爲該數據生成指紋（和整數）。與索引不同，這個指紋只依賴於數據，並且應該沒有基於數據的任何可預測的排序。對數據的單個位進行任何更改都會顯着改變指紋。

請注意，這不保證不同的數據不會給出相同的散列值。事實恰恰相反：這種情況經常發生，稱爲碰撞。但是，對於一個整數，這個概率大約是40億分之一（1^2^32）。如果碰撞發生，您只需比較您正在哈希的實際對象以查看它們是否匹配。

該指紋然後可以用作存儲值的陣列（或陣列列表）的索引。由於指紋僅依賴於數據，因此可以計算某個值的散列值，只需檢查該散列值的數組元素以查看它是否已被存儲。否則，你必須通過整個數組檢查它是否與一個項目匹配。

你也可以通過使用2個數組非常快地完成關聯數組，其中一個使用鍵值（由散列索引），另一個使用映射到這些鍵的值。如果你使用散列，你只需要知道密鑰的散列值就可以找到密鑰的匹配值。這比在排序的鍵列表上進行二分搜索要快得多，或者是對整個數組進行掃描以找到匹配的鍵。

有許多方法可以生成散列，它們都有各種優點，但很少有簡單的方法。我建議查閱哈希函數的維基百科頁面以獲取更多信息。

來源

2009-05-23 07:09:38 BobMcGee

哈希不是「或多或少隨機」;它只是少。因此不那麼隨機，以至於根本不隨機。更好的詞將是「任意的」。通過說散列是「對於這些數據是唯一的」，你確保「不同的數據不會給出相同的散列」。由於這顯然是錯誤的，「獨特」不是合適的詞。 – 2009-05-23 07:24:58

HashCode是一個僞唯一密鑰。我們希望有一個非常獨特的關鍵，但這是不可行的。我們解決了一個快速和安全（無例外）功能。

A HashTable最初使用HashCode在O（1）時間內進行查找。任何索引方案都需要O（log（n））時間。但是由於HashCode函數效率低下，碰撞處理可能會使HashTable變慢很多。

在.NET中有一個GetHashCode的默認實現，但類型可以覆蓋它。

System.String覆蓋GetHashCode（），因爲它重寫了Equals（），然後GetHashCode必須保持一致。

來源

2009-05-23 09:10:02

回答您的問題直接每一個：

由的GetHashCode的（）函數是如何產生的整數哈希？它是不是唯一的隨機值？

整數哈希由任何適合該對象的方法生成。生成方法不是隨機的，但必須遵循一致的規則，確保爲一個特定對象生成的哈希值等於爲等效對象生成的哈希值。作爲一個例子，一個整數的散列函數就是簡單地返回該整數。

在字符串，它被覆蓋，使確保只存在一個哈希特定字符串代碼。如何這樣做？

有很多方法可以做到。下面是我當場思維的例子：

int hash = 0; 
for(int i = 0; i < theString.Length; ++i) 
{ 
    hash ^= theString[i]; 
}

這是一個有效的哈希算法，因爲相同的字符序列，總是會產生相同的哈希數。這不是好的哈希算法（極度低估），因爲許多字符串將產生相同的散列。有效的散列算法不必保證唯一性。 A 好的散列算法將使兩個不同對象產生相同數字的機會極不可能。

如何使用散列碼加快哈希表中的特定鍵的搜索速度？使用哈希碼直接在集合中使用索引（如數組）的優點是什麼？

散列碼通常用於散列表中。哈希表是一個數組，但數組中的每個條目都是一個「桶」的項目，而不僅僅是一個項目。如果你有一個對象，你想知道哪個桶它屬於，計算

hash_value MOD hash_table_size.

然後你只需要在物體在桶中的每一項進行比較。因此，哈希表查找很可能具有O（1）的搜索時間，而非排序列表的O（log（N））或未排序列表的O（N）。

來源

2009-05-23 09:41:55

哈希碼是一個索引，哈希表在其最低級別是一個數組。但是對於給定的鍵值，我們以不同的方式確定哈希表中的索引，以便更快地進行數據檢索。

示例：您有1,000個單詞及其定義。您希望將它們存儲起來，以便您可以非常快速地檢索單詞的定義 - 比二元搜索更快，這就是您需要對數組執行的操作。

所以你創建一個哈希表。您從一個數組開始的數量大大超過1,000個條目 - 比如5,000（更大，更省時）。

您使用表格的方式是，您需要查找單詞並將其轉換爲介於0和4,999之間的數字。你選擇這樣做的算法;這就是哈希算法。但你無疑可以寫出速度非常快的東西。

然後，使用轉換後的數字作爲5000元素數組的索引，並在該索引中插入/找到您的定義。根本沒有搜索：你已經直接從搜索詞創建索引。

我所描述的所有操作都是恆定時間;當我們增加條目數量時，它們都不會花費更長的時間。我們只需要確保散列中有足夠的空間來最小化「衝突」的機會，即兩個不同單詞將轉換爲相同整數索引的機會。因爲這可能會發生在任何散列算法中，所以我們需要添加檢查以查看是否存在衝突並做一些特殊的事情（如果「hello」和「world」都散列爲1,234，並且「hello」已經在表中，我們會用「世界」做什麼？最簡單的是把它放在1,235，並調整我們的查找邏輯，以允許這種可能性。）

編輯：重新閱讀您的文章後：哈希算法絕對不是隨機的，它必須是確定性的。在我的示例中爲「hello」生成的索引每次必須是1,234;這是查找工作的唯一方法。

來源

2009-05-23 15:41:10

爲什麼我們在HashTable中使用哈希代碼而不是索引？

回答

相關問題