Python学习之路22-字典和集合

《流畅的Python》笔记。

本篇主要介绍dict和set的高级用法以及它们背后的哈希表。

1. 前言

dict类型不但在各种程序中广泛使用,它也是Python的基石。模块的命名空间、实例的属性和函数的关键字参数等都用到了dict。与dict先关的内置函数都在__builtins__.__dict__模块中。

由于字典至关重要,Python对其实现做了高度优化,而散列表(哈希函数,Hash)则是字典性能突出的根本原因。而且集合(set)的实现也依赖于散列表。

本片的大纲如下:

  • 常见的字典方法;
  • 如何处理找不到的键;
  • 标准库中dict类型的变种;
  • setfrozenset类型;
  • 散列表工作原理;
  • 散列表带来的潜在影响(什么样的数据可以作为键、不可预知的顺序等)。

2. 字典

和上一篇一样,先来看看collections.abc模块中的两个抽象基类MappingMutableMapping。它们的作用是dict和其他类似的类型定义形式接口:

然而,非抽象映射类型一般不会直接继承这些抽象基类,它们会直接对dict或者collections.UserDict进行扩展。

2.1 创建字典

首先总结下常用的创建字典的方法:

1
2
3
4
5
6
7
8
9
a = dict(one=1, two=2, three=3)
b = {"one": 1, "two": 2, "three": 3}
c = dict(zip(["one", "two", "three"], [1, 2, 3]))
d = dict([("two", 2), ("one", 1), ("three", 3)])
e = dict({"three": 3, "one": 1, "two": 2})
print(a == b == c == d == e)

# 结果
True

2.2 字典推导

列表推导和生成器表达式可以用在字典上。字典推导(dictcomp)可从任何以键值对作为元素的可迭代对象中构建出字典。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
DIAL_CODES = [
(86, 'China'),
(91, 'India'),
(1, 'United States'),
(62, 'Indonesia'),
(55, 'Brazil'),
(92, 'Pakistan'),
(880, 'Bangladesh'),
(234, 'Nigeria'),
(7, 'Russia'),
(81, 'Japan'),
]

country_code = {country: code for code, country in DIAL_CODES}
print(country_code)
code_country = {code: country.upper() for country, code in country_code.items() if code < 66}
print(code_country)

# 结果:
{'China': 86, 'India': 91, 'United States': 1, 'Indonesia': 62, 'Brazil': 55,
'Pakistan': 92, 'Bangladesh': 880, 'Nigeria': 234, 'Russia': 7, 'Japan': 81}
{1: 'UNITED STATES', 62: 'INDONESIA', 55: 'BRAZIL', 7: 'RUSSIA'}

2.3 两个重要的映射方法update和setdefault

2.3.1 update方法

它的参数列表如下:

1
dict.update(m, [**kargs])

update方法处理参数m的方法是典型的“鸭子类型”。该方法首先检测m是否有keys方法,如果有,那么update方法就把m当做映射对象来处理(即使它并不是映射对象);否则退一步,把m当做包含了键值对(key, value)元素的迭代器。

Python中大多数映射类的构造方法都采用了类似的逻辑,因此既可用一个映射对象来新建一个映射对象,也可以用包含(key, value)元素的可迭代对象来初始化一个映射对象。

2.3.2 setdefault处理不存在的键

当更新字典时,如果遇到原字典中不存在的键时,我们一般最开始会想到如下两种方法:

1
2
3
4
5
6
7
8
9
# 方法1
if key not in my_dict:
my_dict[key] = [] # 如果字典中不存在该键,则为该键创建一个空list
my_dict[key].append(new_value)

# 方法2
temp = my_dict.get(key, []) # 去的key对应的值,如果key不存在,则创建空list
temp.append(new_value)
my_dict[key] = temp # 把新列表放回字典

以上两种方法至少进行2次键查询,如果键不存在,第一种方法要查询3次,非常低效。但如果使用setdefault方法,则只需一次就可以完成上述操作:

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

2.4 映射的弹性键查询

上述的setdefault方法在每次调用时都要我们手动指定默认值,那有没有什么办法能方便一些,在键不存在时,直接返回我们指定的默认值?两个常用的方法是:①使用defaultdict类;②自定义一个dict子类,在子类中实现__missing__方法,而这个方法又有至少两种方法。

2.4.1 defaultdict类

collections.defaultdict能优雅的解决3.3.2中的问题:

1
2
3
import collections
my_dict = collections.defaultdict(list)
my_dict[key].append(new_value) # 我们不需要判断键key是否存在于my_dict中

在实例化defaultdict时,需要给构造方法提供一个可调用对象(实现了__call__方法的对象),这个可调用对象存储在defaultdict类的属性default_factory中,当__getitem__找不到所需的键时就会通过default_factory来调用这个可调用对象来创建默认值。

上述代码中my_dict[key]的内部过程如下(假设key是新键):

  1. 调用list()来创建一个新列表;
  2. 把这个新列表作为值,key作为它的键,放到my_dict中;
  3. 返回这个列表的引用

注意

  • 如果在实例化defaultdict时未指定default_factory,那么在查询不存在的键时则会触发KeyError
  • defaultdict中的default_factory只会在__getitem__里被调用,在其它的方法里完全不会发挥作用!比如,dd是个defaultdict,k是个不存在的键,dd[k]这个表达式则会调用default_factory,并返回默认值,而dd.get(k)则会返回None

特殊方法__missing__

其实上述的功能都得益于特殊方法__missing__,实际调用default_factory的就是该特殊方法,且该方法只会被__getitem__调用。即:__getitem__调用__missing____missing__调用default_factory

所有的映射类型在处理找不到键的情况是,都会牵扯到该特殊方法。基类dict没有定义这个方法,但dict有该方法的声明。

下面通过编写一个继承自dict的类来说明如何使用__missing__实现字典查询,不过这里并没有在找不到键时调用一个可调用对象,而是抛出异常。

2.4.2 自定义映射类:继承自dict

某些情况下可能希望在查询字典时,映射里的键通通转换成str类,但为了方便,也允许使用非字符串作为建,比如我们希望实现如下效果:

1
2
3
4
5
6
7
8
9
>>> d = StrKeyDict0([("2", "two"), ("3", "three")])
>>> d["2"]
'two'
>>> d[3]
'three'
>>> d[1]
Traceback (most recent call last):
...
KeyError: "1"

以下便是这个类的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class StrKeyDict0(dict):
def __missing__(self, key):
if isinstance(key, str): # 必须要由此判断,否则无限递归
raise KeyError(key)
return self[str(key)]

# 为了和__getitem__行为一致,所以必须实现该方法,例子在3.4.3中
def get(self, key, default=None):
try:
return self[key]
except KeyError:
return default

def __contains__(self, key):
return key in self.keys() or str(key) in self.keys()

说明:

  • 第3行:这里的isinstance(key, str)测试是必需的。如果没有这个测试,那么当str(key)是个不存在的键时便会发生无限递归,因为第4行self[str(key)]会调用__getitem__,进而又调用__missing__,然后一直重复下去。
  • 第13行:为了保持一致性,__contains__方法在这里也是必需的,因为k in d这个操作会调用该方法。但是从dict继承到的__contains__方法在找不到键的时候不会调用__missing__(间接调用,不会直接调用)。
  • 第14行:这里并没有使用更具Python风格的写法:key in my_dict,因为这样写会使__contains__也发生递归调用,所以这里采用了更显式的方法key in self.keys。同时需要注意的是,这里有两个判断,因为我们本没有强行限制所有的键都必须是str,所以字典中可能存在非字符串的键(key in self.keys())。
  • k in my_dict.keys()这种操作在Python3中很快,即使映射类型对象很庞大也很快,因为dict.keys()返回的是一个”视图“,在视图中查找一个元素的速度很快。

2.4.3 子类化UserDict

如果要自定义一个映射类型,更好的策略是继承collections.UserDict。它是把标准dict用纯Python又实现了一遍。之所以更倾向于从UserDict而不是从dict继承,是因为后者有时会在某些方法的实现上走一些捷径,导致我们不得不在它的子类中重写这些方法,而UserDict则没有这些问题。也正是由于这个原因,如果上个例子要实现将所有的键都转换成字符串,还需要做很多工作,而从UserDict继承则能很容易实现。

注意:如果我们想在上个例子中实现__setitem__,使其将所有的键都转换成str,则会发生无限递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
-- snip -- 
def __setitem__(self, key, value):
self[str(key)] = value

if __name__ == "__main__":
d = StrKeyDict0()
d[1] = "one"
print(d[1])

# 结果:
File "test.py", line 17, in __setitem__
self[str(key)] = value
[Previous line repeated 329 more times]
RecursionError: maximum recursion depth exceeded while calling a Python object

下面使用UserDict来实现一遍StrKeyDict,它实现了__setitem__方法,将所有的键都转换成str。注意这里并没有自行实现get方法,原因在后面。

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
import collections

class StrKeyDict(collections.UserDict):
def __missing__(self, key):
if isinstance(key, str):
raise KeyError(key)
return self[str(key)]

def __contains__(self, key):
# 相比于StrKeyDict0,这里只有一个判断,因为键都被转换成字符串了
# 而且查询是在self.data属性上查询,而不是在self.keys()上查询。
return str(key) in self.data

def __setitem__(self, key, value):
# 把具体实现委托给了self.data属性
self.data[str(key)] = value

if __name__ == "__main__":
d = StrKeyDict()
d[1] = "one"
print(d[1])
print(d)

# 结果
one
{'1': 'one'}

因为UserDict继承自MutableMapping,所以StrKeyDict里剩下的映射类型的方法都是从UserDictMutableMappingMapping继承而来,这些方法中有两个值得关注:

MutableMapping.update

这个方法不但可以直接用,它还用在__init__里,使其能支持各种格式的参数。而这个update方法内部则使用self[key] = value来添加新值,所以它其实是在使用我们定义的__setitem__方法。

Mapping.get

对比StrKeyDict0StrKeyDict的代码可以发现,我们并没有为后者定义get方法。前者如果不定义get方法,则会出现如下情况:

1
2
3
4
5
6
>>> d = StrKeyDict0()
>>> d["1"] = one
>>> d[1]
'one'
>>> d.get(1)
None # 和__getitem__的行为不符合,应该返回'one'

而在StrKeyDict中则没有必要,因为UserDict继承了Mappingget方法,而查看源代码可知,这个方法的实现和StrKeyDict0.get一模一样。

2.5 其他字典

2.5.1 collections.OrderedDict

这个类型在添加键的时候会保持原序,即对键的迭代次序就是添加时的顺序。它的popitem方法默认删除并返回字典中的最后一个元素。值得注意的是,从Python3.6开始,dict中键的顺序也保持了原序。但出于兼容性考虑,如果要保持有序,还是推荐使用OrderedDict

2.5.2 collections.ChainMap

该类型可容纳多个不同的映射对象,然后在查找元素时,这些映射对象会被当成一个整体被逐个查找。这个功能在给有嵌套作用域的语言做解释器的时候很有用,可以用一个映射对象来代表一个作用域的上下文。

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

2.5.3 collections.Counter

这个类会给键准备一个整数计数器,每次更新一个键时就会自动增加这个计数器。所以这个类型可以用来给可散列对象计数,或者当成多重集来使用(相同元素可以出现不止一次的集合)。

1
2
3
4
5
6
7
8
9
>>> import collections
>>> 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(2)
[('a', 10), ('z', 3)]

2.5.4 不可变映射类型

标准库中所有的映射类型都是可变的,但有时候会有这样的需要,比如不能让用户错误地修改某个映射。从Python3.3开始,types模块中引入了一个封装类MappingProxyType。如果给这个类一个映射,它返回一个只读的映射视图。虽然是个只读视图,但它是动态的,如果原映射被修改,我们也能通过这个视图观察到变化。以下是它的一个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>>> from types import MappingProxyType
>>> d = {1: "A"}
>>> d_proxy = MappingProxyType(d)
>>> d_proxy
mappingproxy({1: 'A'})
>>> d_proxy[1]
'A'
>>> d_proxy[2] = "x"
Traceback (most recent call last):
File "<input>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment
>>> d[2] = "B"
>>> d_proxy
mappingproxy({1: 'A', 2: 'B'})
>>> d_proxy[2]
'B'

3. 集合

和前面的字典一样,先来看看集合的超类的继承关系:

集合的本质是许多唯一对象的聚集。即,集合可以用于去重。集合中的元素必须是可散列的,set类型本身是不可散列的,但是frozenset可以。也就是说可以创建一个包含不同frozensetset

集合的操作

注意两个概念:字面量句法,构造方法:

1
2
3
s = {1, 2, 3}  # 这叫字面量句法
s = set([1, 2, 3]) # 这叫构造方法
s = set() # 空集, 不是s = {},这是空字典!

字面量句法相对于构造方法更快更易读。后者速度之所以慢是因为Python必须先从set这个名字来查询构造方法,然后新建一个列表,最后再把这个列表传入到构造方法里。而对于字面量句法,Python会利用一个专门的叫做BUILD_SET的字节码来创建集合。

集合的字面量——{1}{1, 2}等——看起来和它的数学形式一模一样。但要注意空集,如果要创建一个空集,只能是temp = set(),而不是temp = {},后者创建的是一个空字典。

frozenset的标准字符串表示形式看起来就像构造方法调用一样:

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

对于frozenset,一旦创建便不可更改,常用作字典的键的集合。

除此之外,集合还实现了很多基础的中缀运算符,如交集a & b,合集a | b,差集a - b等,还有子集,真子集等操作,由于这类操作太多,这里不再一一列出。下面代码得到两个可迭代对象中共有的元素个数,这是一个常用操作:

1
2
3
found = len(set(needles) & set(haystack))
# 另一种写法
found = len(set(needles).intersection(haystack))

集合推导

和列表推导,字典推导一样,集合也有推导(setcomps):

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

4. dict和set的背后

有人做过实验(就在普通笔记本上),在1,000,000个元素中找1,000个元素,dictset两者的耗时比较接近,大约为0.000337s,而使用列表list,耗时是97.948056s,list的耗时是dictset的约29万倍。而造成这种差距的最根本的原因是,list中找元素是按位置一个一个找(虽然有像折半查找这类的算法,但本质依然是一个位置接一个位置的比较),而dict是根据某个信息直接计算元素的位置,显然后者速度要比挨个找快很多。而这个计算方法统称为哈希函数(hash),即hash(key)-->position

碍于篇幅,关于哈希算法的原理(哈希函数的选择,冲突的解决等)这里便不再赘述,相信经常和算法打交道或者考过研的老铁们一定不陌生。

哈希表(也叫散列表)其实是个稀疏数组(有很多空元素的数组),每个单元叫做表元(bucket),Python中每个表元由对键的引用和对值的引用两部分组成。因为所有表元的大小一致,所以当计算出位置后,可以通过偏移量来读取某个元素(变址寻址)。

Python会设法保证大概还有三分之一的表元是空的,当快要达到这个阈值的时候,原有的哈希表会被复制到一个更大的空间中。

4.1 哈希值和相等性

如果要把一个对象放入哈希表中,首先要计算这个元素的哈希值。Python中可以通过函数hash()来计算。内置的hash()可用于所有的内置对象。如果是自定义对象调用hash(),实际上运行的是自定义的__hash__。如果两个对象在比较的时候相等的,那么它们的哈希值必须相等,否则哈希表就不能正常工作。比如,如果1 == 1.0为真,那么hash(1) == hash(1.0)也必须为真,但其实这两个数字的内部结构完全不一样。而相等性的检测则是调用特殊方法__eq__

补充:从Python3.3开始,为了防止DOS攻击,strbytesdatetime对象的哈希值计算过程中多了随机的“加盐”步骤。所加的盐值是Python进程中的一个常量,但每次启动Python解释器都会生成一个不同的盐值。

4.2 Python中的哈希算法

为获取my_dict[search_key]背后的值(不是哈希值),Python首先会调用hash(search_key)计算哈希值,然后取这个值最低的几位数字当作偏移量(这只是一种哈希算法)去获取所要的值,如果发生了冲突,则再取哈希值的另外几位,知道不冲突为止。

在插入新值的时候,Python可能会按照哈希表的拥挤程度来决定是否要重新分配内存为它扩容。如果增加了散列表的大小,散列值所占的位数和用作索引的位数都会随之增加(目的是为了减少冲突发生的概率)。

这个算法看似费事,但实际上就算dict中有数百万个元素,多数的搜索过程中并不会发生冲突,平均下来每次搜索可能会有一到两次冲突。

4.3 dict的优劣

1、键必须是可散列的

一个可散列对象必须满足一下要求:

(1)支持hash()函数,并且通过__hash__()方法得到的哈希值是不变的;

(2)支持通过__eq__()方法来检测相等性;

(3)若a == b为真,则hash(a) == hash(b)也必须为真。

所有自定义的对象默认都是可散列的,因为它们的哈希值有id()函数来获取,而且它们都是不相等的。如果你实现了一个类的__eq__方法,并且希望它是可散列的,那请务必保证这个类满足上面的第3条要求。

2、字典在内存上的开销巨大

典型的用空间换时间的算法。因为哈希表是稀疏的,这导致它的空间利用率很低。

如果需要存放数量巨大的记录,那么放在由元组或命名元组构成的列表中会是比较好的选择;最好不要根据JSON的风格,用由字典组成的列表来存放这些记录。

用元组代替字典就能节省空间的原因有两个:①避免了哈希表所耗费的空间;②无需把记录中字段的名字在每个元素里都存一遍。

关于空间优化:如果你的内存够用,那么空间优化工作可以等到真正需要的时候再开始,因为优化往往是可维护性的对立面。

3、键查询很快

本节最开始的实验已经证明,字典的查询速度非常快。如果再简单计算一下,上面的实验中,在有1000万个元素的字典里,每秒能进行200万次键查询。

这里之所以说的是“键查询”,而不是“查询”,是因为有可能值的数据不在内存,内在磁盘中。一旦涉及到磁盘这样的低速设备,查询速度将大打折扣。

4、键的次序取决于添加顺序

当往dict里添加新键而又发生冲突时,新键可能会被安排存放到另一个位置。并且同一组数据,每次按不同顺序进行添加,那么即便是同一个键,同一个算法,最后的位置也可能不同。最典型的就是这组数据全冲突(所有的hash值都一样),然后采用的是线性探测再散列解决冲突,这时的顺序就是添加时的顺序。

5、向字典中添加新键可能会改变已有键的顺序。

无论何时往字典中添加新的键,Python解释器都有可能做出扩容的决定。扩容时,在将原有的元素添加到新表的过程中就有可能改变原有元素的顺序。如果在迭代一个字典的过程中同时对修改字典,那么这个循环就很有可能会跳过一些键。

补充:Python3中,.keys().items().values()方法返回的都是字典视图。

4.4 set的实现

setfrozenset也由哈希表实现,但它们的哈希表中存放的只有元素的引用(类似于在字典里只存放了键而没放值)。在set加入到Python之前,都是把字典加上无意义的值来当集合用。5.3中对字典的几个特点也同样适用于集合。

5. 总结

字典是Python的基石。除了基本的dict,标准库中还有特殊的映射类型:defaultdictOrderedDictChainMapCounterUserDict,这些类都在collections模块中。

大多数映射都提供了两个强大的方法:setdefaultupdate。前者可避免重复搜索,后者可批量更新。

在映射类型的API中,有个很好用的特殊方法__missing__,可以通过这个方法自定义当对象找不到某个键时的行为。

setdict的实现都用到了哈希表,两者的查找速度都很快,但空间消耗大,典型的以空间换时间的算法。

VPointer wechat
欢迎大家关注我的微信公众号"代码港"~~
您的慷慨将鼓励我继续创作~~