当您在Apple Store预订Genius酒吧时，您会被指示在一天中的特定时间出现并与礼宾人员一起办理入住手续。在指导您拉起凳子之后，礼宾部会将您添加到队列中并记下如何识别您的身份。
根据前零售员工的匿名报告，对于如何描述客户有严格的指导方针。没有使用他们的外表：年龄，性别，种族，身高 - 甚至没有头发颜色。相反，所有顾客都被他们的服装所描述，如“黑色高领毛衣，牛仔裤和眼镜的人”。
这种描述客户的做法与编程中的散列函数有很多共同之处。与任何良好的散列函数一样，它一致且易于计算，并且可用于快速查找您正在寻找的内容（或谁）。比队列好多了，我想你会同意的！
本周我们的主题是Hashable 它的新相关类型，Hasher。它们共同构成了Swift最受欢迎的两个集合类的基础功能：Dictionary和Set。
小编推荐一个交流群 有技术的来闲聊 没技术的来学习691040931
假设您有一个 可以相互比较的对象列表。要在该列表中查找特定对象，请迭代所有元素，直到找到匹配项。当您向数组添加更多元素时，查找其中任何一个元素所需的平均时间会线性增加（O(n)）。
如果您将这些对象存储在一个 集合中，理论上可以在常量时间（O(1)）中找到它们中的任何一个- 也就是说，对具有10个元素的集合进行查找所花费的时间与使用10,000 *的集合上的查找相同。这是如何运作的？而不是按顺序存储对象，集合根据对象的内容计算<dfn style="box-sizing: border-box;">散列</dfn>作为索引。当您在集合中执行对象的查找时，您使用相同的函数来计算新的散列并在那里查找对象。
*当两个对象 具有相同的哈希值但不相等时会产生<dfn style="box-sizing: border-box;">哈希冲突</dfn>。当插入时发生冲突时，它们将存储在该地址的列表中。对象之间的冲突率越高，哈希集合的性能就变得越线性。
可哈希
在Swift中， Array为列表和Set集提供标准接口。为了将对象存储在a中Set，其类型必须符合Hashable（并且通过扩展名Equatable）。Swift的标准地图 界面Dictionary对其关联Key类型有类似的约束。
在该语言的先前版本中，需要相当多的样板代码 来满足在Set或中存储自定义类型的要求Dictionary。
请考虑以下Color类型，它表示使用红色，绿色和蓝色强度的8位值的颜色：
struct Color {
let red: UInt8
let green: UInt8
let blue: UInt8
}
为了符合Equatable，您必须为==运营商提供实施。为了符合Hashable，您必须提供计算属性的实现：hash<wbr style="box-sizing: border-box;">Value
// Swift < 4.1
extension Color: Equatable {
static func ==(lhs: Color, rhs: Color) -> Bool {
return lhs.red == rhs.red &&
lhs.green == rhs.green &&
lhs.blue == rhs.blue
}
}
extension Color: Hashable {
var hashValue: Int {
return self.red.hashValue ^
self.green.hashValue ^
self.blue.hashValue
}
}
对于大多数开发人员来说，实现Hashable是完成实际工作的速度的快速XOR 突破，因此他们只需要覆盖所有存储的属性并将其称为一天。
这种方法的一个缺点是其高速率的哈希冲突。因为XOR是 可交换的，所以颜色与青色和黄色不同会产生哈希冲突：
// Swift < 4.2
let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF)
let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00)
cyan.hashValue == yellow.hashValue // true, collision
大多数时候，这不是问题; 现代计算机是如此强大，以至于你必须得到许多错误的实现细节才能注意到性能的任何降低。
但这并不是说细节无关紧要 - 它们往往非常重要。稍后会详细介绍。
可靠性一致性的自动合成
从Swift 4.1开始，如果编译器的成员也符合这些协议，编译器会自动合成在声明中采用这些协议的类型Equatable和Hashable协议的一致性。
除了大大提高开发人员的工作效率外，还可以大幅减少代码库的大小。例如，我们Color之前的例子 - 现在是原始尺寸的⅓：
// Swift >= 4.1
struct Color: Hashable {
let red: UInt8
let green: UInt8
let blue: UInt8
}
尽管对语言进行了这些明确的改进，但仍然存在一些关于某些实现细节的挥之不去的问题。
在他的Swift Evolution提案 SE-0185：合成等同和可融合的一致性中， Tony Allevato提供了关于散列函数的这个注释：
散列函数的选择留作实现细节，而不是设计的固定部分; 因此，用户不应该依赖于其行为的特定特征。最可能的实现是在每个成员的散列值上调用标准库的 函数，然后将它们与exclusive-or（）组合在一起，这反映了今天类型的散列方式。
_mix<wbr style="box-sizing: border-box;">Int``^``Collection
幸运的是，没过多久Swift就可以解决哈希函数问题了。我们在下一个版本中得到了答案：
散列器
Swift 4.2 Hashable通过引入Hasher类型并采用新的通用散列函数进一步细化。
根据Swift Evolution提案， SE-0206：Hashable Enhancements：
使用良好的散列函数，简单的查找，插入和删除平均需要恒定的时间。但是，当没有仔细选择散列函数以适应数据时，这种操作的预期时间可以与存储在表中的元素数量成比例。
作为Karoy Lorentey 与文森特Esche注意到，基于散列的集合像正选赛Set，并Dictionary 为他们查找值在固定时间内的能力。如果散列函数不能产生均匀的值分布，则这些集合实际上成为链接列表。
Swift 4.2基于SipHash系列伪随机函数实现散列 ，特别是SipHash-1-3和SipHash-2-4，每个消息块有1或2轮散列，分别有3或4轮终结。
现在，如果要自定义类型的实现方式Hashable，可以覆盖hash(into:)方法而不是。该方法按引用传递对象，您可以调用该对象以添加类型的基本状态信息。hash<wbr style="box-sizing: border-box;">Value``hash(into:)``Hasher``combine(_:)
// Swift >= 4.2
struct Color: Hashable {
let red: UInt8
let green: UInt8
let blue: UInt8
// Synthesized by compiler
func hash(into hasher: inout Hasher) {
hasher.combine(self.red)
hasher.combine(self.green)
hasher.combine(self.blue)
}
// Default implementation from protocol extension
var hashValue: Int {
var hasher = Hasher()
self.hash(into: &hasher)
return hasher.finalize()
}
}
通过抽象掉低级位操作细节，开发人员可以自动利用Swift的内置散列函数，这样可以避免重现我们在原有XOR实现中的冲突：
// Swift >= 4.2
let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF)
let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00)
cyan.hashValue == yellow.hashValue // false, no collision
自定义哈希函数
默认情况下，Swift使用通用散列函数将字节序列减少为单个整数。
但是，您可以通过为您的域定制哈希函数来改进这一点。例如，如果你正在编写一个程序来玩国际象棋或棋盘游戏，你可以实现Zobrist哈希 来快速存储游戏状态。
防范哈希洪水
选择像SipHash这样的加密算法有助于防止<dfn style="box-sizing: border-box;">散列泛滥的DoS</dfn>攻击，这种攻击会故意尝试生成散列冲突，以试图强制执行散列数据结构的最坏情况并导致程序慢慢停止。 这在2010年初引发了一系列网络问题。
为了使事情更安全， Hasher每次启动应用程序时都会生成随机种子值，以使哈希值更难以预测。
您不应该依赖特定的哈希值或在执行中保存它们。在极少数情况下，您需要确定性行为，您可以设置标志SWIFT_DETERMINISTIC_HASHING 以禁用随机散列种子。
编程类比的挑战在于它们通过边缘情况规范化反社会行为。
当我们能够思考攻击者可能将某种特定行为用于某种恶意目的的所有方式时，我们就像软件工程师一样出类拔萃 - 就像哈希泛滥DoS攻击一样。但是，通过这样做，当我们应用知识AFK时，我们冒着失败的风险。
也就是说...亲爱的读者，我不会以任何方式鼓励你在下次访问当地的Apple零售商时与你的好友协调服装，试图在Geniuses中制造混乱和不和。
请不要。
相反，请让你的外卖是这样的：
如果您在Genius酒吧等候，请远离身穿同色衬衫的人。它会让每个人都变得容易多了。
扫码进交流群 有技术的来闲聊 没技术的来学习
691040931
网友评论