聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過(guò)來(lái)免糕，為方便大家閱讀赢乓。如果英語(yǔ)閱讀能力強(qiáng)的朋友，可以直接到swift算法俱樂(lè)部查看所有原文石窑，以便快速學(xué)習(xí)牌芋。作者同時(shí)也在學(xué)習(xí)中，歡迎交流
哈希表允許用戶可以通過(guò)鍵值key存取對(duì)象尼斧。
哈希表可以用來(lái)表示特殊數(shù)據(jù)結(jié)構(gòu)姜贡，比如說(shuō)字典，映射和關(guān)聯(lián)數(shù)組等棺棵。這一類的結(jié)構(gòu)可以通過(guò)樹(shù)狀圖或者普通數(shù)組來(lái)表示楼咳，但是使用哈希表的話效率更高熄捍。
這也說(shuō)明來(lái)為什么Swift內(nèi)置的Dictionary類型的鍵值對(duì)必須遵守Hashable協(xié)議，因?yàn)樗褂玫木褪枪１砟噶c我們接下來(lái)要說(shuō)的內(nèi)容相同余耽。
基本原理
簡(jiǎn)單來(lái)說(shuō)，哈希表就是一個(gè)數(shù)組苹熏。在起始時(shí)候碟贾，數(shù)組本身是空的。當(dāng)我們想要儲(chǔ)存一個(gè)數(shù)值的時(shí)候轨域，我們會(huì)在哈希表里創(chuàng)建一個(gè)鍵值袱耽，這個(gè)鍵值是用來(lái)計(jì)算這個(gè)數(shù)值在數(shù)組中的索引，并指向數(shù)值干发。舉例：
hashTable["firstName"] = "Steve"
The hashTable array:
+--------------+
| 0: |
+--------------+
| 1: |
+--------------+
| 2: |
+--------------+
| 3: firstName |---> Steve
+--------------+
| 4: |
+--------------+
在實(shí)例中朱巨，鍵值firstName對(duì)應(yīng)數(shù)組索引3. 如果我們用不同的鍵值添加新的數(shù)值，該鍵值對(duì)應(yīng)的索引也是不同的枉长。如下：
hashTable["hobbies"] = "Programming Swift"
The hashTable array:
+--------------+
| 0: |
+--------------+
| 1: hobbies |---> Programming Swift
+--------------+
| 2: |
+--------------+
| 3: firstName |---> Steve
+--------------+
| 4: |
+--------------+
這里的竅門(mén)是哈希表如何去計(jì)算這些數(shù)組索引冀续。這也是哈希化開(kāi)始的地方必峰。當(dāng)你寫(xiě)入以下代碼：
hashTable["firstName"] = "Steve"
哈希表取出鍵值firstName并且對(duì)本身的hashValue屬性進(jìn)行詢問(wèn)洪唐。所以，鍵值必須是Hashable吼蚁。
如果你在代碼里寫(xiě)"firstName".hashValue凭需，它將會(huì)返回一個(gè)大整數(shù) ：-4799450059917011053。與此同時(shí)肝匆，"hobbies".hashValue對(duì)應(yīng)的哈希值為4799450060928805186功炮。
這兩個(gè)大整數(shù)都很大，無(wú)法用做數(shù)組的索引值术唬，而且還有一個(gè)是負(fù)數(shù)！所以這里我們對(duì)這兩個(gè)數(shù)值進(jìn)行取絕對(duì)值滚澜，并對(duì)數(shù)值大小進(jìn)行求余數(shù)粗仓。當(dāng)前我們的數(shù)組大小為5，所以鍵值firstName的索引為abs(-4799450059917011053) % 5 = 3.
這樣的過(guò)程也就是字典高效的原因：我們需要在哈希表里找一個(gè)元素设捐，你必須把這個(gè)鍵值哈辖枳牵化去得到一個(gè)索引值，然后去找到數(shù)組對(duì)應(yīng)索引的數(shù)值萝招。所有的操作過(guò)程都消耗固定時(shí)間蚂斤，也就是說(shuō)，插入槐沼，獲取和刪除都是O(1)曙蒸。
注意：因?yàn)槲覀儫o(wú)法預(yù)測(cè)你的數(shù)組將會(huì)有多少對(duì)象捌治，所以字典本身不保證任何順序。
避免沖突
這里有一個(gè)問(wèn)題：因?yàn)槲覀兪怯脭?shù)組大小對(duì)哈希值進(jìn)行取模纽窟，有可能不同鍵值所得到的索引值相同肖油，這里就是沖突。
避免沖突的其中一個(gè)方法是用一個(gè)很大的數(shù)組來(lái)降低兩個(gè)鍵值映射同一個(gè)索引的概率臂港。另一個(gè)方法是用一個(gè)基本數(shù)字來(lái)作為數(shù)組大小森枪。然而，這樣的方法還是無(wú)法避免沖突的發(fā)生审孽，所以我們需要一個(gè)更好的方法來(lái)處理這個(gè)問(wèn)題县袱。
在實(shí)例中，因?yàn)槲覀兊墓１矸浅Ｐ∮恿Γ詻_突的概率很大式散。比如，下圖中鍵值lastName對(duì)應(yīng)的索引也為3搓萧，但是我們并不想要重寫(xiě)索引3對(duì)應(yīng)的數(shù)值杂数。所以，我們用鏈接來(lái)處理沖突瘸洛。
buckets:
+-----+
| 0 |
+-----+ +----------------------------+
| 1 |---> | hobbies: Programming Swift |
+-----+ +----------------------------+
| 2 |
+-----+ +------------------+ +----------------+
| 3 |---> | firstName: Steve |---> | lastName: Jobs |
+-----+ +------------------+ +----------------+
| 4 |
+-----+
通過(guò)使用鏈接揍移，鍵值和它對(duì)應(yīng)的數(shù)值不再直接存儲(chǔ)在數(shù)組中。相反反肋，每一個(gè)數(shù)組元素對(duì)應(yīng)一串零個(gè)到多個(gè)的鍵值對(duì)那伐。這里的數(shù)組元素通常被稱為籃子bucket而對(duì)應(yīng)列表稱為鏈條。這里我們有5個(gè)籃子石蔗，其中有2個(gè)籃子擁有鏈條罕邀。其他三個(gè)籃子為空。
假如我們用以下代碼從哈希表里獲取數(shù)值：
let x = hashTable["lastName"]
首先我們會(huì)對(duì)鍵值lastName哈涎啵化來(lái)獲取對(duì)應(yīng)數(shù)組索引诉探，也就是3。由于3號(hào)籃子有鏈條棍厌，我們進(jìn)一步用鍵值lastName來(lái)獲取最后的數(shù)值肾胯。這個(gè)過(guò)程是通過(guò)字符比較來(lái)完成。哈希表對(duì)比了查找的鍵值與鏈條里的鍵值耘纱，最后返回了對(duì)應(yīng)的數(shù)值敬肚。
通常來(lái)說(shuō)，鏈條的長(zhǎng)度不可以太長(zhǎng)因?yàn)闀?huì)花費(fèi)更多的時(shí)間來(lái)查看數(shù)據(jù)束析，最理想的情況是沒(méi)有鏈條艳馒，但是在現(xiàn)實(shí)中是不可能的。所以我們采用這樣的方法來(lái)避免沖突员寇。當(dāng)然弄慰，我們可以通過(guò)更高質(zhì)量的哈希函數(shù)來(lái)保證哈希表的籃子數(shù)量第美，從而避免沖突。
注意：另一個(gè)可選鏈接方案是"開(kāi)放賦值"曹动。主要思想是：如果某一個(gè)數(shù)組索引已經(jīng)被占用了斋日，我們就使用索引對(duì)應(yīng)的下一個(gè)索引或者上一個(gè)索引。
代碼
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是通用容器墓陈，然后這里有兩個(gè)參數(shù)Key(必須遵守Hashable)和Value恶守。我們還定義了另外兩個(gè)類型：Element是鏈條里的鍵值對(duì)，Bucket是籃子贡必，存放鍵值對(duì)的數(shù)組兔港。
這里的主數(shù)組是buckets。它的大小是固定的仔拟，由init(capacity)來(lái)決定衫樊。同時(shí)我們還對(duì)被加入到哈希表的元素個(gè)數(shù)進(jìn)行統(tǒng)計(jì)，存入變量count利花。
我們可以用以下方法來(lái)創(chuàng)建新的哈希表對(duì)象：
var hashTable = HashTable<String, String>(capacity: 5)
目前哈希表并沒(méi)有實(shí)現(xiàn)任何功能科侈，我們可以加入一些想要的功能。首先炒事，我們可以計(jì)算一個(gè)指定鍵值在主數(shù)組的對(duì)應(yīng)索引值:
private func index(forKey key: Key) -> Int {
return abs(key.hashValue) % buckets.count
}
此函數(shù)的原理在之前我們有提到過(guò)臀栈，我們需要得到鍵值的哈希值，取絕對(duì)值并求余挠乳。由于這個(gè)函數(shù)在很多地方都會(huì)被用到权薯，所以我們把它放到HashTable里。
一般來(lái)說(shuō)睡扬，我們會(huì)對(duì)哈希表或者字典做以下事件：插入新元素盟蚣，尋找元素，更新已存在元素卖怜，取出元素烹骨。對(duì)應(yīng)的語(yǔ)法如下：
hashTable["firstName"] = "Steve" // insert
let x = hashTable["firstName"] // lookup
hashTable["firstName"] = "Tim" // update
hashTable["firstName"] = nil // delete
我們可以通過(guò)subscript函數(shù)來(lái)實(shí)現(xiàn)上述功能：
public subscript(key: Key) -> Value? {
get {
return value(forKey: key)
}
set {
if let value = newValue {
updateValue(value, forKey: key)
} else {
removeValue(forKey: key)
}
}
}
這里調(diào)用了三個(gè)輔助函數(shù)來(lái)實(shí)現(xiàn)真正的功能叠赦。我們可以看一下value(forKey:)涛漂，用于從哈希表中獲取對(duì)象幕帆。
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
}
上述函數(shù)首先通過(guò)index(forKey:)將鍵值轉(zhuǎn)換成數(shù)組索引。這個(gè)索引值也就是之前說(shuō)的籃子標(biāo)號(hào)虑粥，每個(gè)籃子可能存放著多個(gè)鍵值對(duì)，所以還需要將搜索的鍵值與籃子里的鍵值一一進(jìn)行對(duì)比宪哩。如果有相等的娩贷，則返回鍵值相應(yīng)的數(shù)值，若沒(méi)有則返回nil
插入和更新元素的代碼就稍微復(fù)雜點(diǎn)：
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
}
第一步仍然是獲取索引锁孟，然后對(duì)索引值對(duì)應(yīng)的籃子進(jìn)行判斷彬祖，如果已經(jīng)存在鍵值對(duì)茁瘦，則直接更新當(dāng)前鍵值對(duì)應(yīng)的數(shù)值，如果對(duì)應(yīng)籃子沒(méi)有該鍵值储笑，則直接插入新的鍵值對(duì)甜熔。
我們可以看出，每個(gè)籃子里面的鏈條數(shù)量（鍵值對(duì)）多少對(duì)整個(gè)哈希表來(lái)說(shuō)很重要突倍，不然我們每次還需要消耗額外的時(shí)間去比值腔稀。這個(gè)時(shí)候，哈希表的性能就不是O(1)而是O(n)了羽历。
移除的過(guò)程也是類似的：
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
}
總體來(lái)說(shuō)焊虏，哈希表的基本函數(shù)的工作流程都是相似的：首先獲取索引，找到籃子秕磷，再籃子進(jìn)行比值诵闭，然后進(jìn)行相應(yīng)操作。
改變哈希表的大小
上述代碼中HashTable的大小是固定的澎嚣。所以當(dāng)我們有很多數(shù)據(jù)需要存入到哈希表時(shí)候疏尿，我們需要設(shè)定一個(gè)比數(shù)據(jù)最大個(gè)數(shù)還大的數(shù)字來(lái)作為哈希表的容量值。
我們用負(fù)載來(lái)表示當(dāng)前使用量在哈希表容量值的占比易桃。如果哈希表中儲(chǔ)存了3個(gè)元素褥琐，但是有5個(gè)籃子，那么當(dāng)前的負(fù)載為3/5 = 60%.如果哈希表太小颈抚，而鏈表的數(shù)量又多踩衩，負(fù)載值就會(huì)大于1，這并不是一個(gè)理想的情況贩汉。
所以驱富，我們可以對(duì)代碼進(jìn)行修改，假定負(fù)載值大于某一個(gè)百分比匹舞，則容量值自動(dòng)修改為新的大小褐鸥。這里我們不直接提供代碼，由讀者自行探索赐稽。需要注意的是叫榕，如果籃子的數(shù)量改變了，鍵值所對(duì)應(yīng)的索引也會(huì)改變姊舵！所以每一次修改哈希表容量值的時(shí)候晰绎，都需要將所有數(shù)據(jù)重新插入到哈希表內(nèi)！
