Python3的dict类型

假设我们需要用一个数据结构来存储 3 万个汉字，如果我们使用 list 或 tuple 来存储，当我们查找某个汉字时，
就需要从第一个成员开始一直找，直到我们能找到，或者到最后一个成员没有找到为止。

dict 就是字典，其实现原理和我们使用的字典是一样的，假设我们使用 dict 来存储 3
万个汉字，我们只需要在字典的索引表里查这个汉字对应的位置，就可以找到这个字，无论找哪个字，我们都可以一次性定位到该字，也就是时间复杂度为 o(1)。
我们使用 dict 数据结构来存储汉字，查找速度不会随着汉字内容的多少而变化。

对于我们前面学过的 str 类型，list 类型和 tuple 类型都可以通过下标访问里面的成员，
而 Python 的 dict 是无序的集合（无法通过下标访问），但我们可以通过 dict 的键（key）来访问，key 就类似于有序集合的下标。

dict 的定义

dict 是 Python 内置的数据类型，在其它语言中一般属于非内置类型，是由第三方库或者程序员本身写的库，
比如 c++ 中的 stl 库中的 map 和 Python 的 dict 类似，但实现方式不一样（c++ 的 map 用的是红黑树，Python
用的是哈希表），Python 语言用 {} 来表示是一个 dict，每个成员是一个键-值（key-value）配对。

student_dict = {'a': 1, 'b': 2, 'c': 3}  # 内存中顺序为 {'a': 1, 'c': 3, 'b': 2}
print(student_dict)  #（注意：在 Python3.8 中， print 是按照用户创建 dict 的顺序输出，而不是内存顺序输出）

dict 成员在内存中的顺序和定义时候的顺序不一定一样，这是由创建哈希表的算法（大家可自行搜索哈希表算法）
决定的，哈希表的算法决定键的存放位置。

mydict = {'a': 1, 'b': 2, 'c': 3}
print(mydict['b'])
print(mydict.get('b'))
print(mydict['d'])      # 报异常
print(mydict.get('d'))  # 返回 None

dict 的增删改查

我们知道 dict 是无序的，所以无法通过下标访问值，但我们可以通过 key 来访问该 key 对应的值，
访问方式为 dict[key]，但要确保 key 存在，不然会报异常；我们也可以使用 dict 的 get 函数获取 key
对应的值，如果 key 不存在，则返回 None。

mydict = {'a': 1, 'b': 2, 'c': 3}
mydict['d'] = 4
mydict['b'] = 5
print(mydict)

我们如果想给字典添加一个值，可以直接通过 dict[key] = value 的方式，如果 key
已经存在的话，则是修改。

mydict = {'a': 1, 'b': 2, 'c': 3}
del mydict['b']
print(mydict)
mydict.pop('a')
print(mydict)

因为 dict 的每个成员都是键值配对，所以删除成员的时候，通过键删除值，整个成员就会删除掉，
可以使用 Python 内置函数 del 或 dict 成员函数 pop 做删除操作，注意要确保删除的键存在，不然会报异常。

mydict = {'a': 1, 'b': 2, 'c': 3}

allkeys = mydict.keys()
print(allkeys)
print(type(allkeys))
for key in allkeys:
    print(key)

获取 dict 键，值，成员的函数

dict 的 keys 函数获取 dict 所有成员的键放在一个 dict_keys 类型的对象中，这个对象是一个可遍历的集合，我们可以通过遍历这个对象，获取每一个键。

mydict = {'a': 1, 'b': 2, 'c': 3}

allvalues = mydict.values()
print(allvalues)
print(type(allvalues))
for value in allvalues:
    print(value)

dict 的 values 函数获取 dict 所有值放在一个 dict_values 类型的对象中，这个对象是一个可遍历的集合，我们可以通过遍历这个对象，获取每一个值。

mydict = {'a': 1, 'b': 2, 'c': 3}

allitems = mydict.items()
print(allitems)
print(type(allitems))
for item in allitems:
    print(item)

dict 的 items 函数获取 dict 所有的成员放在一个 dict_items 类型的对象中，这个对象是一个可遍历的集合，我们可以通过遍历这个对象，获取每一个成员。

mydict = {'a': 1, 'b': 2, 'c': 3}

allitems = mydict.items()
print(allitems)
print(type(allitems))
for item in allitems:
    print(item)

注意：在 Python 2 中，dict 还提供了 iter 系列函数（iter_keys 函数，iter_values 函数，iter_items
函数）来获取 dict 的键，值和成员，并把他们放入迭代器中；而 Python2 的 keys 函数，values 函数和 items 函数则把取出的值放在一个 list 中。

使用 dict 注意事项

dict 的键就如有序集合的索引一样，dict 成员的键是不可以修改的。

dict 成员的键就像索引一样是不可以重复的。

mydict = {'a': 1, 'b': 2, 'c': 3}
mydict['b'] = 4  # 只会修改键所对应的值
print(mydict)

因为 Python 的 dict 数据结构是采用 hash 算法构建的，hash 算法决定 key 的位置，
所以 dict 成员的键是必须可以 hash 的，所有的常量都是可 hash 的，比如数字，字符串，bool值，None 等等，
对于 tuple 来说，如果 tuple 的成员也都是可 hash 的则可以，否则不行。

mydict = {}                         # 空的 dict
mydict[-1.1] = "Hello"              # 数字
mydict["babye"] = "babye"           # 字符串
mydict[False] = "welcome"           # bool 值
mydict[None] = "Python"
mydict[(1, (2, 3))] = "老鸟python"  # 可哈希的 tuple
mydict[[1, 2]] = "my god"           # [1, 2] 不可 hash
mydict[{'a': 1}] = "my god"         # {'a': 1} 不可 hash
mydict[(1, (2, [3,4]))]             # (1, (2, [3,4]) 不可 hash

对 dict 成员的 key 进行增加，删除操作时，dict 的 hash 表的结构就会改变，
成员的存储顺序就会发生变化，在遍历的时候就会出现混乱，因为已经遍历过的成员有可能再次被遍历等等（在循环章节我们再讲这个问题）。

本节重要知识点

dict 内部存储的数据结构。

熟练使用 dict 增删改查。

熟练使用获取 key，value 和 成员的函数。