TL：DR
他們將鍵映射到值。
哈希映射可能是映射概念最常用的實(shí)現(xiàn)。 它們?cè)试S將任意對(duì)象與其他任意對(duì)象關(guān)聯(lián)。
這對(duì)于執(zhí)行諸如通過某些公共屬性將數(shù)據(jù)分組或連接在一起之類的工作非常有用。
基礎(chǔ)結(jié)構(gòu)執(zhí)行以下操作：
· 計(jì)算密鑰的哈希
· 修改散列以給出0到存儲(chǔ)桶數(shù)組大小之間的整數(shù)
· 遍歷所選存儲(chǔ)桶中的鏈表，比較鍵的相等性
· 當(dāng)/如果鍵匹配，則返回與該鍵關(guān)聯(lián)的值。
基本結(jié)構(gòu)
命名
我稱這些為哈希圖，但根據(jù)語言或上下文的不同，它們可以具有不同的名稱。
在C＃或Python中，粗略的等效項(xiàng)是一個(gè)Dictionary。
在JAVAscript中，可以使用內(nèi)置的Map類，但是可以以類似于哈希圖的方式使用JavaScript對(duì)象。 在后臺(tái)，Javascript不使用哈希圖，因?yàn)樗梢赃M(jìn)行一些優(yōu)化。
Java有一個(gè)名為HashMap的類，它也有HashTable，這基本上是相同的。 但是，通常建議在HashTable上使用HashMap。
如果看到稱為Dictionary / hashmap / hashtable的內(nèi)容，則可以將它們視為此故事中描述的數(shù)據(jù)結(jié)構(gòu)（主要是）。
哈希函數(shù)
顧名思義，哈希圖會(huì)執(zhí)行"哈希"操作。 此操作需要一個(gè)任意對(duì)象并返回一個(gè)整數(shù)。 哈希函數(shù)的工作方式可能會(huì)填滿自己的故事，甚至可能更多。
出于本故事的目的，可以將哈希函數(shù)視為執(zhí)行以下操作的黑盒：
Integer hash = hashFunction(someArbitraryObject);
那為什么有用呢？ 好吧，如果您可以將任何對(duì)象轉(zhuǎn)換為整數(shù)，則可以使用該整數(shù)導(dǎo)航到數(shù)組的索引。 這就是hashmap的作用，基本步驟如下：
· 把握關(guān)鍵和價(jià)值
· 計(jì)算密鑰的哈希
· 使用散列查找數(shù)組的索引
· 將鍵和值存儲(chǔ)在數(shù)組中
這里有一點(diǎn)復(fù)雜。 哈希函數(shù)可以返回哈希值，該哈希值的范圍介于整數(shù)的最大負(fù)值和正值之間。 我們不希望數(shù)組中包含數(shù)十億個(gè)元素，因?yàn)檫@將占用太多空間。 我們也沒有數(shù)組中負(fù)索引的概念。
理想情況下，我們希望索引介于0到某個(gè)數(shù)組的合理大小之間，例如100。
undefined
為此，我們需要兩個(gè)函數(shù)，絕對(duì)函數(shù)和模數(shù)。
絕對(duì)函數(shù)將使任何負(fù)數(shù)成為正數(shù)，因此-34671變?yōu)?34671。
模函數(shù)用于計(jì)算數(shù)字相對(duì)于另一個(gè)的余數(shù)。 例如，如果我們使用100作為要模數(shù)的數(shù)字，則：
· 0模量100 = 0
· 1模數(shù)100 = 1
· 2模數(shù)100 = 2
· 3模數(shù)100 = 3
· …
· 47模數(shù)100 = 47
· …
· 99模數(shù)100 = 99
直到達(dá)到100。在100處，模數(shù)導(dǎo)致返回值循環(huán)回到0。
所以，
· 100模量100 = 0
· 101模數(shù)100 = 1
· 102模數(shù)100 = 2
· …
· 147模數(shù)100 = 47
· …
· 199模量100 = 99
依此類推，直到達(dá)到200。在200處，返回值循環(huán)回到0，并開始向上計(jì)數(shù)回到99，直到我們要模數(shù)的值達(dá)到300，然后返回值回到0，然后重復(fù)并重復(fù)，然后 重復(fù)。
因此，模數(shù)函數(shù)可用于將任何（正）整數(shù)映射到介于0和我們要模數(shù)的值之間的范圍內(nèi)。
給定一個(gè)絕對(duì)函數(shù)和一個(gè)模函數(shù)，我們可以將我們的散列整數(shù)轉(zhuǎn)換為和整數(shù)，該范圍是我們想要的：
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);
一旦我們的整數(shù)處于數(shù)組大小的范圍內(nèi)，就需要將鍵和值存儲(chǔ)在該數(shù)組中。
一系列的水桶
因此，哈希表的另一部分是"存儲(chǔ)桶數(shù)組"。 這是一個(gè)包含其他列表的數(shù)組。 這些其他列表通常是鏈接列表，您可以在我的故事中找到有關(guān)鏈接列表的更多信息。
我們采用哈希的，絕對(duì)的，模整數(shù)，并使用該整數(shù)來選擇存儲(chǔ)桶數(shù)組的索引。 然后，我們獲取我們的密鑰和價(jià)值，并將其存儲(chǔ)在存儲(chǔ)桶中。 存儲(chǔ)桶是一個(gè)鏈接列表，我們將鍵和值存儲(chǔ)在此列表的末尾。
鍵和值對(duì)稱為"條目"。 條目是一個(gè)簡單的包裝對(duì)象，其中包含鍵和值。
插入東西
現(xiàn)在，我們有很多事情：
· 我們可以采用任意對(duì)象并將其哈希/吸收/修改為適合我們數(shù)組的整數(shù)
· 我們知道數(shù)組存儲(chǔ)條目的鏈接列表。
· 條目包含鍵-值對(duì)。
我們可以結(jié)合使用它們來描述鍵值對(duì)如何存儲(chǔ)在哈希圖中：
· 給定鍵-值對(duì)
· 計(jì)算密鑰的哈希
· 將哈希值轉(zhuǎn)換為介于0和數(shù)組大小之間的值
· 在轉(zhuǎn)換后的哈希的索引處找到鏈接列表
· 將鍵-值對(duì)作為條目添加到鏈接列表的末尾
就完成了。
鍵值已存儲(chǔ)，然后可以查詢。 在繼續(xù)進(jìn)行哈希表查詢之前，有必要討論在哈希表中存儲(chǔ)元素的時(shí)間復(fù)雜性。
簡短的答案是它是O（1）或恒定時(shí)間。 也就是說，隨著哈希圖變大，存儲(chǔ)鍵值對(duì)的時(shí)間不會(huì)改變。 這是因?yàn)榻M成哈希表中事物存儲(chǔ)的各種操作都是O（1）時(shí)間復(fù)雜度：
· 計(jì)算哈希為O（1）（或者至少它應(yīng)該是一個(gè)復(fù)雜的主題，這里不再贅述）。
· Abs / Mod為O（1）
· 從數(shù)組中獲取元素是O（1）。 我在數(shù)組列表上還有另一個(gè)故事。 數(shù)組和數(shù)組列表不是一回事，但是它們具有許多時(shí)間復(fù)雜度特征。
· 向鏈接列表的末尾添加元素是O（1）。 我在鏈接列表上的故事對(duì)此進(jìn)行了討論。
隨著這些操作的變大，哈希表的增長都不會(huì)變慢，因此插入哈希表的總體操作也不會(huì)隨著哈希表的增長而變慢。
拿東西
現(xiàn)在，我們的哈希圖充滿了鍵-值對(duì)，如果提供鍵就可以得到我們的值，這將非常有用。 其工作方式如下：
· 給定鍵（但無值）
· 計(jì)算密鑰的哈希
· 將哈希值轉(zhuǎn)換為介于0和數(shù)組大小之間的值
· 在轉(zhuǎn)換后的哈希的索引處找到鏈接列表
· 開始瀏覽鏈接列表中的每個(gè)條目
· 對(duì)于每個(gè)條目，請(qǐng)?jiān)儐栞斎腈I和條目中保持的鍵是否相等
· 如果它們不相等，則轉(zhuǎn)到下一個(gè)條目
· 如果它們相等，則從條目中返回值
通過這些步驟，我們可以獲取我們的密鑰，并將其映射為一個(gè)值。 密鑰的約束是您需要能夠詢問兩個(gè)密鑰是否相等。 在Java中，這不是問題，因?yàn)槊總€(gè)對(duì)象都實(shí)現(xiàn)一個(gè).equals（）方法。
此操作的時(shí)間復(fù)雜度是多少？ 與插入地圖的情況相比，這是一個(gè)更復(fù)雜的問題。 時(shí)間復(fù)雜度非常取決于您在找到具有匹配鍵的條目之前必須在鏈接列表中迭代多少個(gè)條目。
有2種極端情況：
· 所有條目都放在一個(gè)桶中
· 所有條目均已完美均勻地分布在所有可用存儲(chǔ)桶中
所有條目都放在一個(gè)存儲(chǔ)桶中
一種可能的情況是，所有鍵都被散列/ abs /修改為相同的數(shù)組索引。 在這種情況下，所有條目都將添加到同一鏈接列表中，并且找到與我們的鍵匹配的條目將花費(fèi)O（N）（或線性）時(shí)間。 在此討論在鏈表中找到元素的原因是O（N）。
線性時(shí)間復(fù)雜度意味著，隨著哈希圖變大，在其中查找元素所花費(fèi)的時(shí)間也與哈希圖的大小成比例地變大。 如果哈希圖增長了100倍，那么花費(fèi)的時(shí)間也將增長約100倍。
這種情況并不理想，那么我們?nèi)绾蔚竭_(dá)這里呢？
undefined
理想情況下，我們需要一個(gè)"好的"哈希函數(shù)，該函數(shù)返回均勻分布的哈希整數(shù)，這些整數(shù)將全部轉(zhuǎn)換為數(shù)組中均勻分布的索引。
所有條目均已完美均勻地分配
從哈希映射中獲取數(shù)據(jù)時(shí)，理想的情況是每個(gè)條目均已均勻分布在存儲(chǔ)桶中。 這導(dǎo)致每個(gè)鏈接列表包含相同數(shù)量的條目的情況。
對(duì)于哈希映射，這是最好的情況，因?yàn)榭梢栽诖笾孪嗟鹊臅r(shí)間內(nèi)檢索每個(gè)條目，并且該時(shí)間段是最小的。
從具有均勻分布的條目的哈希圖中檢索項(xiàng)目的時(shí)間復(fù)雜度為O（N / k），其中，N是哈希圖所保存的條目數(shù)，而k是該圖具有的存儲(chǔ)桶數(shù)。
什么哈希圖適合
映射任意值
顧名思義，它們擅長映射事物。 您可以將數(shù)組視為將整數(shù)0到N映射到任意值的一種方式。 如果您要處理整數(shù)，這很好，但否則就沒有用。
映射允許您從任意對(duì)象映射到另一個(gè)任意對(duì)象。 它可以是字符串，整數(shù)或具有多個(gè)字段的對(duì)象。
只要可以將鍵用于生成哈希碼，并且可以將其與其他鍵進(jìn)行相等性檢查，則可以在地圖中使用該對(duì)象。
在Java中，每個(gè)對(duì)象都需要實(shí)現(xiàn).hashcode（）和.equals（）方法，因此Java中的每個(gè)對(duì)象都可以在映射中使用。
一個(gè)常見的用例是在對(duì)象列表之間進(jìn)行聯(lián)接。 例如，假設(shè)我們有一個(gè)像這樣的對(duì)象：
public BookDTO { private String id; private String name;}
假設(shè)我們有2個(gè)BookDTO列表："用戶喜歡的圖書"和"正在銷售的圖書"。 企業(yè)所遵循的邏輯是，他們希望向用戶展示用戶喜歡的，正在出售的書籍。 為此，我們需要找到兩個(gè)列表都通用的所有書籍。
一種方法是瀏覽用戶喜歡的每一本書，并瀏覽每本出售的所有書籍。 這將是不理想的，因?yàn)樗婕敖?jīng)歷所有可能的組合。
一種替代方法是從2個(gè)列表中制作2個(gè)地圖，每個(gè)地圖ID到BookDTO。 然后，瀏覽用戶喜歡的每本書，使用該ID從另一張地圖中拉出所有正在出售的書。 使用這種方法，我們只需遍歷地圖即可加入任何相關(guān)書籍，而不必嘗試每種組合。
分組信息
通過一些通用屬性對(duì)信息進(jìn)行分組是很常見的事情。 例如，假設(shè)我們要計(jì)算一個(gè)字符串在任意字符串列表中出現(xiàn)的次數(shù)。
表示其輸出的一種方法是將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;
}
因此對(duì)于輸入：
["Foo", "Bar", "Foo", "Baz"]
輸出為：
{ "Foo": 2, "Bar": 1, "Baz": 1}
這是一個(gè)相對(duì)簡單的示例，但是如果您正在處理事務(wù)并決定要按用戶對(duì)用戶的所有事務(wù)進(jìn)行分組，則將它們表示為用戶ID到List [Transaction]的映射可能是實(shí)現(xiàn)該分組的一種有用方法 。
什么哈希圖不好
存儲(chǔ)訂購的信息
如果您想以有序的方式存儲(chǔ)信息，則哈希映射不是很好。 通常，哈希圖不保證可以迭代其條目的順序，因此您不能依賴于已將訂單項(xiàng)添加到與迭代順序有任何關(guān)系的哈希圖中的順序。
這里有一些反例。 在Java中，存在LinkedHashMap類，該類允許按插入順序迭代條目。 還有一些排序的映射，可以按順序迭代具有顯式順序的鍵。
存儲(chǔ)重復(fù)信息
哈希圖中的鍵定義值的身份。 如果您嘗試為同一鍵存儲(chǔ)多個(gè)值，則這些值將被覆蓋。 這與可以多次重復(fù)添加同一對(duì)象的列表不同。
解決此問題的簡單方法是將要存儲(chǔ)的值更改為多次插入的對(duì)象的列表。
摘要
哈希圖是一種非常有用的數(shù)據(jù)結(jié)構(gòu)，用于將某些任意數(shù)據(jù)映射到其他任意數(shù)據(jù)。
他們依靠良好的哈希函數(shù)，模數(shù)函數(shù)和"存儲(chǔ)桶"列表。
地圖的一些標(biāo)準(zhǔn)用例是將2個(gè)數(shù)據(jù)集合結(jié)合在一起，或通過一些公用密鑰將數(shù)據(jù)分組在一起。
關(guān)于作者
嗨，我是Doogal，我是一位技術(shù)主管，花了很多年的時(shí)間從幾位非常有才華的人那里學(xué)習(xí)軟件工程，而這些故事正是我努力使之付諸實(shí)踐的方法。
在擔(dān)任技術(shù)主管期間，我曾指導(dǎo)過許多新軟件工程師，并且我發(fā)現(xiàn)經(jīng)常存在工程師不知道自己不知道的情況的情況。 因此，"每個(gè)軟件工程師應(yīng)該知道的事情"系列是我在做軟件的第一年里會(huì)給自己提供的信息的摘要。
軟件是一個(gè)很大的主題，黃金法則是，任何問題的答案都可以以"取決于……"開頭，因此，這些故事中的信息并不完整。 這是一種嘗試提供基本信息的嘗試，因此在閱讀這些故事時(shí)，請(qǐng)記住，兔子洞比此處顯示的主題要深。
我可以在Facebook，LinkedIn或Doodl.la上找到。
(本文翻譯自Doogal Simpson的文章《Things every engineer should know: Hashmaps》，參考：https://medium.com/swlh/things-every-engineer-should-know-hashmaps-b354088206b5)
