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",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",visited: false)
london.hashValue  // 4792642925948815646
paris.hashValue   // 4799464424543103873

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

总结

本文简单的介绍了 Swift 中“等同性”、“比较”、“哈希”的概念，并对一些常见哈希冲突进行了分析。当然了，这样一篇文章远远无法全方位覆盖这些知识点，尤其是哈希相关的内容，这些都留给大家自己去探索吧。