声明：此博客是本人在泊学网学习Swift过程的笔记与心得
Dictionary进阶
Swift中，Dictionary的内在查找机制是通过key-value的哈希表实现的，因此，在Swift中，Dictionary的查找效率为O(1)。下面，我们了解一下Dictionary内部的哈希实现机制。
需要强调的是，哈希算法需要计算哈希值，因此导致key的类型必须是一个可以计算哈希值的类型，即遵从了Hashable协议的类型。例如，String，Int，Date，Bool等。协议中定义了hashValue属性，用来获取通过key计算出的哈希值。
当然，自定义类型也可以作为Key存在，就是要手动遵从Hashable协议。
定义一个结构体作为储存学校学生信息：
struct Student {
var studentID: Int
var name: String
}
※使用结构体封装自定义Key而非类封装，是考虑到不要使用引用类型而使用值类型作为Key，防止不经意的修改Key值。
通过Swift的Extension功能为Student添加Hashable的实现：
extension Student: Hashable {
var hashValue: Int // 前面提到的需要计算的哈希值
}
说到计算哈希值，就需要对计算算法进行多方面考虑：性能与哈希值在整数范围的分布。每次Dictionary进行增删改查操作时，都需要通过key值计算哈希值，算法的性能与访问元素位置的O(1)性能要综合考虑。如果哈希算法计算的哈希值相同，则需要进行计算哈希值碰撞，这样很有可能变成一个O(n)的算法。
// 一个极端的例子
extension Student: Hashable {
var hashValue: Int {
return 1
}
}
这种情况下，每一次返回的hashValue都为1，每一次操作，几乎都要进行碰撞处理。一次，虽然有O(1)的性能，但是碰撞处理将这个性能变成了O(n)的性能，因此，哈希值在整数区间均匀分布是设计哈希函数重要考虑的因素。
假设Swift标准库中的hashValue都是满足性能与分布要求的，那么我们就可以利用标准库中的hashValue做一些低性能运算，得到自己的hashValue。
extension Student: Hashable {
var hashValue: Int {
return studentID.hashValue ^ name.hashValue
}
}
值得一提的是，这种情况下可能会报错：Student没有遵从Equatable协议。这是因为，如果遵从Hashable协议，实现哈希函数的同时，我们也必须遵从 Equatable，因为哈希函数有一个重要原则：两个相等的对象的哈希值必须相同。因此需要重载定义“==”。
extension Student: Equatable {
static func == (lhs: Student, rhs: Student) -> Bool {
return lhs.studentID == rhs.studentID && lhs.name == rhs.name
}
}
这样，一个简单的哈希实现就完成了。
当然，这种哈希函数只是简单的异或运算，很有可能计算出同样的值。例如异或运算：ABA = B，A^B = B^A 这些情况。因此，也可以进一步优化一下哈希函数，可以采取对某些值进行”加密“运算，防止上述情况的发生。
// 在定义中实现一个对ID进行加密的算法
struct Student {
var studentID: Int
var name: String
func encryption(ID: Int, with num: Int) -> Int {
return ((ID << num) ^ num) >> num
}
}
Ps.加密运算可以通过简单的位运算来进行。
这样，每一次计算hashValue之前，对studentID进行加密运算，就可以大大防止异或中的一些情况发生。
extension Student: Hashable {
var hashValue: Int {
return encryption(ID: studentID.hashValue, with: 18) ^ name.hashValue
}
}
