聲明：算法和數(shù)據(jù)結構的文章均是作者從github上翻譯過來，為方便大家閱讀。如果英語閱讀能力強的朋友，可以直接到swift算法俱樂部查看所有原文，以便快速學習。作者同時也在學習中，歡迎交流

哈希表允許用戶可以通過鍵值key存取對象。

哈希表可以用來表示特殊數(shù)據(jù)結構，比如說字典，映射和關聯(lián)數(shù)組等。這一類的結構可以通過樹狀圖或者普通數(shù)組來表示，但是使用哈希表的話效率更高。

這也說明來為什么Swift內(nèi)置的Dictionary類型的鍵值對必須遵守Hashable協(xié)議，因為它使用的就是哈希表，與我們接下來要說的內(nèi)容相同。

基本原理

簡單來說，哈希表就是一個數(shù)組。在起始時候，數(shù)組本身是空的。當我們想要儲存一個數(shù)值的時候，我們會在哈希表里創(chuàng)建一個鍵值，這個鍵值是用來計算這個數(shù)值在數(shù)組中的索引，并指向數(shù)值。舉例：

hashTable["firstName"] = "Steve"

    The hashTable array:
    +--------------+
    | 0:           |
    +--------------+
    | 1:           |
    +--------------+
    | 2:           |
    +--------------+
    | 3: firstName |---> Steve
    +--------------+
    | 4:           |
    +--------------+

在實例中，鍵值firstName對應數(shù)組索引3. 如果我們用不同的鍵值添加新的數(shù)值，該鍵值對應的索引也是不同的。如下：

hashTable["hobbies"] = "Programming Swift"

    The hashTable array:
    +--------------+
    | 0:           |
    +--------------+
    | 1: hobbies   |---> Programming Swift
    +--------------+
    | 2:           |
    +--------------+
    | 3: firstName |---> Steve
    +--------------+
    | 4:           |
    +--------------+

這里的竅門是哈希表如何去計算這些數(shù)組索引。這也是哈?；_始的地方。當你寫入以下代碼：

hashTable["firstName"] = "Steve"

哈希表取出鍵值firstName并且對本身的hashValue屬性進行詢問。所以，鍵值必須是Hashable。

如果你在代碼里寫"firstName".hashValue，它將會返回一個大整數(shù) ：-4799450059917011053。與此同時，"hobbies".hashValue對應的哈希值為4799450060928805186。

這兩個大整數(shù)都很大，無法用做數(shù)組的索引值，而且還有一個是負數(shù)！所以這里我們對這兩個數(shù)值進行取絕對值，并對數(shù)值大小進行求余數(shù)。當前我們的數(shù)組大小為5，所以鍵值firstName的索引為abs(-4799450059917011053) % 5 = 3.

這樣的過程也就是字典高效的原因：我們需要在哈希表里找一個元素，你必須把這個鍵值哈?；サ玫揭粋€索引值，然后去找到數(shù)組對應索引的數(shù)值。所有的操作過程都消耗固定時間，也就是說，插入，獲取和刪除都是O(1)。

注意：因為我們無法預測你的數(shù)組將會有多少對象，所以字典本身不保證任何順序。

避免沖突

這里有一個問題：因為我們是用數(shù)組大小對哈希值進行取模，有可能不同鍵值所得到的索引值相同，這里就是沖突。

避免沖突的其中一個方法是用一個很大的數(shù)組來降低兩個鍵值映射同一個索引的概率。另一個方法是用一個基本數(shù)字來作為數(shù)組大小。然而，這樣的方法還是無法避免沖突的發(fā)生，所以我們需要一個更好的方法來處理這個問題。

在實例中，因為我們的哈希表非常小，所以沖突的概率很大。比如，下圖中鍵值lastName對應的索引也為3，但是我們并不想要重寫索引3對應的數(shù)值。所以，我們用鏈接來處理沖突。

buckets:
    +-----+
    |  0  |
    +-----+     +----------------------------+
    |  1  |---> | hobbies: Programming Swift |
    +-----+     +----------------------------+
    |  2  |
    +-----+     +------------------+     +----------------+
    |  3  |---> | firstName: Steve |---> | lastName: Jobs |
    +-----+     +------------------+     +----------------+
    |  4  |
    +-----+

通過使用鏈接，鍵值和它對應的數(shù)值不再直接存儲在數(shù)組中。相反，每一個數(shù)組元素對應一串零個到多個的鍵值對。這里的數(shù)組元素通常被稱為籃子bucket而對應列表稱為鏈條。這里我們有5個籃子，其中有2個籃子擁有鏈條。其他三個籃子為空。

假如我們用以下代碼從哈希表里獲取數(shù)值：

let x = hashTable["lastName"]

首先我們會對鍵值lastName哈?；瘉慝@取對應數(shù)組索引，也就是3。由于3號籃子有鏈條，我們進一步用鍵值lastName來獲取最后的數(shù)值。這個過程是通過字符比較來完成。哈希表對比了查找的鍵值與鏈條里的鍵值，最后返回了對應的數(shù)值。

通常來說，鏈條的長度不可以太長因為會花費更多的時間來查看數(shù)據(jù)，最理想的情況是沒有鏈條，但是在現(xiàn)實中是不可能的。所以我們采用這樣的方法來避免沖突。當然，我們可以通過更高質(zhì)量的哈希函數(shù)來保證哈希表的籃子數(shù)量，從而避免沖突。

注意：另一個可選鏈接方案是"開放賦值"。主要思想是：如果某一個數(shù)組索引已經(jīng)被占用了，我們就使用索引對應的下一個索引或者上一個索引。

代碼

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是通用容器，然后這里有兩個參數(shù)Key(必須遵守Hashable)和Value。我們還定義了另外兩個類型：Element是鏈條里的鍵值對，Bucket是籃子，存放鍵值對的數(shù)組。

這里的主數(shù)組是buckets。它的大小是固定的，由init(capacity)來決定。同時我們還對被加入到哈希表的元素個數(shù)進行統(tǒng)計，存入變量count。

我們可以用以下方法來創(chuàng)建新的哈希表對象：

var hashTable = HashTable<String, String>(capacity: 5)

目前哈希表并沒有實現(xiàn)任何功能，我們可以加入一些想要的功能。首先，我們可以計算一個指定鍵值在主數(shù)組的對應索引值:

  private func index(forKey key: Key) -> Int {
    return abs(key.hashValue) % buckets.count
  }

此函數(shù)的原理在之前我們有提到過，我們需要得到鍵值的哈希值，取絕對值并求余。由于這個函數(shù)在很多地方都會被用到，所以我們把它放到HashTable里。

一般來說，我們會對哈希表或者字典做以下事件：插入新元素，尋找元素，更新已存在元素，取出元素。對應的語法如下：

hashTable["firstName"] = "Steve"   // insert
let x = hashTable["firstName"]     // lookup
hashTable["firstName"] = "Tim"     // update
hashTable["firstName"] = nil       // delete

我們可以通過subscript函數(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)用了三個輔助函數(shù)來實現(xiàn)真正的功能。我們可以看一下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
  }

上述函數(shù)首先通過index(forKey:)將鍵值轉(zhuǎn)換成數(shù)組索引。這個索引值也就是之前說的籃子標號，每個籃子可能存放著多個鍵值對，所以還需要將搜索的鍵值與籃子里的鍵值一一進行對比。如果有相等的，則返回鍵值相應的數(shù)值，若沒有則返回nil

插入和更新元素的代碼就稍微復雜點：

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
  }

第一步仍然是獲取索引，然后對索引值對應的籃子進行判斷，如果已經(jīng)存在鍵值對，則直接更新當前鍵值對應的數(shù)值，如果對應籃子沒有該鍵值，則直接插入新的鍵值對。

我們可以看出，每個籃子里面的鏈條數(shù)量（鍵值對）多少對整個哈希表來說很重要，不然我們每次還需要消耗額外的時間去比值。這個時候，哈希表的性能就不是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
  }

總體來說，哈希表的基本函數(shù)的工作流程都是相似的：首先獲取索引，找到籃子，再籃子進行比值，然后進行相應操作。

改變哈希表的大小

上述代碼中HashTable的大小是固定的。所以當我們有很多數(shù)據(jù)需要存入到哈希表時候，我們需要設定一個比數(shù)據(jù)最大個數(shù)還大的數(shù)字來作為哈希表的容量值。

我們用負載來表示當前使用量在哈希表容量值的占比。如果哈希表中儲存了3個元素，但是有5個籃子，那么當前的負載為3/5 = 60%.如果哈希表太小，而鏈表的數(shù)量又多，負載值就會大于1，這并不是一個理想的情況。

所以，我們可以對代碼進行修改，假定負載值大于某一個百分比，則容量值自動修改為新的大小。這里我們不直接提供代碼，由讀者自行探索。需要注意的是，如果籃子的數(shù)量改變了，鍵值所對應的索引也會改變！所以每一次修改哈希表容量值的時候，都需要將所有數(shù)據(jù)重新插入到哈希表內(nèi)！