Python进阶系列(流畅的Python第二版)：字典和集合

Python 基本就是一堆封装着语法糖的字典。

-Lalo Martins，早期数字游民和 Python 专家

在所有的Python程序中都会使用到字典。即便没在代码中直接使用，也是间接用到，因为dict类型是Python实现的一个基础。类和实例发不发、模块命名空间以及函数关键词参数都是在内存以及字典表示的核心Python结构。__builtins__.__dict__存储着所有的内置类型、对象和函数。

因其作用重大，Python的字典进行了高度的优化，并且还在不断改进。Python高性能字典背后的引擎是哈希表。

其它基于哈希表的内置类型有set和frozenset。它们提供了比其它流行编程语言中集合更多的API和运算符。具体来说，Python集合实现了集合理论中的所有基础运算，如并集、交集、子集测试等。借助于它们，我们以更为声明式的方式表达算法，避免大量的嵌套循环和条件语句。

以下本章的概述：

• 构建、处理dicts和映射的现代语法，包括增强的解包和模式匹配。
• 映射类型的常用方法。
• 缺失键的特殊处理。
• 标准库中dict的变体。
• set和frozenset类型。
• 集合和字典行为中哈希表的内涵。

现代字典语法

下面的小节中讲解构建、解包和处理映射的高级语法。其中一些特性并不是语言中新增的，但对于读者而言可能第一次听到。有一部分语法要求使用Python 3.9(比如管道运算符 |) 或Python 3.10(如 match/case)。我们先从一个优秀而又古老的特性开始。

dict推导式

从Python 2.7开始，列表推导式和生成式表达式就进行了dict推导式（以及set推导式，稍后会讲解）的适配。字典推导式通过从任意迭代对象接收key:value对构造一个dict实例。例3-1演示了使用dict推导式通过同一个元组列表构造两个字典。

例3-1：字典推导式的示例

>>> dial_codes = [           # dial_codes键值对可迭代对象可直接传递给dict构造函数，但是...                                                
...     (880, 'Bangladesh'),
...     (55,  'Brazil'),
...     (86,  'China'),
...     (91,  'India'),
...     (62,  'Indonesia'),
...     (81,  'Japan'),
...     (234, 'Nigeria'),
...     (92,  'Pakistan'),
...     (7,   'Russia'),
...     (1,   'United States'),
... ]
>>> country_dial = {country: code for code, country in dial_codes}  # ...此处进行键值互调：country为键，code为值
>>> country_dial
{'Bangladesh': 880, 'Brazil': 55, 'China': 86, 'India': 91, 'Indonesia': 62,
'Japan': 81, 'Nigeria': 234, 'Pakistan': 92, 'Russia': 7, 'United States': 1}
>>> {code: country.upper()   # 按名称对country_dial排序，键值互调，值置为大写，然后使用code < 70进行过滤
...     for country, code in sorted(country_dial.items())
...     if code < 70}
{55: 'BRAZIL', 62: 'INDONESIA', 7: 'RUSSIA', 1: 'UNITED STATES'}

如果会使用列表推导式的话，就自然会使用字典推导式。如若不会，推导式语法的广泛传播表明流畅使用它能带来诸多好处。

映射解包

PEP 448—解包综述增补自Python 3.5开始增强了对两种映射解包的支持。

首先可在函数调用对一个以上的参数使用**。在所有参数的键为字符串且唯一时可进行使用（因为允许使用重复的关键字参数）。

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

其次可在dict字面量内部使用**，同样可多次使用。

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

上例中出现了重复的键，这是允许的。后出现的会重写先出现的，可以看下本例中x的值。

这种语法也可用于合并映射，但还有其它的方式。请听后文分解。

使用管道符|合并映射

Python 3.9中支持使用|和|=合并映射。这很符合逻辑，国类这两者同时也是集合并集运算符。

使用|运算符新建映射：

>>> d1 = {'a': 1, 'b': 3}
>>> d2 = {'a': 2, 'b': 4, 'c': 6}
>>> d1 | d2
{'a': 2, 'b': 4, 'c': 6}

译者注：映射（mapping）是一种由键和关联值的集合组成的数据类型。目前 Python 唯一内置的映射类型是字典。

本文中会用到 Python 3.9和 Python3.10，当然可以安装最新版，或是在本地安装多个版本的Python，但也可以通过 Docker 进行测试（通过指定镜像版本就可以使用对应版本的 Python，以下默认使用最新版）

docker run -d --name python-alpine python:alpine watch "date >> /var/log/date.log"
docker exec -it python-alpine sh
# 用完就退出也可使用
docker run -it python:alpine sh

通常新映射的类型与左项的类型一致，上例为d1，但如果存在用户自定义类型则亦可为第二项的类型，在第16章中的运算符重载规则部分会进行讲解。

就地更新已有映射可使用|=。继续对前例进行操作，上例中的d1未发生修改，但下例中则不然：

>>> d1
{'a': 1, 'b': 3}
>>> d1 |= d2
>>> d1
{'a': 2, 'b': 4, 'c': 6}

小贴士：如需维护Python 3.8或更早版本中运行的代码，PEP 584—添加并集运算符的动机一节中总结了几种合并映射类型的方法。

下面来学习映射的模式匹配。

映射的模式匹配

match/case语句支持映射对象主体。映射的模式类似于字典字面量，但可以匹配任意实例或collections.abc.Mapping的虚拟子类。

在第2章中，我们只讨论了序列的模式，但不同的类型的模式可进行合并、内嵌。借助于解构，模式匹配是一种处理映射和序列嵌套之类结构记录的强大工具，通常用于读取JSON API和半结构化模式（schema）数据库，如MongoDB、EdgeDB或PostgreSQL。例3-2中进行了演示。get_creators中的简单类型提示表明接收了一个字典，返回了一个列表。

例3-2：creator.py: get_creators()从媒体记录中提取创作者名称

def get_creators(record: dict) -> list:
    match record:
        case {'type': 'book', 'api': 2, 'authors': [*names]}:  # 匹配任意带'type': 'book', 'api' :2以及映射序列的'authors'键映射。以新的列表进行返回
            return names
        case {'type': 'book', 'api': 1, 'author': name}:  # 匹配任意带'type': 'book', 'api' :2以及映射对象的'authors'键映射。在列表内部返回对象。
            return [name]
        case {'type': 'book'}:  # 其它带'type': 'book的映射均无效，抛出ValueError
            raise ValueError(f"Invalid 'book' record: {record!r}")
        case {'type': 'movie', 'director': name}:  # 匹配任意带'type': 'movie', 'api' :2以及映射单个对象的'director'键映射。在列表内部返回对象
            return [name]
        case _:  # 其它均为无效，抛出ValueError
            raise ValueError(f'Invalid record: {record!r}')

例3-2很好地演示了在处理JSON之类的半结构化数据:

• 包含一个描述记录类型的字段（如'type': 'movie'）
• 包含一个标识模式版本的字段（如'api': 2'），方便未来仅有API的演进
• case从句处理具体类型的无效记录（如'book'），以及异常捕获

下面我们来看get_creators是如何处理具体的文档测试的：

>>> b1 = dict(api=1, author='Douglas Hofstadter',
...         type='book', title='Gödel, Escher, Bach')
>>> get_creators(b1)
['Douglas Hofstadter']
>>> from collections import OrderedDict
>>> b2 = OrderedDict(api=2, type='book',
...         title='Python in a Nutshell',
...         authors='Martelli Ravenscroft Holden'.split())
>>> get_creators(b2)
['Martelli', 'Ravenscroft', 'Holden']
>>> get_creators({'type': 'book', 'pages': 770})
Traceback (most recent call last):
    ...
ValueError: Invalid 'book' record: {'type': 'book', 'pages': 770}
>>> get_creators('Spam, spam, spam')
Traceback (most recent call last):
    ...
ValueError: Invalid record: 'Spam, spam, spam'

注意模式中键的排序不重要，像b2中的的有序字典也一样没关系。

不同于序列模式，映射只需要部分匹配即可成功。在文档测试中b1和b2包含'title'键在所有的'book'模式中都没有，但仍能匹配成功。

无需使用**extra来匹配其它的键值对，但如果希望以字典来捕获，可以在一个变量名前添加**。这个变量必须是模式中最后的那个，不允许使用**_，因为这有点画蛇添足。举个简单的例子：

>>> food = dict(category='ice cream', flavor='vanilla', cost=199)
>>> match food:
...     case {'category': 'ice cream', **details}:
...         print(f'Ice cream details: {details}')
...
Ice cream details: {'flavor': 'vanilla', 'cost': 199}

在自动处理无键返回值一节我们会学习defaultdict和其它通过__getitem__(即 d[key]) 来查询键的映射，因其会实时创建缺失项，所以执行成功。在模式匹配中，只有在match语句所需要的键存在时匹配才会成功。

小贴士：没有触发对缺失键的自动处理，原因是模式匹配总会使用d.get(key, sentinel)方法，其中默认的sentinel是一个无法在用户数据中出现的特殊标记值。

语法和结构暂时讲到这，下面学习映射的API。

映射类型的标准API

collections.abc模块中提供了Mapping和MutableMapping抽象基类，描述dict和类似类型的接口。参见图3-1。

抽象基础类的主要价值是记录及统一映射的标准接口，并对需要支持映射的类型在代码中进行isinstance测试时作为其条件：

>>> my_dict = {}
>>> isinstance(my_dict, abc.Mapping)
True
>>> isinstance(my_dict, abc.MutableMapping)
True

小贴士：使用抽象基类的isinstance通常比检测函数参数是否为dict类型要好，因为这样可以使用其它映射类型。我们会在第13章中详细讨论

图3-1：collections.abc中MutableMapping及其父类的简化UML类图（继承箭头由子类指向父类，斜体名称为抽象类和抽象方法）

要实现自定义映射，继承collections.UserDict或通过组合封装dict会比抽象基类的这些子类更容易。collections.UserDict类和所有标准库中的所有具体映射类在实现时封装了基础的dict，然后根据哈希表构建。因此，这些类型的键都必须为可哈希对象（值并无此求，仅针对键）。如果需要复习可哈希的概念，下一节中会进行讲解。

什么是可哈希对象

下面是Python词汇表中节略的对可哈希对象的定义。

一个对象可哈希的意思是在其生命周期内哈希码都不发生改变（使用__hash__()方法），并可与其它对象进行比较（使用__eq__()方法）。相等的可哈希对象必须要有一致的哈希码。

数据类型和普通的不可变类型str及bytes都是可哈希对象。容器类型在不可变及的所含对象也均不可变时是可哈希的。frozenset一定是可哈希的，因为其所含的每个元素在定义上都必须是可哈希的。tuple仅在所有元素都可哈希时才可哈希。参见元组tt、tl和tf：

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
-3907003130834322577
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'list'
>>> tf = (1, 2, frozenset([30, 40]))
>>> hash(tf)
5149391500123939311

在不同机器架构、不同Python版本上对象的哈希码会不同，因为出于安全考虑会在哈希运算时加盐。正确实现的对象的哈希码仅保证在同一Python进程中保持一致。

默认用户定义的类型是可哈希的，因其哈希码为其id()，并且通过object类继承的__eq__()方法可以比对对象的id。如果对象实现了自定义的__eq__()，考虑其自身状态，仅在__hash__()返回的哈希码相同时对象才是可哈希的。在实际使用中，这要求__eq__()和__hash__()仅考虑在对象生命周期内永不改变的实例属性。

下面我们来复习下Python最常用映射类型的API：dict、defaultdict和OrderedDict。

常见映射方法总览

映射的基本API相当丰富。表3-1中展示了由dict及其两个变体defaultdict和OrderedDict实现的方法，两者都在collections模块中定义。

表3-1：映射类型dict、 collections.defaultdict和collections.OrderedDict的方法 (为保持简洁略去了常用对象方法)；可选参数放在[…]中

注：

[a] default_factory不是个方法，而是在defaultdict初始化时由终端用户设置的可调用属性集

[b] OrderedDict.popitem(last=False)删除先插入的子项（先入先出）。在新版本Python 3.10b3中dict或defaultdict不支持关键字参数last

[c] 在第16章中讲解反向运算符

d.update(m)处理第一个参数m的方式是鸭子类型的的一个主要案例：首先查看m是否有keys方法，如有则认为它是一个映射。否则update()会降级为对m进行迭代，假定其子项为(key, value对。

一个微妙的映射方法是setdefault()。在需要原处更新子项的值时它避免了冗余的键查询。下一节讲解如何使用。

插入或更新可变值

遵循Python的快速失败哲学（fail-fast ），访问d[k]在k键不存在时会抛出错误。Python编程人员知道d.get(k, default)是d[k]的替代，用于默认值比处理KeyError更方便的场景。但在获取获取可变值并希望更新时，还有更好的方法。

假设编写脚本来索引文本，生成一个单词为键列表中位置为值的映射，参见示例3-3。

示例3-3：示例3-4中处理Python之禅的部分输出，每行显示单词及其在列表的位置(line_number, column_number)

$ python3 index0.py zen.txt
a [(19, 48), (20, 53)]
Although [(11, 1), (16, 1), (18, 1)]
ambiguity [(14, 16)]
and [(15, 23)]
are [(21, 12)]
aren [(10, 15)]
at [(16, 38)]
bad [(19, 50)]
be [(15, 14), (16, 27), (20, 50)]
beats [(11, 23)]
Beautiful [(3, 1)]
better [(3, 14), (4, 13), (5, 11), (6, 12), (7, 9), (8, 11), (17, 8), (18, 25)]
...

示例3-4是一个次优的版本，展示dict.get不是处理缺失键的最佳方式。本例修改自Alex Martelli的示例。

示例3-4：index0.py使用dict.get获取、更新索引中的单词列表（更好的方案参见示例3-5）

"""Build an index mapping word -> list of occurrences"""

import re
import sys

WORD_RE = re.compile(r'w+')

index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            # 代码丑陋，旨在说明观点
            occurrences = index.get(word, [])  # 获取word的位置， 找不到时返回[]
            occurrences.append(location)       # 在出现时追加新位置
            index[word] = occurrences          # 将变更后的occurrences加到index字典中，这会在index中进行第二次搜索

# 按字母排序进行显示
for word in sorted(index, key=str.upper):      # 对sorted的key=参数没有调用str.upper，只是传递了对该方法的引用，这样sorted函数可使用它来规范单词进行排序
    print(word, index[word])

示例3-4中处理occurrences的三行代码可使用一行dict.setdefault进行替换。示例3-5更接近于Alex Martelli的代码。

示例3-5：index.py使用dict.setdefault获取、更新索引中的单词列表，对比示例3-4

"""Build an index mapping word -> list of occurrences"""

import re
import sys

WORD_RE = re.compile(r'w+')

index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            index.setdefault(word, []).append(location)  # 获取出现word的列表，找不到时设置为[]；setdefault返回该值，因此更新时无需二次搜索

# 按字母排序进行显示
for word in sorted(index, key=str.upper):
    print(word, index[word])

换句话说，下面这行的结果：

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

与以下的结果一致：

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

只是后一种代码会对key至少执行两次搜索（未找到时为3次），而setdefault只进行了一次查询。

相关处理无键查询（不止是插入）的问题会在下一节中进行讨论。

自动处理无键返回值

有时在对映射搜索到不存在的键时统一返回一个值会更方便。有两种主要的方法：一种是使用defaultdict替换dict。另一种是建立dict或其它映射类型的子类，添加__missing__方法。下面会讲到这两种方法。

defaultdict：处理不存在的键

collections.defaultdict实例在使用d[k]语法搜索不存在的键时会按需创建一个带默认值的子项。示例3-6使用defaultdict提供另一种优雅方案处理示例3-5中的单词索引任务。

原理如下：在实例化defaultdict时，传递不存在的键给__getitem__时会提供一个生成默认值的可调用方法。

例如，假定使用dd = defaultdict(list)创建默认值字典，如果dd中没有'new-key'，dd['new-key']会完成如下步骤：

这个可调用方法生成的默认值在实例中以default_factory属性进行存储。

示例3-6：index_default.py：使用defaultdict替换setdefault方法

"""Build an index mapping word -> list of occurrences"""

import collections
import re
import sys

WORD_RE = re.compile(r'w+')

index = collections.defaultdict(list)     # 使用list构造函数创建default_factory默认值字典
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            index[word].append(location)   # 如果index中没有word，会调用default_factory来生成缺失的值，本例中将空列表赋值给index[word]并返回，因此.append(location)可保持成功

# 按字母排序进行显示
for word in sorted(index, key=str.upper):
    print(word, index[word])

如果提供了default_factory，会抛出缺失键的KeyError。

警告：仅在对__getitem__调用提供了默认值时defaultdict的default_factory才会调用，对其它方法无效。例如，假设dd是一个defaultdict，k是不存在的键，dd[k]会调用default_factory创建默认值，但dd.get(k)仍返回None，k in dd 为 False。

调用default_factory来让defaultdict正常运行的机制是__missing__方法，在下一节中讨论。

__missing__方法

映射处理缺失键的底层方法恰到好处地命名为__missing__。该方法不是在dict基类中定义，但dict可以感知到它：如果dict有子类提供了__missing__方法，标准的dict.__getitem__会在找不到键时调用它，而不会抛出KeyError。

假设希望在查找时将映射的键都转化为字符串。实际案例有物联网的设备库，其中带能用I/O针脚的可编程面板（如树莓派或Arduino）使用带my_board.pins属性的Board类表示，该属性是物理针脚标识符与针脚软件对象的映射。物理针脚标识符可能是数字或"A0"、"P9_12"这样的字符串。为保持一致性，最好board.pins中的所有键都是字符串，但通过数字进行查找也很方便，如my_arduino.pin[13]，这样初学者不会因为想要Arduino的13针脚上的LED闪烁而出现问题。示例3-7演示了这类映射如何使用。

示例3-7：在搜索非字符串键时，未找到时StrKeyDict0将其转化为字符串

使用`d[key]`标记获取子项的测试：

    >>> d = StrKeyDict0([('2', 'two'), ('4', 'four')])
    >>> d['2']
    'two'
    >>> d[4]
    'four'
    >>> d[1]
    Traceback (most recent call last):
      ...
    KeyError: '1'

使用`d.get(key)`标记获取子项的测试：

    >>> d.get('2')
    'two'
    >>> d.get(4)
    'four'
    >>> d.get(1, 'N/A')
    'N/A'


`in`运算符的测试

    >>> 2 in d
    True
    >>> 1 in d
    False

示例3-8实现了传入前置测试文档的StrKeyDict0类

小贴士：创建用户定义映射类型更好的方式是使用collections.UserDict子类替换dict（在示例3-9中会这么做）。这里使用dict子类只是为了演示__missing__由内置的dict.__getitem__方法进行支持。

示例3-8：StrKeyDict0在查询时将非字符串键转化为字符串（参数示例3-7）

class StrKeyDict0(dict):  # StrKeyDict0继承dict

    def __missing__(self, key):
        if isinstance(key, str):  # 查看key是否为字符串。如是且不存在，抛出KeyError
            raise KeyError(key)
        return self[str(key)]  # 通过key构造字符串，再进行查找

    def get(self, key, default=None):
        try:
            return self[key]  # get方法通过使用self[key]代理至__getitem__，这给了__missing__起作用的机会
        except KeyError:
            return default  # 如果抛出了KeyError，__missing__已失败，因而返回default

    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys()  # 搜索未修改的键（实例可能包含非字符串键），然后搜索使用键构造的字符串

花一点时间思考为会在__missing__实现中需要测试isinstance(key, str)。

不进行该测试，在str(k)为存在的键时不管k是不是字符串__missing__方法的运行都正常。但如果str(k)不存在的话，会进入无限循环。在__missing__的最后一行，self[str(key)]会调用__getitem__，传入str键，这又会再次调用__missing__。

还需要用到__contains__来保持示例中的一致性，因为k in d运算会调用它，但从dict继承的方法不会降级为调用__missing__。在__contains__的实现中有一个细节：我们没有按Pythonic的方式（k in my_dict）查找键，因为str(key) in self会循环调用__contains__。通过显式的在self.keys()中进行查找规避了这一问题。

像k in my_dict.keys()这样的搜索即使是对超大映射在Python 3中也是很高效的，因为dict.keys()返回一个视图，类似于集合，我们会在字典视图的集合操作一节中进行学习。但是，请记住k in my_dic完成的是同样的任务，它更快的原因在于不必使用属性查询查找.keys方法。

示例3-8中在__contains__内使用self.keys()有特别的原因。对未变更键的检查（key in self.keys()）可保证正确性，因为StrKeyDict0不会强制字典的所有键类型必须为str。这一简例的唯一目的是让搜索更“友好”而不是去强制类型。

警告：由标准派生的用户自定义类在__getitem__、get或__contains__的实现中不一定使用__missing__作为后备方法，在下一节中会进行讲解。

标准库中__missing__的不一致用法

思考以下的场景以及缺失键的查询有何影响：

dict子类

dict子类仅实现__missing__而没有实现其它方法。这时，仅会对d[k]调用__missing__，它会使用从dict继承在__getitem__方法。

collections.UserDict子类

类似地UserDict子类仅实现__missing__而没有实现其它方法。继承自UserDict的get方法调用__getitem__。这表示可能会调用__missing__来处理d[k]和d.get(k)的查找。

带最简化__getitem__的abc.Mapping子类

abc.Mapping的最小化子类实现__missing__及所需的抽象方法，包含对不调用__missing__的__getitem__的实现。在该类中不会触发__missing__方法。

带调用__missing__的__getitem__的abc.Mapping子类

abc.Mapping的最小化子类实现__missing__及所需的抽象方法，包含对调用__missing__的__getitem__的实现。在调用d[k], d.get(k)和k in d时出现缺失键会触发__missing__方法。

参见missing.py 示例代码中对以上场景的演示。

以上的四种场景都是最小化的实现。如果子类实现了__getitem__、get和__contains__，那么就可以根据需要选择是否使用__missing__。本节旨在展示在创建标准库映射子类时应注意__missing__的使用，因为这些基类默认支持的行为不同。

别忘了setdefault和update的行为也受键查询的影响。最后，根据__missing__的逻辑，可能需要在__setitem__中实现特殊的逻辑来规避不一致性或意外行为。我们会在使用UserDict替代dict派生子类一节中查看示例。

至此我们讲解了dict和defaultdict映射类型，但标准库中还有其它的映射实现，下面进行讨论。

dict的变体

本节中综述标准库中所包含的映射类型，defaultdict在defaultdict：处理不存在的键中已进行讨论，这里略过。

collections.OrderedDict

Python 3.6中已对内置dict的键进行了排序，使用OrderedDict的主要原因是编写对更早版本Python向后兼容的代码。Python的文档也列举了dict和OrderedDict之间的区别，引用如下（按日期使用的关联度进行了重排）：

• OrderedDict的等值运算检测匹配排序。
• OrderedDict的popitem()方法存在不同的签名。它接收用于指定弹出项的可选参数。
• OrderedDict有一个move_to_end()方法，有效将元素重定位到端点。
• dict针对映射运算进行了很好的设计。追踪插入顺序放在了次位。
• OrderedDict设计的擅于处理重排序运算。空间效率、迭代速度和更新运算的性能放在了次位。
• 在算法上，OrderedDict对频繁重排序运算的处理要优于dict。这让其适于追踪最新的访问（如LRU缓存）。

collections.ChainMap

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对于实现带嵌套作用域的语言编译器非常有用，其中每个映射代表一个作用域上下文，从最内层作用域直到最外层作用域。collections文档的ChainMap对象一节中有几个ChainMap的使用示例，包括受Python中变量查询基本规则启发的代码片断：

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

示例18-14中会展示用于实现模式编程语言子集解释器的ChainMap子类。

collections.Counter

这是一个存储每个键整型计数的映射。更新已有键或对计算进行添加。这可用于统计可哈希对象或多重集合（本节稍后讨论）。Counter实现了+ 和-运算符来进行合计，还有其它一些有用的方法，如most_common([n])，返回前n最常见元组的排序列表及数量；参见官方文档。以下是对单词中字母进行计数的Counter：

>>> ct = collections.Counter('abracadabra')
>>> ct
Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
>>> ct.update('aaaaazzz')
>>> ct
Counter({'a': 10, 'z': 3, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
>>> ct.most_common(3)
[('a', 10), ('z', 3), ('b', 2)]

注意键'b'和'r'同为第三，但ct.most_common(3)仅显示了3条统计。

要以多重集合使用collections.Counter，假定集合中的每个键是一个元素，统计为该元素在集合中出现的次数。

shelve.Shelf

标准库中的shelve模块提供了对映射的持久化存储，映射为字符串键对以pickle二进制格式序列化的Python对象。在意识到泡菜罐需要在架子上存放时就会发现shelve这个名字是符合逻辑的。

模块级函数shelve.open返回一个shelve.Shelf实例，这是一个由dbm模块支持的简单键值DBM数据库，包含如下特性：

• shelve.Shelf是abc.MutableMapping的子类，因此提供了映射类型应有的基本方法。
• 此外，shelve.Shelf提供了一些I/O管理方法，如sync和close。
• Shelf实例是一个上下文管理器，因此可以使用with代码块来确保在使用后关闭。
• 在将新值赋给键时会保存键和值。
• 键必须是字符串。
• 值必须是pickle可以序列化的对象。

shelve、dbm和 pickle的文档提供更多详情和一些警示。

警告：在最简用例中pickle的使用非常简单，但存在一些不足。在使用涉及pickle的方案前读一读Ned Batchelder的“Pickle9宗罪”。Ned提到了其它可考虑的序列化格式。

可直接使用OrderedDict、 ChainMap、Counter和Shelf，但也可由子类进行自定义。相比较而言，UserDict仅作为待继承的基类。

使用UserDict替代dict派生子类

最好通过继承collections.UserDict而非dict来新建映射类型。在示例3-8中StrKeyDict0继承中意识到要确保添加到映射中的所有键以字符串存储。

使用UserDict替代dict派生子类的主要原因是其内置有一些实现捷径最终强制要求重载方法，而通过继承UserDict则毫无问题。

注意UserDict并非继承自dict，而是使用了组合：它有一个内置的dict实例，名为data，存储着实际的子项。这避免了在使用__setitem__这样的方法时出现预想外的循环，并简化了__contains__的编码，对比示例3-8。

有了UserDict，让StrKeyDict（例3-9）比StrKeyDict0（例3-8）更简洁，但功能更多：它以字符串存储所有键，在通过包含非字符串键数据构建或更新实例时又避免了意义的行为。

例3-9：在插入、更新及查找时StrKeyDict总会将非字符串键更新为str

import collections


class StrKeyDict(collections.UserDict):  # StrKeyDict继承UserDict

    def __missing__(self, key):    # __missing__和例3-8中一样
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]

    def __contains__(self, key):    # __contains__更为简单：我们可以假定所有存储的键为字符串，然后检查self.data，而无需像StrKeyDict0中那样调用self.keys()
        return str(key) in self.data  

    def __setitem__(self, key, item):  # __setitem__将所有的key转化为字符串。在可代理至self.data属性时方法更容易重写
        self.data[str(key)] = item

因为UserDict继承abc.MutableMapping，剩下将StrKeyDict变成完善映射的方法继承自UserDict、MutableMapping或Mapping。后者虽然是抽象基类，但有一些有用的具体方法。有以下方法值得一说：

MutableMapping.update

这个强大的方法可直接调用，但也由__init__用来从其它映射加载实例，从(key, value)对可迭代对象到关键词参数。因其使用self[key] = value添加子项，最终会调用我们的__setitem__实现。

Mapping.get

在StrKeyDict0（例3-8）中，我们需要编写自己的get来返回和__getitem__相同的结果，但在例3-9中我们继承了Mapping.get，实现和StrKeyDict0.get完全一样（参见Python源代码）。

小贴士：Antoine Pitrou编写了PEP 455-在容器中添加键转换字典以及使用TransformDict增强collections模块的补丁，这比StrKeyDict更通用，在应用转换前保留所提供的键。PEP 455在2015年5月被拒，参见Raymond Hettinger的拒绝消息。为体验TransformDict，我将issue18986里Pitrou的补丁提取为一个单独的模块（参见03-dict-set/transformdict.py）。

我们知道有不可变序列类型，那不可变映射呢？在标准库里其实没这个东西，不过有一个替身。下面进行讲述。

不可变映射

由标准库提供的映射类型全部是可变的，但有时需要防止用户意外修改映射。可以找到真实的案例，在 __missing__方法一节提到的像Pingo这样的硬件编程库里：board.pins 映射表示设备上的实际GPIO（通用输入输出）针脚。这时，防止因疏忽更新board.pins会很有用，因为硬件不能通过软件发生改变，因此映射中的修改会让真实的设备出现不一致状况。

types模块提供了名为MappingProxyType的封装类，在给到一个映射时返回mappingproxy实例，它是只读的但可以动态代理至原映射。也就是说对原映射的更新在mappingproxy中可见，但无法通过它作出修改。参见示例3-10中的简单演示。

示例3-10：MappingProxyType通过dict构建一个只读mappingproxy

>>> from types import MappingProxyType
>>> d = {1: 'A'}
>>> d_proxy = MappingProxyType(d)
>>> d_proxy
mappingproxy({1: 'A'})
>>> d_proxy[1]  # 在d_proxy中可以看到d
'A'
>>> d_proxy[2] = 'x'  # 无法通过d_proxy作出修改
Traceback (most recent call last):
  File "", line 1, in 
TypeError: 'mappingproxy' object does not support item assignment
>>> d[2] = 'B'
>>> d_proxy   # d_proxy是动态的，d中的修改都会有体现
mappingproxy({1: 'A', 2: 'B'})
>>> d_proxy[2]
'B'
>>>

这是在硬件编程场景中可能实际使用的方式：Board子类构建构造函数会通过针脚对象直充一个私有映射，并通过按mappingproxy实现的公有.pins属性暴露给API客户端。这样客户端无法意外添加、删除或修改针脚。

接下来会讲解视图，在不经过非必要数据拷贝的情况下，允许对dict的高性能运算。

字典视图

dict实例方法.keys()、.values()和.items()分别返回名为dict_keys、dict_values和dict_items的实例类。这些字典视图是对dict实现中使用的内部数据结构的只读投射。它们避免了Python 2原来中返回dict目标内返回已存在数据的复制列表这类内存压力，还替换了返回迭代器的老方法。

示例3-11展示了所有字典视图支持的一些基本运算。

示例3-11：.values()返回了一个字典中值的视图

>>> d = dict(a=10, b=20, c=30)
>>> values = d.values()
>>> values
dict_values([10, 20, 30])  # 视图对象的repr显示其内容
>>> len(values)     # 可查询视图的长度
3
>>> list(values)  # 视图是可迭代的，因此通过它们创建列表很容易
[10, 20, 30]
>>> reversed(values)  # 视图实现__reversed__，返回一个自定义迭代器

>>> values[0] # 可以使用[]来获取视图中的单项
Traceback (most recent call last):
  File "", line 1, in 
TypeError: 'dict_values' object is not subscriptable

视图对象是一个动态代理 。如果更新了源字典，可以立刻通过已有视图查看其变化。继续使用示例3-11：

>>> d['z'] = 99
>>> d
{'a': 10, 'b': 20, 'c': 30, 'z': 99}
>>> values
dict_values([10, 20, 30, 99])

dict_keys、dict_values和dict_items是内部类：在__builtins__和标准库模块中不可用，即使获取到其指针，也不能使用它在Python代码中从零创建视图：

>>> values_class = type({}.values())
>>> v = values_class()
Traceback (most recent call last):
  File "", line 1, in 
TypeError: cannot create 'dict_values' instances

dict_values类是最简单的字典视图，它仅实现了__len__、__iter__和__reversed__特殊方法。除这些方法外，dict_keys和dict_items还实现了一些集合方法，几乎和frozenset类一样多。在讲完集合后，我们会在字典视图的集合运算一节中更深入讲解dict_keys和dict_items。

下面我们来学习由dict底层实现方式产生的一些规则和贴士。

dict运行的实际结果

Python字典的哈希表实现很高效，但理解这一设计的实际效果很重要：

• 键必须是可哈希对象。它必须实现什么是可哈希对象中讲到的__hash__和__eq__方法。
• 通过键访问子项很快。字典可能有几百万个键，但Python可通过计算键的哈希码并获取哈希表中的索引偏移直接定位到键，查找匹配条目可能会一些少量的尝试负载。
• 在CPython 3.6中保留的有序键促成了dict更紧凑的内存布局，这在3.7中成为官方语言特性。
• 虽然有了新的紧凑布局，但不可避免地存在内存负载。容器最紧凑的内部数据结构是子项指针数组。与其相比，哈希表需要为每条存储更多的数据，并且Python需要至少保持哈希表三分之一的行为空才能维持高效性。
• 为节约内存，避免在__init__方法外创建实例属性。

最后一个有关实例属性的贴士源自Python的默认行为是将实例属性存储在特殊的__dict__属性中，它是一个附加在每条实例上的字典。自从在Python 3.3中实现了PEP 412—键共享字典，类的实例可共享常用哈希表，与类共同存储。常用哈希表在__init__返回时类的首个实例具有相同属性名时，由每个新实例的__dict__共享。每个实例的__dict__随后可以简单的指针数组仅存储其自身的属性值。在__init__后添加实例属性强制Python为该实例的__dict__创建哈希表（这是Python 3.3)之前所有实例的默认行为）。根据PEP 412，这一优化对面向对象编程降低了10%到20%的内存使用。

紧凑布局和键共享优化的细节非常复杂。更多内容请阅读集合和字典的内部原理。

下面进入到集合的讲解。

集合理论

集合在Python中不是新事物，但使用率依然不高。set类型及其不可变的兄弟frozenset首先是在Python 2.3标准库中以模块出现，在Python 2.6中提升为内置类型。

注：本书中，我们使用集合来指代set和frozenset。在具体讨论set类时，我使用定宽字体：set。

集合是一个唯一对象集。基本的用法是删除重复项：

>>> l = ['spam', 'spam', 'eggs', 'spam', 'bacon', 'eggs']
>>> set(l)
{'eggs', 'spam', 'bacon'}
>>> list(set(l))
['eggs', 'spam', 'bacon']

小贴士：如果希望删除重复项但同时保留每项首次出现的排序，可以使用普通的字典来实现，如：

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

集合元素必须是可哈希的。set类型是不可哈希的，因此不能通过内嵌的set实例来构建set。但frozenset是可哈希的，因此在set中可使用frozenset。

除了强制唯一性外，集合类型以中间运算符实现了很多集合运算，因此给定两具集合a和b，a | b返回并集，a & b计算交集，a - b计算差集，而a ^ b为对等差分。对集合运算的合理使用会减少Python程序的代码量及执行时间，同时（通过去除循环和条件逻辑）简化了代码的阅读和推理。

例如，假如有一个邮箱地址大集合（haystack）和一个地址的小集合（needles），需要计算出haystack中出现了多少needles。借助于set的交集（&运算符），可以只使用一行代码（参见示例3-12）。

示例3-12：haystack中needles出现的次数，同为集合类型

found = len(needles & haystack)

如果不使用交集运算符，则需要编写示例3-13中的代码来完成示例3-12的任务

found = 0
for n in needles:
    if n in haystack:
        found += 1

例3-12比例3-13的运行速度要快一些。而例3-13适用于所有迭代对象needles和haystack，但例3-12要求两者都是集合。但如果手上没有集合，可以实时进行构建，参见示例3-14。

示例3-14：计算haystack中needles出现的次数，代码适用任意迭代类型

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

# 另一种方式:
found = len(set(needles).intersection(haystack))

当然示例3-14中构建集合有一些开销，但如果needles或haystack不是集合，示例3-14的开销还是小于示例3-13。

上例中的代码均可用0.3毫秒左右在10,000,000个项目的haystack中查找1,000个元素-相当于个元素大约0.3微秒。

除了极度快速的成员测试外（借助于底层的哈希表），set和frozenset内置类型提供了丰富的API用于新建集合，或是修改已有的set。我们一会儿会讨论运算，但先讲讲语法。

集合字面量

set字面量的语法（{1}、{1, 2}等）和数据标记一样，但有一个重要的区别：没有对空set的字面量标记，因此必须写set()。

语法怪象：别忘了创建一个空set，应当使用不带参数的构造函数set()。如果写{}，创建的是一个空字典，Python 3中也是如此。

在Python 3中，集合的标准字符串表示使用了{…}标记，但空集除外：

>>> s = {1}
>>> type(s)

>>> s
{1}
>>> s.pop()
1
>>> s
set()

{1, 2, 3}这样的字面量集合语法不仅更快速，也比调用构造方法(如set([1, 2, 3]))可读性更强。后者更慢的原因是对其进行运算，Python需要查找set名来获取构造方法，然后构建列表，最后将其传递给构造方法。相反，处理{1, 2, 3}这样的字面量，Python运行一个特殊字节码BUILD_SET。

表示frozenset字面量并没有特殊语法，必须通过调用构造方法创建。Python 3中标准字符串表示类似frozenset构造方法调用。注意看控制台中的输出：

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

说到语法，列表推导式的想法也应用到了集合中。

集合推导式

集合推导式(setcomps)在Python 2.7中就和字典推导式一并进行了添加。参见示例3-15。

示例3-15：构建Unicode名称中包含单词“SIGN”的Latin-1字符集合

>>> from unicodedata import name  # 通过unicodedata导入name获取字符名
>>> {chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i),'')}  # 构建32到255编码名称中包含单词“SIGN”的字符集合
{'§', '=', '¢', '#', '¤', '', '¬', '®', '%'}

每次Python处理的输出顺序不同，原因是在什么是可哈希对象中讨论过的加盐哈希。

把语法放到一边，下面来思考集合的行为。

集合运行的实际结果

set和frozenset类型都通过哈希表实现。这有如下效果：

• 集合元素必须为可哈希对象。它们必须正确实现什么是可哈希对象中所讲到的__hash__和__eq__方法。
• 成员测试极为高效。集合可包含数百万个元素，但可通过计算其哈希码并获取索引偏移，查找匹配条目或是耗尽搜索可能会一些少量的尝试负载。
• 集合有较大的内存负载，这是与指向元素指针的底层数组相比较，数据更为紧凑但搜索大量元素时会很慢。
• 元素的排序取决于插入顺序，但并不一定有用或可靠。如果两个元素不同但哈希码相同，位置取决于哪个元素先添加。
• 对集合添加元素可能改变已有元素的排序。这是因为如果哈希表内容超过三分之二后算法效率下降，因此Python可能需要在表增长时重置其大小。此时会重新插入元素，相对排序可能会发生变化。

参见集合和字典的内部原理了解更多详情。

下面来复习集合所提供的大量运算。

集合运算

图3-2给出了可变和不可变集合中可用的方法的总览。其中很多是重载运算符的特殊方法，如&和>=。表3-2展示了数学集合运算在Python中有对应的运算符或方法。注意有些运算符及方法是在原目标集合中执行修改（如&=、difference_update等）。这种运算在数据集合的理想世界中没有意义，在frozenset中未进行实现。

小贴士：表3-2中的中间运算符要求两个运算项都是集合，但其它的方法接收一个或多个可迭代参数。例如，生成4个集合a、b、c和d的并集，可以调用a.union(b, c, d)，其中a必须是集合，但b、c和d可以是生成哈希项的任意可迭代类型。如果需要通过4个迭代对象的并集新建集合，不对已有集合进行更新，我们可以写{*a, *b, *c, *d}，这得益于Python 3.5开始引入的PEP 448—其它解包规范。

图3-2：MutableSet及其collections.abc中父类的简化UML类图 (斜体名称为抽象类和抽象方法，为简化略去了反向运算符方法)

表3-2：数学集合运算：这些方法要么生成新集合要么在集合可变时更新原目标集合

表3-3列举了集合动词：返回True或False的运算符及方法。

表3-3：返回布尔值的集合比较运算符及方法

除从数学集合理论派生的运算符和方法外，实现其它实用方法的集合类型总结为表3-4。

表3-4：其它集合方法

这就结束了集合特性的总览。在字典视图中承诺过，下面就来讲解字典的两类型为何行为类似frozenset。

字典视图的集合运算

表3-5展示了由字典方法.keys()和.items()返回的视图对象与frozenset惊人的相似。

表3-5：由frozenset、dict_keys和dict_items实现的方法

frozenset | dict_keys | dict_items | 描述 | | -------------------------- | --------- | --------- | ---------- | ------------------ | | s.and(z) | ● | ● | ● | s & z (s 和 z的交集) | | s.rand(z) | ● | ● | ● | 反向 &运算 | | s.contains() | ● | ● | ● | e in s | | s.copy() | ● | | | s的浅拷贝 | | s.difference(it, …) | ● | | | s和可迭代对象it等的差集 | | s.intersection(it, …) | ● | | | s和可迭代对象it等的交集 | | s.isdisjoint(z) | ● | ● | ● | s 和 z不相交(没有公共元素) | | s.issubset(it) | ● | | | s是可迭代对象it的子集 | | s.issuperset(it) | ● | | | s是可迭代对象it的超集 | | s.iter() | ● | ● | ● | 获取s的迭代器 | | s.len() | ● | ● | ● | len(s) | | s.or(z) | ● | ● | ● | s | z (s 和 z的并集) | | s.ror() | ● | ● | ● | 反向 | 运算 | | s.reversed() | | ● | ● | 以反序获取s的迭代器 | | s.rsub(z) | ● | ● | ● | 反向的 - 运算 | | s.sub(z) | ● | ● | ● | s - z (s 和 z的差集) | | s.symmetric_difference(it) | ● | | | s & set(it)的补集 | | s.union(it, …) | ● | | | s和可迭代对象it等的并集 | | s.xor() | ● | ● | ● | s ^ z (s 和 z的对等差分) | | s.rxor() | ● | ● | ● | 反向的 ^ 运算

尤其是dict_keys和dict_items实现了特殊方法用于支持强大的集合运算& (交集), | (并集), - (并集), and ^ (对等差分)。

例如，使用&很容易获取在两个字典同出现的键名：

>>> d1 = dict(a=1, b=2, c=3, d=4)
>>> d2 = dict(b=20, d=40, e=50)
>>> d1.keys() & d2.keys()
{'b', 'd'}

注意&的返回值是set。甚至更好的是字典视图中的集合运算符完全兼容set实例。看下例：

>>> s = {'a', 'e', 'i'}
>>> d1.keys() & s
{'a'}
>>> d1.keys() | s
{'a', 'c', 'b', 'd', 'i', 'e'}

警告：dict_items视图仅在字典中所有元素都可哈希时才可用作集合。对不可哈希值的dict_items视图执行集合运算会抛出TypeError: unhashable type 'T'，T是不符合规则值的类型。

而dict_keys总是可用作集合，因为定义上每个键都是可哈希的。

对视图使用集合运算符查看代码字典内容时会省去大量的循环和条件判断。让Python的高效C实现为你服务吧！

以上便是本章所有内容。

小结

字典是Python的重要版块。经过多年发展，熟悉的{k1: v1, k2: v2}字面量语法增强为支持**解包、模式匹配以及字典推导式。

除了基础的dict，标准库还提供方便、易用的特殊映射，如defaultdict、ChainMap和Counter，都在collections模块中进行定义。有了新的dict实现，OrderedDict不再似过去那般有用，但为向后兼容仍应放在标准库中，并且dict有所不具备的特性，如考虑了== 比较运算中的排序。同时在collections中还有UserDict，用于创建自定义映射的易用基类。

大部份映射中存在的两大方法是setdefault和update。setdefault方法可更新存储可变值的子项，例如，在list值字典中，避免了对同键名的搜索。update允许通过其它映射、提供(key, value对的可迭代对象以及关键字参数批量插入或重写子项。映射构造方法内部也使用了update，允许实例通过映射、迭代对象或关键字参数初始化。从Python 3.9开始，我们还可使用|=运算符更新映射，以及|运算符通过两个映射的并集进行新建。

映射API的一个智能钩子是__missing__方法，允许我们在使用d[k]语法调用__getitem__找不到键时自定义行为。

collections.abc模块提供了Mapping和MutableMapping抽象基类作为标准接口，用益于运行时类型检查。types模块中的MappingProxyType创建不希望意外修改映射的不可变门面。Set和MutableSet也要抽象基类。

字典视图是Python 3中一个伟大的新增内容，去除了Python 2中.keys()、.values()和.items()的内存负载，这些方法当时通过在目标dict实例中复制数据构建列表。此外dict_keys和dict_items类支持了frozenset中最有用的运算符和方法。

作者：AlanHou

来源：稀土掘金