流畅的 Python 第 2 版（3）：字典和集合

dict 类型是实现 Python 的基石。一些 Python 核心结构在内存中以字典的形式存在，比如说类和实例属性、模块命名空间，以及函数的关键字参数等。由于字典的关键作用，Python 对字典做了高度优化，而且一直在改进。Python 字典能如此高效，要归功于哈希表。除了字典之外，内置类型中 set 和 frozenset 也基于哈希表。

字典的现代语法

字典推导式从任何可迭代对象中获取键值对，构建 dict 实例：

>>> l = [(1, "A"), (2, "B"), (3, "C")]

>>> d = {k: v for k, v in l}
>>> d
{1: 'A', 2: 'B', 3: 'C'}
>>> type(d)
<class 'dict'>

>>> d = {k: v.lower() for k, v in l if k < 2}
>>> d
{1: 'a'}

对于映射拆包，首先，调用函数时，不止一个参数可以使用**。但是，所有键都要是字符串，而且在所有参数中是唯一的（因为关键字参数不可重复）​。

>>> def dump(**kwargs):
...     return kwargs
...
>>> dump(**{'x': 1}, y=2, **{'z': 3})
{'x': 1, 'y': 2, 'z': 3}

>>> a = {"a":1}
>>> dump(**a)
{'a': 1}

其次，** 可在 dict 字面量中使用，同样可以多次使用，这种情况下允许键重复，后面的键覆盖前面的键。

>>> {"a":1, **{'x':1}, 'y':2, **{'z':3, 'x':4}}
{'a': 1, 'x': 4, 'y': 2, 'z': 3}

这种句法也可用于合并映射，但是合并映射还有其他方式。Python 3.9 支持使用 | 和 |= 合并映射。这不难理解，因为二者也是并集运算符。

>>> a = {"x":1}
>>> b = {"y":2}
>>> a | b
{'x': 1, 'y': 2}
>>> a |= b
>>> a
{'x': 1, 'y': 2}
>>> b
{'y': 2}

使用模式匹配处理映射

match/case语句的匹配对象可以是映射。映射的模式看似 dict 字面量，其实能够匹配 collections.abc.Mapping 的任何具体子类或虚拟子类。上篇文章讲了序列模式，其实不同类型的模式可以组合和嵌套。模式匹配是一种强大的工具，借助析构可以处理嵌套的映射和序列等结构化记录。

def get_creators(record: dict) -> list:
    match record:
        case {'type': 'book', 'api': 2, 'authors': [*names]}:
            return names
        case {'type': 'book', 'api': 1, 'author': name}:
            return [name]
        case {'type': 'book'}:
            raise ValueError(f"Invalid 'book' record: {record!r}")
        case {'type': 'movie', 'director': name}:
            return [name]
        case _:
            raise ValueError(f'Invalid record: {record!r}')

>>> get_creators({'type': 'book', 'api': 2, 'authors': ["A", "B", "C"]})
['A', 'B', 'C']
>>> get_creators({'type': 'book', 'api': 1, 'author': 'D'})
['D']
>>> get_creators({'type': 'movie', 'director': "E"})
['E']
>>> get_creators({'extra:': "test", 'type': 'book', 'api': 2, 'authors': ["A", "B", "C"]})
['A', 'B', 'C']

>>> t = OrderedDict(api=2, type='book', authors=["A"])
>>> get_creators(t)
['A']

• 可以看到模式中键的顺序无关紧要。而且即使 t 是一个OrderedDict，也能作为匹配对象。与序列模式不同，就算只有部分匹配，映射模式也算成功匹配。

• 没有必要使用 **extra 匹配多出的键值对，倘若你想把多出的键值对捕获到一个 dict 中，可以在一个变量前面加上**，不过必须放在模式最后。**_ 是无效的，纯属画蛇添足。

• 对于 defaultdict 等映射，通过 __getitem__ 查找键（即d[key]​）始终成功。这是因为倘若缺失某一项，则自动创建。但是对模式匹配而言，仅当匹配对象在运行 match 语句之前已经含有所需的键才能成功匹配。模式匹配不自动处理缺失的键

映射类型的标准 API

collections.abc 模块中的抽象基类 Mapping 和 MutableMapping 描述 dict 和类似类型的接口。这两个抽象基类的主要作用是确立映射对象的标准接口，并在需要广义上的映射对象时为 isinstance 提供测试标准。

>>> from collections import abc
>>> mydict = {}
>>> isinstance(mydict, abc.Mapping)
True
>>> isinstance(mydict, abc.MutableMapping)
True

使用 isinstance 测试是否满足抽象基类的接口要求，往往比检查一个函数的参数是不是具体的 dict 类型要好，因为除了 dict 之外还有其他映射类型可用。如果想自定义映射类型，扩展 collections.UserDict 或通过组合模式包装 dict 更简单，那就不要定义这些抽象基类的子类。collections.UserDict 类和标准库中的所有具体映射类都在实现中封装了基本的 dict，而 dict 又建立在哈希表之上。因此，这些类有一个共同的限制，即键必须可哈希（值不要求可哈希，只有键需要）。

如果一个对象的哈希码在整个生命周期内永不改变（依托 __hash__() 方法）​，而且可与其他对象比较（依托__eq__() 方法）​，那么这个对象就是可哈希的。两个可哈希对象仅当哈希码相同时相等。

• 数值类型以及不可变的扁平类型 str 和 bytes 均是可哈希的
• 如果容器类型是不可变的，而且所含的对象全是可哈希的，那么容器类型自身也是可哈希的
• frozenset 对象全部是可哈希的，因为按照定义，每一个元素都必须是可哈希的
• 仅当所有项均可哈希，tuple 对象才是可哈希的

>>> tt = (1, 2, (3))
>>> hash(tt)
529344067295497451
>>> tl = (1, 2, [3])
>>> hash(tl)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

• 默认情况下，用户定义的类型是可哈希的，因为自定义类型的哈希码取自 id()，而且继承自 object 类的 __eq__() 方法只不过是比较对象 ID
• 对于自己实现了 __eq__() 和 __hash__() 方法的类型，为了让自定义类型对象是可哈希的，一般要求 __eq__() 和 __hash__() 只使用在对象的生命周期内始终不变的实例属性

>>> class A():
...     def __hash__(self):
...             return 100
...

>>> t1 = A()
>>> t2 = A()
>>> tc = {t1: 1, t2: 2}
>>> tc[t1]
1
>>> tc[t2]
2

根据 Python 的 快速失败 原则，当键 k 不存在时，d[k] 抛出错误。深谙 Python 的人知道，如果觉得默认值比抛出 KeyError 更好，那么可以把 d[k] 换成 d.get(k, default)。但有时候 d.get(k, default 并不是最佳语法，对于如下代码，换成 dict.setdefault 则只需一行代码，而且效率更高：

# k 不存在，总过执行了 3 次搜索
if k not in d:
    d[k] = []
d[k].append(v)

l = d.get(k, [])
l.append(v)
# 额外进行一次搜索
d[k] = l

d.setdefault(k, []).append(v)

• setdefault 获取 k 对应的值，如果不存在则设置为 [] 并返回，这样就可以直接更新，不用额外执行一次搜索

自动处理缺失的键

有时搜索的键不一定存在，为了以防万一，可以人为设置一个值，以方便某些情况的处理。人为设置的值主要有两种方法：

• 把普通的 dict 换成 defaultdict
• 定义 dict 或其他映射类型的子类，实现 missing 方法

对于 collections.defaultdict，d[k] 句法找不到搜索的键时，使用指定的默认值创建对应的项。实例化 defaultdict 对象时需要提供一个可调用对象，当 __getitem__ 遇到不存在的键时，调用那个可调用对象生成一个默认值，生成默认值的可调用对象 存放在实例属性 default_factory 中。如未提供 default_factory，遇到缺失的键时，则像往常一样抛出 KeyError。

d = defaultdict(list)
d[k].append(v)

defaultdict 的 default_factory 仅为 __getitem__ 提供默认值，其他方法用不到，例如 d.get(k) 或者 k in d。

defaultdict 之所以调用 default_factory，背后的机制是接下来要讨论的特殊方法 __missing__。

__missing__ 方法

映射处理缺失键的底层逻辑在 __missing__ 方法中。dict 基类本身没有定义这个方法，但是如果 dict 的子类定义了这个方法，那么 dict.__getitem__ 找不到键时将调用 __missing__ 方法，不抛出 KeyError。

在自己定义的子类中实现 __getitem__、get 和 __contains__ 方法时，可以根据实际需求决定是否使用 __missing__ 方法。需要指出，继承标准库中的映射时要小心谨慎，不同的基类对 __missing__ 的使用方式不一样。

dict 的变体

自 Python3.6 起，内置的 dict 也保留键的顺序。使用 OrderedDict 最主要的原因是编写与早期 Python 版本兼容的代码。当然 OrderedDict 和和 dict 之间还是有一些差异。常规的 dict 主要用于执行映射操作，插入顺序是次要的，OrderedDict 的目的是方便执行重新排序操作，空间利用率、迭代速度和更新操作的性能是次要的。

ChainMap 实例存放一组映射，可作为一个整体来搜索。查找操作按照输入映射在构造函数调用中出现的顺序执行，一旦在某个映射中找到指定的键，则结束。

>>> d1 = dict(a=1, b=3)
>>> d2 = dict(a=2, b=4, c=6)
>>> from collections import ChainMap
>>> chain = ChainMap(d1, d2)
>>> chain['a']
1
>>> chain['c']
6

ChainMap 实例不复制输入映射，而是存放映射的引用。ChainMap 的更新或插入操作只影响第一个输入映射：

>>> chain['c'] = -1
>>> d1
{'a': 1, 'b': 3, 'c': -1}
>>> d2
{'a': 2, 'b': 4, 'c': 6}

ChainMap 可用于实现支持嵌套作用域的语言解释器，按嵌套层级从内到外，一个映射表示一个作用域上下文。。

import builtins
pylookup = ChainMap(locals(), globals(), vars(builtins))

collections.Counter 是一种对键计数的映射。更新现有的键，计数随之增加。可用于统计可哈希对象的实例数量，或者作为多重集（multiset）。若想把 collections.Counter 当作多重集使用，假设各个键是集合中的元素，计数值则是元素在集合中出现的次数。

>>> from collections import Counter
>>> ct = Counter('abcdabcdef')
>>> ct
Counter({'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 1, 'f': 1})
>>> ct.update("abcd")
>>> ct
Counter({'a': 3, 'b': 3, 'c': 3, 'd': 3, 'e': 1, 'f': 1})

标准库中的 shelve 模块持久存储字符串键与（以 pickle 二进制格式序列化的）Python 对象之间的映射。模块级函数 shelve.open 返回一个 shelve.Shelf 实例，这是一个简单的键值 DBM 数据库，背后是 dbm 模块。

子类应继承 UserDict 而不是 dict

创建新的映射类型，最好扩展 collections.UserDict，而不是 dict。子类最好继承 UserDict 的主要原因是，内置的 dict 在实现上走了一些捷径，如果继承 dict，那就不得不覆盖一些方法，而继承 UserDict 则没有这些问题。

不可变映射

标准库提供的映射类型都是可变的，不过有时也需要防止用户意外更改映射。types 模块提供的MappingProxyType 是一个包装类，把传入的映射包装成一个 mappingproxy 实例，这是原映射的动态代理，只可读取。这意味着，对原映射的更新将体现在 mappingproxy 实例身上，但是不能通过 mappingproxy 实例更改映射。

字典映射

dict 的实例方法 .keys()、.values() 和 .items() 分别返回 dict_keys、dict_values 和dict_items 类的实例。这些字典视图是 dict 内部实现使用的数据结构的只读投影。另外，视图还取代了返回迭代器的旧方法。视图是可迭代对象，方便构建列表，但是不能使用 [​] 获取视图中的项。

>>> t = {"a":1, "b":2, "c":3}
>>> v = t.values()
>>> v
dict_values([1, 2, 3])
>>> list(v)
[1, 2, 3]

>>> v[0]
Traceback (most recent call last):
  File "<python-input-10>", line 1, in <module>
    v[0]
    ~^^^
TypeError: 'dict_values' object is not subscriptable

>>> t['a']=10
>>> v
dict_values([10, 2, 3])

dict_keys、dict_values 和 dict_items是内部类，不能通过__builtins__或标准库中的任何模块获取，尽管可以得到实例，但是在 Python 代码中不能自己动手创建。

dict_values 类是最简单的字典视图，只实现了 __len__、__iter__ 和 __reversed__ 这 3 个特殊方法。除此之外，dict_keys 和 dict_items 还实现了多个集合方法，基本与 frozenset 类相当。

dict 的实现方式对实践的影响

Python 使用哈希表实现 dict，因此字典的效率非常高，不过这种设计对实践也有一些影响，不容忽视：

• 键必须是可哈希的对象：必须正确实现 __hash__ 和 __eq__ 方法
• 通过键访问项速度非常快
• 尽管采用了新的紧凑布局，但是字典仍然占用大量内存，这是不可避免的
• 为了节省内存，不要在 __init__ 方法之外创建实例属性：这里涉及 python 实现，__init__ 方法执行完毕后再添加实例属性，Python 就不得不为这个实例的 __dict__ 属性创建一个新哈希表

集合论

集合是一组唯一的对象。集合的基本作用是去除重复项。

>>> l = [1, 1, 2, 3]
>>> set(l)
{1, 2, 3}

>>> dict.fromkeys(l).keys()
dict_keys(['spam', 'eggs', 'bacon'])
>>> list(dict.fromkeys(l).keys())
['spam', 'eggs', 'bacon']

集合元素必须是可哈希的对象。set 类型不可哈希，因此不能构建嵌套 set 实例的 set 对象。但是 frozenset 可以哈希，所以 set 对象可以包含 frozenset 元素。

巧妙使用集合运算既可以减少代码行数，也能缩减 Python 程序的运行时间，同时还能少编写一些循环和条件逻辑，从而让代码更易于阅读和理解。

found = len(set(needles) & set(haystack))
found = len(set(needles).intersection(haystack))

set 字面量

set 字面量的句法与集合的数学表示法几乎一样，例如 {1}、{1, 2} 等。唯有一点例外：空 set 没有字面量表示法，必须写作 set()。frozenset 没有字面量句法，必须调用构造函数创建：

>>> frozenset(range(10))
frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9})

Python 也支持集合推导式：

>>> s = {i + 10 for i in range(10)}
>>> s
{10, 11, 12, 13, 14, 15, 16, 17, 18, 19}

set 和 frozenset 类型都使用哈希表实现。这种设计带来了以下影响：

• 集合元素必须是可哈希对象
• 成员测试效率非常高
• 与存放元素指针的低层数组相比，集合占用大量内存。尽管集合的结构更紧凑，但是一旦要搜索的元素数量变多，搜索速度将显著下降
• 元素的顺序取决于插入顺序，但是顺序对集合没有什么意义，也得不到保障。如果两个元素具有相同的哈希码，则顺序取决于哪个元素先被添加到集合中。
• 向集合中添加元素后，现有元素的顺序可能发生变化

字典试图的集合运算

.keys() 和 .items() 这两个 dict 方法返回的视图对象与 frozenset 极为相似。而且字典视图的集合运算符均兼容 set实例，如下所示。

>>> d1 = dict.fromkeys(range(1, 10))
>>> d2 = dict.fromkeys(range(2, 11))

>>> d1.keys() & d2.keys()
{2, 3, 4, 5, 6, 7, 8, 9}

>>> d1.keys() & {3, 5, 6}
{3, 5, 6}

>>> d = {"a":1, "b":2}
>>> d.items()
dict_items([('a', 1), ('b', 2)])
>>> set(d.items())
{('b', 2), ('a', 1)}

• 仅当 dict 中的所有值均可哈希时，dict_items 视图才可当作集合使用
• dict_keys 视图始终可当作集合使用，因为按照其设计，所有键均可哈希