Python 中常见的数据结构：字典、映射和散列表

在 Python 中，字典是核心数据结构。字典可以存储任意数量的对象，每个对象都由唯一的字典键标识。

字典通常也被称为映射、散列表、查找表或关联数组。字典能够高效查找、插入和删除任何与给定键关联的对象。

这在现实中意味着什么呢？字典对象相当于现实世界中的电话簿。

电话簿有助于快速检索与给定键（人名）相关联的信息（电话号码）。因此不必为了查找某人的号码而浏览整本电话簿，根据人名基本上就能直接跳到需要查找的相关信息。

若想研究以何种方式组织信息才有利于快速检索，上述类比就不那么贴切了。但基本性能特征相同，即字典能够用来快速查找与给定键相关的信息。

总之，字典是计算机科学中最常用且最重要的数据结构之一。

那么 Python 如何处理字典呢？

我们来看看 Python 及其标准库中可用的字典实现。

dict——首选字典实现

由于字典非常重要，因此 Python 直接在语言核心中实现了一个稳健的字典 1：dict 数据类型 2。

1 为了与其他资料统一，这里将不区分中文语境下的 dict（字典）和“字典类型的数据结构”，统称为“字典”。——译者注

2 详见 Python 文档：“Mapping Types — dict”。

Python 还提供了一些有用的“语法糖”来处理程序中的字典。例如，用花括号字典表达式语法和字典解析式能够方便地创建新的字典对象：

phonebook = {    'bob': 7387,    'alice': 3719,    'jack': 7052,}
squares = {x: x * x for x in range(6)}
>>> phonebook['alice']3719
>>> squares{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

关于哪些对象可以作为字典键，有一些限制。

Python 的字典由可散列类型 3 的键来索引。可散列对象具有在其生命周期中永远不会改变的散列值（参见__hash__），并且可以与其他对象进行比较（参见__eq__）。另外，相等的可散列对象，其散列值必然相同。

像字符串和数这样的不可变类型是可散列的，它们可以很好地用作字典键。元组对象也可以用作字典键，但这些元组本身必须只包含可散列类型。

Python 的内置字典实现可以应对大多数情况。字典是高度优化的，并且是 Python 语言的基石，例如栈帧中的类属性和变量都存储在字典中。

Python 字典基于经过充分测试和精心调整过的散列表实现，提供了符合期望的性能特征。一般情况下，用于查找、插入、更新和删除操作的时间复杂度都为 O(1)。

大部分情况下，应该使用 Python 自带的标准字典实现。但是也存在专门的第三方字典实现，例如跳跃表或基于 B 树的字典。

除了通用的 dict 对象外，Python 的标准库还包含许多特殊的字典实现。它们都基于内置的字典类，基本性能特征相同，但添加了其他一些便利特性。

下面来逐个了解一下。

collections.OrderedDict——能记住键的插入顺序

collections.OrderedDict 是特殊的 dict 子类，该类型会记录添加到其中的键的插入顺序。

尽管在 CPython 3.6 及更高版本中，标准的字典实现也能保留键的插入顺序，但这只是 CPython 实现的一个副作用，直到 Python 3.7 才将这种特性固定下来了。因此，如果在自己的工作中很需要用到键顺序，最好明确使用 OrderedDict 类。

顺便说一句，OrderedDict 不是内置的核心语言部分，因此必须从标准库中的 collections 模块导入。

>>> import collections>>> d = collections.OrderedDict(one=1, two=2, three=3)
>>> dOrderedDict([('one', 1), ('two', 2), ('three', 3)])
>>> d['four'] = 4>>> dOrderedDict([('one', 1), ('two', 2),             ('three', 3), ('four', 4)])
>>> d.keys()odict_keys(['one', 'two', 'three', 'four'])

collections.defaultdict——为缺失的键返回默认值

defaultdict 是另一个 dict 子类，其构造函数接受一个可调用对象，查找时如果找不到给定的键，就返回这个可调用对象。

与使用 get()方法或在普通字典中捕获 KeyError 异常相比，这种方式的代码较少，并能清晰地表达出程序员的意图。

>>> from collections import defaultdict>>> dd = defaultdict(list)
# 访问缺失的键就会用默认工厂方法创建它并将其初始化# 在本例中工厂方法为list()：>>> dd['dogs'].append('Rufus')>>> dd['dogs'].append('Kathrin')>>> dd['dogs'].append('Mr Sniffles')
>>> dd['dogs']['Rufus', 'Kathrin', 'Mr Sniffles']

collections.ChainMap——搜索多个字典

collections.ChainMap 数据结构将多个字典分组到一个映射中 8，在查找时逐个搜索底层映射，直到找到一个符合条件的键。对 ChainMap 进行插入、更新和删除操作，只会作用于其中的第一个字典。

>>> from collections import ChainMap>>> dict1 = {'one': 1, 'two': 2}>>> dict2 = {'three': 3, 'four': 4}>>> chain = ChainMap(dict1, dict2)
>>> chainChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})
# ChainMap在内部从左到右逐个搜索，# 直到找到对应的键或全部搜索完毕：>>> chain['three']3>>> chain['one']1>>> chain['missing']KeyError: 'missing'

types.MappingProxyType——用于创建只读字典

MappingProxyType 封装了标准的字典，为封装的字典数据提供只读视图。该类添加自 Python 3.3，用来创建字典不可变的代理版本。

举例来说，如果希望返回一个字典来表示类或模块的内部状态，同时禁止向该对象写入内容，此时 MappingProxyType 就能派上用场。使用 MappingProxyType 无须创建完整的字典副本。

>>> from types import MappingProxyType>>> writable = {'one': 1, 'two': 2}>>> read_only = MappingProxyType(writable)
# 代理是只读的：>>> read_only['one']1>>> read_only['one'] = 23TypeError:"'mappingproxy' object does not support item assignment"
# 更新原字典也会影响到代理：>>> writable['one'] = 42>>> read_onlymappingproxy({'one': 42, 'two': 2})

小结：Python 中的字典

本节列出的所有 Python 字典实现都是内置于 Python 标准库中的有效实现。

一般情况下，建议在自己的程序中使用内置的 dict 数据类型。这是优化过的散列表实现，功能多且已被直接内置到了核心语言中。

如果你有内置 dict 无法满足的特殊需求，那么建议使用本节列出的其他数据类型。

虽然前面列出的其他字典实现均可用，但大多数情况下都应该使用 Python 内置的标准 dict，这样其他开发者在维护你的代码时就会轻松一点。

本文内容来自作者图书作品《深入理解 Python 特性》，点击购买。