字典（dict）这个数据结构在Python里无处不在，不但在各种程序里广泛使用，它也是 Python 语言的基石。模块的命名空间、实例的属性和函数的关键字参数中都可以看到字典的身影。正是因为字典至关重要，Python 对它的实现做了高度优化，而散列表则是字典类型性能出众的根本原因。集合（set）的实现也同样依赖于散列表。

字典

标准库里的所有映射类型都是利用 dict 来实现的，因此它们有个共同的限制，即只有可散列的数据类型才能用作这些映射里的键（只有键有这个要求，值并不需要是可散列的数据类型）。

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

Python中可散列的数据类型： 原子不可变数据类型（str、bytes 和数值类型）都是可散列类型，frozenset 也是可散列的，因为根据其定义，frozenset 里只能容纳可散列类型。元组的话，只有当一个元组包含的所有元素都是可散列类型的情况下，它才是可散列的。

>>> 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里所有的不可变类型都是可散列的”。这个说法其实是不准确的，比如虽然元组本身是不可变序列，它里面的元素可能是其他可变类型的引用。（恍然大悟，原来自己错了好几年。。）

创建字典的不同方式：

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

字典推导（dict comprehension）也可以用来建造新 dict:

>>> 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}
>>> country_code
{'Pakistan': 92, 'Bangladesh': 880, 'Japan': 81, 'China': 86, 'United States': 1, 'Indonesia': 62, 'Nigeria': 234, 'Brazil': 55, 'India': 91, 'Russia': 7}
>>> {code: country.upper() for country, code in country_code.items() if code < 66}
{1: 'UNITED STATES', 7: 'RUSSIA', 62: 'INDONESIA', 55: 'BRAZIL'}

用setdefault处理找不到的键。

像 k in my_dict.keys() 这种操作在 Python 3 中是很快的，而且即便映射类型对象很庞大也没关系。这是因为 dict.keys() 的返回值是一个“视图”。视图就像一个集合，而且跟字典类似的是，在视图里查找一个元素的速度很快。Python 2 的 dict.keys() 返回的是个列表，因此虽然上面的方法仍然是正确的，它在处理体积大的对象的时候效率不会太高，因为k in my_list 操作需要扫描整个列表。

从 dict 或者其他内置类继承不好。 colllections.UserDict 这个类其实就是把标准 dict 用纯 Python 又实现了一遍。UserDict 是让用户继承写子类的。UserDict 并不是 dict 的子类，但是 UserDict 有一个叫作 data 的属性，是 dict 的实例，这个属性实际上是 UserDict 最终存储数据的地方。 示例：

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):
        return str(key) in self.data

    def __setitem__(self, key, item):
        self.data[str(key)] = item

不可变映射类型:

从 Python 3.3 开始，types 模块中引入了一个封装类名叫 MappingProxyType。如果给这个类一个映射，它会返回一个只读的映射视图。虽然是个只读视图，但是它是动态的。这意味着如果对原映射做出了改动，我们通过这个视图可以观察到，但是无法通过这个视图对原映射做出修改。

用 MappingProxyType 来获取字典的只读实例 mappingproxy:

>>> from types import MappingProxyType
>>> d = {1:'A'}
>>> d_proxy = MappingProxyType(d)
>>> d_proxy
mappingproxy({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'

集合

集合中的元素必须是可散列的，set 类型本身是不可散列的，但是 frozenset 可以。

除了保证唯一性，集合还实现了很多基础的中缀运算符。给定两个集合 a 和 b，a | b 返回的是它们的合集，a & b 得到的是交集，而 a - b 得到的是差集。合理地利用这些操作，不仅能够让代码的行数变少，还能减少 Python 程序的运行时间。这样做同时也是为了让代码更易读，从而更容易判断程序的正确性，因为利用这些运算符可以省去不必要的循环和逻辑操作。

如果要创建一个空集，你必须用不带任何参数的构造方 法 set()。如果只是写成 {} 的形式，跟以前一样，你创建的其实是个空字典。

像 {1, 2, 3} 这种字面量句法相比于构造方法（set([1, 2, 3])）要更快且更易读。后者的速度要慢一些，因为 Python 必须先从 set 这个名字来查询构造方法，然后新建一个列表，最后再把这个列表传入到构造方法里。但是如果是像 {1, 2, 3} 这样的字面量，Python 会利用一 个专门的叫作 BUILD_SET 的字节码来创建集合。

用 dis.dis（反汇编函数）来看看两个方法的字节码的不同：

>>> from dis import dis
>>> dis('{1}')
>>> dis('set([1])')

集合推导：

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

unicodedata 模块里导入 name 函数，用以获取字符的名字。 把编码在 32~255 之间的字符的名字里有“SIGN”单词的挑出来，放到一个集合里。

中缀运算符需要两侧的被操作对象都是集合类型，但是其他的所有方法则只要求所传入的参数是可迭代对象。例如，想求 4 个聚合类型 a、b、c 和 d 的合集，可以用 a.union(b, c, d)，这里 a 必须是个 set，但是 b、c 和 d 则可以是任何类型的可迭代对象。

散列表

所有的 Python 程序员都从经验中得出结论，认为字典和集合的速度是非常快的。实际上是非常非常快的。dict和set的查找速度是极快的，归功于背后的散列表。

由于列表的背后没有散列表来支持 in 运算符，每次搜索都需要扫描一次完整的列表，导致所需的时间跟据大小呈线性增长。

散列表其实是一个稀疏数组（总是有空白元素的数组称为稀疏数组）。在一般的数据结构教材中，散列表里的单元通常叫作表元（bucket）。在 dict 的散列表当中，每个键值对都占用一个表元，每个表元都有两个部分，一个是对键的引用，另一个是对值的引用。因为所有表元的大小一致，所以可以通过偏移量来读取某个表元。

因为 Python 会设法保证大概还有三分之一的表元是空的，所以在快要达到这个阈值的时候，原有的散列表会被复制到一个更大的空间里面。

两个对象在比较的时候是相等的，那它们的散列值必须相等。

由于字典使用了散列表，而散列表又必须是稀疏的，这导致它在空间上的效率低下。举例而言，如果你需要存放数量巨大的记录，那么放在由元组或是具名元组构成的列表中会是比较好的选择；最好不要根据 JSON 的风格，用由字典组成的列表来存放这些记录。用元组取代字典就能节省空间的原因有两个：其一是避免了散列表所耗费的空间，其二是无需把记录中字段的名字在每个元素里都存一遍。记住我们现在讨论的是空间优化。如果你手头有几百万个对象，而你的机器有几个 GB 的内存，那么空间的优化工作可以等到真正需要的时候再开始计划，因为优化往往是可维护性的对立面。

dict 的实现是典型的空间换时间：字典类型有着巨大的内存开销，但它们提供了无视数据量大小的快速访问——只要字典能被装 在内存里。

无论何时往字典里添加新的键，Python 解释器都可能做出为字典扩容的决定。扩容导致的结果就是要新建一个更大的散列表，并把字典里已有的元素添加到新表里。这个过程中可能会发生新的散列冲突，导致新散列表中键的次序变化。如果你在迭代一个字典的所有键的过程中同时对字典进行修改，那么这个循环很有可能会跳过一些键——甚至是跳过那些字典中已经有的键。

由此可知，不要对字典同时进行迭代和修改。如果想扫描并修改一个字典，最好分成两步来进行：首先对字典迭代，以得出需要添加的内容，把这些内容放在一个新字典里；迭代结束之后再对原有字典进行更新。

在 Python 3 中，.keys()、.items() 和 .values() 方法返回的都是字典视图。也就是说，这些方法返回的值更像集合，而不是像 Python 2 那样返回列表。视图还有动态的特性，它们可以实时反馈字典的变化。

set 和 frozenset 的实现也依赖散列表，但在它们的散列表里存放的只有元素的引用（就像在字典里只存放键而没有相应的值）。在 set 加 入到 Python 之前，我们都是把字典加上无意义的值当作集合来用的。

字典和散列表的几个特点，对集合来说几乎都是适用的：

  • 集合里的元素必须是可散列的。
  • 集合很消耗内存。
  • 可以很高效地判断元素是否存在于某个集合。
  • 元素的次序取决于被添加到集合里的次序。
  • 往集合里添加元素，可能会改变集合里已有元素的次序。

总结

大多数映射类型都提供了两个很强大的方法：setdefault 和 update。setdefault 方法可以用来更新字典里存放的可变值（比如列 表），从而避免了重复的键搜索。update 方法则让批量更新成为可能，它可以用来插入新值或者更新已有键值对，它的参数可以是包含 (key, value) 这种键值对的可迭代对象，或者关键字参数。映射类型的构造方法也会利用 update 方法来让用户可以使用别的映射对象、可迭代对象或者关键字参数来创建新对象。

dict 和 set 背后的散列表效率很高，对它的了解越深入，就越能理解为什么被保存的元素会呈现出不同的顺序，以及已有的元素顺序会发生变化的原因。同时，速度是以牺牲空间为代价而换来的。

Python 的特点是“简单而正确”。dict 类型正是这一特点的完美体现——对它的优化只为一个目标：更好地实现对随机键的读取。而优化的结果非常好，由于速度快而且够健壮，它大量地应用于 Python 的解释器当中。如果对排序有要求，那么还可以选择OrderedDict。然而对于映射类型来说，保持元素的顺序并不是一个常用需求，因此会把它排除在核心功能之外，而以标准库的形式提供其他衍生的类型。

由于拥有紧凑的列表和字典表达，JSON 格式可以完美地用于数据交换。

PHP 和 Ruby 的散列语法借鉴了 Perl，它们都用 => 作为键和值的连接。JavaScript 则从 Python 那儿偷师，使用了 :。而 JSON 又从 JavaScript 发展而来，它的语法正好是 Python 句法的子集。因此，除了在 true、false 和 null 这几个值的拼写上有出入之外， JSON 和 Python 是完全兼容的。于是，现在大家用来交换数据的格式全是 Python 的 dict 和 list。

整理自《流畅的Python》第3章内容。