字典（Dictionary）与数组是程序设计语言的两个台柱子，这两种数据结构不但以自己的形象高频出镜，而且我们可以利用他们模拟出更多的数据结构，例如栈、链表、堆、以及各种队列等等。
1、什么是字典
我们在生活当中不可避免的要使用 key : value 这种键值对的方式来描述信息，比方说我们的成绩单，用科目名称作为key，成绩作为value。
成绩单
-------------------
“语文” ： 60
“数学” ： 61
“英语” ： 60
这种需求是如此的频繁出现，所以编程语言责无旁贷的需要为我们提供一种数据结构来描述这种信息，这种数据结构就是字典（Dictionary）。
2、字典与数组的区别
数组是通过下标（索引号）来访问数组元素的，但数组的下标只是一个连续递增的数字，因为数字无法表达逻辑上的意义，因此这就显示了数组的一个缺陷：数组不擅长处理数据查询。比方说我们创建一个数组。
var array = ["a","b","c","d"]
如果我们想判断“f“是否在数组array中，那我们就不得逐一遍历数组的每一个元素才能知道（也就是说时间复杂度是o(n)）。字典也使用下标（key）来访问数据，与数组下标的区别是，字典的下标可以表达出逻辑意义，比方说,我们如果在字典中查找语文成绩，那么字典完全有能力在不遍历所有元素的情况下给出答案（时间复杂度为o(1)）。这就是字典与数组之间的重要区别。
3、在swift中创建字典
在swift中，字典也是通过struct来来定义的，所以我们可以这样来创建一个字典。
var dict = Dictionary<String,Int>()
也许这是字典最庄重的创建方式了吧，我们其实可以简单一点。
var dict = [String:Int]()
或者干脆，我们直接这样
var dict = ["语文":60,"数学":61,"英语":60]
这种方法比前两中方法更简洁，并且利用了类型推断机制，让编译器判定dict的类型。那么编译器是如何判定dict的类型的呢？和数组的类型一样，字典的类型也是由元素的类型所决定的，但字典元素的类型比数组的类型复杂，我们可以看到元素 "语文":60 其实是由两种类型构成 String：Int，所以dict的类型被判定为 [String:Int] 类型 。我们也可以用显示声明类型的方式定义字典。
var dict: [String:Int] = ["语文":60,"数学":61,"英语":60]
4、字典的实现原理
字典是在数组的基础之上构建起来的，在每个字典中都包含着一个数组。数组元素的定义顺序与存储循序是一致的。比方说我们创建一个数组。
var array = ["a","b","c","d"]
array元素的定义顺序为["a","b","c","d"]，那么array的存储顺序也一定为["a","b","c","d"]。但如果我们创建一个字典。
var dict: [String:Int] = ["语文":60,"数学":61,"英语":60]
字典元素的定义顺序是["语文":60,"数学":61,"英语":60]，那么字典元素的存储顺序和定义顺序是一致的吗？答案是： 不一定。原因是字典使用了一种散列机制。
在字典在存储元素 "语文":60 之前，字典首先对元素的key “语文” 进行一次hash运算，hash运算的目的是将key转换为一个Int类型的整数，比方说3，这个3就是元素将要在数组中的存放位置。同理，字典会对每一个将要存放的元素都会进行hash运算，以确定该元素的存放位置。字典正是凭借这种散列机制，获得了高效访问数据元素的能力。
5、字典的管理
字典的管理功能，都是围绕着字典元素的key展开的。理论上hash运算要达到两个目的，首先是不同的key经过hash运算后，会得到不同散列值（元素的存放位置）；其次相同的key经过相同的hash运算会得到相同的散列值。
* 字典元素的访问
var dict: [String:Int] = ["语文":60,"数学":61,"英语":60]
dict["语文"] // 60
我们使用元素的key来实现对字典元素的访问。当使用“语文”作为下标，进行成绩的查询时，字典首先会对“语文”进行hash运算，这样我们会再次得到散列值3，也就是元素 "语文":60 的存储位置。之后字典会用“语文”这个key，与3位置对应元素的key进行比较，如果确实相同，那么就会返回60。这样字典就实现了用o(1)的时间复杂度查找元素。如果我们访问的元素不存在，比方说我们插叙了“体育”成绩，swift字典的处理方式可以看另外一篇内容swift的Optional类型
* 字典元素修改与新增
dict["语文"] = 70
修改字典元素的value与对变量赋值操作并没有什么区别。除了修改之外，我们可以给字典新增元素，比方说我们现在新增一门体育成绩。
dict["体育"] = 60
这个新增操作确实令我们感觉有一点奇怪，字典并没有像数组那样提供一个append方法来新增元素，而是用了一种和修改操作同样的方式来新增元素，那么字典是如何判定一个操作是新增还是修改呢？当我们使用key来访问字典元素，并用=号进行赋值操作的时候，字典首先对key进行hash运算，如果得到的散列值对应的存储位置没有被其他元素占用，那么字典会将当前操作判定为新增操作。
如果得到散列值对应的存储位置上已经有元素了，那么字典会进一步判断当前的key与对应位置元素的key是否是相等的，如果是相等的，那么则判定为修改操作。新增与修改的融合，新增也是一种修改，修改也是一种新增。
* 什么是hash冲突
理论上，不同的key经过hash运算后会得到不同的散列值，但是hash算法总是会有自己的局限性，实际上不同的key经过相同hash运算后很有可能会产生相同的散列值，我们把这种现象称为hash冲突。正是因为hash冲突时无法避免的，所以，所有的字典都会提供对应的解决方案。通常的方案是，字典使用链表，将冲突的元素保存在同一个散列值指定的位置。当发生hash冲突的时候，字典的访问效率会降低，因为一但在一个存储位置产生冲突，那么字典就不得不在这个位置逐个访问每一个元素，才能确定哪一个才是真正要查询的元素。如果用一个极端的例子，如果字典中只有一个存储位置，那么所有的字典元素将会以链表的形式存储在这个唯一的位置上，从而使字典退化成为一个数组。
* 字典管理方法小结
如果我们需要删除一个字典元素，我们可以这样做
var dict: [String:Int] = ["语文":60,"数学":61,"英语":60]
dict.removeValueForKey("语文") // 语文key对应的元素被从字典中删除
当然，我们可以使用更简单的方法
dict["语文"] // 和removeValueForKey方法产生相同的效果
我们可以统计字典元素中的个数，以及判断一个字典是否为空
dict.count // 统计当前字典中元素的个数
dict.isEmpty // 判断字典是否为空
我们还可以把字典中的 key与value分别转换为数组
var keyArray = [String](dict.keys)
var valueArray = [Int](dict.values)
对于初学者来说，字典的操作方法并不值得我们去特意记忆，我们只需要有个印象，并在需要的时候查阅文档就可以了。
网友评论