聲明：此博客是本人在泊學(xué)網(wǎng)學(xué)習(xí)Swift過程的筆記與心得

Dictionary進(jìn)階

Swift中，Dictionary的內(nèi)在查找機(jī)制是通過key-value的哈希表實(shí)現(xiàn)的，因此，在Swift中，Dictionary的查找效率為O(1)。下面，我們了解一下Dictionary內(nèi)部的哈希實(shí)現(xiàn)機(jī)制。

需要強(qiáng)調(diào)的是，哈希算法需要計(jì)算哈希值，因此導(dǎo)致key的類型必須是一個(gè)可以計(jì)算哈希值的類型，即遵從了Hashable協(xié)議的類型。例如，String，Int，Date，Bool等。協(xié)議中定義了hashValue屬性，用來獲取通過key計(jì)算出的哈希值。

當(dāng)然，自定義類型也可以作為Key存在，就是要手動(dòng)遵從Hashable協(xié)議。

定義一個(gè)結(jié)構(gòu)體作為儲(chǔ)存學(xué)校學(xué)生信息：

struct Student {
    var studentID: Int
    var name: String
}

※使用結(jié)構(gòu)體封裝自定義Key而非類封裝，是考慮到不要使用引用類型而使用值類型作為Key，防止不經(jīng)意的修改Key值。

通過Swift的Extension功能為Student添加Hashable的實(shí)現(xiàn)：

extension Student: Hashable {
    var hashValue: Int // 前面提到的需要計(jì)算的哈希值
}

說到計(jì)算哈希值，就需要對(duì)計(jì)算算法進(jìn)行多方面考慮：性能與哈希值在整數(shù)范圍的分布。每次Dictionary進(jìn)行增刪改查操作時(shí)，都需要通過key值計(jì)算哈希值，算法的性能與訪問元素位置的O(1)性能要綜合考慮。如果哈希算法計(jì)算的哈希值相同，則需要進(jìn)行計(jì)算哈希值碰撞，這樣很有可能變成一個(gè)O(n)的算法。

// 一個(gè)極端的例子
extension Student: Hashable {
    var hashValue: Int {
        return 1 
    }
}

這種情況下，每一次返回的hashValue都為1，每一次操作，幾乎都要進(jìn)行碰撞處理。一次，雖然有O(1)的性能，但是碰撞處理將這個(gè)性能變成了O(n)的性能，因此，哈希值在整數(shù)區(qū)間均勻分布是設(shè)計(jì)哈希函數(shù)重要考慮的因素。

假設(shè)Swift標(biāo)準(zhǔn)庫中的hashValue都是滿足性能與分布要求的，那么我們就可以利用標(biāo)準(zhǔn)庫中的hashValue做一些低性能運(yùn)算，得到自己的hashValue。

extension Student: Hashable {
    var hashValue: Int {
        return studentID.hashValue ^ name.hashValue
    }
}

值得一提的是，這種情況下可能會(huì)報(bào)錯(cuò)：Student沒有遵從Equatable協(xié)議。這是因?yàn)?，如果遵從Hashable協(xié)議，實(shí)現(xiàn)哈希函數(shù)的同時(shí)，我們也必須遵從 Equatable，因?yàn)楣：瘮?shù)有一個(gè)重要原則：兩個(gè)相等的對(duì)象的哈希值必須相同。因此需要重載定義“==”。

extension Student: Equatable {
    static func == (lhs: Student, rhs: Student) -> Bool {
        return lhs.studentID == rhs.studentID && lhs.name == rhs.name
    }
}

這樣，一個(gè)簡(jiǎn)單的哈希實(shí)現(xiàn)就完成了。

當(dāng)然，這種哈希函數(shù)只是簡(jiǎn)單的異或運(yùn)算，很有可能計(jì)算出同樣的值。例如異或運(yùn)算：A^BA = B，A^B = B^A 這些情況。因此，也可以進(jìn)一步優(yōu)化一下哈希函數(shù)，可以采取對(duì)某些值進(jìn)行”加密“運(yùn)算，防止上述情況的發(fā)生。

// 在定義中實(shí)現(xiàn)一個(gè)對(duì)ID進(jìn)行加密的算法
struct Student {
    var studentID: Int
    var name: String

    func encryption(ID: Int, with num: Int) -> Int {
        return ((ID << num) ^ num) >> num
    }
}

Ps.加密運(yùn)算可以通過簡(jiǎn)單的位運(yùn)算來進(jìn)行。

這樣，每一次計(jì)算hashValue之前，對(duì)studentID進(jìn)行加密運(yùn)算，就可以大大防止異或中的一些情況發(fā)生。

extension Student: Hashable {
    var hashValue: Int {
        return encryption(ID: studentID.hashValue, with: 18)  ^ name.hashValue
    }
}