Swift 新特性 Hasher

Swift 新特性 Hasher

Previously on the Hashable

用 Swift 3年多了。

近期Xcode从10.1更新到10.2，支持Swift 5了，

升级自己工程的时候，除了switch语句要增加对未知枚举的处理外，

还发现Hashable的hashValue被弃用了，取而代之的是

func hash(into hasher: inout Hasher)。

这是个啥？直译过来是散列器，一起来看看吧。

Deprecation & New

public protocol Hashable : Equatable {

    // 被弃用的hashValue。
    var hashValue: Int { get }

    // 现在遵循Hashable需要实现这个方法。
    func hash(into hasher: inout Hasher)
    
}

func hash(into hasher: inout Hasher)的原文注释

 Hashes the essential components of this value by feeding them into the given hasher.

 Implement this method to conform to the `Hashable` protocol. 
 The components used for hashing must be the same as 
 the components compared in your type's `==` operator implementation. 
 Call `hasher.combine(_:)` with each of these components.

 - Important: Never call `finalize()` on `hasher`. Doing so may become a
   compile-time error in the future.

 - Parameter hasher: The hasher to use when combining the components
   of this instance.

结合自己的理解，翻译过来就是

将这个instance的必要成分填充至给定的散列器，来散列它。

实现这个方法来遵循Hashable协议。

这些必要成分必须和以前实现的==方法里面的成分一样。

• 要点：不要调用Hasher的finalize() 方法，未来可能会造成编译错误。
• 参数haser: 主要是用来组合这个实例的成分。

Hasher

 The universal hash function used by `Set` and `Dictionary`.

 `Hasher` can be used to map an arbitrary sequence of bytes to an integer
 hash value. You can feed data to the hasher using a series of calls to
 mutating `combine` methods. When you've finished feeding the hasher, the
 hash value can be retrieved by calling `finalize()`:

     var hasher = Hasher()
     hasher.combine(23)
     hasher.combine("Hello")
     let hashValue = hasher.finalize()

 Within the execution of a Swift program, `Hasher` guarantees that finalizing
 it will always produce the same hash value as long as it is fed the exact
 same sequence of bytes. However, the underlying hash algorithm is designed
 to exhibit avalanche effects: slight changes to the seed or the input byte
 sequence will typically produce drastic changes in the generated hash value.

 - Note: Do not save or otherwise reuse hash values across executions of your
   program. `Hasher` is usually randomly seeded, which means it will return
   different values on every new execution of your program. The hash
   algorithm implemented by `Hasher` may itself change between any two
   versions of the standard library.

Hasher，通用的哈希函数，被Set和Dictionary所采用。

Hasher，可以将一段任意字节数据映射为integer哈希值。

你可以调用多次combine方法来填充hasher(该方法是可以修改hasher的，所以用mutating修饰)，

在这之后，通过finalize()可以取得hash value。

代码示例。

在Swift程序的执行过程中，只要填充了相同的数据，

Hasher就能确保finalize()始终能得到相同的哈希值，

但是呢，设计的底层哈希算法拥有这样的特性：

种子或数据发生轻微的变化，会造成巨大的哈希值变化。

(PS: 以上这两点可以提高查找的效率，减少hash value冲突，也就减少调用==方法)

需要注意的是，不要保存或重用程序执行中得到的hash value，

Hasher会经常随机化种子，意味着每次程序执行的时候，Hasher的哈希算法可能会变。

public struct Hasher {

 Creates a new hasher.

 The hasher uses a per-execution seed value that is set during process
 startup, usually from a high-quality random source.
 
 创建一个新的hasher，它会使用高质量的随机种子，每次进程开启，这些种子都会重新生成。
 
    public init()
 

 Adds the given value to this hasher, mixing its essential parts into the
 hasher state.

 Parameter value: A value to add to the hasher.
 
 添加已遵循Hashable的值到Hasher中，这些值是构成哈希的重要部分。
 
    @inlinable public mutating func combine<H>(_ value: H) where H : Hashable


 Adds the contents of the given buffer to this hasher, mixing it into the
 hasher state.

 Parameter bytes: A raw memory buffer.
 
 添加字节数组到Hasher中。
 
    public mutating func combine(bytes: UnsafeRawBufferPointer)


 Finalizes the hasher state and returns the hash value.

 Finalizing consumes the hasher: it is illegal to finalize a hasher you
 don't own, or to perform operations on a finalized hasher. (These may
 become compile-time errors in the future.)

 Hash values are not guaranteed to be equal across different executions of
 your program. Do not save hash values to use during a future execution.

 Returns: The hash value calculated by the hasher.
 
 终结这个hasher的状态，获得hash value。
 
 不是你生成的haser，调用finalize是非法的。
 
 已经调用过finalize的hasher也不能再调用finalize了。未来可能会引起编译错误。
 
 每次程序执行不能保证得到相同的哈希值。因此不要持久化它。
 
    public __consuming func finalize() -> Int
    
}

Why Hasher?

结合自己的理解，Hasher有以下优点：

1. 简化开发者遵循Hashable的工作量。开发者不需要关心hashValue怎么计算的。
2. 一定程度上降低了Swift在hashValue上的冲突。基于文档上所说的底层哈希算法。
3. 扩展了可哈希的范围。除了已遵循Hashable的类型，还支持字节数组。

Seems like Zobrist Hash

在中国象棋的实现中，哈希启发我用到了Zobrist Hash。

过程是这样的，

• 对于每个棋子，每个棋盘位置，均预先生成随机数。每次程序运行的时候，随机数总是新生成的。

• 对于每个局面，由棋子和棋子的位置构成。

• 局面的key，可以表示为，棋子在其位置上的随机数异或和。

有以下优点：

1. 顺序无关性。A ^ B = B ^ A。
2. 差异性。若 B ≠ C，则 A ^ B ≠ A ^ C。
3. 快速删除、添加。若 Key = Value ^ A，那么移除A的操作是 Key ^= A，其他操作同理。

Conclusion

遵循Hashable的步骤：

1. 声明：func hash(into hasher: inout Hasher)。
2. 实现：连续调用hasher.combine(targetValue)。

注意事项：

1. 不要调用你没生成的Hasher的finalize方法。
2. 尽量不要持久化hash value，即便在同一个程序执行生命周期内。