【译】SE-0206 Hashable 加强

提案: SE-0206
作者: Karoy Lorentey, Vincent Esche
审核人: Joe Groff
状态: 已实现 (Swift 4.2)
决策记录: Rationale
实现：
- apple/swift#14913 (standard library, underscored),
- apple/swift#16009 (Hasher interface),
- apple/swift#16073 (automatic synthesis, de-underscoring)
上一个版本: 1

简介

本提案计划引入一个新的类型 Hasher 来抽象标准库里的通用哈希函数，并且会相应地加入一个新的 hash(into:) 实现要求来扩展 Hashable 协议。hashValue 属性将会被弃用，并且使用这个新的实现要求来替换掉它。

切换到 hash(into:) 之后意味着把哈希函数的选择从 Hashable 的实现里分离了出来，放到了标准库里。这让手动遵循 Hashable 变得更加简单，自定义实现的内容减少到只需要指定参与哈希的成员即可。

使用单一，高质量的标准化哈希函数非常有助于提高 Set 和 Dictionary 的可靠性。这些集合可以使用特定的哈希函数并且针对哈希表进行微调，避免哈希碰撞导致性能的下降。

Hasher 是一个 resilient 的结构体，后续版本的标准库可以在避免破坏当前 Hashable 实现的同时改进哈希函数（甚至无需重新编译）。把哈希函数从 Hashable 类型里剥离出来，在当前算法出现问题时显得特别重要。

Swift-evolution 讨论进程: Combining Hashes

提案缘由

Swift 标准库包含了两个通用的哈希集合 —— Set 和 Dictionary。这两个集合是围绕哈希表构建的，但旧版本里他们的性能极度依赖于他们存储的元素，更准确的来说是每一个元素的哈希函数的质量。

使用一个好的哈希函数时，简单的查找，插入，删除操作都只需要常数时间即可完成。然而，如果没有为当前数据选择一个合适的哈希函数时，这些操作的期望时间就会变成线性时间。如果这个表足够大的话，很容易导致无法接受的性能。但它们被哈希碰撞淹没时，应用和网络服务也许会长期处于无法工作的状态；这会很容易导致 app 无响应或者服务器宕机。

现状

自 Swift 1.0 之后，Hashable 就是 Equatable 的实现前提：hashValue 属性。hashValue 属性看起来很简单，但却非常难实现：我们不止需要决定类型的哪一部分需要参与哈希，而且还不得不想出一种方法去把这些输入的元素糅合到一起，输出一个整型。这个 API 本质上是要求我们每一次遵循 Hashable，都实现一个新的哈希函数。

在文档完备时，我们相信一个经验丰富的工程师可以在实现自定义类型了解哪些部分需要参与哈希。但另一方面，实现一个足够好的哈希函数需要仔细的考究和特定的知识。期望一个 Swift 工程师去花时间和精力让每一个 Hashable 的类型都得到正确实现是不合理的。

举个例子，让我们看下面的代码，这是从 Swift 4.1 的 Hashable 文档里直接摘录过来。请问这是一个好的 hashValue 的实现吗？

struct GridPoint {
  var x: Int
  var y: Int
}

extension GridPoint: Hashable {
  var hashValue: Int {
    return x.hashValue ^ y.hashValue &* 16777619
  }

  static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {
    return lhs.x == rhs.x && lhs.y == rhs.y
  }
}

答案是具体情况具体分析；如果 x 和 y 都是从受信任的来源里产出的小整型，那这个函数就很合适。但这个哈希函数有下面这么几个不好的地方：

这些位运算符很难直观得反映出代码的意图或者是其工作原理。例如，你能说出为什么 16777619 是比 16777618 更好的选择嘛？^ 和 &* 的运算符哪一个优先级更高？这里的 & 代表了什么？

我们只是想要在 Dictionary 里使用 GridPoint，但首先我们需要花时间去学习位运算符，整数移除，以及互素因子。

（真正有价值的是，上面的例子中的 magic constant 跟 32 位版本的 FNV-1a 哈希算法使用的的是一样的，使用了同样的方式去在字节序列中提取整型值）
任意构建一个足够大的 GridPoint 集合都很容易导致不同的元素产生了同样的哈希值。而如果数据的来源不可信，那它们就有可能会恶意诱发哈希碰撞。
这个哈希函数并没有很好地将输入的数据糅合到一起；它更倾向于组合一串整数簇的长链。虽然这不像哈希碰撞那么糟糕，但一些哈希表的操作在簇已经被占用时性能会急剧下降。（在 Swift 4.1 里，Set 和 Dictionary 会使用线性探测，对哈希值进行智能预处理去避免这种状况）

这些都意味着标准库需要为大家提供一种更好的 hashValue 实现指引。

通用哈希函数

伴随着 SE-0185，Swift 4.1 引入了 Hashable 实现自动合成的编译器支持。例如，前面提到的的 GridPoint 结构体就不需要显式地实现 hashValue 就可以遵循 Hashable：

struct GridPoint: Hashable {
  var x: Int
  var y: Int
  
  // hashValue 和 == 实现都会由编译器自动生成
}

SE-0185 并没有给这种自动实现指定一个哈希函数，而是把实现细节留给了编译器和标准库。为了更好得完成这件事，需要哈希函数使用在任意数量元素时的性能都一样优秀，无论它们离散预期是怎么样。

幸运的是，这个问题之前在别的情境下发生过了，并且已经针对这些情况设计了出一系列函数：Foller-Noll-Vo, MurmurHash, CityHash, SipHash 和 HighwayHash 是其中一部分。最后两个算法还包含了一些密码学的元素在里面，可以提供一定级别的哈希碰撞攻击防护。这让他们成为 Set 和 Dictionary 更好的选择。

由于 SE-0185 要求标准库去实现一个高质量的通用哈希函数，那么顺便把它们作为 API 公开出来也是一件理所应当的事情，这也可以让手动实现 Hashable 变得更方便。

一般的哈希函数工作原理都是通过维护一系列的内部状态去运作 —— 最简单的可以是 32/64-bit 的整型数值（例如：FNV-1a），但通常会比这个数据量更多。例如，SipHash 维护了一个 256-bit 的状态，而 HighwayHash 使用的是 1024-bit 的。

解决方案

我们解决 Hashable 实现问题的方案分为两个部分。第一，我们把标准库的哈希函数作为 API 公开出来。第二我们把 hashValue 替换掉，换成一个让手动实现 Hashable 产出的结果更加可预测的 API。

`Hasher` 结构体

我们提议将标准库的哈希函数通过一个新的，公开的结构体类型 Hasher 暴露出来。这个新的结构体会捕获哈希函数的状态，并且提供以下的操作：

一个创建空状态的构造器。为了让哈希值更加难以预测，每次程序初始化时生成一个随机数，程序的整个生命周期里都会把它作为哈希函数的种子值进行使用，以便让每次运行时产生的哈希值都不同。
```
public struct Hasher {
  public init()  // 每次运行程序都生成一个随机数，作为种子值使用
}
```

给哈希函数填充字节序列，并且把它们揉合到自己状态里的操作：
```
extension Hasher {
  public mutating func combine(bytes buffer: UnsafeRawBufferPointer)
  public mutating func combine<H: Hashable>(_ value: H)
}
```
combine(bytes:) 是最通用的操作，当字节序列可以作为一段单独的连续内存区域被哈希时就可以使用。 combine(_:) 是一个便利操作，能够直接传入任意 Hashable 的值；我们希望这个函数会被更频繁地使用到。（在下一个小节我们会介绍这是如何实现的）

一个提取哈希值，结束状态的操作，

extension Hasher {
  public __consuming func finalize() -> Int
}

结束 hasher 的状态；对不属于你的 hasher 调用 combine 或者 finalize 方法是非法的，或者对已经结束了状态的 hasher 也是一样的。

例如，这是 Hasher 的其中一种用法

在同一个 Swift 程序的同一次运行中，Hasher 可以保证只要传入一样的字节序列，就会产出一样的哈希值。（注意：combine 操作的顺序会对结果产生影响；只要交换上面两个整型传入的顺序就会产生完全不同的哈希）

然而，Hasher 在另外一次运行里会产生完全不同的结果，就算传入的是一样的字节序列。这种随机性很关键，因为它让潜在的攻击者更难预测到哈希值。通常 Hashable 在文档里会被定义为非确定性的。

注意：相同程序，在不同次运行中，不保证会产生相同的哈希值。所以不要把哈希值保留到下一次运行中去使用。

– Hashable 文档

（随机种子可以通过特定的环境变量进行关闭；详情请看对于 ABI 稳定的影响。）

Hasher 对于哈希函数的选择取决于标准库的实现细节，并且在未来的版本里可能会进行修改。这包括了 Hasher 自身的大小和内存布局。（目前的实现使用了 320 bits 的 SipHash-1-3 状态）

`hash(into:)` 实现要求

引入 Hasher 是一个巨大的提升，但还需要再进一步：我们需要调整 Hashable 才能更好地使用 Hasher。

我们提议给 Hashable 增加一个新的 hash(into:) 实现要求：

public protocol Hashable: Equatable {
  var hashValue: Int { get }
  func hash(into hasher: inout Hasher)
}

同时，我们会将 hashValue 属性标记为弃用。（请看代码稳定小节，了解我们如何在不破坏旧版 Swift 代码的同时做到这一点。）在未来的版本里，我们倾向于把 hashValue 转换为一个 extension 方法。

为了让我们更容易地在 Hashable 里使用 hash(into:)，Haser 提供了一个 combine 的变体，唯一做的事情就是对传入的值调用 hash(into:)：

extension Hasher {
  @inlinable
  public mutating func combine<H: Hashable>(_ value: H) {
    value.hash(into: &self)
  }
}

这单纯只是为了方便；hasher.combine(foo) 比 foo.hash(into: &hasher) 更容易敲出来。

乍一看，我们似乎没有很充分的理由去替换掉 hashValue，但毕竟 Hasher 可以用来把离散预测的逻辑从 Hashable 的实现里剥离出来：

extension GridPoint: Hashable {
  var hashValue: Int { 
    var hasher = Hasher()
    hasher.combine(x)
    hasher.combine(y)
    return hasher.finalize()
  }
}

这段代码有什么问题？是什么让 hash(into:) 比之前更好，以至于我们需要去修改一个基础的协议？

更好的可发现性 – 使用 hashValue 时，你需要去了解怎么使用 Hasher：这个 API 并不能引导你去正确地完成这件事。甚至你还需要每次实现 hashValue 时手动初始化和结束一个 Hasher 示例。对比上面 hash(into:) 的实现：
```
extension GridPoint: Hashable {
  func hash(into hasher: inout Hasher) {
    hasher.combine(x)
    hasher.combine(y)
  }
}
```
这段代码简单明了，没有任何多余的部分。Hasher 作为函数签名的一部分，让你实现 hash(into:) 时自然会知道怎么去做。

保证了离散度 – 保留现有的 hashValue 接口意味着 Set 和 Dictionary 难以保证 Hashable 类型可以产生足够离散的哈希值。因此，这些集合还需要去存储预处理过的哈希值。所以我们想通过引入 Hasher 来避免存储这些预处理值。

Hasher 可自定义性 – hash(into:) 把 Hasher 的初始化从 Hashable 中剥离出来，放到了哈希的集合里。这让我们可以根据每一个哈希数据结构的需要去自定义 Hasher。例如，标准库可以使用给每一个 Set 和 Dictionary 实例使用不同的种子值；这种做法可以让哈希值更难以预测，提高了可靠性，但（或者更重要的是），它极大地提升了那些需要在 Set / Dictionary 实例之间复制数据的常用操作的性能。

更优秀的性能 – 同样的，hash(into:) 把计算最终值的步骤从 Hashable 里剥离了出来。最终值计算是一个很消耗性能的操作；例如，在 SipHash-1-3 里，它等价于三次 64-bit 的 combine 操作。对复合类型里的每一个组件进行求值会让哈希求值过程变得非常慢。

例如，下面的 GridRectangle 类型：

struct GridRectangle {
  let topLeft: GridPoint
  let bottomRight: GridPoint
}

使用 hashValue 时，它的 Hashable 实现大概会是这样：

extension GridRectangle: Hashable {
  var hashValue: Int { // 性能差，不建议使用
    var hasher = Hasher()
    hasher.combine(bits: topLeft.hashValue) 
    hasher.combine(bits: bottomRight.hashValue)
    return hasher.finalize()
  }
}

每一个 hashValue 的求解都会创建各自的 hasher 并且求值。假设求值操作相当于三次 combine（并且假设初始化不消耗资源），那就需要 15 个 combine 的运行时间：

1   hasher.combine(topLeft.hashValue)
1       hasher.combine(topLeft.x)     (在 topLeft.hashValue 里)
1       hasher.combine(topLeft.y)
3       hasher.finalize()
1   hasher.combine(bottomRight.hashValue)
1       hasher.combine(bottomRight.x) (在 bottomRight.hashValue 里)
1       hasher.combine(bottomRight.y)
3       hasher.finalize()
3   hasher.finalize()
---
15

而使用 hash(into:) 就会是下面这样：

extension GridRegion: Hashable {
  func hash(into hasher: inout Hasher) {
    hasher.combine(topLeft)
    hasher.combine(bottomRight)
  }
}

这可以显著降低哈希的消耗，只需要四次 combine 和一次最终值求解即可，比起原来的方式减少了将近一半的消耗：

 1   hasher.combine(topLeft.x)      (在 topLeft.hash(into:) 里)
 1   hasher.combine(topLeft.y)
 1   hasher.combine(bottomRight.x)  (在 bottomRight.hash(into:) 里)
 1   hasher.combine(bottomRight.y)
 3   hasher.finalize()             (在 GridRectangle.hash(into:) 外面)
---
 7

切换到 hash(into:) 之后让我们可以使用更加高效，健壮的方式去获取哈希值，同时代码也更加简洁。

具体设计

`Hasher`

给标准库添加下面的类型：

/// 表示 `Set` 和 `Dictionary` 使用的通用哈希函数。
///
/// 这个哈希函数是一个 128-bit 的种子值和一个随机字节序列到一个整型哈希值的映射。
/// 种子值会在 `Hasher` 初始化时确定下来，而 `combine` 函数
/// 则会在填充字节序列时调用。当所有的字节都填充到 hasher 的时候，
/// 哈希值可以通过调用 `finalize()` 获取到：
///
///     var hasher = Hasher()
///     hasher.combine(23)
///     hasher.combine("Hello")
///     let hashValue = hasher.finalize()
///
/// 内部的哈希算法是为了雪崩效应而设计的：种子值或者输入的字节序列微小的
/// 差异就会让最终产生的哈希值产生巨大的改变。
///
/// - 注意：`Hasher` 的种子通常是随机生成的，这意味着每一次程序的运行都会产生不同的值。
///   `Hasher` 实现的哈希算法在不同版本的标准库里也会有差异，所以不要在运行期里
///   保存哈希值到下一次运行里复用。
public struct Hasher {
  /// 通过一个运行期产生的随机值初始化。
  /// 种子通常会通过一个高质量的随机来源获取，在程序启动时就确定下来。
  public init()
  
  /// 给 hasher 填充 `value`，把必要的部分糅合到 hasher 的状态里
  @inlinable
  public mutating func combine<H: Hashable>(_ value: H) {
    value.hash(into: &self)
  }

  /// 把 `buffer` 里的原始字节喂给 hasher，把它的 bits 揉合到 hasher 的状态里
  public mutating func combine(bytes buffer: UnsafeRawBufferPointer)
  
  /// 结束 hasher 的状态并且返回一个哈希值
  ///
  /// finalize 会将 hasher 的状态耗尽：手动 finalize 一个不属于你的 hasher，
  /// 或者对一个已经结束的 hasher 进行任何操作都是非法的。
  ///（以后这些都可能会成为编译错误）
  public __consuming func finalize() -> Int
}

`Hashable`

把 Hashable 协议改成下面这样：

/// 一个可以被哈希到 `Hasher` 里的类型。
///
/// 你可以使用任意遵循 `Hashable` 协议的类型作为 Set 或者 Dictionary 的 key。
/// 许多标准库里的类型都遵循 `Hashable`：
/// 字符串，整型，浮点数和布尔类型，甚至 Set 默认也是 Hashable 的。一些其他类型，
/// 例如 Optional，Array 和 Range 在元素为 Hashable 时也会遵循 Hashable。
///
/// 你自定义的类型也可以是 Hashable 的。当你定义了一个不带关联值的枚举时，
/// 它可以自动实现 Hashable，并且你也可以通过实现 `hash(into:)` 函数去遵循 `Hashable`。
/// 对于那些所有成员变量都是 `Hashable` 的结构体，以及那些所有关联值都是 `Hashable` 的枚举类型，
/// 编译器都可以为它们自动生成 `hash(into:)` 的实现。
///
/// 哈希一个值意味着把它的必要部分填充到一个哈希函数里，这就是 `Hasher` 类型的抽象。
/// 这里的必要部分指的就是那些在 `Equatable` 实现里进行比较的部分。
/// 两个相等的实例必须在 `hash(into:)` 里以同样的顺序向 `Hasher` 填充同样的数据。
///
/// 遵循 Hashable 协议
/// ===================================
///
/// 为了在 Set 里使用你的自定义类型或者在 Dictionary 里把它作为 Key 类型，
/// 请让它遵循 `Hashable` 协议。`Hashable` 协议是继承自 `Equatable` 协议的，
/// 所以你必须也让它遵循协议的实现。
///
/// 一个自定义类型的 `Hashable` 和 `Equatable` 实现可以由编译器为你自动生成，
/// 只要你的类型声明了 `Hashable` 的遵循，并且符合以下要求：
///
/// - 对于一个 `struct`，它的所有存储变量都必须遵循 `Hashable`。
/// - 对于一个 `enum`，它的所有关联值都必须遵循 `Hashable`。（一个没有关联值的枚举
///   甚至不需要显式声明 `Hashable` 的遵循）
///
/// 为了自定义你的类型的 `Hashable` 遵循，让不符合以上条件的类型也可以遵循 `Hashable`，
/// 或者是拓展一个现有的类型让它遵循 `Hashable`，只要你手动实现 `hash(into:)` 方法
/// 即可，同时为了保证你的类型能够符合 `Hashable` 和 `Equatable` 协议的语义，
/// 最好也手动实现 Equatable。
///
/// 举一个例子，我们设想使用 `GridPoint` 类型描述一个网格的点击位置。
/// 这是 `GridPoint` 类型的初始声明：
///
///     /// 一个 x-y 坐标系统里的点
///     struct GridPoint {
///         var x: Int
///         var y: Int
///     }
///
/// 你需要创建一个 grid point 的集合，去表示用户已经点击过的点。
/// 因为 `GridPoint` 类型不是 hashable 的，所以他不能作为 Set 里的 `Element`。
/// 为了遵循 `Hashable`，我们需要提供实现 `==` 函数和 `hash(into:)` 函数。
///
///     extension GridPoint: Hashable {
///         func hash(into hasher: inout Hasher) {
///             hasher.combine(x)
///             hasher.combine(y)
///         }
///
///         static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {
///             return lhs.x == rhs.x && lhs.y == rhs.y
///         }
///     }
///
/// `hash(into:)` 在这个例子里需要把属性 `x` 和 `y` 填充到 hasher 里，
/// 并且在 `==` 里对相同的元素进行比较。
///
/// 现在 `GridPoint` 遵循了 `Hashable` 协议，你可以创建一个已经点击过的坐标点的集合。
///
///     var tappedPoints: Set = [GridPoint(x: 2, y: 3), GridPoint(x: 4, y: 1)]
///     let nextTap = GridPoint(x: 0, y: 1)
///     if tappedPoints.contains(nextTap) {
///         print("监测到一个已经点击过的点 (\(nextTap.x), \(nextTap.y))。")
///     } else {
///         tappedPoints.insert(nextTap)
///         print("监测到一个新的点击点 (\(nextTap.x), \(nextTap.y))。")
///     }
///     // 打印结果 "监测到一个新的点击点 (0, 1).")
public protocol Hashable: Equatable {
  /// 哈希值。
  ///
  /// 哈希值只在同一次运行里保证相同，所以不要在运行期间保存哈希值并且到
  /// 下一次运行时使用。
  var hashValue: Int { get }
  
  /// 通过调用 `hasher` 的 `combine` 函数，把这个值的必要部分填充到 `hasher` 里.
  ///
  /// 准确的来说，必要的部分指的就是在 `Equatable` 的实现里拿来比较的那一部分。
  func hash(into hasher: inout Hasher)
}

代码兼容性

引入新的 Hasher 类型是一个单纯的增量修改。然而，添加 hash(into:) 实现要求会破坏代码稳定。为了保证我们兼容旧版的代码，在允许新代码只实现 hash(into:) 的同时，我们拓展了 SE-0185 里的 Hashable 自动实现，以便让类型遵循老的 Hashable 时，可以自动为类型实现新的实现要求。

提案实现之后，使用 Swift 4.1 或更早版本编写的代码仍然可以通过编译（在正确的语言模式下）。编译器将会自动合成缺失的 hash(into:) 的实现要求：

struct GridPoint41: Hashable { // Swift 4.2 之前写的代码
  let x: Int
  let y: Int
  
  var hashValue: Int {
    return x.hashValue ^ y.hashValue &* 16777619
  }
  
  // 由编译器自动实现
  func hash(into hasher: inout Hasher) {
    hasher.combine(self.hashValue)
  }
}

但使用 Swift 4.2 的模式时，编译器会自动抛出一个弃用的警告。（然而，注意，如果仅仅只是使用了 hashValue 的代码，依旧可以通过编译并且不会有编译警告）

使用 Swift 4.2 或者更新版本写出来的代码，必须满足 Hashable 的 hash(into:) 实现需求。编译器将会自动使用一个合适的 hashValue 实现。

struct GridPoint42: Hashable { // 使用 Swift 4.2 编写的代码  
  let x: Int
  let y: Int
  
  func hash(into hasher: inout Hasher) {
    hasher.combine(x)
    hasher.combine(y)
  }
  
  // 由编译器自动实现：
  var hashValue: Int {
    var hasher = Hasher()
    self.hash(into: &hasher)
    return hasher.finalize()
  }
}

在升级到 Swift 4.2 后，Hashable 类型在旧版里的实现都应该迁移到 hash(into:)。

而符合 SE-0185 里的要求自动生成 Hashable 实现的，可以直接去除掉显式的 hashValue 实现。注意，Swift 4.2 通过 Conditional Conformance 给许多标准库的类型实现了 Hashable；这让 Hashable 的自动实现可以使用这些类型去作为组件。

而那些还需要手动实现 Hashable 的类型，迁移程序可以帮助你完成升级的过程。例如，上面 GridPoint41.hashValue 的实现应该像下面这样重写：

struct GridPoint41: Hashable { 
  // 从 Swift 4.1 迁移过来的代码
  let x: Int
  let y: Int

  // 从 hashValue 迁移过来：
  func hash(into hasher: inout Hasher) {
    hash.combine(x.hashValue ^ y.hashValue &* 16777619)
  }
}

这么做无法像逐个元素 combine 那样产生高质量的哈希，但这可以作为一个不错的开始。

对于 ABI 稳定的影响

Hasher 和 hash(into:) 对于标准库的 ABI 页是单纯的增量修改。Hasher 是一个 resilient 的结构体，拥有不透明的内存布局以及几乎不透明的成员。（唯一一个例外就是泛型函数 combine(_:)，仅仅是作为语法糖的存在）

虽然这个计划会把 hashValue 标记为弃用，但不会移除它。实现了 Hashable 的类型可以继续保留这个实现，尽管具体实现可能是由编译器自动合成的。

为了实现不确定性，程序启动时会由 runtime 初始化一个种子值给 Hasher 使用。种子通常是随机生成的，但可以通过 SWIFT_DETERMINISTIC_HASHING 这个环境变量来关闭掉这个功能，设置为 1 即可。

对于 API 稳定的影响

把 hashValue 替换成换成 hash(into:)，把哈希函数的选择从 Hashable 里剥离了出来，放到了标准库里，在 resilient 的边界之内。

Hasher 的设计让未来版本的标准库可以替换掉哈希函数。使用旧版本编译的 Hashable 在 link 到新版本的时候可以使用新的算法。这也包含了对 Hasher 内存布局的修改。

（我们预想了几种替换掉哈希函数的情况。例如，我们也许需要在当前函数的漏洞被发现时这么做，去恢复 Set 和 Dictionary 的可靠性，我们也许还想要调整哈希函数去应对特殊的场景特殊的需要（例如网络服务），又或者只是哈希的性能优化）

其它弃用的方案

保留 `Hashable` 原本的定义

我们考虑的其中一个方案是暴露 Hasher，但保留 Hashable 原本的实现。独立的 Hashable 类型可以选择是否使用 Hasher，或者采取它们自己的哈希函数。

我们觉得这个做法并不那么令人满意；根本原因在 hash(into:) 实现要求里有比较详细的说明。

有过几次创建新协议取代 Hashable 的尝试。例如，在 Swift 的测试里有一个叫做 NewHashable protocol 的原型实现。提案的作者们也有过自己的尝试并且分享了出来：Karoy 早前开源了哈希工具包，提供了内置的 Hashable 替代方案，并且 Vincent 也写了一篇添加 HashVisitable 协议到标准库的提案 —— 这些都是这个提案的先驱者。

在这些方案里，都是定义一个新的协议去替代 Hashable，或者是与 Hashable 无关的一些方案。这是其中一部分：

protocol Hashable: Equatable {
  var hashValue: Int { get }
}

protocol Hashable2: Hashable {
  func hash(into hasher: inout Hasher)
}

extension Hashable2 {
  var hashValue: Int {
    var hasher = Hasher()
    hash(into: &hasher)
    return hasher.finalize()
  }
}

虽然对于一个外部的哈希库来说是一个很合适的做法，但我们认为它并不适用于标准库。添加一个新的协议会显著增加新用户关于哈希的认知负担，并且也会让标准库增加一些不必要的 API。

新的协议需要有一个新的名字，但 Hashable 已经是哈希相关的协议里最好的名字了 —— 所以我们需要为这个“更好”的协议选一个没那么好的名字。

相比起完整保留 Hashable 或者是同时使用两个协议，我们认为弃用一个协议的实现要求虽然会产生很大的变动，但总体来说是值得的。

另外，添加新协议会让 Hashable 整体变得更复杂。同时 Set 和 Dictionary 应该如何使用 Hasher（这些问题都没有很好的得到解决，但它们也许还需要一些一次性的编译支持，例如，我们也许会想要让所有遵循了 Hashable2 的类型自动实现 Hashable）

让 `Hasher` 成为一个协议，使得 `hash(into:)` 变成一个泛型函数

让 Swift 程序员可以定义自己的哈希函数，并且把它们应用到任意的 Hashable 类型是一件很棒的事情：

protocol Hasher {
  func combine(bytes: UnsafeRawBufferPointer)
}
protocol Hashable {
  func hash<H: Hasher>(into hasher: inout H)
}

然而，这会增加一个新的讨论维度，并且很难评判其收益。我们认为自定义 hasher 是一个很小众的需求。例如，我们想不到将来给 Set 和 Dictionary 增加一个自定义 hasher 的需要。而另一方面，标准化，使用单一的，高质量的哈希函数的优势反而很明显：

给 hash(into:) 增加一个泛型参数会让 Hashable 的 API 变得复杂。
只支持一种 Hasher 的话，我们可以投入所有精力去让它运行得足够快。例如，我们知道标准的 hasher 内部的 mutating 函数，或者在哈希值计算期间任何引用类型的 mutation 都不会触发任何 retain/release 操作；让编译器了解这些信息可以得到更多的优化，否则很难做到。
Swift 里的泛型不是 zero-cost 的抽象。我们也许会倾向于认为通过使用一些为场景特殊优化过的哈希函数可以获取到更高的性能表现，但这并不是必然的 —— 支持自定义的 hasher 的性能消耗反而会掩盖掉算法带来的提升。

注意，非泛型的 Hasher 是完全支持 Bloom filter 或者其他需要多个哈希函数的数据结构。（选择另外的哈希函数时，只要支持一个新的种子值就可以了）

把 `hash(into:)` 的参数改为闭包，而不是一个新的类型

上一个方案的另一个变种就是，把 hasher 声明为一个简单的闭包参数：

protocol Hashable {
  func hash(into hasher: (Int) -> Void)
}

extension GridPoint: Hashable {
  func hash(into hasher: (Int) -> Void) {
    hasher(x)
    hasher(y)
  }
}

虽然这是一个简单有效的 API，但它存在颗粒度的问题 —— 它不支持任何除了 Int 以外的有效字节加入到哈希的状态里。

另外，就像泛型，这种基于闭包的接口性能相比起 Hasher 来说不够好，因为编译器无法保证闭包不产生任何潜在的副作用。

简介

提案缘由

现状

通用哈希函数

解决方案

`Hasher` 结构体

`hash(into:)` 实现要求

具体设计

`Hasher`

`Hashable`

代码兼容性

对于 ABI 稳定的影响

对于 API 稳定的影响

其它弃用的方案

保留 `Hashable` 原本的定义

定义一个新的协议

让 `Hasher` 成为一个协议，使得 `hash(into:)` 变成一个泛型函数

把 `hash(into:)` 的参数改为闭包，而不是一个新的类型

Recommend

Dar1in9's Blog

常见Web源码泄露

读书笔记：《自由及其背叛》

开年随笔：关于肺炎、游戏、电影和书

Shrinking BSON Documents

Using Schema.org with Microdata

Crypto-RSA加密

Union.ai with Ketan Umare

ASP.NET Core + Azure Key Vault + Azure AD MSI = Awesome way to do config

Guide to WCAG

About Joyk