Swift 中“等同性”、“比較”、“哈希” 概念理解

KelKirkcald 7年前發布 | 31K 次閱讀哈希表 Swift Apple Swift開發

最近 Google 又搞了個大新聞：成功攻破了業界廣泛使用的 SHA-1 哈希算法，加上看了 MrPeak 的 a 閑聊 Hash 算法，所以我就去仔細看了下 Swift 中的相關內容與概念。這篇文章算是對 Swift 中對象的“等同性”、“比較”、“哈希”概念的一個簡單介紹。

Equatable

Class 這種引用類型存在基于指針的默認的等同判斷，但是 Struct 所代表的值類型則沒有這個特性。而且有時候我們也會對引用類型的等同判斷進行自定義實現，所有下面我們通過 Struct 類型作為示例來講解這些概念。我們定義一個 Country 類型，其中包含國家名、首都、是否旅游三個屬性。

struct Country {
    let name: String
    let capital: String
    var visited: Bool
}

接下來我們新建一些實例變量并添加到數組中：

let canada = Country(name: "Canada", capital: "Ottawa", visited: true)
let australia = Country(name: "Australia", capital: "Canberra", visited: false)
...
let bucketList = [brazil,australia,canada,egypt,uk,france]

如果此時需要對 bucketList 變量進行檢查，判斷其中是否包含某個 Country 類型對象，那么最直接的代碼實現可能是：

let object = canada
let containsObject = bucketList.contains { (country) -> Bool in
    return  country.name == object.name &&
            country.capital == object.capital &&
            country.visited == object.visited
}

當然上訴實現是有很大問題的。你不得不在每一處判斷中拷貝代碼，而且這種強耦合結構會后期對 Country 結構修改造成大麻煩。好在我們可以使用標準庫里面的 Equatable 協議來進行 == 判斷的實現：

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

改造后，不僅對象 == 比較代碼寫起來簡單了，而且也讓代碼更易于維護。

bucketList.contains(canada)  // true

Comparable

如果此時需要對 bucketList 按升序進行排序的話又該如何應對呢？我們可以使用 Array 的排序閉包：

bucketList.sorted(by: { $0.name < $1.name } )

為了使上述代碼能正常工作，我們需要對上面的 extension 進行修改，實現 Comparable 協議中的 < 方法。

extension Country: Comparable {

    static func == (lhs: Country, rhs: Country) -> Bool {
        return  lhs.name == rhs.name &&
                lhs.capital == rhs.capital &&
                lhs.visited == rhs.visited
    }

    static func < (lhs: Country, rhs: Country) -> Bool {
        return  lhs.name < rhs.name ||
                (lhs.name == rhs.name && lhs.capital < rhs.capital) ||
                (lhs.name == rhs.name && lhs.capital == rhs.capital && rhs.visited)
    }
}

當然， < 實現中屬性的比較順序完全依據個人選擇。

Comparable協議繼承自 Equatable 協議，其中還有 <= 、 > 、 >= 方法。

Hashable

除了將自定義類型存入數組外，有時候我們還需要將其存入 Dictionary、Set。甚至某些場景下還需要將其作為鍵值對中的 Key，這就涉及到哈希函數以及哈希值的碰撞問題了。Swift 標準庫里的類型，例如：String, Integer, Bool 都已經哈希函數并且可以通過 hashValue 屬性直接獲得哈希值：

let hello  = "hello"
let world = "world"
hello.hashValue                 // 4799432177974197528
"\(hello) \(world)".hashValue   // 3658945855109305670
"hello world".hashValue         // 3658945855109305670

對于我們的自定義類型 Country 來說，我們可以取出每個屬性的哈希值然后在進行異或操作。

extension Country: Hashable {
    var hashValue: Int {
        return name.hashValue ^ capital.hashValue ^ visited.hashValue
    }
}

// 這樣 Country 類型對象就可以作為 Key了。
let counts = [uk: 1000, canada: 2000]

上面 Country 實現了 Hashable 協議，并且能夠在應用于 Dictionary、Set 中，但是這里還有一些問題需要注意。

我們知道相同的對象的哈希值是一樣的，而哈希值相同則并不表示對象相同。這意味著哈希碰撞必定存在，但是我們可以采用一些方法來減少碰撞域。
對于 Bool 類型的對象來說，它的哈希值只可能是0或1，所以其不能單獨用于生成哈希值。

下面我們通過一段代碼來直觀感受下哈希碰撞（此處只考慮哈希碰撞，不要糾結于變量含義）：

let london = Country(name: "London", capital: "London", visited: false)
let paris = Country(name: "Paris", capital: "Paris", visited: false)
london.hashValue  // 0
paris.hashValue   // 0

這段代碼中因為每個對象自身的 name 、 capital 屬性相同，而 london 、 paris 的 visited 屬性也相同，最后加上抑或操作的特點，兩個對象無可避免的發生了哈希碰撞。因為抑或操作中 A ^ B = B ^ A 的特性，下面這張碰撞情況也常發生：

let canada = Country(name: "Canada", capital: "Ottawa", visited: false)
let ottawa = Country(name: "Ottawa", capital: "Canada", visited: false)
canada.hashValue  // 3695199242423112
ottawa.hashValue  // 3695199242423112

這就尷尬了。不過仔細查看代碼，我們會發現上訴沖突的原因之一就是 name 、 capital 屬性采用了同樣的哈希函數。如果我們對其中某一個屬性的哈希進行改造那么一定程度上能減少碰撞域。當然哈希函數并不是隨手寫一個就行的，我們可以參照 [哈希函數] [1] 一文實現其中的 djb2 、 sdbm 。

extension String {
    var djb2hash: Int {
    let unicodeScalars = self.unicodeScalars.map { $0.value }
        return unicodeScalars.reduce(5381) {
            ($0 << 5) &+ $0 &+ Int($1)
        }
    }

    var sdbmhash: Int {
        let unicodeScalars = self.unicodeScalars.map { $0.value }
            return unicodeScalars.reduce(0) {
                Int($1) &+ ($0 << 6) &+ ($0 << 16) - $0
        }
    }
}

并修改 Country 中的哈希實現：

extension Country: Hashable {
    var hashValue: Int {
        return name.djb2hash ^ capital.hashValue ^ visited.hashValue
    }
}

改進后上訴沖突得以解決：

let london = Country(name: "London", capital: "London", visited: false)
let paris = Country(name: "Paris", capital: "Paris", visited: false)
london.hashValue  // 4792642925948815646
paris.hashValue   // 4799464424543103873

let canada = Country(name: "Canada", capital: "Ottawa", visited: false)
let ottawa = Country(name: "Ottawa", capital: "Canada", visited: false)
canada.hashValue  // 4792300300145562762
ottawa.hashValue  // 4795361053083927978

總結

本文簡單的介紹了 Swift 中“等同性”、“比較”、“哈希”的概念，并對一些常見哈希沖突進行了分析。當然了，這樣一篇文章遠遠無法全方位覆蓋這些知識點，尤其是哈希相關的內容，這些都留給大家自己去探索吧。

來自：https://segmentfault.com/a/1190000008924262

本文由用戶 KelKirkcald 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1491093983669.html

哈希表 Swift Apple Swift開發

Swift 中“等同性”、“比較”、“哈希” 概念理解

Equatable

Comparable

Hashable

總結

相關經驗

相關資訊

相關文檔

目錄