Fluent Python 笔记 —— 字典与集合

一、映射类型

标准库里的所有映射类型都是利用 dict 实现的，它们有个共同的限制：其中的键必须是可散列的数据类型。
关于可散列的数据类型的定义：
若某对象是可散列的，则它的散列值在其整个生命周期中是保持不变的。该对象需要实现 __hash__ 方法和 __qe__ 方法（跟其他键做比较）。如果两个可散列对象是相等的，那么他们的散列值一定相等。

不可变数据类型中的 str、bytes 和数字都是可散列类型。
虽然元组本身是不可变序列，但元组中的元素有可能是其他可变类型的引用。只有当一个元组中包含的所有元素都是可散列类型的情况下，该元组才是可散列的。

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

一般用户自定义类型的对象都是可散列的，因此这些对象在比较时都是不相等的。
若某个对象实现了 __eq__ 方法，并且在方法中用到了该对象的内部状态，则只有当这些内部状态都是不可变类型的情况下，该对象才是可散列的。

二、字典推导

>>> DIAL_CODES = [
...     (86, 'China'),
...     (91, 'India'),
...     (1, 'America'),
...     (55, 'Brazil'),
...     (7, 'Russia')
... ]
>>> country_code = {country: code for code, country in DIAL_CODES}
>>> country_code
{'China': 86, 'India': 91, 'America': 1, 'Brazil': 55, 'Russia': 7}
>>> {code: country.upper() for country, code in country_code.items() if code < 66}
{1: 'AMERICA', 55: 'BRAZIL', 7: 'RUSSIA'}

三、setdefault 处理找不到的键

以下代码的写法：

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

其效果等同于如下代码：

1
2
3

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

都是获取 my_dict 中 key 键对应的值（如果该 key 不存在，则新增 key 并令其值为 []），然后向 key 对应的值（列表）中添加新元素。
只不过后者至少要进行两次键查询（如果键不存在，则执行三次键查询），而使用 setdefault 只需要一次键查询就可以完成整个操作。setdefault 在获取 key 键对应的值时，如果该 key 不存在，则把 key 和空列表直接放进映射并返回空列表，因而不需要执行第二次键值查找。

四、弹性键查询

defaultdict

collections.defaultdict 可以做到即便某个键在映射里不存在，也能够在读取这个键的时候得到一个默认值。只需要用户在初始化 defaultdict 对象时，为其指定一个创建默认值的方法。
即在实例化 defaultdict 的时候，向构造方法提供一个可调用对象，该对象会在 __getitem__ 碰到找不到的键的时候被调用，让 __getitem__ 返回某种默认值。

如 dd = defaultdict(list)。若键 new-key 在 dd 中不存在，表达式 dd['new-key'] 会执行以下操作：

调用 list() 创建一个新列表
把新列表作为值，new-key 作为键存放到 dd 中
返回新列表的引用

这个用来生成默认值得可调用对象（list()）存放在名为 default_factory 的实例属性里。若创建 defaultdict 的时候没有指定 default_factory，则查询不存在的键会触发 KeyError。
这些特性背后依赖的是 __missing__ 特殊方法，这个特殊方法是所有映射类型都可以选择性地去支持的。

missing

所有的映射类型处理找不到的键的时候，都会涉及到 __missing__ 方法。虽然基类 dict 并没有定义这个方法，但如果有一个类继承了 dict，该类提供 __missing__ 方法，则 __getitem__ 找不到键的时候，会自动调用 __missing__ 而不会抛出 KeyError 异常。

__missing__ 方法只会被 __getitem__ 调用（比如在表达式 d[k] 中）。提供 __missing__ 方法对 get 或 __contains__ 方法的使用没有影响。

如需要实现一种自定义的映射类型，在查询的时候将映射里的键都转换成 str。示例代码如下：

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

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

运行结果如下：

>>> from strkeydict import StrKeyDict
>>> d = StrKeyDict([('2', 'two'), ('4', 'four')])
>>> d['2']
'two'
>>> d[4]
'four'
>>> d[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/starky/program/python/algorithm/strkeydict.py", line 5, in __missing__
    return self[str(key)]
  File "/home/starky/program/python/algorithm/strkeydict.py", line 4, in __missing__
    raise KeyError(key)
KeyError: '1'
>>> d.get('2')
'two'
>>> d.get(4)
'four'
>>> d.get(1, 'N/A')
'N/A'
>>> 2 in d
True
>>> 1 in d
False

StrKeyDict 继承自 dict，如果找不到的键本身是字符串，抛出 KeyError 异常；如果找不到的键不是字符串，则将其转换成字符串后再进行查找。
get 方法把查找工作用 self[key] 的形式委托给 __getitem__，这样在确定查找失败之前，还能通过 __missing__ 在给某个键一个机会。

isinstance(key, str) 在 __missing__ 中是必须的，若 str(k) 不是一个存在的键，代码就会陷入无限递归。因为 __missing__ 最后一行中的 self[str(key)] 会调用 __getitem__，而 str(key) 又不存在，则 __missing__ 又会被调用。

__contains__ 方法也是必须的，因为从 dict 继承到的 __contians__ 方法不会在找不到键时调用 __missing__ 方法。

不可变 Map

标准库里所有的映射类型都是可变的。从 Python 3.3 开始，types 模块引入了一个名为 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 "<stdin>", 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'

集合

集合的本质是许多唯一对象的聚集，可用于去重：

1
2
3

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

除了保证唯一性，集合还实现了很多基础的中缀运算符。比如 a | b 求并集，a & b 求交集，a - b 求差集等。合理使用这些运算符可以省去不必要的循环和逻辑操作，使代码行数更少且更易读。

比如有一个电子邮件地址的集合 haystack，还要维护一个较小的电子邮件集合 needles，然后求出 needles 中有多少地址同时也出现在了 heystack 里。
求 needles 的元素在 heystack 中出现的次数，两个变量都是集合类型，则只用一行代码即可实现：

1	found = len(needles & haystack)

若不使用交集操作的话，则需要通过以下代码实现：

1
2
3

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

散列表

散列表（Hash Map）是一种稀疏数组（即总是有空白元素的数组），散列表中的单元通常叫做表元（bucket）。在 dict 背后的散列表中，每个键值对都占用一个表元，每个表元都包含两个部分，对键的引用和对值的引用。因为所有表元的大小一致，可以通过偏移量来读取某个表元。

Python 会保证大概三分之一的表元是空的，当快要达到这个阈值时，原有的散列表会被复制到一个更大的空间里。把对象存入散列表中之前，需要先计算该元素键的散列值。

内置的 hash() 函数可用于计算所有内置类型对象的散列值。若自定义对象调用 hash()，实际上运行的是自定义的 __hash__ 方法。若两个对象比较时大小相等，则它们的散列值也必须相等。即 1 == 1.0 为真，则 hash(1) == hash(1.0) 也必须为真。

为了让散列值能够作为散列表索引使用，这些散列值必须在索引空间内尽量分散开。意味着在理想状态下，越是相似但不相等的对象，其散列值差别也越大。

>>> hash(1.0001)
230584300921345
>>> hash(1.0002)
461168601842689
>>> hash(1.0003)
691752902764033

散列表算法
为了获取 my_dict[search_key] 背后的值，Python 首先会调用 hash(search_key) 来计算 search_key 的散列值，将该值最低的几位数字作为偏移量（具体几位作为偏移量，需依据当前散列表的大小），在散列表里查找表元。若查找出的表元为空，则抛出 KeyError 异常。若表元非空，该表元中会有一对 found_key: found_value。Python 会检查 search_key == found_key 是否为真，若为真则返回 found_value。
若 search_key 与 found_key 不匹配，这种情况称为散列冲突。算法会在散列值中另外再取几位数字，用特殊方法处理一下，把新得到的数字作为索引继续寻找表元并重复以上步骤。

字典的特性

键必须是可散列的
可散列对象满足以下三个要求：

支持 hash() 函数，且通过 __hash__() 得到的散列值是不变的
支持通过 __eq__() 方法检测相等性
若 a == b 为真，则 hash(a) == hash(b) 也为真

所有用户自定义对象默认都是可散列的，其散列值有 id() 获取，且都不相等。

字典在内存上开销巨大
字典使用了散列表，散列表又必须是稀疏的，从而导致字典在空间的使用上效率低下。
若需要存放数量巨大的记录，放在由元组或具名元组构成的列表中会是比较好的选择。
用元组取代字典存储记录，一是避免了散列表所耗费的空间，二是无需把记录中字段的名字在每个元素里都存一遍，从而节省空间。
在用户自定义类型中，__slots__ 属性可以改变实例属性的存储方式，由 dict 变为 tuple。

字典的键查询很快
dict 的实现是典型的空间换时间。字典类型有着巨大的内存开销，但是它提供了无视数据量大小的快速访问。

键的次序取决于添加顺序

集合的特性

集合里的元素必须是可散列的

集合很消耗内存

可以很高效地判断元素是否存在于某个集合中

元素的次序取决于被添加到集合里的次序

参考资料

Fluent Python