购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

2.2 字典

Swift中另一个关键的数据结构是Dictionary——字典。字典包含键以及它们所对应的值。在一个字典中,每个键只能出现一次。通过键来获取值所花费的平均时间是常数量级的(作为对比,在数组中搜寻一个特定元素所花的时间将与数组尺寸成正比)。和数组有所不同,字典是无序的,使用for循环来枚举字典中的键值对时,顺序是不确定的。

在下面的例子中,我们虚构一个App的设置界面,并使用字典作为模型数据层。这个界面由一系列的设置项构成,每一个设置项都有自己的名字(也就是我们字典中的键)和值。值可以是文本、数字或者布尔值之中的一种。我们使用一个带有关联值的enum来表示:

enum Setting{

case text(String)

case int(Int)

case bool(Bool)

}

let defaultSettings:[String:Setting]=[

"Airplane Mode":.bool(true),

"Name":.text("My iPhone"),

]

defaultSettings["Name"]//Optional(Setting.text("My iPhone"))

我们使用下标的方式可以得到某个设置的值(比如defaultSettings["Name"])。字典查找将返回的是 可选值 ,当特定键不存在时,下标查询返回nil。这一点和数组有所不同,在数组中,使用越界下标进行访问将会导致程序崩溃。

从理论上来说,产生这个区别的原因是数组索引和字典的键的使用方式有很大的不同。我们已经讨论过,对数组来说,我们很少需要直接使用数组的索引。即使用到索引,这个索引也一般是通过某些方式由数组属性计算得来的(比如从0..<array.count这样的范围内获取到)。也就是说,使用一个无效索引一般都是程序员的失误。而另一方面,字典的键往往是从其他渠道得来的,从字典本身获取键反而十分少见。

与数组不同,字典是一种稀疏结构。即使在name键下存在某个值,你也还是无法确定address键下是否有值。

可变性

和数组一样,使用let定义的字典是不可变的:你不能向其中添加、删除或者修改条目。如果想要定义一个可变的字典,那么你需要使用var进行声明。如果想要将某个值从字典中移除,那么可以用下标将对应的值设为nil,或者调用removeValue(forKey:)。后一种方法除会删除这个键外,还会将被删除的值返回(如果待删除的键不存在,则返回nil)。对于一个不可变的字典,想要进行改变的话,则首先需要进行复制:

var localizedSettings=defaultSettings

localizedSettings["Name"]="Mein iPhone"

localizedSettings["Do Not Disturb"]=true

再次注意,defaultSettings的值并没有改变。和键的移除类似,除下标外,还有一种方法可以更新字典内容,那就是updateValue(_:forKey:),这个方法将在更新之前有值的时候返回这个更新前的值:

let oldName=localizedSettings

.updateValue(.text("Il mio iPhone"),forKey:"Name")

localizedSettings["Name"]//Optional(Setting.text("Il mio iPhone"))

oldName//Optional(Setting.text("Mein iPhone"))

有用的字典扩展

如果想要将一个默认的设置字典和某个用户更改过的自定义设置字典合并,应该怎么做呢?自定义的设置应该要覆盖默认设置,同时得到的字典中应当依然含有那些没有被自定义的键值。换句话说,我们需要合并两个字典,用来做合并的字典需要覆盖重复的键。标准库中并没有这样的函数,不过我们可以自己写一个。

扩展Dictionary类型,为它添加一个merge方法,该方法接受待合并的字典作为参数。可以将这个参数指明为Dictionary类型,不过更好的选择是用更加通用的泛型方法来实现。对参数的要求是,它必须是一个序列,这样我们就可以对其进行循环枚举。另外,序列的元素必须是键值对,而且它必须和接受方法调用的字典的键值对拥有相同类型。对于任意的Sequence,如果它的Iterator.Element是(Key,Value),那么它就满足我们的要求,因此我们将其作为泛型的约束(这里的Key和Value是我们所扩展的Dictionary中已经定义的泛型类型参数):

extension Dictionary{

mutating func merge<S>(_other:S)

where S:Sequence,S.Iterator.Element==(key:Key,value:Value){

for(k,v)in other{

self[k]=v

}

}

}

正如下例所示,我们可以将一个字典合并进另一个字典了。另外,方法的参数还可以是键值对数组或者其他类似的任意序列,而不一定必须是字典:

var settings=defaultSettings

let overriddenSettings:[String:Setting]=["Name":.text("Jane's iPhone")]

settings.merge(overriddenSettings)

settings

//["Name":Setting.text("Jane\'s iPhone"),"Airplane Mode":Setting.bool(true)]

另一个有意思的扩展是从一个(Key,Value)键值对的序列来创建字典。标准库中为数组提供了一个类似的初始化方法,我们也经常用到它。每次将一个范围转变为数组时(Array (1...10)),或者是将一个ArraySlice转换回数组时(Array(someSlice)),都用到了从序列创建数组的方法。但是,对于Dictionary,还没有这样的初始化方法。(在Swift-Evolution的提案中,有人提议添加 [4] 这样的方法,所以我们有可能在未来能见到这样的初始化方法。)

我们可以先创建一个空字典,然后将序列合并到字典中。这样一来,就可以重用上面的

merge方法,让它来做实际的工作:

extension Dictionary{

init<S:Sequence>(_sequence:S)

where S.Iterator.Element==(key:Key,value:Value){

self=[:]

self.merge(sequence)

}

}

//所有alert默认都是关闭的

let defaultAlarms=(1..<5).map{(key:"Alarm\($0)",value:false)}

let alarmsDictionary=Dictionary(defaultAlarms)

下面要添加的第三个有用扩展是一个map函数,它可以用来操作并转换字典中的值。因为Dictionary已经是一个Sequence类型,它已经有一个map函数来产生数组。不过我们有时候想要的是结果保持字典的结构,只对其中的值进行映射。我们的mapValues方法将首先调用标准的map,来创建一个 (键,转换后的值) 的数组。接下来,使用上面定义的初始化方法将其转换回字典:

extension Dictionary{

func mapValues<NewValue>(transform:(Value)->NewValue)

->[Key:NewValue]{

return Dictionary<Key,NewValue>(map{(key,value)in

return(key,transform(value))

})

}

}

let settingsAsStrings=settings.mapValues{setting->String in

switch setting{

case.text(let text):return text

case.int(let number):return String(number)

case.bool(let value):return String(value)

}

}

settingsAsStrings//["Name":"Jane\'s iPhone","Airplane Mode":"true"]

Hashable要求

字典其实是哈希表 [5] 。字典通过键的hashValue来为每个键指定一个位置,以及它所对应的存储。这也就是Dictionary要求它的Key类型需要遵守Hashable协议的原因。标准库中所有的基本数据类型都是遵守Hashable协议的,它们包括字符串、整数、浮点数以及布尔值。不带有关联值的枚举类型也会自动遵守Hashable。

如果想要将自定义的类型用作字典的键,那么必须手动为类型添加Hashable并满足它,这需要你实现hashValue属性。另外,因为Hashable本身是对Equatable的扩展,因此还需要为你的类型重载==运算符。你的实现必须保证哈希不变原则:两个同样的实例(由你实现的==定义相同),必须拥有同样的哈希值。不过反过来不必为真:两个相同哈希值的实例不一定需要相等。不同的哈希值的数量是有限的,然而很多可以被哈希的类型(比如字符串)的个数是无穷的。

哈希值可能重复这一特性,意味着Dictionary必须能够处理哈希碰撞。不必说,优秀的哈希算法总是能给出较少的碰撞,这将保持集合的性能特性。在理想状态下,我们希望得到的哈希值在整个整数范围内平均分布。在极端的例子下,如果你的实现对所有实例返回相同的哈希值(比如0),那么这个字典的查找性能将下降到 O ( n )。

优秀哈希算法的第二个特性是它应该很快。记住,在字典中进行插入、移除或者查找时,这些哈希值都要被计算。如果你的hashValue实现要消耗太多时间,那么它很可能会拖慢程序,

让你从字典的 O (1)特性中得到的好处损失殆尽。

写一个能同时做到这些要求的哈希算法并不容易。对一些由本身就是Hashable的数据类型组成的类型来说,将成员的哈希值进行“异或”(XOR)运算往往是一个不错的起点:

struct Person{

var name:String

var zipCode:Int

var birthday:Date

}

extension Person:Equatable{

static func==(lhs:Person,rhs:Person)->Bool{

return lhs.name==rhs.name

&&lhs.zipCode==rhs.zipCode

&&lhs.birthday==rhs.birthday

}

}

extension Person:Hashable{

var hashValue:Int{

return name.hashValue^zipCode.hashValue^birthday.hashValue

}

}

异或计算方法的一个限制是,这个操作本身是左右对称的(也就是说a^b==b^a),这对于某些数据的哈希计算,有时候会造成不必要的碰撞。可以添加一个位旋转 [6] 并混合使用它们来避免这个问题。

最后,当你使用不具有值语义的类型(比如可变的对象)作为字典的键时,需要特别小心。如果你在将一个对象用作字典键后,改变了它的内容,则它的哈希值和/或相等特性往往也会发生改变。这时候你将无法再在字典中找到它。这时字典会在错误的位置存储对象,这将导致字典内部存储的错误。对值类型来说,因为字典中的键不会和复制的值共用存储,因此它也不会被从外部改变,所以不存在这个的问题。 wT+WzGIg55V5FNwRV4GOBlTxMDc4WLj4rS4MVen7QtaxqWk58z9Iq9HpUaClI0qH

点击中间区域
呼出菜单
上一章
目录
下一章
×