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

   <p>最近 Google 又搞了个大新闻：成功攻破了业界广泛使用的 SHA-1 哈希算法，加上看了 MrPeak 的 a <a href="/misc/goto?guid=4959746559242113171" rel="nofollow,noindex">闲聊 Hash 算法</a> ，所以我就去仔细看了下 Swift 中的相关内容与概念。这篇文章算是对 Swift 中对象的“等同性”、“比较”、“哈希”概念的一个简单介绍。</p>    <h2>Equatable</h2>    <p>Class 这种引用类型存在基于指针的默认的等同判断，但是 Struct 所代表的值类型则没有这个特性。而且有时候我们也会对引用类型的等同判断进行自定义实现，所有下面我们通过 Struct 类型作为示例来讲解这些概念。我们定义一个 Country 类型，其中包含国家名、首都、是否旅游 三个属性。</p>    <pre>  <code class="language-swift">struct Country {      let name: String      let capital: String      var visited: Bool  }</code></pre>    <p>接下来我们新建一些实例变量并添加到数组中：</p>    <pre>  <code class="language-swift">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]</code></pre>    <p>如果此时需要对 <em>bucketList</em> 变量进行检查，判断其中是否包含某个 Country 类型对象，那么最直接的代码实现可能是：</p>    <pre>  <code class="language-swift">let object = canada  let containsObject = bucketList.contains { (country) -> Bool in      return  country.name == object.name &&              country.capital == object.capital &&              country.visited == object.visited  }</code></pre>    <p>当然上诉实现是有很大问题的。你不得不在每一处判断中拷贝代码，而且这种强耦合结构会后期对 Country 结构修改造成大麻烦。好在我们可以使用标准库里面的 <strong>Equatable</strong> 协议来进行 <strong>==</strong> 判断的实现：</p>    <pre>  <code class="language-swift">extension Country: Equatable {      static func == (lhs: Country, rhs: Country) -> Bool {          return  lhs.name == rhs.name &&                  lhs.capital == rhs.capital &&                  lhs.visited == rhs.visited      }  }</code></pre>    <p>改造后，不仅对象 <strong>==</strong> 比较代码写起来简单了，而且也让代码更易于维护。</p>    <pre>  <code class="language-swift">bucketList.contains(canada)  // true</code></pre>    <h2>Comparable</h2>    <p>如果此时需要对 <em>bucketList</em> 按升序进行排序的话又该如何应对呢？我们可以使用 Array 的排序闭包：</p>    <pre>  <code class="language-swift">bucketList.sorted(by: { $0.name < $1.name } )</code></pre>    <p>为了使上述代码能正常工作，我们需要对上面的 extension 进行修改，实现 <strong>Comparable</strong> 协议中的 <strong><</strong> 方法。</p>    <pre>  <code class="language-swift">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)      }  }</code></pre>    <p>当然， <strong><</strong> 实现中属性的比较顺序完全依据个人选择。</p>    <p>Comparable协议继承自 <strong>Equatable</strong> 协议，其中还有 <strong><=</strong> 、 <strong>></strong> 、 <strong>>=</strong> 方法。</p>    <h2>Hashable</h2>    <p>除了将自定义类型存入数组外，有时候我们还需要将其存入 Dictionary、Set。甚至某些场景下还需要将其作为键值对中的 Key，这就涉及到哈希函数以及哈希值的碰撞问题了。Swift 标准库里的类型，例如：String, Integer, Bool 都已经哈希函数并且可以通过 <em>hashValue</em> 属性直接获得哈希值：</p>    <pre>  <code class="language-swift">let hello  = "hello"  let world = "world"  hello.hashValue                 // 4799432177974197528  "\(hello) \(world)".hashValue   // 3658945855109305670  "hello world".hashValue         // 3658945855109305670</code></pre>    <p>对于我们的自定义类型 Country 来说，我们可以取出每个属性的哈希值然后在进行异或操作。</p>    <pre>  <code class="language-swift">extension Country: Hashable {      var hashValue: Int {          return name.hashValue ^ capital.hashValue ^ visited.hashValue      }  }    // 这样 Country 类型对象就可以作为 Key了。  let counts = [uk: 1000, canada: 2000]</code></pre>    <p>上面 Country 实现了 Hashable 协议，并且能够在应用于 Dictionary、Set 中，但是这里还有一些问题需要注意。</p>    <ul>     <li> <p>我们知道相同的对象的哈希值是一样的，而哈希值相同则并不表示对象相同。这意味着哈希碰撞必定存在，但是我们可以采用一些方法来减少碰撞域。</p> </li>     <li> <p>对于 Bool 类型的对象来说，它的哈希值只可能是0或1，所以其不能单独用于生成哈希值。</p> </li>    </ul>    <p>下面我们通过一段代码来直观感受下哈希碰撞（此处只考虑哈希碰撞，不要纠结于变量含义）：</p>    <pre>  <code class="language-swift">let london = Country(name: "London", capital: "London", visited: false)  let paris = Country(name: "Paris", capital: "Paris", visited: false)  london.hashValue  // 0  paris.hashValue   // 0</code></pre>    <p>这段代码中因为每个对象自身的 <em>name</em> 、 <em>capital</em> 属性相同，而 <em>london</em> 、 <em>paris</em> 的 <em>visited</em> 属性也相同，最后加上抑或操作的特点，两个对象无可避免的发生了哈希碰撞。因为抑或操作中 <strong>A ^ B = B ^ A</strong> 的特性，下面这张碰撞情况也常发生：</p>    <pre>  <code class="language-swift">let canada = Country(name: "Canada", capital: "Ottawa", visited: false)  let ottawa = Country(name: "Ottawa", capital: "Canada", visited: false)  canada.hashValue  // 3695199242423112  ottawa.hashValue  // 3695199242423112</code></pre>    <p>这就尴尬了。不过仔细查看代码，我们会发现上诉冲突的原因之一就是 <em>name</em> 、 <em>capital</em> 属性采用了同样的哈希函数。如果我们对其中某一个属性的哈希进行改造那么一定程度上能减少碰撞域。当然哈希函数并不是随手写一个就行的，我们可以参照 [哈希函数] [1] 一文实现其中的 <strong>djb2</strong> 、 <strong>sdbm</strong> 。</p>    <pre>  <code class="language-swift">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          }      }  }</code></pre>    <p>并修改 <em>Country</em> 中的哈希实现：</p>    <pre>  <code class="language-swift">extension Country: Hashable {      var hashValue: Int {          return name.djb2hash ^ capital.hashValue ^ visited.hashValue      }  }</code></pre>    <p>改进后上诉冲突得以解决：</p>    <pre>  <code class="language-swift">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</code></pre>    <h2>总结</h2>    <p>本文简单的介绍了 Swift 中“等同性”、“比较”、“哈希”的概念，并对一些常见哈希冲突进行了分析。当然了，这样一篇文章远远无法全方位覆盖这些知识点，尤其是哈希相关的内容，这些都留给大家自己去探索吧。</p>    <p> </p>    <p>来自：https://segmentfault.com/a/1190000008924262</p>    <p> </p>