深度剖析Python字典和集合

“字典这个数据结构活跃在所有Python程序的背后，即便你的源码里并没有直接用到它”，摘抄自《代码之美》第18章Python的字典类：如何打造全能战士。字典是Python语言的基石！在函数的关键字参数、实例的属性和模块的命名空间都能够看到它的身影，我们自己写代码时也经常会用到。

“集合”这个概念在Python中算是比较年轻的，使用率也比较低，我只在元素去重和求差集并集时使用过。

字典和集合有个共同点，它们都是基于同一种数据结构实现的：散列表，又叫做哈希表，Hash Table。要理解集合和字典，得先理解散列表。要理解散列表，得先理解可散列的数据类型。

可散列的数据类型

在Python词汇表中，关于可散列类型的定义有这样一段话：

“如果一个对象是可散列的，那么在这个对象的生命周期中，它的散列值是不变的，而且这个对象需要实现__hash__（）方法。另外可散列对象还要有__eq__()方法，这样才能跟其他键做比较。如果两个可散列对象是相等的，那么它们的散列值一定是一样的。”

重点是散列值不变！

字典的键必须是可散列的，否则变来变去就找不到映射了。

于是可以得知原子不可变数据类型（str、bytes、和数值类型）都是可散列类型，frozenset冻结不可变集合，也是可散列的。元组有两种情况，一、如果所有元素都是可散列的数据类型，那么元组是可散列的，二、如果元组里面的元素是其他可变类型的引用，那么元组是不可散列的，示例：

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
-3907003130834322577

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

>>> tf = (1, 2, frozenset([30, 40]))
>>> hash(tf)
5149391500123939311

其中tl元组包含了列表（可变），hash()函数报错了。

散列表简介

假设你们班级100个同学每个人的学号是由院系-年级-班级-编号组成，例如学号为01100168表示是01系-10级-01班-68号。为了快速查找到68号的成绩信息，可以建立一张表，但是不能用学号作为下标，学号的数值实在太大。因此将学号除以1100100取余，即得到编号作为该表的下标。要查找学号为01100168的成绩的时候，只要直接访问表下标为68的数据即可。

散列表就是一张表，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查询速度。这个映射函数称作散列函数，存放记录的表称作散列表。再举个例子，比如下面这几个人物，按数组存储：

这样我要找到沈嘉文的电话号码，需要顺序查找对比整个数组，第一个余罪，不是，第二个傅老大，不是，直到第三个才找到沈嘉文。换成散列表：

左边是姓名首字母的Key，右边是电话号码的Value，当我们要查找沈嘉文的时候，通过计算，在s位置，1次查找就找到了。

为了不让本文显得生硬，接下来先介绍字典和集合，最后再看看散列表是如何实现它们的。

字典

Mapping和MutableMapping

Mapping和MutableMapping是collections.abc模块中的两个抽象基类，它们的作用是作为形式化的文档，定义了构建一个映射类型所需要的最基本的接口。比如判断是否是映射类型：

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

非抽象映射类型一般不会直接继承这两个抽象基类，而是会直接对dict或collections.UserDict进行扩展。正是如此，Python标准库里的所有映射类型都是利用dict来实现的。

dict构造方法

dict构造方法如下：

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

>>> a == b == c == d == e
True

一共竟然有五种！还有第六种：字典推导，跟列表推导和生成器表达式类似：

>>> my_list = [("two", 2), ("one", 1), ("three", 3)]
>>> my_dict = {en: num for en, num in my_list}
>>> my_dict
{'two': 2, 'one': 1, 'three': 3}

常见映射方法

除了dict，还有两个dict的变种：defaultdict和OrderedDict，它们对常见映射方法的支持区别如下：

鸭子类型

鸭子类型是动态语言的说法，指一个对象只要“看起来像鸭子，走起路来像鸭子”，那它就可以被看做是鸭子。比如：

class Animal(object):
    
    def run(self):
        print("The animal is running...")

class Dog(Animal):

    def run(self):
        print('The dog is running...')

class Cat(Animal):

    def run(self):
        print('The cat is running...')

def make_run(animal):
    animal.run()

dog = Dog()
cat = Cat()
make_run(dog)
make_run(cat)

对于 make_run() 函数来说，传入的参数并不一定需要是 Animal 类型的，只需要保证传入的对象有一个 run() 方法即可。

在静态语言中，如果需要传入 Animal 类型，则传入的对象就必须是 Animal 类型或者它的子类，否则，将无法调用 run() 方法。

update

update方法用来更新字典里对应的条目，它处理参数m的方式，是典型的“鸭子类型”。函数首先检查m是否有keys方法，如果有，那么update函数就把它当作映射对象来处理，不关心是不是真的映射类型。如果没有，函数会把m当作包含了键值对(key, value)元素的迭代器。

Python里大多数映射类型的构造方法都采用了类似的逻辑。

setdefault

当字典dk不能找到正确的键的时候，Python会抛出异常。也许每个Python使用者都知道可以用d.get(k, default)来代替dk，给找不到的键一个默认的返回值。但是要更新字典时，该怎么办呢？比如要在my_dict中添加键为b，值为列表1, 2, 3, 4, 5, 6的键值对：

my_dict = {"a": 1}
key = "b"
my_list = range(2, 7)

# {"a": 1, "b": [2, 3, 4, 5, 6]}

不能用mylist[key] = my_list，必须用for循环动态append。

方法1，先添加空列表，再append：

my_dict[key] = []
for i in my_list:
    my_dict[key].append(i)

方法2，第一次没有键，先用get查询返回空列表，再append，再赋值：

for i in my_list:
    temp = my_dict.get(key, [])
    temp.append(i)
    my_dict[key] = temp

方法3，先用if判断，再append：

for i in my_list:
    if key not in my_dict:
        my_dict[key] = []
    my_dict[key].append(i)

方法4，一行代码：

for i in my_list:
    # 除了for循环，一行代码
    my_dict.setdefault(key, []).append(i)

Python骚操作总是这么多！setdefault你学会了么？

setdefault只需要进行一次键查询就可以完成操作，节省键查询，程序更高效。

defaultdict字典变种

有没有办法直接执行my_dict[key].append(i)呢？答案是有的，借助defaultdict可以实现：

import collections

my_dict = collections.defaultdict(list)
my_dict["a"] = 1
key = "b"
my_list = range(2, 7)

for i in my_list:
    my_dict[key].append(i)

my_dictkey会按以下步骤执行：

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

通过列表引用继续执行append()函数。

defaultdict的__init__(self, default_factory=None, **kwargs)有个参数default_factory用来生成默认值，必须是可调用对象。比如：

def init_list():
    return [0]

my_dict = collections.defaultdict(init_list)

注意了！此时my_dict的值是{}空字典，default_factory只会在__getitem__里被调用，也就是说my_dict[key]时才会用这个默认值：

print(my_dict)  # defaultdict(<function init_list at 0x014E84F0>, {})
print(my_dict["b"]) # defaultdict(<function init_list at 0x014E84F0>, {'b': [0]})

my_dict.get("b")不会调用__getitem__，不会使用default_factory，返回值为None。

为什么get不会调用__getitem__?__getitem__是为[]提供的语法糖，get()已经是取值方法了，不需要这个语法糖。

default_factory默认为None，如果不指定，查询不存在的键会触发KeyError，这个道理和[]取值是一样的。

所有这一切背后的功臣其实是魔法方法__missing__。所有的映射类型在处理找不到的键的时候，都会牵扯到__missing__方法。基类dict并没有定义这个方法，但是dict是能知道它的，如果一个类继承了dict，然后实现了__missing__方法，Python就会自动调用它，而不是抛出一个KeyError异常。

__missing__只会被__getitem__调用，这就是default_factory只对__getitem__有作用的原因！

示例如下，当用非字符串键查询时，转换为字符串键查询：

class StrKeyDict0(dict):  # <1>

    def __missing__(self, key):
        if isinstance(key, str):  # <2> 不加这个判断，如果str(key)不存在，就会第3处再次调用__missing__无限递归
            raise KeyError(key)
        return self[str(key)]  # <3>

    def get(self, key, default=None):
        try:
            return self[key]  # <4>
        except KeyError:
            return default  # <5>

    # k in my_dict 会导致__contains__递归调用，所以这里用了self.keys()    
    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys()  # <6>

像k in my_dict.keys()这种操作在Python3中是很快的，而且即便映射类型对象很庞大也没关系，这是因为dict.keys()的返回值时一个“视图”。

OrderdDict及其他字典变种

collections.OrderedDict

在Django REST framework中的分页就用到了OrderedDict，返回分页数据必须是有序的，否则会提示UnOrdered。OrderedDict的popitem方法默认删除并返回字典里的最后一个元素（栈），如果加了参数OrderedDict(last=False)，那么它会删除并返回第一个被添加进度的元素（队列）。

collections.ChainMap

示例：

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

该类型可以容纳多个不同的映射对象，在按键查找时，这些对象会被当作一个整体被逐一查找。

collections.Counter

示例：

>>> 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()
[('a', 10), ('z', 3), ('b', 2), ('r', 2), ('c', 1), ('d', 1)]
>>> ct.most_common(2)
[('a', 10), ('z', 3)]

Counter是用来给可散列表对象计数的。

collections.UserDict

让用户继承写子类。

它比dict更适合继承的原因是，后者有时会在某些方法的实现上走一些捷径，导致我们不得不在它的子类中重写这些方法，而UserDict就不需要。

不可变映射类型

借助MappingProxyType，可以实现不可变字典。它返回的是一个只读的视图，会跟随源字典动态展示，但是无法对源字典做出改动。示例：

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

集合

集合的字面量是{1}、{1, 2}，和字典有点像，不同的是集合只有值没有键。

set构造方法

set构造方法如下：

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

前者比后者更快更易读，因为对于前者，Python会利用一个专门的叫做BUILD_SET的字节码来创建集合。而对于后者，Python必须先从set这个名字来查询构造方法，然后新建一个列表，最后再把这个列表传入到构造方法里。

{}是空字典，空集合必须用set()。

集合也有集合推导：

>>> my_set = {x for x in range(1, 4)}
>>> my_set
{1, 2, 3}
>>> type(my_set)
<class 'set'>

集合还有个不可变类型叫做frozenset，如同元组之于列表，它的构造函数如下：

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

只有这一种方法，没有字面量。

集合的操作

集合的本质是许多唯一对象的聚集，它最常见的操作是用来去重：

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

除此之外，集合还能进行数学运算，比如求交集、并集、差集等。示例，求needles的元素在haystack里出现的次数，暴力解法：

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

集合解法：

found = len(needles & haystack)

即使不是set也能先转换为set：

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

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

集合支持的操作如下：

散列表揭秘

这一部分的内容略微有点硬，请注意提前喝点水！

从上篇的简介可以知道，散列表就是一张表，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录。散列表其实是一个稀疏数组（总是有空白元素的数组称为稀疏数组），散列表里的单元叫作表元，在dict的散列表中，每个键值对占用一个表元，每个表元有两个部分，一个是对键的引用，另一个是对值的引用，因为所有表元的大小一致，所以可以通过偏移量来读取某个表元。

为什么要用稀疏数组？举个例子，身份证号411697199702076425，如果把它作为键存储到数组中，虽然能用O(1)时间就找到，但是需要开辟一个999999999999999999大的空间。假如只有1的空间，就只能把最后一位作为键存储到数组中，多个身份证号的键就容易冲突，得多看n位才能找到，要用O(n)时间。空间既不能太大，也不能太小，需要结合时间，在两者之间产生一个平衡，即空间和时间的平衡，所以要用稀疏数组！

Python会设法保证大概还有三分之一的表元是空的，用空间换时间，提高散列表查询效率。如果剩余空间不足，原有的散列表会被复制到一个更大的空间里面。

散列表的键值，又称为散列值，Python中可以用hash()方法来计算所有内置类型对象的散列值。

自定义类型实际上调用的是自定义的__hash__。

如果两个对象在比较的时候是相等的，那么它们的散列值必须相等，否则散列表就不能正常运行了：

>>> a = 1
>>> b = 1
>>> a == b
True
>>> hash(a)
1
>>> hash(b)
1
>>> a = "x"
>>> b = "x"
>>> a == b
True
>>> hash(a)
706802421
>>> hash(b)
706802421

越是相似但不相等的对象，它们的散列值的差别越大：

>>> a = 1.0001
>>> b = 1.0002
>>> hash(a)
783616733
>>> hash(b)
1567233465

这是因为散列值是散列表索引，它们必须在索引空间尽量分散开来。

我的理解是，散列值是要被尽量打散的，1.0001和1.0002相差0.0001，这个0.0001被打散后的值导致它们的散列值相差很大。

了解了基本概念后，该看下散列表算法了（不用害怕，只有思路，没有代码）：

为了获取my_dictsearch_key背后的值：

1. 调用hash(search_key)计算search_key的散列值。
2. 把最低几位数字当做偏移量，在散列表里查找表元。
3. 如果表元为空，返回KeyError。
4. 如果表元有值，表元里会有一对found_key:found_value。
5. 检验search_key == found_key，相等就返回found_key。
6. 不相等的情况称为散列冲突！为了解决冲突，算法会在散列值中另外再取几位，处理一下，把新得到的数字当做索引来寻找表元。

实际上散列冲突发生概率非常小，散列表查询效率非常高！

添加新元素和更新现有键值的操作几乎一样，区别在于添加新元素时发现空表元，会放入一个新元素；更新现有键值时，会把原表里的值替换成新值。

另外，添加新元素时，Python会根据剩余空间大小决定是否要重新分配内容为它扩容。

散列表与dict

dict的键必须是可散列的：

1. 支持hash()函数，通过__hash__()得到的散列值是不变的。
2. 支持通过__eq__()来判断是否相等。
3. 若a == b为真，则hash(a) == hash(b)也为真。

所有由用户自定义的对象默认都是可散列的，因为它们的散列值由id()来获取（符合第1条），而且它们都是不相等的（符合第2条和第3条）。

dict的实现是典型的空间换时间：键查询很快，在内存上的开销巨大！

dict键的次序取决于添加顺序，当往dict添加新键时，如果发生了散列冲突，新键可能会被放到另一个位置，键的位置不一样，次序也就不一样了。比如：

my_list = [("a", 1), ("b", 2)]

my_dict1 = dict(my_list)
my_dict2 = dict(reversed(my_list))

print(my_dict1)  # {'a': 1, 'b': 2}
print(my_dict2)  # {'b': 2, 'a': 1}
print((my_dict1 == my_dict2))  # True

但是它们是相等的，因为它们所包含的数据是一样的。

值得注意的是，往字典里添加新键可能会改变已有键的顺序！当空间不足，Python会为字典扩容，新建一个更大的散列表，并把字典已有的元素添加进去，这个过程中可能会发生散列冲突，导致新散列表中键的次序变化。

由此可知，不要对字典同时进行迭代和修改，循环很可能会跳过一些键，甚至是跳过那些字典中已经有的键。最好分成两步来做，首先对字典进行迭代，得出需要添加的内容，把这些内容放在一个新字典里；在迭代结束后再对原有字典进行更新。

散列表与set

集合的散列表里存放的只有元素的引用（就像在字典里只存放键而没有相应的值）。上一节讨论的散列表与dict的内容，对集合来说几乎都是适用的。

在set加入Python以前，原书作者他们是把字典加上无意义的值当作集合来用的。

小结

本文介绍了字典和集合，包含了一些Python骚操作，也用示例解释了什么是鸭子类型，重点揭秘了散列表的原理，正是由于散列表的支撑，dict和set的查询效率非常高，代价是空间换时间，内容占用也比较大，当数据量很大时，不适合用dict和set，而应该考虑用元组或由具名元组构成的列表。散列表也给dict和set带来了限制，比如dict键的次序取决于添加顺序，往字典里添加新键可能会改变已有键的顺序等。

参考资料：

《流畅的Python》

https://zhuanlan.zhihu.com/p/64853220

https://www.jianshu.com/p/101c263cd93e

http://www.woshipm.com/pmd/805326.html

https://zhuanlan.zhihu.com/p/149463934?from_voters_page=true

https://www.jianshu.com/p/e97044a8169a

https://github.com/fluentpython/example-code/blob/master/03-dict-set/strkeydict0.py

https://www.jianshu.com/p/4e64fce04a38