TL：DR

他們將鍵映射到值。

哈希映射可能是映射概念最常用的實現。 它們允許將任意對象與其他任意對象關聯。

這對于執行諸如通過某些公共屬性將數據分組或連接在一起之類的工作非常有用。

基礎結構執行以下操作：

· 計算密鑰的哈希

· 修改散列以給出0到存儲桶數組大小之間的整數

· 遍歷所選存儲桶中的鏈表，比較鍵的相等性

· 當/如果鍵匹配，則返回與該鍵關聯的值。

基本結構

 

命名

我稱這些為哈希圖，但根據語言或上下文的不同，它們可以具有不同的名稱。

在C＃或Python中，粗略的等效項是一個Dictionary。

在JAVAscript中，可以使用內置的Map類，但是可以以類似于哈希圖的方式使用JavaScript對象。 在后臺，Javascript不使用哈希圖，因為它可以進行一些優化。

Java有一個名為HashMap的類，它也有HashTable，這基本上是相同的。 但是，通常建議在HashTable上使用HashMap。

如果看到稱為Dictionary / hashmap / hashtable的內容，則可以將它們視為此故事中描述的數據結構（主要是）。

哈希函數

顧名思義，哈希圖會執行"哈希"操作。 此操作需要一個任意對象并返回一個整數。 哈希函數的工作方式可能會填滿自己的故事，甚至可能更多。

出于本故事的目的，可以將哈希函數視為執行以下操作的黑盒：

Integer hash = hashFunction(someArbitraryObject);

那為什么有用呢？ 好吧，如果您可以將任何對象轉換為整數，則可以使用該整數導航到數組的索引。 這就是hashmap的作用，基本步驟如下：

· 把握關鍵和價值

· 計算密鑰的哈希

· 使用散列查找數組的索引

· 將鍵和值存儲在數組中

這里有一點復雜。 哈希函數可以返回哈希值，該哈希值的范圍介于整數的最大負值和正值之間。 我們不希望數組中包含數十億個元素，因為這將占用太多空間。 我們也沒有數組中負索引的概念。

理想情況下，我們希望索引介于0到某個數組的合理大小之間，例如100。

undefined

為此，我們需要兩個函數，絕對函數和模數。

絕對函數將使任何負數成為正數，因此-34671變為+34671。

模函數用于計算數字相對于另一個的余數。 例如，如果我們使用100作為要模數的數字，則：

 

· 0模量100 = 0

· 1模數100 = 1

· 2模數100 = 2

· 3模數100 = 3

· …

· 47模數100 = 47

· …

· 99模數100 = 99

直到達到100。在100處，模數導致返回值循環回到0。

所以，

· 100模量100 = 0

· 101模數100 = 1

· 102模數100 = 2

· …

· 147模數100 = 47

· …

· 199模量100 = 99

依此類推，直到達到200。在200處，返回值循環回到0，并開始向上計數回到99，直到我們要模數的值達到300，然后返回值回到0，然后重復并重復，然后 重復。

因此，模數函數可用于將任何（正）整數映射到介于0和我們要模數的值之間的范圍內。

給定一個絕對函數和一個模函數，我們可以將我們的散列整數轉換為和整數，該范圍是我們想要的：

Integer sizeOfArray = array.size();
// hashedInteger is somewhere between -BigNumber -> +BigNumberInteger 
hashedInteger = hashFunction(key);
// absInteger is somewhere between 0 -> +BigNumberInteger 
absInteger = absolute(hashedInteger);
// modInteger is somewhere between 0 -> sizeOfArrayInteger 
modInteger = modulus(absInteger, sizeOfArray);

一旦我們的整數處于數組大小的范圍內，就需要將鍵和值存儲在該數組中。

一系列的水桶

因此，哈希表的另一部分是"存儲桶數組"。 這是一個包含其他列表的數組。 這些其他列表通常是鏈接列表，您可以在我的故事中找到有關鏈接列表的更多信息。

 

我們采用哈希的，絕對的，模整數，并使用該整數來選擇存儲桶數組的索引。 然后，我們獲取我們的密鑰和價值，并將其存儲在存儲桶中。 存儲桶是一個鏈接列表，我們將鍵和值存儲在此列表的末尾。

鍵和值對稱為"條目"。 條目是一個簡單的包裝對象，其中包含鍵和值。

插入東西

現在，我們有很多事情：

· 我們可以采用任意對象并將其哈希/吸收/修改為適合我們數組的整數

· 我們知道數組存儲條目的鏈接列表。

· 條目包含鍵-值對。

我們可以結合使用它們來描述鍵值對如何存儲在哈希圖中：

· 給定鍵-值對

· 計算密鑰的哈希

· 將哈希值轉換為介于0和數組大小之間的值

· 在轉換后的哈希的索引處找到鏈接列表

· 將鍵-值對作為條目添加到鏈接列表的末尾

就完成了。

鍵值已存儲，然后可以查詢。 在繼續進行哈希表查詢之前，有必要討論在哈希表中存儲元素的時間復雜性。

簡短的答案是它是O（1）或恒定時間。 也就是說，隨著哈希圖變大，存儲鍵值對的時間不會改變。 這是因為組成哈希表中事物存儲的各種操作都是O（1）時間復雜度：

· 計算哈希為O（1）（或者至少它應該是一個復雜的主題，這里不再贅述）。

· Abs / Mod為O（1）

· 從數組中獲取元素是O（1）。 我在數組列表上還有另一個故事。 數組和數組列表不是一回事，但是它們具有許多時間復雜度特征。

· 向鏈接列表的末尾添加元素是O（1）。 我在鏈接列表上的故事對此進行了討論。

隨著這些操作的變大，哈希表的增長都不會變慢，因此插入哈希表的總體操作也不會隨著哈希表的增長而變慢。

拿東西

現在，我們的哈希圖充滿了鍵-值對，如果提供鍵就可以得到我們的值，這將非常有用。 其工作方式如下：

 

· 給定鍵（但無值）

· 計算密鑰的哈希

· 將哈希值轉換為介于0和數組大小之間的值

· 在轉換后的哈希的索引處找到鏈接列表

· 開始瀏覽鏈接列表中的每個條目

· 對于每個條目，請詢問輸入鍵和條目中保持的鍵是否相等

· 如果它們不相等，則轉到下一個條目

· 如果它們相等，則從條目中返回值

通過這些步驟，我們可以獲取我們的密鑰，并將其映射為一個值。 密鑰的約束是您需要能夠詢問兩個密鑰是否相等。 在Java中，這不是問題，因為每個對象都實現一個.equals（）方法。

此操作的時間復雜度是多少？ 與插入地圖的情況相比，這是一個更復雜的問題。 時間復雜度非常取決于您在找到具有匹配鍵的條目之前必須在鏈接列表中迭代多少個條目。

有2種極端情況：

· 所有條目都放在一個桶中

· 所有條目均已完美均勻地分布在所有可用存儲桶中

所有條目都放在一個存儲桶中

一種可能的情況是，所有鍵都被散列/ abs /修改為相同的數組索引。 在這種情況下，所有條目都將添加到同一鏈接列表中，并且找到與我們的鍵匹配的條目將花費O（N）（或線性）時間。 在此討論在鏈表中找到元素的原因是O（N）。

線性時間復雜度意味著，隨著哈希圖變大，在其中查找元素所花費的時間也與哈希圖的大小成比例地變大。 如果哈希圖增長了100倍，那么花費的時間也將增長約100倍。

這種情況并不理想，那么我們如何到達這里呢？

undefined

理想情況下，我們需要一個"好的"哈希函數，該函數返回均勻分布的哈希整數，這些整數將全部轉換為數組中均勻分布的索引。

所有條目均已完美均勻地分配

從哈希映射中獲取數據時，理想的情況是每個條目均已均勻分布在存儲桶中。 這導致每個鏈接列表包含相同數量的條目的情況。

對于哈希映射，這是最好的情況，因為可以在大致相等的時間內檢索每個條目，并且該時間段是最小的。

從具有均勻分布的條目的哈希圖中檢索項目的時間復雜度為O（N / k），其中，N是哈希圖所保存的條目數，而k是該圖具有的存儲桶數。

什么哈希圖適合

映射任意值

顧名思義，它們擅長映射事物。 您可以將數組視為將整數0到N映射到任意值的一種方式。 如果您要處理整數，這很好，但否則就沒有用。

映射允許您從任意對象映射到另一個任意對象。 它可以是字符串，整數或具有多個字段的對象。

只要可以將鍵用于生成哈希碼，并且可以將其與其他鍵進行相等性檢查，則可以在地圖中使用該對象。

在Java中，每個對象都需要實現.hashcode（）和.equals（）方法，因此Java中的每個對象都可以在映射中使用。

一個常見的用例是在對象列表之間進行聯接。 例如，假設我們有一個像這樣的對象：

public BookDTO { private String id; private String name;}

假設我們有2個BookDTO列表："用戶喜歡的圖書"和"正在銷售的圖書"。 企業所遵循的邏輯是，他們希望向用戶展示用戶喜歡的，正在出售的書籍。 為此，我們需要找到兩個列表都通用的所有書籍。

一種方法是瀏覽用戶喜歡的每一本書，并瀏覽每本出售的所有書籍。 這將是不理想的，因為它涉及經歷所有可能的組合。

一種替代方法是從2個列表中制作2個地圖，每個地圖ID到BookDTO。 然后，瀏覽用戶喜歡的每本書，使用該ID從另一張地圖中拉出所有正在出售的書。 使用這種方法，我們只需遍歷地圖即可加入任何相關書籍，而不必嘗試每種組合。

 

分組信息

通過一些通用屬性對信息進行分組是很常見的事情。 例如，假設我們要計算一個字符串在任意字符串列表中出現的次數。

表示其輸出的一種方法是將String映射為Integer。 該代碼可以編寫如下：

public Map<String, Integer> countItems(List<String> items) { 
	Map<String, Integer> stringToCount = new HashMap<>(); 
  for (String item in items) { 
    if (!stringToCount.containsKey(item)) { 
      stringToCount.put(item, 0); 
    } 
  Integer currentCount = stringToCount.get(item); 
  Integer newCount = currentCount + 1; stringToCount.put(item, newCount); 
  } 
  return stringToCount;
}

因此對于輸入：

["Foo", "Bar", "Foo", "Baz"]

輸出為：

{ "Foo": 2, "Bar": 1, "Baz": 1}

這是一個相對簡單的示例，但是如果您正在處理事務并決定要按用戶對用戶的所有事務進行分組，則將它們表示為用戶ID到List [Transaction]的映射可能是實現該分組的一種有用方法 。

什么哈希圖不好

存儲訂購的信息

如果您想以有序的方式存儲信息，則哈希映射不是很好。 通常，哈希圖不保證可以迭代其條目的順序，因此您不能依賴于已將訂單項添加到與迭代順序有任何關系的哈希圖中的順序。

這里有一些反例。 在Java中，存在LinkedHashMap類，該類允許按插入順序迭代條目。 還有一些排序的映射，可以按順序迭代具有顯式順序的鍵。

存儲重復信息

哈希圖中的鍵定義值的身份。 如果您嘗試為同一鍵存儲多個值，則這些值將被覆蓋。 這與可以多次重復添加同一對象的列表不同。

解決此問題的簡單方法是將要存儲的值更改為多次插入的對象的列表。

摘要

哈希圖是一種非常有用的數據結構，用于將某些任意數據映射到其他任意數據。

他們依靠良好的哈希函數，模數函數和"存儲桶"列表。

地圖的一些標準用例是將2個數據集合結合在一起，或通過一些公用密鑰將數據分組在一起。

關于作者

嗨，我是Doogal，我是一位技術主管，花了很多年的時間從幾位非常有才華的人那里學習軟件工程，而這些故事正是我努力使之付諸實踐的方法。

在擔任技術主管期間，我曾指導過許多新軟件工程師，并且我發現經常存在工程師不知道自己不知道的情況的情況。 因此，"每個軟件工程師應該知道的事情"系列是我在做軟件的第一年里會給自己提供的信息的摘要。

軟件是一個很大的主題，黃金法則是，任何問題的答案都可以以"取決于……"開頭，因此，這些故事中的信息并不完整。 這是一種嘗試提供基本信息的嘗試，因此在閱讀這些故事時，請記住，兔子洞比此處顯示的主題要深。

我可以在Facebook，LinkedIn或Doodl.la上找到。

(本文翻譯自Doogal Simpson的文章《Things every engineer should know: Hashmaps》，參考：https://medium.com/swlh/things-every-engineer-should-know-hashmaps-b354088206b5)