第三章 字典和集合_字典与集合

目录

本章的新内容

现代 dict 语法

字典推导式

字典拆包

使用 | 合并映射

字典的模式匹配

映射类型的标准API

什么是可散列的

常见的映射方法概述

插入或更新可变值

找不到的键的自动处理

defaultdict：解决找不到的键的问题的另一种方案

__missing__ 特殊方法

__missing__ 在标准库中的使用不一致

dict的变体

collections.OrderedDict

collections.ChainMap

collections.Counter

shelve.Shelf

子类化 UserDict 而不是 dict

不可变映射

字典视图

dict 工作原理带来的实际后果

集合论

集合字面量

集合推导式

集合的工作原理带来的实际后果

集合的操作

dict view的集合操作

散列表内部的原理

散列和相等的关系

散列冲突

散列表算法

在散列表中查找元素

字典（dict）中散列表的使用

紧凑的dict如何节省空间并保持顺序

将项目添加到紧凑字典的算法

处理冲突的步骤

紧凑型字典如何增长

共享键的字典

---

Python 基本上是大量包装成语法糖的字典。                                                                

                        ----Lalo Martins, early digital nomad and Pythonista.

我们在所有 Python 程序中都使用了字典。如果没有直接在我们的代码中使用，那么就是间接的，因为 dict 类型是 Python 实现的基本部分。类和实例属性、模块命名空间和函数的关键字参数都是由内存中的字典表示的一些核心 Python 结构。__builtins__.__dict__ 字典存储了所有的内置类型、对象和函数。

由于字典所起到的关键作用，Python 的dicts 得到了高度优化——并且不断的进行改进。散列表是 Python 高性能字典背后的引擎。

其他基于散列表的内置类型是 set 和frozenset。这两种集合类型可能比您在其他流行语言中使用的集合具有更丰富的 API 和运算符。特别是，Python 集合实现了数学集合的所有基本操作，例如取并集、取交集、测试是否是子集等。有了这些操作，我们可以用更明确的方式表示算法，避免在代码中使用大量嵌套循环和条件语句。

以下是本章的简要概述：

• 用于构建和处理字典和映射的现代语法，包括增强的拆包和模式匹配。
• 映射类型的常用方法。
• 对查找不到的键的特殊处理。
• 标准库中 dict 的变体。
• set 和frozenset 类型。

• 散列表实现对集合和字典行为的影响。

本章的新内容

第二版中的大多数更改都涵盖了与映射类型相关的新功能：

• “Modern dict Syntax”涵盖了增强的解包语法和不同的合并映射方式——包括 自 Python 3.9 后，dicts 支持| 和 |= 运算符。
• ““Pattern Matching with Mappings”演示了从 Python 3.10 后，可以使用 match/case 处理映射。
• “collections.OrderedDict” 部分现在侧重于 dict 和 OrderedDict 之间微小却相关的差异——由于 dict 类型 在Python 3.6 后会保持键插入顺序。
• 关于 dict.keys、dict.items 和 dict.values 返回的视图对象的引入的新部分：“Dictionary Views” 和 “Set Operations on dict Views”

dict 和 set 的底层实现仍然依靠散列表，但是 dict的实现有两个重要的优化-----节省内存和保留 dict 中键的插入顺序。 “Practical Consequences of How dict Works”和“Practical Consequences of How Sets Work”总结了这些内容。

Note:

在第二版中添加了 200 多页之后，我将可选部分 Internals of sets and dicts 移到了 fluentpython.com 配套网站。更新和扩展的 18 页帖子包括关于以下内容的解释和图表：

• 散列表算法和数据结构，先从它在set中的使用说起，比较容易理解。
• 在 dict 实例中保留键插入顺序的内存优化（自 Python 3.6 起）。
• 保存实例属性的字典的键共享布局——用户定义对象的 __dict__（在 Python 3.3 中实现的优化）。

现代 dict 语法

接下来的部分描述了用于构建、拆包和处理映射的高级语法功能。其中一些功能在python中并不新鲜，但对您来说可能是全新的。其他需要 Python 3.9（如 | 运算符）或 Python 3.10（如match/case）。让我们从最经典的功能开始。

字典推导式

从 Python 2.7 开始，listcomps 和 genexps 的语法适用于 dict 推导式（以及集合推导式，我们很快就会看到）。dictcomp 通过从任何可迭代对象中获取key:value对来构建 dict 实例。示例 3-1 展示了使用 dict 推导式从相同的元组列表构建两个字典。

>>> dial_codes = [                                                  1
...     (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}  2
>>> 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()                                          3
...     for country, code in sorted(country_dial.items())
...     if code < 70}
{55: 'BRAZIL', 62: 'INDONESIA', 7: 'RUSSIA', 1: 'UNITED STATES'}

1. 像 dial_codes 这样的键值对的可迭代对象可以直接传递给 dict 构造函数，但是……
2. ...在这里我们交换对：key是country，value是code。 
3. 按名称对 country_dial 进行排序，再次反转键值对，将值转换为大写，并过滤code < 70 的项。

如果您习惯了 listcomps，那么很自然就掌握了dictcomps 。如果不是这样，理解语法的传播意味着现在比以往任何时候都更能流利地掌握它。

字典拆包

从 Python 3.5 开始，PEP 448—Additional Unpacking Generalizations以两种方式增强了对映射拆包的支持。

首先，我们可以将 ** 应用于函数调用中的多个参数，需要键都是字符串并且在所有参数中都是唯一的（因为禁止重复的关键字参数）。

>>> 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}

通常新映射的类型将与左操作对象的类型相同——也就是示例中的 d1 --但如果涉及用户定义的类型，它可以是第二个操作对象的类型，根据我们在第 16 章中探讨的运算符重载规则。

要就地更新现有映射，请使用 |=。继续前面的例子，d1 没有改变，但现在是：

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

TIP:

如果您需要维护在 Python 3.8 或更早版本上运行的代码，PEP 584—Add Union Operators To dict 的Motivation 部分提供了合并映射的其他方法的很好的总结。 

现在让我们看看模式匹配如何应用于映射。

字典的模式匹配

match/case 语句支持映射对象的主题。映射的模式看起来像字典的字面量，但它们可以匹配 collections.abc.Mapping 的任何实际或虚拟子类的实例。

在第 2 章中，我们只关注序列模式，但不同类型的模式是可以组合和嵌套的。由于解构的支持，模式匹配是处理嵌套映射和序列等结构化记录的强大工具，我们经常需要从 JSON API 和具有半结构化模式的数据库中读取这样的数据，例如 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]}:  1
            return names
        case {'type': 'book', 'api': 1, 'author': name}:  2
            return [name]
        case {'type': 'book'}:  3
            raise ValueError(f"Invalid 'book' record: {record!r}")
        case {'type': 'movie', 'director': name}:  4
            return [name]
        case _:  5
            raise ValueError(f'Invalid record: {record!r}')

1. 匹配任何具有 'type': 'book', 'api' :2 和 'authors' 键映射到序列的映射。返回序列中的项，作为一个新列表。 
2. 匹配具有 'type': 'book', 'api' :1 和'author' 键映射到任何对象的任何映射。返回包含该对象的列表。
3. 任何其他带有 'type': 'book' 的映射无效，抛出 ValueError异常。
4. 匹配任何映射到 'type': 'movie' 和映射到单个对象的 'director' 键。返回包含该对象的列表。
5. 任何其他主题无效，抛出ValueError异常。

示例 3-2 展示了一些处理半结构化数据（例如 JSON 记录）的实用做法：

• 包括描述记录类型的字段（例如“type”：“movie”）；
• 包括一个标识模式版本的字段（例如'api': 2'），给公共 API 的未来扩容保留空间；
• 有 case 子句来处理特定类型的无效记录（例如“book”），以及一个匹配所有主题的case子句。

现在让我们看看 get_creators 如何处理一些具体的 doctests：

>>> 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'

请注意，模式中键的顺序是无关紧要的，即使主题是OrderedDict类型的 b2也是可以的  。 

与序列模式相反，映射模式在部分匹配时成功。在 doctests 中，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}

在“Automatic Handling of Missing Keys” 中，我们将研究 defaultdict 和其他映射，有时即时键不存在通过 __getitem__（即 d[key]）进行键查找会成功，因为找不到的键可以即时创建。在模式匹配的上下文中，只有当顶部的match主题已经具有匹配语句所需的键时，匹配才会成功。

TIP：

模式匹配中查找不到键的情况不会触发字典的自动处理，因为模式匹配总是使用 d.get(key, sentinel) 方法——其中默认的 sentinel 是一个特殊的标记值，sentinel不会出现在用户的数据里面。

从语法和结构继续，让我们研究映射的 API。

映射类型的标准API

collections.abc模块中有Mapping和MuteableMapping两个抽象基类，用来定义字典和其他类似类型的接口，请参见图 3-1。

ABC 的主要价值是记录和形式化一个映射类型的标准接口，然后它们还可以和isinstance一起被用来判定某个数据是不是广义上的映射类型：

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

TIP:

在 isinstance 内使用 ABC 通常比检查函数参数是否是具体的 dict 类型更好 ，因为这样就可以使用替代映射类型。我们将在第 13 章详细讨论这一点

实现一个自定义映射，扩展 collections.UserDict或者通过组合包装一个dict比子类化ABC抽象类要更容易一些。标准库中的 collections.UserDict 类和所有具体的映射类在它们的实现中封装了一个基本的 dict，而dict是建立在散列表上的。因此，它们都有一个限制，即键必须是可散列的（值不需要是可散列的，只有键需要是可散列的）。如果您需要复习，下一节将进行说明。

什么是可散列的

以下是改编自 Python Glossary 的 可散列定义的一部分：

如果一个对象在其生命周期中，它的散列码永远不会改变（这个对象需要实现 __hash__() 方法），并且可以与其他对象进行比较（它需要一个 __eq__() 方法），那么它就是可散列的。相等的可散列对象必须具有相同的散列值。

数字类型和不可变扁平类型 str 和 bytes 都是可散列的。如果容器类型是不可变的并且所有包含的对象也是可散列的，则这个容器类型是可散列的。frozenset始终是可散列的，因为它包含的每个元素根据定义都必须是可散列的。只有当tuple的所有项都是可散列的时，tuple才是可散列的。参见元组 tt、tl 和 tf：

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

对象的散列码可能会因 Python 版本、机器架构以及出于安全原因添加到散列计算中的盐值不同而有所不同 。正确实现的对象的散列码保证仅在一个 Python 进程中保持不变。

默认情况下，用户定义的类型是可散列的，因为它们的散列值是它们的 id() 并且从object类继承的 __eq__() 方法只会比较对象 id。如果一个对象实现了一个自定义的 __eq__() 并考虑了它的内部状态，那么只有当它的 __hash__() 总是返回相同的散列值时，它才是可散列的。在实践中，这要求 __eq__() 和 __hash__() 只考虑在对象生命周期中永远不会改变的实例属性。

现在让我们回顾一下 Python 中最常用的映射类型的 API：dict、defaultdict 和 OrderedDict。

常见的映射方法概述

映射的基本 API 非常丰富。表 3-1 显示了 dict 实现的方法和两个流行的变体：defaultdict 和 OrderedDict，它们都在collections模块中定义。

Table 3-1. Methods of the mapping types dict, collections.defaultdict, and collections.OrderedDict (common object methods omitted for brevity); optional arguments are enclosed in […]

a:default_factory 并不是一个方法，而是在实例化 defaultdict 时由用户设置的一个可调用对象的属性。

b:OrderedDict.popitem(last=False) 删除插入的第一个项目（FIFO）。最近的 Python 3.10b3 不支持 dict 或 defaultdict 中的最后一个关键字参数。

c:反转运算符在第 16 章中进行了解释。

d.update(m) 处理它的第一个参数 m 的方式是鸭子类型的一个主要例子：它首先检查 m 是否有 keys 方法，如果有，则假定它是一个映射。否则，update() 会去迭代 m，并假设m中的项是 (key, value) 对。大多数 Python 映射的构造函数在内部使用 update() 函数的逻辑，这意味着它们可以从其他映射或任何生成（key,value）对的可迭代对象进行初始化.

一个微妙的映射方法是 setdefault()。当我们需要就地更新项目的值时，它避免了冗余的键查找。下一节将展示如何使用它。

插入或更新可变值

根据 Python 的快速失败哲学，当 k 不是存在的键时，使用 d[k]访问dict会抛出异常。Pythonistas 知道 d.get(k, default) 是 d[k] 的替代方法，因为使用默认值比处理 KeyError 更方便。但是，当您检索可变值​​并想要更新它时，有更好的方法。

考虑一个用于索引文本的脚本，生成一个映射，其中每个键是一个词，值是该词出现的位置列表，如示例 3-3 所示。

例 3-3。示例 3-4 处理 Python Zen 的部分输出；每行显示一个单词和一个成对编码的出现列表：(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)
            # this is ugly; coded like this to make a point
            occurrences = index.get(word, [])  1
            occurrences.append(location)       2
            index[word] = occurrences          3
 
# display in alphabetical order
for word in sorted(index, key=str.upper):  4
    print(word, index[word])

1. 获取单词的occurrences列表，如果未找到，则返回 [ ]。 
2. 将新位置附加到occurrences。
3. 将更改的occurrences放入index字典中；这需要通过index进行第二次搜索。
4. 在 sorted 的 key= 参数中，我没有调用 str.upper，只是传递对该方法的引用，以便 sorted 函数可以使用它来规范化word的排序

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

例 3-5。 index.py 使用 dict.setdefault 从单行索引中获取和更新单词occurrences列表；与示例 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)  1
 
# display in alphabetical order
for word in sorted(index, key=str.upper):
    print(word, index[word])

1：获取单词的occurrences列表，如果没有找到，则将其设置为 []； setdefault 返回该值，因此无需第二次搜索即可对其进行更新。

换句话说，这样写

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

和这样写

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

执行效果是一样的，除了后者的代码至少执行两次键搜索操作——如果没有键不存在，则执行三次查找——而 setdefault 只需一次查找即可完成所有操作。

一个相关的问题，在任何查找中处理不存在的键（不仅仅是在插入时），是下一节的主题。

不存在的键的自动处理

有时，当搜索不存在的键时，映射返回一些虚构值会很方便。有两种主要方法：一种是使用 defaultdict 。另一种是子类化 dict 或任何其他映射类型并实现 __missing__ 方法。接下来将介绍这两种解决方案。

defaultdict：解决不存在的键的问题的另一种方案

每当使用 d[k] 语法搜索不存在的键时， collections.defaultdict 实例都会根据需要创建具有默认值的项。示例 3-6 使用 defaultdict 为示例 3-5 中的单词索引任务提供了另一种优雅的解决方案。

下面是它的工作原理：当实例化一个 defaultdict 时，只要向 __getitem__ 传递一个不存在的键参数，defaultdict就会根据传入的可调用对象参数来生成一个默认值。

例如，给定创建为 dd = defaultdict(list) 的 defaultdict，如果键 'new-key' 不在 dd 中，则表达式 dd['new-key'] 执行以下步骤：

1. 调用 list() 创建一个新列表
2. 将 'new-key' 作为键，创建的新列表作为值 插入到 dd 中。
3. 返回一个对该列表的引用。

生成默认值的可调用对象保存在名为 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)     1
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)  2
 
# display in alphabetical order
for word in sorted(index, key=str.upper):
    print(word, index[word])

1.  使用list构造函数作为 default_factory 创建一个 defaultdict。
2. 如果 word 最初不在索引中，则调用 default_factory 以生成该键对应的值，在本例中，它是一个空列表，然后赋值给 index[word] 并返回，因此 .append(location) 操作总是成功。

如果没有提供 default_factory，则程序会因键不存在而抛出KeyError异常。

Warning:

defaultdict 的 default_factory 仅用于为 __getitem__ 调用提供默认值，而不是为其他方法提供默认值。例如，如果 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异常。

假设您想要一个映射，其中在查找时将键转换为 str 。一个具体的用例是物联网的设备库：其中具有通用 I/O 引脚（例如，Raspberry Pi 或 Arduino）的可编程板由具有 my_board.pins 属性的 Board 类表示，该属性是物理引脚标识符到引脚软件对象的映射。物理引脚标识符可能只是一个数字或字符串，如“A0”或“P9_12”。为了保持一致性，board.pins 中的所有键都是字符串是可取的，但通过数字查找引脚也很方便，如 my_arduino.pin[13]，这样初学者在想要使 Arduino 引脚 13 上的 LED 闪烁时不会发生问题。示例 3-7 展示了这种映射的工作原理。

例 3-7。搜索非字符串键时，如果找不到键，StrKeyDict0 将其转换为 str进行再次查找

Tests for item retrieval using `d[key]` notation::
 
    >>> d = StrKeyDict0([('2', 'two'), ('4', 'four')])
    >>> d['2']
    'two'
    >>> d[4]
    'four'
    >>> d[1]
    Traceback (most recent call last):
      ...
    KeyError: '1'
 
Tests for item retrieval using `d.get(key)` notation::
 
    >>> d.get('2')
    'two'
    >>> d.get(4)
    'four'
    >>> d.get(1, 'N/A')
    'N/A'
 
 
Tests for the `in` operator::
 
    >>> 2 in d
    True
    >>> 1 in d
    False

示例 3-8 实现了一个 StrKeyDict0 类，它通过了前面的 doctests。

TIP:

创建用户定义的映射类型的更好方法是继承 collections.UserDict 而不是 dict（我们将在示例 3-9 中做）。在这里，我们对 dict 进行子类化只是为了表明内置 dict.__getitem__ 方法支持 __missing__ 。 

例 3-8。 StrKeyDict0 在查找时将非字符串键转换为 str（参见示例 3-7 中的测试）

class StrKeyDict0(dict):  1
 
    def __missing__(self, key):
        if isinstance(key, str):  2
            raise KeyError(key)
        return self[str(key)]  3
 
    def get(self, key, default=None):
        try:
            return self[key]  4
        except KeyError:
            return default  5
 
    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys()  6
 
 
 
    #plain __contains__
    def __contains__(self, key):
        try:
            self[key]
        except KeyError:
            return False
        else:
            return True

1. StrKeyDict0 继承自 dict。
2. 检查 key 是否已经是 str 。如果是，并且找不到该键，则抛出 KeyError异常。 
3. 使用 key 构建 一个str 并查找它
4. get 方法通过使用 self[key] 符号委托给 __getitem__；这样找不到键就可以触发 __missing__ 了
5. 如果抛出 KeyError异常 ，则 __missing__ 已经失败，因此我们返回default。
6. 搜索未修改的键（实例可能包含非 str 键），然后搜索使用键构建的 str类型的键。

现在思考为什么在 __missing__ 实现中需要测试 isinstance(key, str)。如果没有那个测试，我们的 __missing__ 方法对于任何键 k——str 或不是 str——只要 str(k) 是一个存在的键就可以正常工作。但是如果 str(k) 不是存在的键，就会产生无限递归。在 __missing__ 的最后一行，self[str(key)] 会调用 __getitem__ 并传递那个 str 键，而后者又会再次调用 __missing__。

__contains__ 方法也是本例中字典的一致行为所必需的，因为k in d 操作调用了这个方法，但是从 dict 继承的方法没有回退调用 __missing__ 。在我们的 __contains__ 实现中有一个微妙的细节：我们不以通常的 Pythonic 方式检查key——k in my_dict :因为 str(key) in self  会递归调用 __contains__。我们通过在 self.keys() 中显式查找键来避免这种情况。

像 k in my_dict.keys()这样的搜索在 Python 3 中即使对于非常大的映射也是高效的，因为 dict.keys() 返回一个类似于集合的视图，我们将在“Set Operations on dict Views”中看到.但是，请记住 k in my_dict 会做相同的工作，并且速度更快，因为它避免了查找 .keys 方法的属性查找。

在示例 3-8 中的 __contains__ 方法中使用 self.keys() 是有特殊原因的.检查未修改的键——key in self.keys() ——对于正确性是必要的，因为 StrKeyDict0 不强制字典中的所有键都必须是 str 类型。这个简单示例的唯一目标是使搜索“更友好”而不是强制要求类型。

Warning:

从标准库映射派生的用户定义的类可能会也可能不会在其 __getitem__、get 或 __contains__ 实现中使用 __missing__ 作为后备机制。如下一节所述。

__missing__ 在标准库中的使用不一致

根据以下场景，思考不存在的键查找是否会受影响。

dict 的子类：

        dict 的子类，仅实现 __missing__ 而没有实现其他方法。在这种情况下， __missing__ 只能在 d[k] 调用起作用，这将使用从 dict 继承的 __getitem__。

collections.UserDict的子类：

        同样， UserDict 的子类仅实现 __missing__ 而没有实现其他方法。从 UserDict 继承的 get 方法调用 __getitem__。这意味着可以调用 __missing__ 来处理 d[k] 和 d.get(k) 的查找。

abc.Mapping 子类，并实现了最简单的__getitem__：

        abc.Mapping 的最小实现子类，实现 __missing__ 和所需的抽象方法， __getitem__ 实现不使用__missing__ 。__missing__ 方法永远不会在此类中触发

abc.Mapping 子类，其__getitem__ 的实现调用了__missing__：

        abc.Mapping 的最小子类，实现 __missing__ 和所需的抽象方法，包括调用 __missing__ 的 __getitem__ 实现。__missing__ 方法在此类中触发，用于使用 d[k]、d.get(k) 和 k in d 进行的不存在的键查找。

请参阅示例代码存储库中的 missing.py 以了解此处描述的场景的演示。

刚刚描述的四个场景假设了完成最小的实现。如果您的子类实现了 __getitem__、get 和 __contains__，那么您可以根据您的需要让这些方法的实现使用或不使用 __missing__。本节的重点是表明在将标准库映射子类化以使用 __missing__ 时必须小心，因为基类默认支持不同的行为。

不要忘记 setdafault 和 update 的行为也受键查找的影响。最后，根据你的 __missing__ 的逻辑，你可能需要在 __setitem__ 中实现特殊的逻辑，以避免不一致或令人惊讶的行为。我们将在 “Subclassing UserDict Instead of dict”中看到这样的例子。

到目前为止，我们已经介绍了 dict 和 defaultdict 映射类型，但是标准库还附带了其他映射实现，我们接下来讨论。

dict的变体

本节概述了标准库中包含的映射类型，除了 defaultdict，已在“defaultdict: Another Take on Missing Keys”进行描述。

collections.OrderedDict

自 Python 3.6 以来，内置的dict 也保持的键排序，使用 OrderedDict 的最常见原因是编写向后兼容早期 Python 版本的代码。话虽如此，Python 的文档列出了 dict 和 OrderedDict 之间的一些剩余差异，我在这里引用了这些差异——仅根据日常使用中的相关性对元素重新排序：

• OrderedDict 的相等操作检查匹配键的顺序。
• OrderedDict 的 popitem() 方法具有不同的签名。它接受一个可选参数来指定pop哪个元素。
• 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['b'] = -1
>>> d1
{'a': 1, 'b': -1}
>>> d2
{'a': 2, 'b': 4, 'c': 6}

 ChainMap 可用于为具有嵌套作用域的语言实现解释器，其中每个映射代表一个作用域上下文，从最内层的闭包作用域到最外层的作用域。 The “ChainMap objects” section of the collections docs 有几个 ChainMap 使用示例，包括这个片段，其灵感来自 Python 中变量查找的基本规则：

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

collections.Counter

保存每个键的整数计数的映射。更新存在的键会增加其计数。这可用于计算可散列对象的实例或作为多重集合（见下文）。Counter 实现了 + 和 - 运算符来组合计数，以及其他有用的方法，例如 most_common([n])，它返回一个有序的元组列表，其中包含 n 个最常见元素目及其计数；请参阅 documentation。这是用于计算单词中字母的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) 仅显示三个计数。 

要将 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 模块的文档提供了更多详细信息和一些注意事项。

WARNING:ython 的 pickle 在最简单的情况下很容易使用，但有几个缺点。在采用任何涉及 pickle 的解决方案之前，请阅读 Ned Batchelder 的  Pickle’s nine flaws 。在他的帖子中，Ned 提到了其他需要考虑的序列化格式。

OrderedDict、ChainMap、Counter 和 Shelf 都可以使用，但也可以通过子类化进行自定义。相比之下， UserDict 仅用作要扩展的基类。

子类化 UserDict 而不是 dict

最好通过继承 collections.UserDict 而不是 dict 来创建新的映射类型。这体现在我们扩展示例 3-8 中的 StrKeyDict0 以确保所有添加到映射中的键都存储为 str 类型时。

子类化 UserDict 而不是 dict 更好的主要原因是内置函数有一些实现的快捷方式，最终需要我们重写这些方法，从 UserDict 继承这些方法没有任何问题。

请注意， UserDict 没有 继承dict，而是使用组合的方式：它有一个内部的 dict 实例 data，它保存实际的数据。与示例 3-8 相比，这避免了实现 __setitem__ 等特殊方法时出现不需要的递归，并简化了 __contains__ 的编码。

由于使用了 UserDict，StrKeyDict（示例 3-9）比 StrKeyDict0（示例 3-8）更简洁，并且完成了更多的功能：它将所有键存储为 str ，并且使用包含非字符串键的数据构建或更新实例时不会发生意外情况。

例 3-9。 StrKeyDict 总是在插入、更新和查找时将非字符串键转换为 str

import collections
 
 
class StrKeyDict(collections.UserDict):  1
 
    def __missing__(self, key):  2
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]
 
    def __contains__(self, key):
        return str(key) in self.data  3
 
    def __setitem__(self, key, item):
        self.data[str(key)] = item   4

1. StrKeyDict 继承了 UserDict。 
2. __missing__ 与示例 3-8 中的完全相同。
3. __contains__ 更简单：我们可以假设所有存储的键都是 str 并且我们可以检查 self.data 而不是像我们在 StrKeyDict0 中那样调用 self.keys() 
4. __setitem__ 将键转换为 str再进行存储。当我们可以委托给 self.data 属性时，重写这个方法会更容易。

因为 UserDict 继承自 abc.MutableMapping，StrKeyDict 的其余方法继承自 UserDict、MutableMapping 或 Mapping，从而成为完整映射。尽管MutableMapping是抽象基类 (ABC)，它有几个实用的具体方法。以下两个方法值得注意：

MutableMapping.update：

这个强大的方法可以直接调用，但也被 __init__ 用来从其他的映射、由（key,value）对组成的可迭代对象和关键字参数来加载实例。因为它使用 self[key] = value 来添加元素，所以它调用了我们实现的 __setitem__ 方法。

Mapping.get：

在 StrKeyDict0（示例 3-8）中，我们必须编写自己的 get 方法以返回与 __getitem__ 相同的结果，但是在示例 3-9 中，我们继承了 Mapping.get，它的实现与 StrKeyDict0.get 完全一样（参见 Python source code）。

TIP:

Antoine Pitrou 撰写了 PEP 455 — Adding a key-transforming dictionary to collections以使用 TransformDict 增强集合模块,这比 StrKeyDict 更通用，并在应用转换之前保留提供的键。PEP 455 于 2015 年 5 月被拒绝——请参阅 Raymond Hettinger 的 rejection message.。为了试验 TransformDict，我将 Pitrou 的补丁从 issue18986 提取到一个独立模块（Fluent Python Second Edition 代码库中的 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]  1
'A'
>>> d_proxy[2] = 'x'  2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment
>>> d[2] = 'B'
>>> d_proxy  3
mappingproxy({1: 'A', 2: 'B'})
>>> d_proxy[2]
'B'
>>>

1. d 中的元素可以通过 d_proxy 看到。 
2. 不能通过 d_proxy 进行更改。
3. d_proxy 是动态的：d 中的任何变化都会被反映到d_proxy中。

以下是在硬件编程场景中如何在实践中使用它：具体 Board 子类中的构造函数将使用 pin 对象填充私有映射，并通过实现为 mappingproxy 的公共 .pins 属性将其公开给 API 的客户端。这样客户端就不会意外添加、删除或更改引脚

接下来，我们将介绍视图——它允许对 dict 进行高性能操作，无需进行不必要的数据复制。

字典视图

dict 的实例方法 .keys()、.values() 和 .items() 分别返回名为 dict_keys、dict_values 和 dict_items 的类的实例。这些字典视图是 dict 实现中使用的内部数据结构的只读投影。它们避免了的等效 Python 2 方法复制目标字典中已有数据并返回列表的内存开销，并且它们还替换了返回迭代器的旧方法。

下面示例展示了所有的字典视图支持的一些基本操作：

例 3-11。 .values() 方法返回字典中值的视图。

>>> d = dict(a=10, b=20, c=30)
>>> values = d.values()
>>> values
dict_values([10, 20, 30])  1
>>> len(values)  2
3
>>> list(values)  3
[10, 20, 30]
>>> reversed(values)  4
<dict_reversevalueiterator object at 0x10e9e7310>
>>> values[0] 5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'dict_values' object is not subscriptable

1. 视图对象的 repr 表示。
2.  我们可以通过len查询视图的 长度。
3. 视图是可迭代的，因此很容易从它们创建列表。
4. 视图实现 __reversed__特殊方法，该方法返回一个自定义迭代器。
5. 我们不能使用 [] 从视图中获取单个元素。

视图对象是一个动态代理。如果视图所代理的dict 发生变化，可以立即通过现有视图查看更新。继续示例 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 "<stdin>", line 1, in <module>
TypeError: cannot create 'dict_values' instances

dict_values 类是最简单的字典视图——它只实现了 __len__、__iter__ 和 __reversed__ 特殊方法。，dict_keys 和 dict_items 除了这些方法外还实现了几个 set 方法，几乎​​和frozenset 类支持的方法一样多。在我们介绍了集合之后，我们将在“字典视图上的集合操作”中更多地讨论 dict_keys 和 dict_items。

现在让我们看看 dict 在幕后实现的方式所总结的一些规则和技巧。

dict 工作原理带来的实际后果

Python 的 dict 的哈希表实现非常高效，并且了解这种设计的带来的实际效果很重要。

• 键必须是可散列的对象。他们必须实现正确的 __hash__ 和 __eq__ 方法，如What Is Hashable”中所述。
• 通过键访问值的操作非常快。一个 dict 可能有数百万个键，但 Python 可以通过计算键的散列码并推导出其在散列表中的索引偏移量来直接定位键，可能只会有少量尝试找到匹配元素的开销。
• 键排序作为 CPython 3.6 中 实现更紧凑的dict 的内存布局的副作用而保留，在 3.7 中成为官方语言功能。
• 尽管采用了新的紧凑布局，但 dicts 不可避免地具有显著的内存开销。最紧凑的容器内部数据结构使用了指向项的指针数组。相比之下，散列表每个元素需要存储更多数据，而 Python 需要将散列表中至少 1/3 的行保留为空以保持高效。
• 为了节省内存，请避免在 __init__ 方法之外创建实例属性。

最后一点关于实例属性的说明来自这样一个事实， Python 的默认行为是将实例属性存储在一个特殊的 __dict__ 属性中，这个属性是附加到每个实例的一个 dict。由于 PEP 412——键共享字典是在 Python 3.3 中实现的，类的实例可以共享一个公共散列表，这个散列表存储在类中。该公共散列表由每个实例的 __dict__ 共享，当 __init__ 返回时，实例具有与类的第一个实例相同的属性名称。每个实例的__dict__ 只需将其自己的属性值保存为一个简单的指针数组。在 __init__ 之后添加实例属性会强制 Python 为该实例的 __dict__ 创建一个新的散列表（这是 Python 3.3 之前所有实例的默认行为）。根据 PEP 412，这种优化将面向对象程序的内存使用降低了 10% 到 20%。

字典的紧凑布局和键共享优化的细节相当复杂。有关更多信息，请阅读 fluentpython.com 上的“Internals of sets and dicts” 。

现在让我们深入研究集合

集合论

集合在 Python 中并不新鲜，但使用率仍然较低。 set 类型和它的不可变的兄弟frozenset 首先作为模块出现在Python 2.3 标准库中，并在Python 2.6 中升级为内置函数。

Note:

在本书中，我使用“set”这个词来指代 set 和frozenset。在专门谈论 set 类时，我使用了等宽字体：set。

一个set是不同对象的集合。因此，集合可以用来去重

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

TIP:

如果您想删除重复项但同时保留每个元素第一次出现的顺序，可以使用 dict，如下所示：

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

集合中的元素必须是可散列的。但是集合本身是不可散列的，因此您不能使用嵌套的集合实例构建集合。但是frozenset 是可散列的，因此您可以在集合中包含frozenset 元素。

除了强制唯一性之外，集合类型将许多集合操作实现为中缀运算符，所以，给定两个集合 a 和 b，a | b 返回它们的并集， a & b 计算交集， a - b 计算差，a ^ b 计算对称差（异或）。巧妙地使用集合操作可以减少 Python 程序的行数和执行时间，同时删除循环和条件逻辑使代码更易于阅读和推理。

例如，假设您有大量电子邮件地址（haystack）和一组较小的地址（needles），您需要计算haystack中出现的needles。使用集合交集（& 运算符），您可以只写一行代码就实现该功能（参见示例 3-12）。

例 3-12。计算haystack中needles的出现次数，两个变量类型都是set

found = len(needles & haystack)

如果没有交集运算符，您将需要编写示例 3-13 来完成与示例 3-12 相同的任务。

例 3-13。计算haystack中needles的出现次数（最终结果与示例 3-12 相同） 

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

示例 3-12 的运行速度比示例 3-13 稍快。另一方面，示例 3-13 适用于任何可迭代对象 Needles 和 haystack，而示例 3-12 要求两者都是集合。但是，如果您手头没有 Set，您可以随时动态构建集合，如示例 3-14 所示。

例 3-14。计算haystack中needles出现次数；这些行适用于任何可迭代类型

found = len(set(needles) & set(haystack))
 
# another way:
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 的情况下，改变现有的集合。我们将很快讨论这些操作，但需要先看一下相关的语法。

集合字面量

集合字面量的语法——{1}、{1、2} 等——看起来和数学符号完全一样，但有一个重要的例外：空集没有字面量符号，所以空集必须是set()。

语法怪癖：

要创建一个空的集合，您应该使用不带参数的构造函数：set()。如果使用 {}，则您正在创建一个空字典——这在 Python 3 中没有改变。 

在 Python 3 中，集合的标准字符串表示总是使用 {...} 表示法，除了空集：

>>> s = {1}
>>> type(s)
<class 'set'>
>>> 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 构造函数调用。请注意控制台会话中的输出：

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

说到语法，listcomps 也适用于构建集合。

集合推导式

集合推导式 (setcomps) 早在 Python 2.7 中就添加了，以及我们在“dict Comprehensions”中看到的 dictcomps。示例 3-15 展示了如何操作。

例 3-15。构建一组在其 Unicode 名称中包含“SIGN”一词的 Latin-1 字符

>>> from unicodedata import name  1
>>> {chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i),'')}  2
{'§', '=', '¢', '#', '¤', '<', '¥', 'µ', '×', '$', '¶', '£', '©',
'°', '+', '÷', '±', '>', '¬', '®', '%'}

1. 从 unicodedata 导入 name 函数以获取字符名称。
2. 使用从 32 到 255 的代码且其名称中带有“SIGN”一词构建集合。

由于“什么是可散列的”中提到的散列加盐，每个 Python 进程的输出顺序都会发生变化。

介绍完语法问题后，现在让我们考虑集合的行为。

集合的工作原理带来的实际后果

set 和frozenset 类型都是用散列表实现的。这会带来下面的影响：

• 集合元素必须是可散列的对象。必须实现正确的 __hash__ 和 __eq__ 方法，如“什么是可散列的”中所述。
• 集合的成员关系测试非常高效。一个集合可能有数百万个元素，但可以通过计算其散列值并计算索引偏移量来直接定位一个元素，可能会有少量尝试找到匹配元素或用尽搜索的开销。
• 与指向其元素的指针的低级数组（这会更紧凑，但搜索少数元素的速度也会慢得多）相比，集合具有显着的内存开销。
• 元素排序取决于插入顺序，但是并不总是这样。如果两个元素不同但具有相同的散列值，则它们的位置取决于添加顺序的先后。
• 向集合中添加元素可能会改变现有元素的顺序。这是因为如果散列表的使用率超过 ⅔ ，则算法效率会降低，因此 Python 可能需要随着表的增长而移动和调整表的大小。发生这种情况时，元素会被重新插入并且它们的相对顺序可能会发生变化。

有关详细信息，请参阅 fluentpython.com 上的Internals of sets and dicts 。

现在让我们回顾一下集合提供的丰富的API。

集合的操作

图 3-2 概述了可用于可变和不可变集合的方法。其中许多是重载运算符（例如 & 和 >=）的特殊方法。表 3-2 显示了在 Python 中具有相应运算符或方法的数学集合运算符。请注意，某些运算符和方法对目标集合执行就地更改（例如，&=、difference_update 等）。这样的操作在数学集合的理想世界中没有意义，并且在frozenset中没有实现这些操作。

TIP:

表 3-2 中的中缀运算符要求两个操作数均为集合类型，但其他方法都接收一个或多个可迭代对象作为参数。例如，要生成 a、b、c 和 d 四个集合的并集，可以调用 a.union(b, c, d)，其中 a 必须是一个集合，但 b、c 和 d 可以是生成可散列项的任何类型的可迭代对象。如果您需要将4个可迭代对象的并集创建一个新集合，而不是更新现有集合，Python 3.5后，可以这样编写 {*a, *b, *c, *d} ，这要归功于 PEP 448—Additional Unpacking Generalizations。

 表 3-3 列出了集合谓词：返回 True 或 False 的运算符和方法。

除了源自数学集合论的运算符和方法之外，集合类型还实现了其他实际使用的方法，总结在表 3-4 中。

这完成了我们对集合特征的概述。正如“字典视图”中所承诺的那样，我们现在将看到两种字典视图类型的行为与frozenset非常相似。 

dict view的集合操作

表 3-5 显示 dict 方法 .keys() 和 .items() 返回的视图对象与frozenset 非常相似。

特别是 dict_keys 和 dict_items 实现了特殊的方法来支持强大的集合运算符 & (intersection交集), | （并集），-（差）和 ^（对称差-异或）。

这意味着，例如，查找两个字典中的共同键就像这样简单：

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

注意 & 操作的返回值是一个集合。更优秀的是：字典视图中的集合运算符与集合实例兼容。看一下这个：

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

WARNING：

dict_items 视图仅在 dict 中的所有值都是可散列的情况下才能进行集合操作。尝试对具有不可散列值的 dict_items 视图进行集合操作会引发 TypeError: unhashable type 'T'，其中 T 是不可散列的类型。

另一方面，dict_keys 视图总是可以用作一个集合，因为根据定义，每个键都是可散列的。

在检查代码中字典的内容时，将集合运算符与视图一起使用将节省大量循环和 if。让 Python 在 C 中的高效实现为您提供更高效服务！

散列表内部的原理

散列表是一项了不起的发明。让我们看看在向集合中添加元素时如何使用散列表。

在这里我们创建了一个工作日缩写的字典：

>>> workdays = {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}
>>> workdays
{'Tue', 'Mon', 'Wed', 'Fri', 'Thu'}

Python 集合的核心数据结构是一个至少有 8 行的散列表，一般散列表中的行称为桶。包含工作日的散列表如下图所示：

每个桶有两个字段：散列值和指向元素值的指针。空桶在散列值字段中被置为-1。排序看起来是随机的。

在64 位 CPU 的 CPython 中，集合中的每个桶都有两个字段：一个 64 位散列值和一个指向元素值的 64 位指针——元素本身被存储在内存中其他地方。因为每个桶大小都是固定的，访问一个桶可以使用偏移量。在上表中字段不包含0-7的索引。

在介绍散列表算法之前，我们需要更多地了解散列值，以及它们与相等性的关系。

散列和相等的关系

内置函数hash() 可以直接计算内置类型的散列值，如果是用户定义类型则去调用特殊方法__hash__ 。如果两个对象是相等的，则它们的散列值也必须相等，否则散列表算法不起作用。例如，如果 1 == 1.0 为 True，那么hash(1) == hash(1.0) 也必须为 True，即使 int 和 float 的内部表示差异很大。

此外，为了提高散列表索引的有效性，散列值应该尽可能地在索引中分散分布。这意味着，在理想情况下相似但不相等的对象的散列值的差异会最明显。请注意 1 和 1.0 的散列值是相同的，但是1和1.0001、1.0002 、 1.0003 的散码则具有明显的差异。

32-bit Python build
1        00000000000000000000000000000001
                                          != 0
1.0      00000000000000000000000000000001
------------------------------------------------
1.0      00000000000000000000000000000001
           ! !!! ! !! ! !    ! ! !! !!!   != 16
1.0001   00101110101101010000101011011101
------------------------------------------------
1.0001   00101110101101010000101011011101
          !!!  !!!! !!!!!   !!!!! !!  !   != 20
1.0002   01011101011010100001010110111001
------------------------------------------------
1.0002   01011101011010100001010110111001
          ! !   ! !!! ! !  !! ! !  ! !!!! != 17
1.0003   00001100000111110010000010010110
------------------------------------------------

在 32 位 Python 版本上比较 1、1.0001、1.0002 和 1.0003 的位模式下的散列差异

从 Python 3.3 开始，计算 str、bytes 和 datetime 对象的散列值时会包含随机盐值，如 Issue 13703—Hash collision security issue所述。盐值在 一个Python进程中是固定的，但在解释器运行时会发生变化。在 PEP-456 中，Python 3.4 采用了 SipHash 加密函数来计算 str 和 bytes 对象的散列值。随机盐值和 SipHash 是防止 DoS 攻击的安全措施。详细信息可以查看 the __hash__ special method的文档。

散列冲突

如前所述，在 64 位 CPython 上，散列值是一个 64 位的数字，一共有2的64次方种可能——这个值大于 10的19次方。但是大多数 Python 类型可以表示比10的19次方更多种不同的值。例如，由随机选取的 10 个 ASCII 可打印字符组成的字符串有 100的10次方个可能的值——大于2的66次方。因此，对象的散列值通常比实际对象值包含的信息少。这意味着不同的对象可能具有相同的散列值。

实现正确时，散列算法保证不同的散列值总是对应不同的对象，但反之则不然：不同的对象并不总是具有不同的散列值。当不同的对象具有相同的散列值时，就产生了散列冲突。

散列表算法

我们将首先关注 set 的内部结构，然后使用相同的概念来理解dict。这仅仅是 Python使用散列表来实现集合的简化视图。更多细节请参阅 CPython 的 set 和frozenset 的注释源代码Include/setobject.h 和 Objects/setobject.c.

让我们看看 Python 是如何一步步构建像 {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'} 这样的集合的。该算法由下面的流程图说明，并进行描述。

第0步：构建散列表

如前所述，集合的哈希表被初始化为8个空的桶。随着元素的添加，Python 确保至少 1/3 的桶是空的——当需要更多空间时，将散列表的大小加倍。每个桶的散列码字段被初始化为-1，表示“没有散列码”。

第1步：计算元素的散列值

根据字面量 {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}，Python 获取第一个元素 'Mon' 的散列值。例如，这里有一个真实的 'Mon' 散列值——你可能会得到不同的结果，因为 Python 使用加随机的盐值来计算字符串的散列值：

>>> hash('Mon')
4199492796428269555

第2步：用散列值衍生的索引探测散列表

Python 获取散列值和表长度的模来获得散列表索引。当前表长度为8，模为3：

>>> 4199492796428269555 % 8
3

探测包括从散列计算索引，然后查看散列表对应的桶。在这个例子，Python 查看偏移量 为3 的桶，并在其散列码字段中获取其散列码为 -1，也就是空桶。

第3步：把元素放入空桶中

Python 将新元素 4199492796428269555 的散列值存储在偏移量 为3 的桶对应的散列值字段，并在元素字段中存储一个指向字符串对象“Mon”的指针。下图展示了散列表的当前状态:

第四步：剩余的步骤

下面是第二个元素“Tue”，重复上面的步骤 1、2、3。 'Tue' 的散列值为 2414279730484651250，其索引为 2。

>>> hash('Tue')
2414279730484651250
>>> hash('Tue') % 8
2

散列值和指向元素 'Tue' 的指针放置在偏移量为2的桶中，该桶也是空的。当前状态如下：

发生冲突的步骤：

将 'Wed' 添加到集合中时，Python 计算散列值 -5145319347887138165 和并得到索引3。Python 探测桶3 并发现它已经被占用。但是存储的散列值4199492796428269555 和‘Wed’的散列值是不同的。如“散列与相等”中所述，如果两个对象具有不同的散列值，则它们的值也不同。这是一个索引冲突。然后 Python 探测下一个存储桶并发现它是空的。所以 'Wed' 被放置在索引为4的桶，如下图所示：

添加下一个元素 'Thu' 则很顺利：没有冲突，它被存放在索引 7的桶中。放置元素“Fri”更有趣。它的散列值7021641685991143771对应索引 3，它被 'Mon' 占据。探测下一个存储桶，也就是第四个桶，Python 找到存储在那里的 'Wed' 的散列值。由于散列值不匹配，所以又发生了一次索引冲突。Python 探测下一个存储桶。它是空的，所以“Fri”存放在索引 5 处。散列表的结束状态如下图所示：

当探测到的桶中有一个元素冲突且散列码值相等时，Python 还需要比较实际的对象值。这是因为，如“散列冲突”部分所述，两个不同的对象可能具有相同的散列值——尽管这对于字符串来说很少见，这要归功于 Siphash 算法的质量。这解释了为什么可散列对象必须同时实现 __hash__ 和 __eq__。

如果一个新元素被添加到我们的示例散列表中，它将超过 ⅔ 的容量，因此增加了索引冲突的机会。为了防止这种情况发生，Python 会分配一个包含 16 个桶的新散列表，并在新表重新插入所有元素。

插入操作看起来似乎需要大量工作，但即使在一个集合中有数百万个元素，绝大多数插入操作不会产生冲突，每次全部插入操作产生的冲突次数平均下来不过在1次到2次之间。在正常情况下，即使是最不幸的元素也可以在处理几次冲突后完成插入。

现在，按照我们目前所知，请按照流程图在不使用计算机的情况下回答以下问题。

根据下面的集合，将整数 1 添加到其中会发生什么？

>>> s = {1.0, 2.0, 3.0}
>>> s.add(1)

现在 s 中有多少个元素？ 1 会替换元素 1.0 吗？得到答案后，请使用 Python 控制台进行验证。

在散列表中查找元素

考虑使用之前的工作日集合与散列表。 'Sat' 在里面吗？这是表达式 'Sat' in workdays的最简单执行路径：

1. 调用 hash('Sat') 获取散列值。假设它是 4910012646790914166
2. 使用 hash_code % table_size 从散列值中计算出其在散列表中的索引。本例索引为 6。
3. 探针偏移量为6的桶：它是空的。这意味着“Sat”不在集合中。返回False。

现在考虑集合中存在的元素的最简单路径。执行‘Thu’ in workdays语句的过程如下：

1. 调用 hash('Thu')。假设结果是 6166047609348267525。
2. 计算索引：6166047609348267525 % 8 的结果是 5
3. 探测偏移量为5的桶：比较散列值--相等，比较对象的值--相等。返回True.

散列冲突的处理方式与添加元素时描述的方式相同。事实上，插入的流程图也适用于搜索，除了终端节点（绿色的带圆角的矩形）不同。如果找到空桶，则该元素不存在，因此 Python 返回 False；当散列码和搜索元素的值都匹配散列表中的元素时，返回True。

字典（dict）中散列表的使用

自 2012 年以来，dict 类型的实现有两个主要优化以减少内存使用。第一个是  PEP 412 — Key-Sharing Dictionary，并在 Python 3.3 中实现。第二个叫做“compact dict"，在Python 3.6正式上线。作为副作用，紧凑型字典空间优化保留了键插入顺序。在接下来的部分中，为了更容易展示，我们将按下面顺序讨论紧凑字典和新的密钥共享方案。

紧凑的dict如何节省空间并保持顺序

注意：

这是 Python dict 实现的高级解释。一个区别是 dict 中散列表的实际可用部分是 ⅓，而不是集合中的 ⅔。在我的示例 dict 中，实际的 ⅓ 分数需要 16 个桶来容纳 4 个项目，并且本节中的图表会变得太高，所以我假装在这些解释中可用的分数是 ⅔。Objects/dictobject.c 中的一条评论解释说，⅓ 和 ⅔ 之间的任何分数“在实践中似乎都运行良好”

下例为一个包含从“Mon”到“Thu”的工作日缩写名称以及每天参加游泳课的学生人数的字典：

>>> swimmers = {'Mon': 14, 'Tue': 12, 'Wed': 14, 'Thu': 11}

在紧凑字典优化之前，swimmers 字典底层的散列表看起来像下图所示。如您所见，在 64 位 Python 中，每个桶包含三个 64 位字段：键的散列值、指向键对象的指针和指向值对象的指针。也就是每个桶的大小为 24 个字节（192bit）。

前两个字段和set中散列表的实现是一样的。为了查找键，Python 计算键的散列值，推导出键的索引，然后探查散列表以找到具有匹配散列值和匹配键对象的桶。第三个字段提供 dict 的主要功能：将键映射到一个任意值。键必须是一个可散列的对象，散列表算法确保它在字典中是唯一的。但是值可以是任何对象——它不需要是可散列的或唯一的。

Raymond Hettinger 发现，如果散列值和指向键和值的指针保存在没有空行的条目数组中，则可以节省大量成本，而实际的散列表是一个稀疏数组，其中包含小得多的存储桶，存储桶中的字段为条目数组的索引。在他最初的 message to python-dev文章中，Hettinger 称这个散列表为索引（indices）。索引中桶的宽度随着字典的增长而变化，从每个桶 8 位开始——足以索引多达 128 个条目，同时为特殊目的保留负值，例如 -1 表示空，-2 表示删除。

例如，swimmers 字典的存储如下图所示：

假设 CPython 是 64 位版本，我们的 4 项swimmer字典在旧方案中将占用 192 字节的内存,每个桶24个字节，共8个桶：24*8=192 bytes。等效的紧凑 dict 总共使用 104 个字节：条目数组中的 96 个字节 (24 * 4)，加上索引中的桶的 8 个字节——设定为一个8个字节的数组。

将项添加到紧凑字典的算法

第0步，初始化索引（Indices）

索引表最初设置为带符号字节的数组，一共有 8 个桶，每个桶初始化为 -1 以表示“空桶”。其中最多 5 个桶保存indices数组中行的索引，至少1/3 的桶的值为 -1。另一个数组（entries）将保存具有与旧方案相同的三个字段的键/值数据——但是按照插入的顺序。

第1步，计算键的散列值

要将键值对 ('Mon', 14) 添加到swimmer字典中，Python 首先调用 hash('Mon') 来计算该键的散列码。

第2步，通过索引探测indices数组

Python 计算 hash('Mon') % len(indices)的结果。在我们的示例中，这个值是 3。索引数组中的偏移量 3的桶值 为 -1：它是一个空桶。

第 3 步：将键值放入entries数组中，并更新索引数组。

entries数组为空，因此下一个可用偏移量为 0（entries）。Python 将 0 存储在indices数组的偏移量为3的桶，并在entries组的偏移量0存储键的散列值、指向键对象“Mon”的指针和指向int 值14的指针。下图展示了当 Swimmers 的值为 {'Mon': 14} 时数组的状态。

下个元素的步骤
添加('Tue', 12) 到 swimmers：

1. 计算键'Tue'的散列值
2. 计算索引的偏移量，本次为 hash('Tue') % len(indices)。结果是 2。indices数组偏移量2对应的值是 -1。目前为止未发生碰撞。
3. 将下一个entries对应的偏移量 1 放入indices[2]，然后将数据存储在entries[1] 中。

现在状态如下图。请注意，entries数组按插入顺序保存键值对。

处理冲突的步骤

1. 计算'Wed'的散列值
2. 现在， hash('Wed') % len(indices) 是 3。indices[3] 等于 0，指向一个现有的entry。查看entries [0] 中的散列值为“Mon”的散列码，恰好与“Wed”的散列值不同。这种不匹配标志着碰撞。探测下一个索引：Indices [4],值为-1，所以它可以使用。
3. 将Indices [4] 赋值为2，因为 2 是Entries数组的下一个可用偏移量。然后将数据存储在Entries[2]中,如下图所示

紧凑型字典如何增长

回想一下，Indices数组中的桶最初可以容纳8个有符号字节类型，足以容纳多达 5 个indices的偏移量，使 1/3 的桶为空。当第 6 项添加到 dict 时，Indices数组被重新分配到 16 个桶——足够 10 个indices偏移量。随后，Indices数组的大小根据需要加倍，同时仍存储有符号字节类型，直到将第 129 项添加到 dict中。此时，Indices数组有 256 个桶,每个桶存储的是8位有符号字节。然而，一个8位有符号字节不足以保存 128 个条目之后的偏移量，因此Indices数组被重建以保存 256个长度为16位宽（2字节）的桶来保存有符号整数——足够表示Entries数组中 32,768 行的偏移量。下一次调整大小发生在第 171 次添加时，此时Indices数组的有效值数量将超过其长度的⅔ 。然后Indices数组的桶数翻倍到512个，但每个桶仍然是 16 位宽。总而言之，Indices数组的增长是通过将存储桶的数量加倍，偶尔通过将每个存储桶的宽度加倍以容纳Entries数组中越来越多的行。

我们对紧凑型字典实现的总结到此结束。我省略了很多细节，但现在让我们看看字典的另一个节省空间的优化：共享键。

共享键的字典

用户定义类的实例通常将它们的属性保存在 __dict__ 属性中，这个属性是一个常规的dict。在 __dict__ 实例中，键是属性名称，值是属性的值。大多数情况下，所有类实例都具有相同的属性和不同的值。发生这种情况时，每个实例的Entries表中的 3 个字段中有 2 个具有完全相同的内容：属性名称的散列值和指向属性名称的指针。只有指向属性值的指针不同。

在PEP 412 — Key-Sharing Dictionary中,Mark Shannon 提出拆分用作实例 __dict__ 的字典的存储，这样每个属性散列值和指针只存储一次，并将其链接到类，然后将属性值保存在附加到每个实例的指针数组中。

给定一个 Movie 类，其中所有实例都具有相同的属性，名为“title”、“release”、“directors”和“actors”，下图显示了拆分字典中共享键的排列——也使用新的紧凑布局实现。

PEP 412 引入了术语combined-table来讨论旧布局和split-table用于优化建议。

当您使用字面量语法或调用 dict() 创建 dict 时，combined-table布局仍然是默认设置。当实例是类的第一个实例时，会创建一个拆分表字典来填充实例的 __dict__ 特殊属性，然后将键表缓存在类对象中。这利用了大多数面向对象的 Python 代码在 __init__ 方法中分配所有实例属性的事实。类的第一个实例（以及它之后的所有实例）将只保存它自己的值的数组。如果实例获取在共享键表中找不到的新属性，然后这个实例的 __dict__ 会被转换为组合表形式。但是，如果此实例是其类中唯一的实例，则 __dict__ 将转换回拆分表，因为假定后续创建的实例将具有相同的一组属性并且键共享会是有用的。

在 CPython 源代码中表示字典的 PyDictObject 结构对于组合表和拆分表字典是相同的。当 dict 从一种布局转换为另一种布局时，在其他内部数据结构的帮助下，PyDictObject 字段会发生变化。

章节总结

字典是 Python 的基石。多年来，我们熟悉的 {k1: v1, k2: v2} 字面量语法得到了增强，以支持使用 ** 解包、模式匹配以及 dict推导式。

除了基本的 dict，标准库还提供了方便的、即用型的专用映射，如 defaultdict、ChainMap 和 Counter，所有这些都在 collections 模块中定义。使用新的 dict 实现后，OrderedDict 没有以前那么有用，但应该保留在标准库中以实现向后兼容性--并且具有 dict 所没有的特定特性，例如在 == 比较中会考虑键的顺序。集合模块中还有 UserDict，这是一个易于使用的基类，用于创建自定义映射。

在绝大多数映射中可用的两种强大方法是 setdefault 和 update。setdefault 方法可以更新包含可变值的项——例如，在值是列表的字典中——避免二次搜索相同的键。update 方法允许从任何其他映射、提供（键、值）对的可迭代对象以及关键字参数中批量插入或覆盖元素。映射构造函数也在内部使用update方法，允许从映射、迭代或关键字参数初始化实例。从 Python 3.9 开始，我们还可以使用 |= 运算符来更新映射，而 |运算符从两个映射的并集创建一个新的映射。

映射 API 中的一个聪明的钩子是 __missing__ 方法，它允许您在使用调用 __getitem__ 的 d[k] 语法时找不到键时，使用__missing__方法。

collections.abc 模块提供 Mapping 和 MutableMapping 抽象基类作为标准接口，对运行时类型检查很有用。types 模块中的 MappingProxyType 为要防止意外更改的映射提供一个不可变的代理。 Set 和 MutableSet 也有 ABC。

字典视图是 Python 3 中的一个很好的补充，消除了 Python 2 .keys()、.values() 和 .items() 方法的内存开销，这些方法在目标 dict 实例中构建重复数据的列表。此外，dict_keys 和 dict_items 类支持 freezeset 最有用的操作符和方法。