本質(zhì)上來說，Dictionary是一個哈希表，它所有的key都用各自的哈希值保存在一個數(shù)組里。因此，通過key在Dictionary中訪問value是一個O(1)操作。但這也對key的類型做出了一個要求，它必須可以計算哈希值。Swift標準庫中提供的絕大多數(shù)類型，例如：Int / Float / Double / String / Bool / Date ...等，都滿足這個要求，因此我們可以直接拿它們來定義Dictionary。
但如果我們有一個自定義類型Account，表示泊學(xué)的網(wǎng)站賬號，其中的alias / type / createdAt分別表示賬號的別名、類型和注冊日期：
struct Account {
var alias: String
var type: Int
var createdAt: Date
}
當我們把Account用作key的時候，Swift就會給我們提示下面的錯誤：Account沒有遵從Hashable protocol：
let account11 = Account(alias: "11",
type: 1, createdAt : Date())
let data:[Account: Int] = [ account11: 1000 ]
Conform to Hashable protocol
如何讓自定義類型遵從Hashable protocol呢？第一件要做的事，就是告訴Swift，如何獲取一個類型的哈希值，這是通過一個叫hashValue的屬性完成的：
extension Account: Hashable {
var hashValue: Int
}
如何計算Account.hashValue呢？有兩個最重要的考量，分別是：性能和哈希值在整數(shù)范圍的分布。因為每當我們要在Dictionary中查詢、添加、修改或刪除元素的時候，都要計算key的哈希值，如果這個計算過于消耗性能，那么計算哈希值的過程就有可能抵消掉通過key隨機訪問value帶來的O(1)性能提升。
當然，你也不能盲目追求性能而忽視哈希值的整數(shù)值分布。說一個最極端的例子，如果你讓所有情況計算得到的哈希值都是某個常數(shù)：
extension Account: Hashable {
// A BAD idea
var hashValue: Int { return 1 }
}
這個哈希函數(shù)有O(1)的性能，但這樣，不同的Account對象就會有不同的哈希值，這叫做Collision。當然，Swift Dictionary可以處理哈希值碰撞的情況，但你要隨之付出的代價就是，通過哈希值讀取value將從一個O(1)變成一個O(n)算法。因此，讓哈希值在整數(shù)區(qū)間均勻分布也是設(shè)計哈希函數(shù)很重的考慮。
綜上所述，設(shè)計一個好的哈希函數(shù)并不是一個容易的事情。對于我們來說，可以假設(shè)Swift標準庫的類型提供的hashValue都滿足性能和分布的要求。因此，當我們設(shè)計復(fù)合類型的哈希值的時候，可以基于這些標準類型的哈希值進行一些“低功耗”運算，例如，對這些值進行異或運算，絕大多數(shù)的CPU都對這個操作提供了指令級支持：
extension Account: Hashable {
var hashValue: Int {
return alias.hashValue ^
type.hashValue ^
createdAt.hashValue
}
}
解決了Account的哈希值之后，Swift會繼而提示我們：Account沒有遵從Equatable protocol。為什么還要遵從Equatable呢？這是因為哈希函數(shù)還有一個很重要的性質(zhì)：兩個相等對象的哈希值必須是相同的。因此，我們必須要解決什么叫做兩個相等的對象，然后才有比較它們各自哈希值的事情。
Equatable只有一個約束，就是為自定義類型實現(xiàn)==操作符：
extension Account: Equatable {
static func == (lhs: Account, rhs: Account) -> Bool {
return lhs.alias == rhs.alias &&
lhs.type == rhs.type &&
lhs.createdAt == rhs.createdAt
}
}
在Swift里，運算符必須要定義成static方法，它的兩個參數(shù)lhs / rhs則表示==兩邊的操作數(shù)。我們判斷Account相等的方式很簡單，只要它們每一個屬性相等，則兩個Account對象就是相等的。
當我們讓Account遵從了Equatable之后，Swift編譯器就不會再報錯了。此時，我們在一開始創(chuàng)建的data也可以正常工作了。
Bitwise rotation
我們上面例子中提到的把所有屬性進行XOR運算的方法，雖然簡單高效，但也有一個問題，就是比較容易造成碰撞。因為XOR運算是可交換的，也就是說a ^ b == b ^ a，因此，如果一個自定義類型中，有多個類型相同屬性的時候，就會增大哈希值發(fā)生碰撞的概率，因此，我們可以用下面的代碼，對其中的一些基礎(chǔ)屬性的哈希值進行按位旋轉(zhuǎn)后再進行XOR運算：
struct Account {
let INT_BIT = (Int)(CHAR_BIT) * MemoryLayout<Int>.size
func bitwiseRotate(value: Int, bits: Int) -> Int {
return (((value) << bits) | ((value) >> (UINT_BIT - bits)))
}
}
extension Account: Hashable {
var hashValue: Int {
return bitwiseRotate(value: alias.hashValue, bits: 10) ^
type.hashValue ^
createdAt.hashValue
}
}
首先，我們在Account中添加了一個常量INT_BIT表示一個整數(shù)的位數(shù)。其次，定義了一個輔助方法bitwiseRotate(value:bits:)，它用于先把value向左移動bits位，再向右移動(UINT_BIT - bits)位。
有了這個方法之后，我們就可以在計算哈希值的時候，對其中的屬性進行按位旋轉(zhuǎn)了。
警惕引用類型的Key
和Dictionary.Key相關(guān)的最后一個內(nèi)容，是盡可能避免使用引用類型作為key，這通常會給你帶來不必要的麻煩。當一個引用類型作為key之后，當引用類型的對象在Dictionary之外被修改的時候，Key的內(nèi)容也會隨之修改。這樣你就再也無法獲得之前的哈希值，也就無法獲得對應(yīng)的value了。
What's next?
以上就是和如何用自定義類型作為Key相關(guān)的話題，至此，我們對Dictionary的討論就可以告一段落了。在下一節(jié)中，我們會看到Swift標準庫中的另外一個無序集合：Set。
