哈希映射中的哈希部分如何工作？

Question

因此，有在hash maps article維基百科上這樣漂亮的圖片：

都清楚了，到目前爲止，除了中間的散列函數。

• 函數如何從任何字符串中生成正確的索引？這些索引是否也是現實？如果是的話，John Smith,2的Lisa Smith等功能如何輸出1等？

Answer 1

這是hashmaps/dictionaries等關鍵問題之一。你必須選擇一個好的散列函數。一個非常糟糕但快速的散列函數可能是密鑰的長度。你馬上就會看到，你會得到很多的碰撞（不同的鍵，但相同的散列）。另一個不好的哈希函數可能是您的密鑰的第一個字符的ASCII值。很多也是碰撞。
所以你需要一個比這兩個更好的函數。您可以添加（xor）關鍵字符的所有ASCII值並混合長度。在實踐中，你經常依賴於你想散列的對象的值（字段）（相同的值給出相同的hash =>值類型）。例如，對於參考類型，您可以在內存位置混合使用。

在你的例子中，這只是簡化了很多。沒有真正的散列函數會將這些鍵映射到連續的數字。

也許你想讀我的previous answers to hashmaps

Answer 2

散列函數最常（但不一定總是）輸出所需範圍內的整數（通常參數哈希函數）之一。該整數可以用作索引。注意，散列函數不能保證在給予散列的不同數據時始終產生唯一結果。這被稱爲散列衝突，並且散列算法必須總是以某種方式處理它。

至於你的具體問題，一個字符串如何變成一個數字。任何字符串都由字符（J，o，h，n ...）組成，字符可以被解釋爲數字（在計算機中）。 ASCII和UTF標準將某些值綁定到某些字符，因此結果是確定性的，並且在所有計算機上始終保持一致。所以散列函數對這些字符進行操作，將它們作爲數字進行處理，併產生另一個數字（輸出）。例如，您可以簡單地將所有值相加並使用模運算來範圍限制結果值。

這將是一個相當可怕的哈希函數，因爲例如「ab」和「ba」會得到相同的結果。散列函數的設計很困難，所以應該使用一些現成的算法，除非情況需要其他解決方案。

Answer 3

一個簡單的散列函數可以如下：

$hash = $string[0] % HASH_TABLE_SIZE; 

該函數將返回0和HASH_TABLE_SIZE之間的數 - 1，根據字符串的第一個字母。這個數字可以用來到哈希表中的正確位置。

一個真正的散列函數將考慮字符串中的所有字母，並且它將被設計爲使得在這些桶之間存在均勻分佈。

Answer 4

散列函數所需要的只是它返回給定相同鍵的相同整數。從技術上講，總是返回'1'的散列函數並不正確。

Answer 5

有一個關於如何散列函數（和colision檢測/分辨率）在MSDN上一個真正的好文章：

Part 2: The Queue, Stack, and Hashtable

您可以向下跳到壓縮有序索引與散列函數頭

有一些特定於.NET的元素（當他們談論默認使用哪種Hash算法.NET時），但大多數情況下它是語言不可知的。