Python 字典、映射和散列表|极客教程

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

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

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

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

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

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

那么Python如何处理字典呢？

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

Python 字典、映射和散列表 `dict`——首选字典实现

由于字典非常重要，因此Python直接在语言核心中实现了一个稳健的字典：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的字典由可散列类型的键来索引。可散列对象具有在其生命周期中永远不会改变的散列值（参见__hash__），并且可以与其他对象进行比较（参见__eq__）。另外，相等的可散列对象，其散列值必然相同。

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

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

Python字典基于经过充分测试和精心调整过的散列表实现，提供了符合期望的性能特征。一般情况下，用于查找、插入、更新和删除操作的时间复杂度都为。
大部分情况下，应该使用Python自带的标准字典实现。但是也存在专门的第三方字典实现，例如跳跃表或基于B树的字典。

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

下面来逐个了解一下。

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)

>>> d
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> d['four'] = 4
>>> d
OrderedDict([('one', 1), ('two', 2),
             ('three', 3), ('four', 4)])

>>> d.keys()
odict_keys(['one', 'two', 'three', 'four'])

Python 字典、映射和散列表 `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']

Python 字典、映射和散列表 `collections.ChainMap`——搜索多个字典

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

>>> from collections import ChainMap
>>> dict1 = {'one': 1, 'two': 2}
>>> dict2 = {'three': 3, 'four': 4}
>>> chain = ChainMap(dict1, dict2)

>>> chain
ChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})

# ChainMap在内部从左到右逐个搜索，
# 直到找到对应的键或全部搜索完毕：
>>> chain['three']
3
>>> chain['one']
1
>>> chain['missing']
KeyError: 'missing'

Python 字典、映射和散列表 `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'] = 23
TypeError:
"'mappingproxy' object does not support item assignment"

# 更新原字典也会影响到代理：
>>> writable['one'] = 42
>>> read_only
mappingproxy({'one': 42, 'two': 2})