【Swift】 Collections初识 - Dictiona

声明：此博客是本人在泊学网学习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
    }
}

这样，一个简单的哈希实现就完成了。

当然，这种哈希函数只是简单的异或运算，很有可能计算出同样的值。例如异或运算：A^BA = 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
    }
}