本文是對 Swift Algorithm Club 翻譯的一篇文章。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項目，目前在GitHub上有18000+??，我初略統(tǒng)計了一下，大概有一百左右個的算法和數(shù)據(jù)結(jié)構(gòu)，基本上常見的都包含了，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯的資源。
??andyRon/swift-algorithm-club-cn是我對Swift Algorithm Club，邊學(xué)習(xí)邊翻譯的項目。由于能力有限，如發(fā)現(xiàn)錯誤或翻譯不妥，請指正，歡迎pull request。也歡迎有興趣、有時間的小伙伴一起參與翻譯和學(xué)習(xí)??。當(dāng)然也歡迎加??，??????????。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Hash Table
哈希表(Hash Table)
哈希表允許您通過“鍵”存儲和檢索對象。
哈希表用于實現(xiàn)一些結(jié)構(gòu)，例如字典，映射和關(guān)聯(lián)數(shù)組。 這些結(jié)構(gòu)可以通過樹或普通數(shù)組實現(xiàn)，但使用哈希表效率更高。
這也可以解釋為什么Swift的內(nèi)置Dictionary類型要求鍵符合Hashable協(xié)議：在內(nèi)部Dictionary使用哈希表實現(xiàn)，就像你將在這里學(xué)到的那樣。
怎么工作的
哈希表只不過是一個數(shù)組。 最初，此數(shù)組為空。 將值放入某個鍵下的哈希表時，它使用該鍵計算數(shù)組中的索引。 這是一個例子：
hashTable["firstName"] = "Steve"
The hashTable array:
+--------------+
| 0: |
+--------------+
| 1: |
+--------------+
| 2: |
+--------------+
| 3: firstName |---> Steve
+--------------+
| 4: |
+--------------+
In this example, the key "firstName" maps to array index 3.
在這個例子中，鍵"firstName"映射到數(shù)組索引3。
Adding a value under a different key puts it at another array index:
在不同的鍵下添加值會將其放在另一個數(shù)組索引處：
hashTable["hobbies"] = "Programming Swift"
The hashTable array:
+--------------+
| 0: |
+--------------+
| 1: hobbies |---> Programming Swift
+--------------+
| 2: |
+--------------+
| 3: firstName |---> Steve
+--------------+
| 4: |
+--------------+
The trick is how the hash table calculates those array indices. That is where the hashing comes in. When you write the following statement,
這邊的訣竅是哈希表如何計算這些數(shù)組索引。 這就是哈希的用武之地。當(dāng)你寫下面的陳述時，
hashTable["firstName"] = "Steve"
哈希表使用鍵"firstName"并詢問它的hashValue屬性。 因此，鍵必須符合Hashable協(xié)議。
當(dāng)你寫"firstName".hashValue時，它返回一個大整數(shù)：-4799450059917011053。 同樣，"hobbies".hashValue的哈希值為4799450060928805186.（您看到的值可能會有所不同。）
這些數(shù)字很大，可以用作我們數(shù)組的索引，其中一個甚至是負(fù)數(shù)！使這些大數(shù)字可用的常用方法是首先使哈希值為正，然后數(shù)組大小進行取模運算（取余數(shù)），這個值就是數(shù)組的索引。
我們的數(shù)組大小為5，所以"firstName"鍵的索引變?yōu)?code>abs(-4799450059917011053) % 5 = 3。 你可以計算出"hobbies"的數(shù)組索引是1（譯注： abs(4799450060928805186) % 5 = 1）。
以這種方式使用哈希是使字典有效的原因：要在哈希表中查找元素，必須用鍵的哈希值以獲取數(shù)組索引，然后在底層數(shù)組中查找元素。 所有這些操作都需要不變的時間，因此插入，檢索和刪除都是 O(1)。
注意： 很難預(yù)測數(shù)組中對象的最終位置。 因此，字典不保證哈希表中元素的任何特定順序。
避免沖突
有一個問題：因為我們采用哈希值的模數(shù)和數(shù)組的大小，可能會發(fā)生兩個或多個鍵被賦予相同的數(shù)組索引。 這稱為沖突。
避免沖突的一種方法是使用大型數(shù)組，這樣可以降低兩個鍵映射到同一索引的可能性。另一個技巧是使用素數(shù)作為數(shù)組大小。但是，必然會發(fā)生沖突，因此您需要找到一種方法來處理沖突。
因為我們的表很小，很容易出現(xiàn)沖突。 例如，鍵"lastName" 的數(shù)組索引也是3，但我們不想覆蓋已在此數(shù)組索引處的值。
處理沖突的常用方法是使用鏈接（chaining）。 該數(shù)組如下所示：
buckets:
+-----+
| 0 |
+-----+ +----------------------------+
| 1 |---> | hobbies: Programming Swift |
+-----+ +----------------------------+
| 2 |
+-----+ +------------------+ +----------------+
| 3 |---> | firstName: Steve |---> | lastName: Jobs |
+-----+ +------------------+ +----------------+
| 4 |
+-----+
使用鏈接，鍵和它們的值不會直接存儲在數(shù)組中。 相反，每個數(shù)組元素都是零個或多個鍵/值對的列表。 數(shù)組元素通常稱為 buckets(可以譯為桶)，列表稱為 chains(可以譯為鏈)。 這里我們有5個桶，其中兩個桶有鏈。 其他三個桶都是空的。
如果我們編寫以下語句來從哈希表中檢索項目，
let x = hashTable["lastName"]
它首先用哈希鍵 "lastName" 來計算數(shù)組索引，即3。由于桶3有一個鏈，我們逐步遍歷列表，找到帶有 "lastName"鍵的值。這是通過使用字符串比較來比較鍵來完成的。 哈希表檢查鍵是否屬于鏈中的最后一項，并返回相應(yīng)的值 "Jobs"。
實現(xiàn)此鏈機制的常用方法是使用鏈表或其他數(shù)組。由于鏈中項目的順序無關(guān)緊要，您可以將其視為集合而不是列表。（現(xiàn)在你也可以想象術(shù)語“桶”的來源;我們只是將所有對象一起轉(zhuǎn)儲到桶中。）
鏈不應(yīng)該變長，因為查找哈希表中的項將變得緩慢。理想情況下，我們根本沒有鏈，但實際上不可能避免沖突。您可以通過使用高質(zhì)量哈希函數(shù)為哈希表提供足夠的桶來提高（避免沖突的）幾率。
注意： 鏈的替代方法是“開放尋址”。 這個想法是這樣的：如果已經(jīng)采用了數(shù)組索引，我們將該元素放在下一個未使用的存儲桶中。 這種方法有其自身的優(yōu)點和缺點。
代碼
讓我們看一下Swift中哈希表的基本實現(xiàn)。 我們將逐步建立起來。
public struct HashTable<Key: Hashable, Value> {
private typealias Element = (key: Key, value: Value)
private typealias Bucket = [Element]
private var buckets: [Bucket]
private(set) public var count = 0
public var isEmpty: Bool { return count == 0 }
public init(capacity: Int) {
assert(capacity > 0)
buckets = Array<Bucket>(repeatElement([], count: capacity))
}
HashTable是一個通用容器，兩個泛型類型被命名為Key（必須是Hashable）和Value。 我們還定義了另外兩種類型：Element是在鏈中使用的鍵/值對，而Bucket是這樣的Elements的數(shù)組。
主數(shù)組名為buckets。 初始化方法init(capacity)利用固定容量來確定數(shù)組的大小。 我們還可以使用count變量跟蹤已經(jīng)向哈希表添加了多少項。
如何創(chuàng)建新哈希表對象的示例：
var hashTable = HashTable<String, String>(capacity: 5)
哈希表還不能做任何事情，所以讓我們添加下面的功能。 首先，添加一個幫助方法來計算給定鍵的數(shù)組索引：
private func index(forKey key: Key) -> Int {
return abs(key.hashValue) % buckets.count
}
這將執(zhí)行您之前看到的計算：它將鍵的hashValue的絕對值對桶數(shù)組的大小取模。 我們已將其置于其自身的功能中，因為它在少數(shù)不同的地方使用。
使用哈希表或字典有四種常見的事情：
insert a new element
插入一個新元素
查找元素
更新現(xiàn)有元素
刪除元素
這些的語法是：
hashTable["firstName"] = "Steve" // insert
let x = hashTable["firstName"] // lookup
hashTable["firstName"] = "Tim" // update
hashTable["firstName"] = nil // delete
我們也可以使用 subscript 函數(shù)完成所有這些操作：
public subscript(key: Key) -> Value? {
get {
return value(forKey: key)
}
set {
if let value = newValue {
updateValue(value, forKey: key)
} else {
removeValue(forKey: key)
}
}
}
這需要三個輔助函數(shù)來完成實際工作。 讓我們看一下value(forKey:)，它從哈希表中檢索一個對象。
public func value(forKey key: Key) -> Value? {
let index = self.index(forKey: key)
for element in buckets[index] {
if element.key == key {
return element.value
}
}
return nil // key not in hash table
}
首先，它調(diào)用index(forKey:)將鍵轉(zhuǎn)換為數(shù)組索引。 這給了我們桶號，但如果有碰撞，這個桶可能被多個鍵使用。 value(forKey:)從該存儲桶循環(huán)鏈并逐個比較key。 如果找到，則返回相應(yīng)的值，否則返回nil。
插入新元素或更新現(xiàn)有元素的代碼位于updateValue(_:forKey:)中。 這復(fù)雜一點：
public mutating func updateValue(_ value: Value, forKey key: Key) -> Value? {
let index = self.index(forKey: key)
// Do we already have this key in the bucket?
for (i, element) in buckets[index].enumerated() {
if element.key == key {
let oldValue = element.value
buckets[index][i].value = value
return oldValue
}
}
// This key isn't in the bucket yet; add it to the chain.
buckets[index].append((key: key, value: value))
count += 1
return nil
}
同樣，第一步是將key轉(zhuǎn)換為數(shù)組索引以查找存儲桶。然后我們循環(huán)通過該桶的鏈。如果我們在鏈中找到key，我們就使用新值更新它。如果key不在鏈中，我們將新的鍵/值對插入到鏈的末尾。
正如您所看到的，保持鏈短（通過使哈希表足夠大）非常重要。 否則，你在這些for ...in循環(huán)中花費的時間過長，哈希表的性能將不再是 O(1)，而更像O(n)。
刪除也類似，再次遍歷鏈：
public mutating func removeValue(forKey key: Key) -> Value? {
let index = self.index(forKey: key)
// Find the element in the bucket's chain and remove it.
for (i, element) in buckets[index].enumerated() {
if element.key == key {
buckets[index].remove(at: i)
count -= 1
return element.value
}
}
return nil // key not in hash table
}
這些是哈希表的基本功能。 它們都以相同的方式工作：使用其哈希值將key轉(zhuǎn)換為數(shù)組索引，找到存儲桶，然后遍歷該存儲桶的鏈并執(zhí)行所需的操作。
在 playground 試試這些東西。 它應(yīng)該像標(biāo)準(zhǔn)的Swift Dictionary 一樣工作。
調(diào)整哈希表的大小
這個版本的HashTable總是使用固定大小或容量的數(shù)組。 如果要在哈希表中存儲許多項目，則對于容量，請選擇大于最大項數(shù)的素數(shù)。
哈希表的加載因子是當(dāng)前使用的容量的百分比。 如果哈希表中有3個項有5個桶，那么加載因子是3/5 = 60％。
如果哈希表很小，并且鏈很長，那么加載因子可能會大于1，這不是一個好主意。
如果加載因子變大，大于75％，則可以調(diào)整哈希表的大小。添加此條件的代碼留給讀者練習(xí)。請記住，使桶數(shù)組更大將改變鍵映射到的數(shù)組索引！這要求您在調(diào)整數(shù)組大小后再次插入所有元素。
然后去哪兒？(Where to go from here?)
HashTable非?；A(chǔ)。 作為Swift標(biāo)準(zhǔn)庫高效集成為SequenceType。
