字典和集合

本章对python中字典和集合的内容做一些拾遗，主要内容来自流畅的python第三章。
建议通过Jupyter Notebook来试验本文代码，关于Jupyter Notebook使用可以阅读这里, 本文代码已经放在这里。

本章内容适合对python有一定了解的读者。
通过本章你可以了解到：

字典和集合的基本使用
如何处理字典中不存在的键
字典和集合为何比列表高效
一些简单字典变种的介绍

映射

我们知道，字典的本质是键（key）和值（value）的映射，在python中，除了字典之前还有一些其他的特殊映射类型，但是它们都是基于collections.abc.Mapping的。

可散列

需要注意的是，这些映射类型对key是有要求的，即只有可散列的数据类型才能用作映射的键值。那么什么是可散列的数据类型呢：

从定义上来说，任何实现了__hash__()和__qe__()的对象都是可散列的，前者将key值映射到另一个空间，后者则用来比较两个键值是否相同。
具体而言，所有原子不可变的数据类型都是可散列的（str，bytes和数值），frozenset也可散列。
元组（tuple）有些特殊，当且仅当元祖内所有元素都可散列时，它才是可散列的。
列表（list）是不可散列的。

下面我们通过两个元组的例子来说明一下：

1 2	hash((1,2,3)) # 这里我们成功求得了元祖(1,2,3)的hash值

2528502973977326415

1 2	hash((1,2,[3])) # 这里由于元组中包含了不可散列的列表元素[3],因此无法求其hash

---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

<ipython-input-2-f5fc4ae74995> in <module>()
----> 1 hash((1,2,[3]))
      2 # 这里由于元组中包含了不可散列的列表元素[3],因此无法求其hash


TypeError: unhashable type: 'list'

消失的键

映射类型(除了dict，常用的映射类型还有defaultdict和OrderedDict)的方法很丰富，大部分都较为常用，下面介绍一个较为冷门但很有用的方法setdefault。
这个方法可以用来处理找不到的键值。对于一个字典d及其键k，我们通常用d[k]来获取值，但是如果字典中不包含该键时会报KeyError，当然我们可以通过d.get(k, default)来给找不到的键指定默认值。
不过setdefault往往会更方便，相比d.get(k, default)，它加了一个当d中不含k时设定d[k]=default的动作。

举一个例子，下面三种写法是等价的：

key = 'foo'
new_value = 'bar'
my_dict = {}

# plain
if key not in my_dict:
    my_dict[key] = []
my_dict[key].append(new_value)

# get
values = my_dict.get(key, [])
values.append(new_value)
my_dict[key] = values

# setdefault  
my_dict.setdefault(key, []).append(new_value)

当然，另一种常用的方法是使用defaultdict类，或是自己定义一个dict的子类并实现__missing__方法，前一种方法简单查一下defaultdict的用法就行，不再赘述，主要来谈谈__missing__的实现。
所有映射类型在处理找不到的键时，都会用到这个方法，具体地说，当该类执行__getitem__时找不到该键，就会自动调用__missing__方法，需要注意的是默认来说，get和__contains__并不会使用__missing__。

例子下面举一个例子，我们现在有一个字典文件，其中的key都是一些数字，但是可惜的是这些key有的是以int存在的，有的则是以字符串存在的。我们的需要保证，对这个字典执行查找时，数字key的形式不会造成差异，即123和"123"作为查询的键值应该是等价的。

d = dict([('123', 'Yes'), (234, 'No')])
print(d['123'])
print(d[123])
# 可以发现查询123时出现了KeyError

Yes



---------------------------------------------------------------------------

KeyError                                  Traceback (most recent call last)

<ipython-input-4-80e778fd0b83> in <module>()
      1 d = dict([('123', 'Yes'), (234, 'No')])
      2 print(d['123'])
----> 3 print(d[123])
      4 # 可以发现查询123时出现了KeyError


KeyError: 123

# 下面我们自己定义一个dict，重新实现__missing__方法来满足上面的需求

class mydict(dict):
    
    def __missing__(self, key):
        # 如果出现missing，则试试看其key的另一种形式
        if isinstance(key, str):
            return self[int(key)]
        if isinstance(key, int):
            return self[str(key)]
        
d = mydict([('123', 'Yes'), (234, 'No')])
print(d['123'])
print(d[123])  
print(d[234])
print(d['234'])

Yes
Yes
No
No

字典变种

除了defaultdict之外，collections包中还提供了一些其他的常用字典的变种。

OrderedDict 该类型在添加键时会保持顺序，因此键之间的顺序是固定的。
ChainMap 该类型可以容纳数个不同的映射对象并将其合并为一个映射对象
Counter 这个类型给键值对应了一个整数计数器

不可变映射

有时我们有这样的需求，即设置映射为只读使其不可更改。例如对于一条学生数据，其名字key为name，不可更改。
此时我们可以用types模块中的MappingProxyType来完成这个需求。通过该类来构造原映射A，则会返回一个只读的映射视图，该视图是不可更改的，但是任何对原映射A的更改也会反映到这个映射视图上。
举例来说：

from types import MappingProxyType 
std = {'name': 'John'} # 原映射  
std_proxy = MappingProxyType(std) # 只读的映射视图   
# 打印发现和原映射一致
print('映射视图：', std_proxy)

映射视图： {'name': 'John'}

1 2	#下面我们试图来修改这个映射视图，会发现报错 std_proxy['grade'] = 100

---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

<ipython-input-7-b70293becf62> in <module>()
      1 #下面我们试图来修改这个映射视图，会发现报错
----> 2 std_proxy['grade'] = 100


TypeError: 'mappingproxy' object does not support item assignment

# 然后我们修改原映射   
std['grade'] = 100
print('可以看到映射视图也随之改变：', std_proxy)
print('grade', std_proxy['grade'])

可以看到映射视图也随之改变： {'name': 'John', 'grade': 100}
grade 100

集合

集合本质上许多唯一元素的无序聚集，当然数学意义上的很多集合运算python也都用相应实现。

a | b 返回两个集合的并集
a & b 返回两个集合的交集
a - b 返回两个集合的差集
i in a 元素i是否在集合a中
b <= a 集合b是否为a的子集
b < a 集合b是否为a的真子集

除了以上二元中缀运算，还有一些其他常见方法：

a.add(i) 添加元素i
a.clear() 清除所有元素
a.copy() 对a进行浅复制
a.discard(i) 如果a中有i这个元素的话，就将它移除
a.pop() 返回a中的一个元素并将其从集合中移除，若a为空，则抛出异常
a.remove(i) 从a中移除i，若不含该元素，抛出异常

set和dict背后

掌握了基本的使用时候，我们对set和dict背后的知识再做一些探索。

首先实验不难发现，相对于list来说，set和dict是非常高效的。究其原因，以在这些对象中寻找元素为例，set和dict用的都是哈希算法也就是散列表算法来查找（关于哈希算法可以看维基百科的介绍），此时复杂度为哈希函数复杂度+冲突处理复杂度，一般是一个很小的函数，而list的复杂度则是线性的。
当然，这样的处理有优势也有限制：