Dictionary

[TOC]

Dictionary相关的基础知识

Dictionary是除了Array之外的另一种非常重要的数据结构，它用于把某种形式的key，关联到某种形式的value。

定义Dictionary

假设我们要定义一个数据结构，用来保存用户对某个视频的观看情况。

enum RecordType {
    case bool(Bool)
    case number(Int)
    case text(String)
}

let record11: [String: RecoredType] = [
    "uid": .number(11),
    "exp": .number(100),
    "favourite": .bool(true),
    "title": .text("Dictionary basics")
]

在上面的代码里，我们用[KeyType: ValueType]的形式定义一个Dictionary。当定义好Dictionary之后，我们就能直接用[Key]来访问某个key对应的值了：

record11["uid"] // number(11)
record11["favourite"] //bool(true)
record11["title"] //text("Dictionary basics")
record11["invalid"] //nil

//Optional<RecordType>.Type
type(of: record11["favourite"])

在上面的例子里，我们发现Dictionary和Array不同的是，[]用在Dictionary的时候，会返回一个Optional类型来确保这种形式的访问安全。因此访问不存在的key，并不会导致运行时错误。

因为索引这个概念，对于Array和Dictionary来说，是截然不同的。对于Array来说，我们有可能使用的正常索引值只源于Array自身，也就是0 ..< array.count，因此，如果你使用了不在这个范围里的值，则应是可以被定性为Bug的。而对于Dictionary来说，它包含的内容并不直接决定我们可以查询的内容。举个例子来说，英汉词典中也可能并不包含我们要查询的单词。所以，Dictionary中包含的所有键值，从语义上说，并不完全决定了它的使用者会查询的值，所以，我们也无法把这类问题明确的归因于是Bug。所以，Swfit为Dictionary的索引查询操作，提供了optional保护。要么得到正确的结果，要么通过nil表示要查询的内容不存在。

常用的基本属性

作为一个集合类型，Dictionary同样有count和isEmpty两个属性读取其元素的个数以及判断其是否为空：

record11.count //4
record11.isEmpty //false

另外，我们可以单独访问一个Dictionary的所有的Keys和所有的Values

record11.keys
record11.values

如果我们要访问它们的每一个元素，直接用for循环或forEach遍历就好了：

for key in record11.keys { print( key ) }
// or 
record11.keys.forEach { print($0) }

添加、更新和删除元素

和Array一样，Dictionary也是一个值类型，当我们复制Dictionary对象的时候，就会拷贝Dictionary中的所有内容：

var record10 = record11

并且，直接使用key就可以访问和修改Dictionary的内容：

record10["favourite"] = .bool(false) // false
record11["favourite"] // true

如果我们希望更新value的时候，同时获得修改前的值，还可以使用updateValue(_:forKey:)方法：

record10.updateValue(.bool(true), forKey: "favourite") // .bool(false)

从上面的结果可以看出修改record10并不会影响record11。
当我们要在Dictionary中添加元素时，直接给要添加的key赋值就好了：

record10["watchLater"] = .bool(false)
// [
//  "favourite": RecordType.bool(false),
//  "exp": RecordType.number(100),
//  "title": RecordType.text("Directory basics"),
//  "uid": RecordType.number(11),
//  "watchLater": RecordType.bool(false)
// ]

这样，record10中的内容，就变成了5项。而当我们要删除特定的key时，直接把它的值设置为nil：

record10["watchLater"] = nil
// [
//  "favourite": RecordType.bool(false),
//  "exp": RecordType.number(100),
//  "title": RecordType.text("Directory basics"),
//  "uid": RecordType.number(11)
// ]

这里，并不是把特定的key的值设置为nil(毕竟Dictionary中的value部分的类型也不是optional)，而是删除特定的key。当某个key的value被设置为nil后，这个key也就从Dictionary中删除了。

遍历Dictionary

由于Dictionary同时包含了key和value，因此，我们也有多重方式来遍历Dictionary。最简单的，就是遍历Dictionary中的每个元素：

for (k, v) in record10 {
    print("\(k): \(v)")
}

record10.forEach { print("\($0): \($1)") }

从上面的例子可以看出，Dictionary和Array的遍历是类似的。但是，Dictionary是一个无序集合，因此当我们编辑了Dictionary之后，每次遍历，访问元素的顺序都可能是不同的，如果我们希望按照固定的顺序来访问Dictionary中的元素，一个最简单的办法，就是对key排序后，在进行遍历：

for key in record10.keys.sorted() {
    print("\(key): \(record10[key])")
}

常用的Dictionary extension

我们为上一节提供一个默认值：

enum RecordType {
    case bool(Bool)
    case number(Int)
    case text(String)
}

let defaultRecord: [String: RecordType] = [
    "uid": .number(0),
    "exp": .number(100),
    "favourite": .bool(false),
    "title": .text("")
]

这样，当创建新记录时，我们希望保持默认记录中的默认值，同时合并进不同的用户的设置，例如：

var template = defaultRecord
var record11Patch: [String: RecordType] = [
    "uid": .number(11)
    "title": .text("Common dictionary extensions")
]
// How can we do this?
// template.merge(record11Patch)
// [
//    uid: .number(11),
//    "exp": .number(100),
//    "favourite": .bool(false),
//    "title": .text("Common dictionary extensions")
// ]

merge

然而，该如何实现这个merge呢？最重要的事情，就是要想一下什么内容可以被merge进来。最一般的情况来说，无论什么形式的序列，只要它的元素中的key和value的类型和Dictionary相同，就可以进行合并

那么如何在代码中表达这个特征呢？来看下面这个例子：

extension Dictionary {
    mutating func merge<S:Sequence>(_ sequence: S) where S.Interator.Element == (key: Key, value: Value) {
        sequence.forEach {
            self[$0] = $1
        }
    }
}

由于Dictionary是一个Struct,并且merge修改了self,我们必须使用mutating关键字修饰这个方法。而对于sequence参数，我们通过where关键字限定了两个内容：

• S必须遵循Sequenceprotocol，Dictionary是众多遵从了Sequence protocol的collection类型之一，但是，我们没必要一定只能合并Dictionary；
• S的元素类型必须和原Dictionary的Element相同，其中Key和Value是Dictionary声明中的两个反省参数；

解决了参数问题之后，实现合并的算法就很简单了，我们只是更新self中每一个和sequence有相同的key的值就好了。

这样，之前template.merge(record11Patch)就可以正常工作了。
既然，我们把merge参数的约束定义为了Sequence，那我们就来看一个合并非Dictionary类型的情况，例如，合并一个包含正确内容的Array

let record10Patch: [(key: String, value: RecordType)] = [
    (key: "uid", value: .number(10)),
    (key: "title", value: .text("Common dictionary extensions")),
]

var template1 = defaultRecord
template1.merge(record10Patch)
// [
//    uid: .number(10),
//    "exp": .number(100),
//    "favourite": .bool(false),
//    "title": .text("Common dictionary extensions")
// ]

在上面的代码里我们合并了一个tuple数组，它的类型是Array<String, RecordType>，数组中的每一项都包含了一个要合并进来的键值对。如果没有意外，合并Array和Dictionary都应该是可以正常工作的。

按照我们对merge的实现方式，实际上，任何一个遵从了Sequenceprotocol类型，只要它包含了和template相同的元素类型，都是可以merge的

用一个tuple数组初始化Dictionary

理解了merge的实现和用法之后，其实，我们可以很容易的把这个场景进一步拓展下，如果我们可以merge类型兼容的Sequence,那么，用这样的Sequence来初始化一个Dictionary也是可以的，把它看成是和一个空的Dictionary进行合并就好了：

extension Dictionary {
    init<S: Sequence>(_ sequence: S) where S.interator.Element == (key: Key, value: Value) {
        self = [:]
        self.merge(sequence)
    }
}

有了这个方法之后，我们直接用下面的代码就可以创建一个新的Dictionary对象：

let record11 = Dictionary(record11Patch) 
// [
//    uid: .number(11),
//    "title": .text("Common dictionary extensions")
// ]

定制map的行为

最后要给大家介绍的常用功能，是定制Dictionary.map行为，默认情况下它返回的是一个Array,例如：

record11.map { $1 }
// [.number(11).text("...")]

在上面的例子里，map返回一个Array<RecordType>,但有时，我们仅仅希望对value做一些变换，而仍旧保持Dictionary的类型。为此，我们可以自定义一个"只map value"的方法：

extention Dictionary {
    func mapValue<T>(_ transform: (Value) -> T) -> [Key: T] {
        return Dictionary<Key,T>(map { (k, v) in 
            return (k, transform(v))
         })
    }
}

在这个实现的最内部，我们用标准库中的map得到了一个Array<(String, RecordType)>类型的Array, 而后，由于Array也遵循了Sequence protocol,因此，我们就能直接使用这个Array来定义新的Dictionary了。

代码测试一下：

let newRecord11 = record11.mapValue { record -> String in 
    switch record {
    case .text(let title):
        return title
    case .number(let exp):
        return String(exp)
    case .bool(let favourite):
        return String(favourite)
    }
}
// [
//    "uid": "11",
//    "title": "Common dictionary extensions"
// ]

为自定义类型实现Hashable Key

本质上来说，Dictionary是一个哈希表，它所有的key都用各自的哈希值保存在一个数组里。因此，通过key在Dictionary中访问value是一个O(1)操作。但这也对key的类型做出了一个要求：它必须可以计算哈希值。Swift标准库中提供的绝大多数类型，例如：Int / Float/ Double/ String/ Bool/ Date ...等，都满足这个要求，因此我们可以直接拿他们来定义Dictionary。

但如果我们有一个自定义类型Account,表示一个账号，其中的alias/type/createdAt分别表示账号的别名，类型和注册日期：

struct Account {
    case alias: String
    case type: Int
    case createdAt: Date
}

当我们把Account用作key的时候，Swift就会给我们提供下面的错误：Account没有遵从Hashableprotocol:

let account11 = Account(alias: "11", type: 1, createdAt: Date())
let data:[Account: Int] = [account11: 1000]

Conform to Hashable protocol

如何让自定义类型遵从Hashable protocol 呢？ 第一件要做的事，就是告诉swift，如何获取一个类型的哈希值，这是通过一个叫hashValue的属性完成的：

extension Account: Hashable {
    var hashValue: Int
}

如何计算Account.hashValue呢？有两个最重要的考量，分别是：性能和哈希值在整数范围的分布。因为每当我们要在Dictionary中查询、添加、修改或删除元素的时候，都要计算key的哈希值，如果这个计算过于消耗性能，那么计算哈希值的过程就有可能抵消掉通过key随机访问value带来的O(1)性能提升。
当然也不能盲目追求性能而忽略哈希值的整数值分布。说一个最极端的例子，如果你让所有情况计算得到的哈希值都是某个常数：

extension Account: Hashable {
    // A Bad idea
    var hashValue: Int { return 1 }
}

这个哈希函数有O(1)的性能，但这样，不同的Account对象就会有不同的哈希值，这叫做Collision。当然，SwiftDictionary可以处理哈希值碰撞的情况，但你要随之付出的代价就是，通过哈希值读取value将从O(1)变成一个O(n)算法。因此，让哈希值在证书区间均匀分布也是设计哈希函数很重的考虑。

综上所述，设计一个好的哈希函数并不是一个容易的事情。对于我们来说，可以假设Swift标准库的类型提供的hashValue都满足性能和分布的要求。因此，当我们设计复合类型的哈希值的时候，可以基于这些标准类型的哈希值进行一些“低功耗”运算，例如，对这些值进行异或运算，绝大多数的CPU都对这个操作提供了指令级支持：

extension Account: Hashable {
    var hashValue: Int {
        return alias.hashValue ^
                type.hashValue ^
                createdAt.hashValue
    }
}

解决了Account 的哈希值后，Swift会继而提示我们：Account没有遵从Equatableprotocol。为什么还要遵从Equatable呢？这是因为哈希函数还有一个很重要的性质：两个相等对象的哈希值必须是相同的。因此，我们必须要解决什么叫做两个相等的对象，然后才有比较它们各自哈希值的事情。

Equatable只有一个约束，就是为自定义类型实现 ==操作符：

extension Account: Equatable {
    static func == (lhs: Account, rhs: Account) -> Bool {
        return lhs.alias == rhs.alias &&
               lhs.type == rhs.type &&
               lhs.createdAt == rhs.createdAt   
    }
}

在Swift里，运算符必须要定义成static方法，它的两个参数lhs/rhs则表示==两边的操作数。我们判断Account相等的方式很简单，只要它们每一个属性相等，则两个Account对象就是相等的。

当我们让Account遵从了Equatable之后，Swift编译器就不会再报错了。此时，我们在一开始创建的data也可以正常工作了。

Bitwise rotation

我们上面例子中提到的把所有属性进行XOR运算的方法，虽然简单高效，但也有一个问题，就是比较容易造成碰撞。因为XOR运算是可交换的，也就是说a ^ b == b ^ a，因此，如果一个自定义类型中，有多个类型相同属性的时候，就会增大哈希值发生碰撞的概率，因此，我们可以用下面的代码，对其中的一些基础属性的哈希值进行按位旋转后再进行XOR运算：

struct Account {
    let INT_BIT = (Int)(CHAR_BIT) * MemoryLayout<Int>.size

    func bitwiseRotate(value: Int, bits: Int) -> Int {
        return (((value) << bits) | ((value) >> (UINT_BIT - bits)))
    }
}

extension Account: Hashable {
    var hashValue: Int {
        return bitwiseRotate(value: alias.hashValue, bits: 10) ^
            type.hashValue ^
            createdAt.hashValue
    }
}

首先，我们在Account中添加了一个常量INT_BIT表示一个整数的位数。其次，定义了一个辅助方法bitwiseRotate(value:bits:)，它用于先把value向左移动bits位，再向右移动(UINT_BIT - bits)位。

有了这个方法之后，我们就可以在计算哈希值的时候，对其中的属性进行按位旋转了。

警惕引用类型的Key

和Dictionary.Key相关的最后一个内容，是尽可能的避免使用引用类型作为key，这通常会给你带来不必要的麻烦。当一个引用类型作为key之后，当引用类型的对象在Dictionary之外被修改的时候，Key的内容也会随之修改。这样你就再也无法获得之前的哈希值，也就无法获得对应的value了。