《流畅的Python第二版》读书笔记——字典和集合_流畅的python第二版 epub

引言

这是《流畅的Python第二版》抢先版的读书笔记。Python版本暂时用的是python3.8。为了使开发更简单、快捷，本文使用了JupyterLab。

字典类型不仅广泛地应用于我们的程序，而且是Pthon实现的基础。类和实例的属性、模型命名空间和函数的关键词参数都是通过字典表示的。

正是因为字典这种重要的角色，Python字典是高度优化的。而哈希表(Hash talbes)是高性能的字典里面的引擎。

其他基于哈希表的内建类型是set和frozenset。

新内容简介

与第一版相比，本章的新内容为：

• 从哈希表在set中的使用开始解释它。
• 在字典中保持键插入顺序(python3.6)的内存优化和字典保持实例属性的键共享布局——Python3.3中的__dict__。
• dict.keys,dict.items,dict.values返回的视图对象(Python3.0)

Mapping类型的标准API

collections.abc模块提供了Mapping和MutableMappings抽象基类来描述字典和类似类型的接口。

这些抽象基类的主要价值是记录和形式化映射的标准接口，并作为代码中 isinstance需要支持是否为映射的测试要求:

from collections import abc
from pprint import pprint

my_dict = {}
print(isinstance(my_dict, abc.Mapping)) # True
print(isinstance(my_dict, abc.MutableMapping)) # True
1
2
3
4
5
6

如果想要实现自定义映射，比较容易的方式是继承collections.UserDict类，或通过组合模式封装一个dict，而不是去继承这些抽象基类。标准库中的collections.UserDict类和所有具体的映射类都封装了基本的字典，都是基于哈希表实现的。因此，它们都需要键是hashable(可哈希的)。

可哈希的是什么意思？

一个对象是可哈希的如果它有一个整个生命周期内都不会改变的哈希值，这需要实现__hash__()方法；还需要能和其他对象比较，要实现__eq__()方法。当可哈>希的对象相等时必须有相同的哈希值。

基于这些规则，你可以通过多种方式构建字典。

a = dict(one=1, two=2, three=3)
b = {'three': 3, 'two': 2, 'one': 1}
c = dict([('two', 2), ('one', 1), ('three', 3)])
d = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
e = dict({'three': 3, 'one': 1, 'two': 2})

a == b == c == d == e # True
1
2
3
4
5
6
7

所有上面字典的实例都是相等的，因为它们有相同的键值对，这里键值对的顺序无关。

Python3.6开始支持保存键的插入顺序，并作为一个Python3.7的特性。所以我们可以依赖这一点：

在Python3.6之前，c.popitem()会返回任意的键值对，现在它总是返回最后的键值对。

字典推导式

话不多说，举个例子：

# 一个键值对列表
dial_codes = [                                               
    (880, 'Bangladesh'),
    (55,  'Brazil'),
    (86,  'China'),
    (91,  'India'),
    (62,  'Indonesia'),
    (81,  'Japan'),
    (234, 'Nigeria'),
    (92,  'Pakistan'),
    (7,   'Russia'),
    (1,   'United States'),
]

# 利用字典推导式构建字典
# 这里我们把country作为key, code作为value
country_dial = {country: code for code, country in dial_codes} 
country_dial
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

{'Bangladesh': 880,
 'Brazil': 55,
 'China': 86,
 'India': 91,
 'Indonesia': 62,
 'Japan': 81,
 'Nigeria': 234,
 'Pakistan': 92,
 'Russia': 7,
 'United States': 1}
1
2
3
4
5
6
7
8
9
10

# 排序、把code作为key,country作为value、过滤
{code: country.upper() 
    for country, code in sorted(country_dial.items())
    if code < 70}
1
2
3
4

{55: 'BRAZIL', 62: 'INDONESIA', 7: 'RUSSIA', 1: 'UNITED STATES'}
1

通用映射方法概览

下面显示了dict和两个有用的变种的方法，defaultdict和OrderedDict。

当字典d执行d.update(m)时，Python会把参数m当成鸭子类型(duck type)：首先会检查m是否有keys方法，若有，假设它为一个映射。
否则，假设m是(key,value)键值对。

一个好用的映射方法是setdefault()，当字典元素的值可变时，它避免了冗余的键查找，并且可以原地修改它。

用setdefault方法处理缺失键

在Python的快速失败哲学里，字典访问d[k]会抛出异常当k不存在时。每个Python人都知道d.get(k,default)是d[k]的一种替代方法，当k不存在时，不是报错，而是返回默认值default。然而，当我们想不存在即更新时，无论是d[k]还是get都不方便。

这段程序从索引中获取单词出现的频率信息，并把它们写进对应的列表里。

index0.py:

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          # ③把新的列表放回字典中，又涉及到一次查询操作

# 以字母顺序打印结果
for word in sorted(index, key=str.upper):  # 用sorted 函数的 key= 参数没有调用 str.uppper，而是把这个方法的引用传递给 sorted 函数，这样在排序的时候，单词会被规范成统一格式。
    print(word, index[word])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

zen.txt:

The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

以上面这个文件作为参数调用。

(py38) $ python 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)]
break [(10, 40)]
by [(1, 20)]
cases [(10, 9)]
complex [(5, 23)]
Complex [(6, 1)]
complicated [(6, 24)]
counts [(9, 13)]
dense [(8, 23)]
do [(15, 64), (21, 48)]
Dutch [(16, 61)]
easy [(20, 26)]
enough [(10, 30)]
Errors [(12, 1)]
explain [(19, 34), (20, 34)]
Explicit [(4, 1)]
explicitly [(13, 8)]
face [(14, 8)]
first [(16, 41)]
Flat [(7, 1)]
good [(20, 55)]
great [(21, 28)]
guess [(14, 52)]
hard [(19, 26)]
honking [(21, 20)]
idea [(19, 54), (20, 60), (21, 34)]
If [(19, 1), (20, 1)]
implementation [(19, 8), (20, 8)]
implicit [(4, 25)]
In [(14, 1)]
is [(3, 11), (4, 10), (5, 8), (6, 9), (7, 6), (8, 8), (17, 5), (18, 16), (19, 23), (20, 23)]
it [(15, 67), (19, 43), (20, 43)]
let [(21, 42)]
may [(16, 19), (20, 46)]
more [(21, 51)]
Namespaces [(21, 1)]
nested [(7, 21)]
never [(12, 15), (17, 20), (18, 10)]
not [(16, 23)]
Now [(17, 1)]
now [(18, 45)]
obvious [(15, 49), (16, 30)]
of [(1, 9), (14, 13), (21, 56)]
often [(18, 19)]
one [(15, 17), (15, 43), (21, 16)]
only [(15, 38)]
pass [(12, 21)]
Peters [(1, 27)]
practicality [(11, 10)]
preferably [(15, 27)]
purity [(11, 29)]
Python [(1, 12)]
re [(16, 58)]
Readability [(9, 1)]
refuse [(14, 27)]
right [(18, 38)]
rules [(10, 50)]
s [(19, 46), (21, 46)]
should [(12, 8), (15, 7)]
silenced [(13, 19)]
silently [(12, 26)]
Simple [(5, 1)]
Sparse [(8, 1)]
Special [(10, 1)]
special [(10, 22)]
t [(10, 20)]
temptation [(14, 38)]
than [(3, 21), (4, 20), (5, 18), (6, 19), (7, 16), (8, 18), (17, 15), (18, 32)]
that [(16, 10)]
The [(1, 1)]
the [(10, 46), (14, 4), (14, 34), (19, 4), (20, 4)]
There [(15, 1)]
those [(21, 59)]
Tim [(1, 23)]
to [(10, 37), (14, 49), (15, 61), (19, 31), (20, 31)]
ugly [(3, 26)]
Unless [(13, 1)]
unless [(16, 47)]
way [(15, 57), (16, 15)]
you [(16, 54)]
Zen [(1, 5)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

index0.py中的①-③那三行可以用dict.setdfault一行来代替。如下所示：

index.py:

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)  # 获取单词的出现情况列表，如果单词不存在，把单词和一个空列表放进映射，然后返回这个空列表，这样就能在不进行第二次查找的情况下更新列表了。

for word in sorted(index, key=str.upper):
    print(word, index[word])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总之，下面这行代码的结果：

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

和三行代码的结果是一样的：

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

不过后者至少要进行两次键查询——如果键不存在的话，就是三次，用 setdefault 只需要一次查询就可以完成整个操作。

映射的弹性键查询

有时候为了方便起见，就算某个键在映射里不存在，我们也希望在通过这个键读取值的时候能得到一个默认值。有两个途径能帮我们达到这个
目的，一个是通过 defaultdict 这个类型而不是普通的 dict，另一个是继承dict或任意映射类型，然后在子类中实现 __missing__ 方法。下面将介绍这两种方法。

defaultdict: 处理缺失键的另一种选择

index_default.py:

import collections
import re
import sys

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

index = collections.defaultdict(list)     # 创建一个defaultdict实例，以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])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

当实例化一个defaultdict时,需要给构造方法提供一个可调用对象，这个可调用对象会在 __getitem__碰到找不到的键的时候被调用，让 __getitem__ 返回某种默认值。

像上面那样，新建一个这样的字典：dd = defaultdict(list)，如果键new-key 在 dd 中还不存在的话，表达式 dd['new-key'] 会执行以下的步骤：

1. 调用 list() 来建立一个新列表。
2. 把这个新列表作为值，new-key 作为它的键，放到 dd 中。
3. 返回这个列表的引用。

而这个用来生成默认值的可调用对象存放在名为 default_factory 的实例属性里。如果没有default_factory被提供，那么会报KeyError。

defaultdict中的defalut_factory只会为__getitem__提供默认值。比如，如果dd是defaultdict，k是一个不存在的键，dd[k]会调用default_factory去创建默认值，而dd.get(k)仍然返回None。

所有这一切背后的功臣其实是特殊方法 __missing__。它会在defaultdict 遇到找不到的键的时候调用 default_factory，而实际上这个特性是所有映射类型都可以选择去支持的。

__missing__方法

所有的映射类型在处理找不到的键的时候，都会牵扯到 __missing__方法。这也是这个方法称作“missing”的原因。虽然基类 dict 并没有定义这个方法，但是 dict 是知道有这么个东西存在的。也就是说，如果有一个类继承了 dict，然后这个继承类提供了 __missing__ 方法，那么在 __getitem__ 碰到找不到的键的时候，Python 就会自动调用它，而不是抛出一个 KeyError 异常。

__missing__方法只会被__getitem__调用。

有时候，你会希望在查询的时候，映射类型里的键统统转换成 str。

strkeydict0.py:

class StrKeyDict0(dict):  # 继承dict

    def __missing__(self, key):
        if isinstance(key, str):  # 如果缺失键本身就是str，则抛出KeyError异常
            raise KeyError(key)
        return self[str(key)]  # 否则转换为str再查找

    def get(self, key, default=None):
        try:
            return self[key]  # self[key]把查找委托给__getitem__，这样在宣布查找失败之前，还能通过__missing__再给某个键一个机会
        except KeyError:
            return default  # 如果抛出KeyError，那么说明__missing__也失败了，于是返回默认值

    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys()  # 先按照传入键的原本值查找，如果没找到，再用str()方法把键转换成str再查找一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

当搜索非字符串键时，如果键不存在，StrKeyDict0将它转换为str：

from strkeydict0 import StrKeyDict0

d = StrKeyDict0([('2', 'two'), ('4', 'four')])

1
2
3
4

花点时间考虑为什么在__missing__实现中需要测试isinstance(key,str)。

没有该测试，我们的__missing__方法对于任何键k,str或不是str。每当str(k)产生现有键时，可以正常工作。 但是，如果str(k)不是现有的键，我们会有无限的递归。
最后一行，self[str(key)]会调用__getitem__传递该str键，反过来会再次调用__missing__。

__contains__方法也是必须的，为了保持一致。这是因为k in d 这个操作会调用它，但是我们从 dict 继承到的 __contains__方法不会在找不到键的时候调用 __missing__ 方法。__contains__里还有个细节，就是我们这里没有用更具 Python 风格的方式——k in my_dict——来检查键是否存在，因为那也会导致__contains__ 被递归调用。为了避免这一情况，这里采取了更显式的方法，直接在这个self.keys() 里查询。

字典的变种

• collections.OrderedDict

  • 这个类型在添加键的时候会保持顺序，因此键的迭代次序总是一致的。OrderedDict 的 popitem 方法默认删除并返回的是字典里的最后一个元素，但是如果像 my_odict.popitem(last=False) 这样调用它，那么它删除并返回第一个被添加进去的元素。自从Python3.6之后，内建的dict也有这个特性，因此使用这个类只是为了向前兼容。

• collections.ChainMap

  • 该类型可以容纳的映射对象列表，然后在进行键查找操作的时候，这些对象会被当作一个整体被逐个查找，直到键被找到为止。这个功能在给有嵌套作用域的语言做解释器的时候很有用，可以用一个映射对象来代表一个作用域的上下文。

• collections.Counter

  • 这个映射类型会给键准备一个整数计数器。每次更新一个键的时候都会增加这个计数器。所以这个类型可以用来给可散列表对象计数，或者是当成多重集来用——多重集合就是集合里的元素可以出现不止一次。Counter 实现了 + 和 - 运算符用来合并记录，还有像most_common([n]) 这类很有用的方法most_common([n]) 会按照次序返回映射里最常见的 n 个键和它们的计数。

构建自定义映射

下面这些映射类型不是用来直接实例化的，而是给我们继承的，以创建自定义映射类型。

• collections.UserDict : 一个纯Python的实现，看起啦像标准的dict。
• collections.TypedDict : 这允许你使用类型提示来定义映射类型，以指定每个键的预期值类型。

collections.UserDict 类的行为类似于 dict，但是它更慢，因为它是在 Python 中实现的，而不是在 C 中。

继承UserDict

通常通过继承UserDict而不是dict来创建一个新的映射类型，因为这更简单。这体现正在，我们能够改进上面定义的 StrKeyDict0 类，使得所有的键都存储为字符串类型。

主要的原因是，内建的dict的某些方法在实现时走了一些捷径，而我们继承它时，不得不实现这些方法。但UserDict就不会存在这些问题。

另外一个值得注意的是，UserDict 并不是 dict 的子类，而是利用组合：它有一个叫作 data 的属性，是 dict 的实例，这个属性实际上是 UserDict 最终存储数据的地方。这样做的好处是，比起示例strkeydict0.py中UserDict 的子类就能在实现 __setitem__ 的时候避免不必要的递归，也可以让 __contains__ 里的代码更简洁。

多亏了 UserDict，下面StrKeyDict 的代码比StrKeyDict0 要短一些，功能却更完善：它不但把所有的键都以字符串的形式存储，还能处理一些创建或者更新实例时包含非字符串类型的键这类意外情况。

import collections


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

    def __missing__(self, key):  # 和StrKeyDict0相同
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]

    def __contains__(self, key):
        return str(key) in self.data  #  __contains__ 则更简洁些。这里可以放心假设所有已经存储的键都是字符串。
                                      # 因此，只要在 self.data 上查询就好了，并不需要像StrKeyDict0 那样去麻烦 self.keys()。

    def __setitem__(self, key, item):
        self.data[str(key)] = item    # __setitem__ 会把所有的键都转换成字符串。由于把具体的实现委
                                      # 托给了 self.data 属性，这个方法写起来也不难。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

因为 UserDict 继承的是 MutableMapping，所以 StrKeyDict 里剩下的那些映射类型的方法都是从 UserDict、MutableMapping 和Mapping这些超类继承而来的。
特别是最后的 Mapping 类，它虽然是一个抽象基类(ABC)，但它却提供了好几个实用的方法。以下两个方法值得关注。

• MutableMapping.update

  • 这个方法不但可以为我们所直接利用，它还用在 __init__ 里，让构造方法可以利用传入的各种参数（其他映射类型、元素是 (key,value) 对的可迭代对象和键值参数）来新建实例。因为这个方法在背后是用 self[key] = value 来添加新值的，所以它其实是在使用我们的 __setitem__ 方法。

• Mapping.get

  • 在 StrKeyDict0中，我们不得不改写 get 方法，好让它的表现跟 __getitem__ 一致。而在StrKeyDict中就没这个必要了，因为它继承了 Mapping.get 方法，而 Python 的源码中，这个方法的实现方式跟StrKeyDict0.get是一模一样的。

不可变映射

有时你需要不可变的映射类型。从 Python 3.3 开始，types 模块中引入了一个封装类名叫MappingProxyType。
如果给这个类一个映射，它会返回一个只读的动态代理mappingproxy。这意味着如果对原映射做出了改动，我们通过这个mappingproxy可以观察到，但是无法通过它对原映射做出修改

from types import MappingProxyType

d = {1: 'A'}
d_proxy = MappingProxyType(d)
d_proxy
1
2
3
4
5

字典视图

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

如果源字典更新了，你能马上观察到现存视图内容的更新。

类dict_key、dict_values和dict_items是内部的：它们不能通过内建或任何标准模块获取，甚至如果你获取到它们的一个引用，也无法用来创建新的视图。

values_class = type({}.values())
v = values_class()
1
2

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-45-f3d02f8dd591> in <module>
      1 values_class = type({}.values())
----> 2 v = values_class()

TypeError: cannot create 'dict_values' instances
1
2
3
4
5
6
7

集合论

集合并不是Python中的新事物，但仍然是未充分利用的。set 和它的不可变类型 frozenset 直到 Python 2.3 才首次以模块的形式出现，然后在 Python 2.6 中它们升级成为内置类型。

集合本质是许多唯一对象的聚集。大家都知道可以用来去重：

集合中的元素必须是可哈希的，set 类型本身是不可哈希的，所以你不能创建一个元素是set的set。
但是frozenset是可哈希的，所以可以创建一个包含不同 frozenset 的 set。

除了保证唯一性，集合还实现了很多基础的中缀运算符。

给定两个集合a 和b，a | b 返回的是它们的合集，a & b 得到的是交集，而 a - b得到的是差集。

例如，我们有一个电子邮件地址的集合（haystack），还要维护一个较小的电子邮件地址集合（needles），然后求出 needles 中有多少地
址同时也出现在了 heystack 里。借助集合操作，我们只需要一行代码就可以了。

found = len(needles & haystack)
1

这种方式很快，但是需要它们都是集合。如果不是集合，你也可以很快地构造。

found = len(set(needles) & set(haystack))
# 或
found = len(set(needles).intersection(haystack))
1
2
3

除了极快的成员检测(基于哈希表实现的)，内建的集合类型还提供了丰富的API来创建或修改集合。

集合字面量

除空集之外，集合的字面量——{1}、{1, 2}，等等——看起来跟它的数学形式一模一样。如果是空集，那么必须写成 set() 的形式。

如果写{}，创建的是空字典，而不是空集合。

集合字面量像{1,2,3}不仅比调用构造函数的形式(如set([1,2,3]))更可读，而且速度更快。

没有特殊的语法来表示frozenset的字面量，因此，只能通过构造函数构建。

frozenset(range(10))
1

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

结合推导式

from unicodedata import name 
{chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i),'')} # 把编码在 32~255 之间的字符的名字里有“SIGN”单词的挑出来，放到一个集合里。
1
2

{'#',
 '$',
 '%',
 '+',
 '<',
 '=',
 '>',
 '¢',
 '£',
 '¤',
 '¥',
 '§',
 '©',
 '¬',
 '®',
 '°',
 '±',
 'µ',
 '¶',
 '×',
 '÷'}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

集合操作

下图列出了可变和不可变集合所拥有的方法的概况，其中不少是运算符重载的特殊方法。

下表则包含了数学里集合的各种操作在 Python 中所对应的运算符和方法。

集合的比较运算符，返回值是布尔类型:

除了跟数学上的集合计算有关的方法和运算符，集合类型还有一些为了实用性而添加的方法:

到这里，我们差不多把集合类型的特性总结完了。

正如在字典视图中提到的，我们现在来看这两个字典视图类型表现得多像frozenset。

字典视图上的集合操作

下表显示了集合方法：.keys()、.items()返回的视图对象与frozenset有多相似：

特别地，dict_keys 和 dict_items 实现了支持强大的集合运算符 & (交集)、 | (并集)、-(差集)和 ^ (对称差)的特殊方法。

这意味着，例如，找到出现在两个字典中的键就像这样简单:

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

{'b', 'd'}
1

注意，& 的返回值是一个集合。更好的是: 字典视图中的 set 操作符与 set 实例兼容。看看这个:

s = {'a', 'e', 'i'}
d1.keys() & s
1
2

{'a'}
1

d1.keys() | s
1

{'a', 'b', 'c', 'd', 'e', 'i'}
1

现在我们换个话题来讨论如何使用哈希表实现集合和字典。

dict和set的背后

想要理解 Python 里字典和集合类型的长处和弱点，它们背后的哈希表是绕不开的一环。

这一节将会回答以下几个问题。

• Python 里的 dict 和 set 的效率有多高？
• 为什么它们是无序的？
• 为什么并不是所有的 Python 对象都可以当作 dict 的键或 set 里的元素？
• 为什么 dict 的键和 set 元素的顺序是跟据它们被添加的次序而定的？
• 为什么set中的元素顺序看起来像随机的？

集合底层的哈希表

哈希表是一个精彩的发明， 我们看看当插入元素到集合时，哈希表是如何使用的。

假设我们有一个工作日缩写的集合：

workdays = {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}
workdays
1
2

{'Fri', 'Mon', 'Thu', 'Tue', 'Wed'}
1

Python集合的核心数据结构就是哈希表，它至少有8行。通常，哈希表中的行叫作桶(bucket)，所有的行叫作buckets。

一个存有工作日集合的哈希表如下所示：

每个桶有两个字段：哈希码(hash code)和指向元素值的指针。空桶的哈希码为-1，顺序看起来是随机的。

因为存储桶的大小是固定的，所以对单个桶的访问是通过偏移量完成的。

哈希码和相等性

内置的 hash() 方法可以用于所有的内置类型对象。如果是自定义对象调用hash() 的话，实际上运行的是自定义的 __hash__。
如果两个对象在比较的时候是相等的，那它们的哈希码必须相等，否则哈希表就不能正常运行了。例如，如果 1 == 1.0 为真，那么hash(1) == hash(1.0) 也必须为真，但其实这两个数字（整型和浮点）的内部结构是完全不一样的。

为了让哈希码能够胜任哈希表索引这一角色，它们必须在索引空间中尽量分散开来。这意味着在最理想的状况下，越是相似但不相等
的对象，它们哈希码的差别应该越大。下面是一段代码输出，这段代码被用来比较哈希码的二进制表达的不同。
注意其中 1和 1.0 的哈希码是相同的，而 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
------------------------------------------------
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

哈希冲突

在64位的CPython中，一个哈希码是一个64位的数字，即有$2^{64}$可能值，它超过$10^{19}$。但是大多数 Python 类型可以表示更多不同的值。例如，一个由10个可打印字符组成的字符串有$100^{10}$个可能的值——超过$2^{66}$个。因此，对象的哈希码的信息通常少于实际对象值。这意味着不同的对象可能具有相同的哈希码。

当不同的对象具有相同的哈希码，被称为哈希冲突。

哈希表算法

我们首先关注集合的内部实现，后面再探讨字典。

我们一步步看Python是如何构建集合{'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}的。该算法通过上面的流程图展示。

Step 0:实例化哈希表

正如前面提到的，一个集合的哈希表从8个空桶开始。在添加元素时，Python 会确保至少有$\frac{1}{3}$个桶是空的，在需要更多空间时将哈希表的大小增加一倍。每个 bucket 的哈希码字段用-1初始化，这意味着“没有哈希码”。

Step 1:计算元素的哈希码

给定文本{'Mon', 'Tue', 'Wed', 'Thu', 'Fri'} ，Python 获得第一个元素'Mon'的哈希码。例如，这里有一个实际的 'Mon' 的哈希码，你可能会得到一个不同的结果，因为 Python 加随机盐来计算字符串的哈希码:

hash('Mon') # 4199492796428269555  因为每次计算hash都加盐了，导致每次启动Python得到的结果都不一样，但是在每次Python运行期间内都是一样的。 为了简单，这里假设得到的哈希码和原文中一样。
1

Step 2:用哈希码计算的索引来探测哈希表

计算哈希码对哈希表大小取模的结果，作为索引。这里表大小为8，结果为：

4199492796428269555  % 8 # 3
1

探测包括从哈希码计算索引，然后查看哈希表中相应的桶。在这种情况下，Python 查看位于偏移量3的 bucket，然后在哈希码字段找到值-1，说明这是一个空桶。

Step 3:将元素放到空桶内

Python存储新元素的哈希吗,4199492796428269555,偏移量为3的bucket中，还存储一个指向字符串对象'Mon'的指针到元素字段。下图显示了当前的哈希表状态。

对于待插入集合内第二个元素，重复Step1,2,3。'Tue'的哈希码为2414279730484651250，索引为2。

2414279730484651250 % 8 # 2
1

位于哈希表中索引2的桶依旧是空桶，放入其中，现在哈希表如下：

处理冲突

当添加'Wed'到集合中，Python计算得哈希码为-5145319347887138165 索引为3。Python检测索引3的桶，发现已经被用了。但是存储在该桶中的哈希码不同。这是索引冲突。Python然后探测下一个空桶。所以'Wed'最终放入索引4，如下：

添加下一个元素,'Thu'，没有冲突，它放入索引7。

添加最后一个元素'Fri'，它的哈希码为7021641685991143771 ，索引为3，它已经被'Wed'占用了。下面的索引4也被占用了，最终放入索引为5的位置：

最终哈希表的状态如上图所示。
这种在索引冲突后，增加索引值的方法叫做线性寻址法。

这个过程还有一种情况没有说明，当新插入的元素的哈希码和待插入位置处的哈希码相同时，还需要比较元素是否相等。因为不同的对象仍然有可能有相同的哈希码。

如果还有一个新元素要插入到我们例子中的哈希表，那么总元素个数会超过$\frac{2}{3}$，这会增加索引冲突的可能。
Python此时会进行扩容操作，分配一个具有16个桶的哈希表，并把旧表中的元素全部插入。

给定下面的set，当插入整数1时会发生什么

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

此时集合中有多少元素？整数1替换了1.0吗？我们来看一下：

在哈希表中搜索

考虑上面的哈希表。我们想要知道’Sat’是否在表中。下面是最简单的检测Sat是否在其中的执行路径：

1. 调用hash('Sat')得到哈希码，假设为4910012646790914166
2. 计算索引，4910012646790914166 % 8 = 6
3. 探测索引6的位置，它是空的，即Sat并不在集合中，返回False。

下面考虑集合中存在的元素，假设是’Thu’：

1. 调用hash('Thu')得到哈希码，假设为6166047609348267525
2. 计算索引，6166047609348267525 % 8 = 5
3. 探测索引5的位置
   • 比较哈希码，它们是相等的。
   • 比较对象是否相等，它们是相等的，返回True。

集合底层的哈希表特性

Set 和 frozenset 类型都是通过哈希表实现的，哈希表具有以下特性:

• 集合元素必须是可哈希对象。它们必须实现 __hash__ 和 __eq__ 方法。
• 成员资格测试非常高效。一个集合可能有数百万个元素，但是一个元素的桶可以通过计算元素的哈希码和生成一个索引偏移量来直接定位，只是可能会有少量探针来寻找匹配元素或空桶的开销。
• 集合具有显著的内存开销。容器最紧凑的内部数据结构是指针数组。相比之下，哈希表中每个元素都会加入一个哈希码，并且至少有$\frac{1}{3}$的空桶来减少碰撞。
• 元素顺序取决于插入顺序，但不是以有用或可靠的方式。如果碰撞涉及两个元素，则每个桶的存储取决于首先添加哪个元素。
• 向集合中添加元素可能会改变其他元素的顺序。那是因为，当哈希表被填满时，Python 可能需要重新创建它来保持至少$\frac{1}{3}$个桶是空的。当这种情况发生时，元素被重新插入，可能会发生不同的碰撞。

自从2012，字典类型的实现有两个主要优化来减少内存占用。第一个是共享键字典(Key-Sharing Dictionary)，第二是叫作压缩字典(compact dict)。

压缩字典是如何节省空间和保持顺序的

考虑工作日->报名游泳人数的字典：

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

在进行压缩字典优化之前，swimmers字典下面的哈希表如下图所示。如你所见，在64位 Python 中，每个 bucket 包含三个64位字段: 键的哈希码、键对象的指针和值对象的指针。也就是每个桶24个字节。

前两个字段在集合的实现中起着相同的作用。为了找到key，Python 计算key的哈希码，得到索引，然后探测哈希表，找到具有匹配哈希码和匹配key对象的 bucket。第三个字段提供了 dict 的主要特性: 将键映射到任意值。key必须是一个可哈希的对象，哈希表算法确保它在字典中是唯一的。但它的值可以是任何对象———它不需要是可哈希的或唯一的。

Raymond Hettinger 提出，如果引入稀疏的索引数组，那么可以节省大量资源。具体来说，将哈希码和指向键和值的指针保持在一个没有空行的条目数组entries中。而实际的哈希表成了一个小得多的只保存索引的数组indices。这些索引指向的是entries数组中的元素。索引数组indices中桶的宽度从8位开始，因为2**8 = 256，但为了特殊用途保留负值(比如-1代表空，-2代表删除)，即仍然能对128个条目进行索引。

(因为是抢先版，这里感觉图片和原文中计算压缩字典共用104字节的结果都有问题。)

以swimmers字典为例，它的存储状态可能如上图所示。

假设基于64位的 CPython，我们的4个元素的swimmers词典在旧的方案中将占用192字节的内存: 每桶24字节，乘以8。
而等效的压缩字典总共使用160个字节: 条目数组占96个字节(24 * 4) ，加上8个索引数组中的桶，每个桶占8字节，即64字节(8 * 8)。

压缩字典的插入算法

Step 0: 构建索引数组indices

索引数组由有符号字节构成，初始8个桶，每个桶初始化为-1表示空桶。但最多只有5个桶会存有值，留下$\frac{1}{3}$的空桶。
另一个数组entries会存储键值对数组，和传统的字典一样有3个字段，但以插入顺序存储。

Step 1: 计算键的哈希码

要插入键值对('Mon', 14)到swimmers字典，还是首先调用hash('Mon')得到哈希码。

Step 2: 在索引数组中探测

计算hash('Mon') % len(indices)，在我们的例子中，得到3。索引3位置的值是-1，代表空桶。

Step 3: 将键值对放入条目数组，并更新索引数组

条目数组此时是空的，所以条目数组中下一个可用的偏移量为0。Python把该偏移量0保存到索引数组中索引为3的位置，然后存储键的哈希码、指向键对象'Mon'的指针、指向值整数值14的指针到偏移量为0的条目数组中。

即索引数组保存的是条目数组中对应的偏移量。

添加下个元素

要添加('Tue', 12)：

1. 计算键'Tue'的哈希码
2. 计算索引，hash('Tue') % len(indices)，这里是2。同时indices[2] == -1，此时还没有冲突。
3. 将下一个可用的偏移量1存入索引数组中的indices[2]，然后存储条目到条目数组entries[1]。

现在状态如上，注意到条目数组保存了条目的插入顺序信息。

处理冲突

1. 计算键'Wed'的哈希码
2. 现在hash('Wed') % len(indices) == 3。而indices[3] == 0，指向了存在的条目。然后查看entries[0]处的哈希码，它是'Mon'计算得到的哈希码，假设和'Wed'得到的哈希码不同。此时产生了冲突，则探测下一个索引：indices[4]，它的值为-1，所以是可用的。
3. 设置indices[4] = 2，因为2是条目数组中下一个可用的偏移量，然后像之前那样填充条目数组。

压缩字典如何扩容

回想一下，索引数组中的 bucket 最初是8个带符号字节，足以为最多5个条目保留偏移量，只留下$\frac{1}{3}$个 bucket 为空。当第6项被添加到字典时，索引数组被重新分配到16个桶——足够保存10个项。索引数组的大小根据需要加倍，同时仍然保留有符号字节，直到需要添加地129个元素到字典。此时，索引数组有256个8位桶。但是，一个有符号字节不足以保持128项以后的偏移量，因此重新构建索引数组以保存256个16位桶，以保存有符号整数——其宽度足以表示条目表中32,768行的偏移量。

下一次调整大小发生在第171次插入，当索引数组将存有超过$\frac{2}{3}$。然后，索引数组中桶的数量增加了一倍，达到512个，但每个桶仍然是16位宽的。总之，索引数组的增长是通过将桶的数量加倍来实现的，而且通过将每个桶的宽度增加一倍来容纳条目中越来越多的行，增长的频率也会降低。

共享键字典

用户定义类的实例通常将它们的属性保存在 __dict__ 属性中，它是一种常规字典。在实例 __dict__中，键值对中的键是属性名称，值是属性值。大多数情况下，所有实例具有相同的属性和不同的值。此时，条目表中每个实例的3个字段中有2个具有完全相同的内容: 属性名称的哈希码和指向属性名称的指针。只有指向属性值的指针是不同的。

在 PEP 412 — Key-Sharing Dictionary 中，Mark Shannon 提出了将键(与哈希码)和值的存储分离，键与哈希码可以被多个字典实例共享。

给定一个 Movie 类，其中所有实例都具有相同的属性，分别命名为"title"、“release”、“directors"和"actors”，下图显示了在一个拆分字典(split dictionary)中键共享的安排——也是用新的压缩布局实现的。

PEP 412引入了术语 combined-table 来描述旧的布局以及用split-table描述新布局。

当使用字面语法或调用 dict ()创建 dict 时，默认使用combined-talbe。当某个类的第一个实例被创建时，一个split-table被创建来填充这个实例的特殊属性__dict__。然后将 keys 表(见上图)缓存到类对象中，这利用了大多数面向对象的 Python 代码在 __init__ 方法中分配所有实例属性的事实。

第一个实例(以及之后的所有实例)将只保存自己的value 数组(value arrays)。如果一个实例获得了一个在共享键表(keys 表)中没有找到的新属性，那么该实例的
__dict__ 被转换为combined-table格式。但是，如果这个实例是它所属类唯一的实例，那么 __dict__ 将被转换回split-table。因此假定新的实例将具有相同的属性集，然后共享键是有用的。

在 CPython 源代码中表示 dict 的 PyDictObject 结构对于combined-table和split-table字典是相同的。当 dict 从一个布局转换到另一个布局时，在其他内部数据结构的帮助下，可以在PyDictObject字段中发生改变。

字典底层实现的影响

• 键必须是可哈希的对象，它们必须实现__hash__和__eq__方法。
• 键搜索几乎和在集合中搜索一样快。
• 字典元素项顺序被保存在entries表中。
• 为了节省内存，避免在__init__方法外创建实例属性。如果所有的实例属性都在__init__方法中创建，那么你类的实例的__dict__属性会使用split-talbe布局，可以共享该类存储的索引数组(indices)和键条目数组(key entries array)。