Python中的映射类型

Python中最常见的映射类型是字典。本文将从字典入手对Python中的映射类型进行探讨。

字典

字典类型dict对应的抽象基类为MutableMapping。而MutableMapping是Mapping的子类。

dict中的数据组织为键-值对的形式，字典对值的类型没有要求，但要求键的类型必须可散列（hashable）。由此可见，字典结构的底层实现类似散列表，以加快字典内元素的访问速度。字典的执行效率远高于列表。

Python 3.6及以后，dict类型在实现上是有序的，键的顺序取决于添加顺序，但标准并没有规定dict类型的有序性。因此两个键顺序不同的字典被视为相同。

>>> a = {1: 2, 2: 1}
>>> b = {2: 1, 1: 2}
>>> a == b
True
>>>

New in version 3.9

Python 3.9中，字典对象支持|运算符，用于将两个字典合并为一个。当两个字典中出现重复值时右侧字典中的值优先。

>>> import sys 
>>> ver = sys.version_info
>>> if ver.major == 3 and ver.minor > 8:
...     a = {1: 2}
...     b = {3: 4}
...     print(a | b == {1: 2, 3: 4})
... else:
...     print(True)
True
>>>

迭代

dict对象是可迭代对象，当对dict对象进行迭代时，实际上是迭代dict的键。

>>> for key in {1: 2, 3: 4}:
...     print(key)
...
1
3
>>>

• dict.keys()方法返回由字典中的键组成的可迭代对象；
• dict.values()方法返回由字典中的值组成的可迭代对象；
• dict.items()方法返回由键-值元组组成的可迭代对象。

注意，每次调用values方法时，都会返回一个新的迭代器。因此，即使是对同一个字典调用多次values方法，其返回值也不想等。

Changed in version 3.8

内置函数reversed支持传递字典作为参数，返回字典中的键逆序组成的可迭代对象。

映射类型通常是可修改的，使用types.MappingProxyType会创建一个原映射的视图。对原映射的任何修改都会反映在视图中，但不能对视图进行任何直接的修改。此方法间接地创建一个不可修改的映射类型。

>>> from types import MappingProxyType
>>> a = {1: 2, 3: 4}
>>> b = MappingProxyType(a)
>>> b
mappingproxy({1: 2, 3: 4})
>>> a.update({1: 5})
>>> b
mappingproxy({1: 5, 3: 4})
>>> b[1] = 2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment
>>>

可散列类型

满足如下条件的对象称为可散列对象：

1. 如果该对象可散列，则在其生命周期中，该散列值不变
2. 对象实现了__hash__()与__eq__()方法（没有实现__eq__()方法的对象不应实现__hash__()方法）
3. 如果它和另一个对象相等，则两者有相同的散列值

如：

>>> a = "abc"
>>> b = "".join(["a", "b", "c"])
>>> a is b
False
>>> hash(a) == hash(b)
True
>>>

注：若一个自定义类型定义了__eq__，且没有定义__hash__，__hash__会被设为None。可散列的自定义对象必须有__hash__方法。

以下内容来自于Python文档

根据如上规则可以判断一些内置数据结构是否为可散列对象

• 可变序列在生命周期中序列的内容可能发生变化，因此可变序列（如list、set等）不是可散列对象。
• 原子不可变数据类型满足如上所有条件，是可散列对象
• 容器frozenset要求其中的所有元素均为可散列对象，并且其中内容在整个生命周期中不会发生变化，因此是可散列对象
• 容器tuple中可以容纳不可散列对象，因此tuple不是可散列对象，但不含可散列对象的元组是可散列对象。

>>> t1 = hash((1, 2))
>>> t2 = hash((1, [2]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>

使用hash函数可以取得可散列对象的散列值。为了避免DOS攻击，在计算散列值时会加上一个随机的噪声。噪声的值仅在同一Python实例中相同。对于一个整数，若它的值小于散列值所允许的最大值（即可以被放进散列值所限定的空间内），则散列的值就是该整数的值。

散列表的使用是“空间换时间”策略的典型体现。为了尽可能减少冲突，散列表必须有较低的装填因子，这意味着散列表会占用更多的内存空间。

构造

字典提供了多种构造方式，如下构造字典{'a': 1, 'b': 2}

1. 花括号构造，如{'a': 1, 'b': 2}
2. 通过类构造函数，如dict(a=1, b=2)
3. 通过元组/列表（只需是长度为2的可迭代对象）构造，如dict([('a', 1), ['b', 2]])
4. 通过zip打包构造，如dict(zip(['a', 'b'], [1, 2]))
5. 通过字典推导构造，如{chr(97 + _): _ + 1 for _ in range(2)}

变种

collections提供了字典的两个变种，即defaultdict与OrderDict

defaultdict

当在一个字典d中找不到键k时，Python会产生KeyError异常。使用d.get(k, default)可以为找不到的键设置默认返回值。但dict.get函数不会对字典进行更新，插入找不到的键。

dict.setdefault提供了另一种从字典中获取值的方法。setdefault接收两个参数，第一个参数为key，第二个参数为可选的默认值default。当字典中找到key所对应的元素时，setdefault直接返回该值，否则setdefault会在字典中添加键值对key: default，然后返回default。

>>> a = {}
>>> a.setdefault(0, True)
True
>>> a[0] = False
>>> a.setdefault(0, False) 
False
>>>

使用setdefault从字典中获取值时，可以减少字典的查询次数，提高字典执行的效率：

>>> a = {}
>>> try:
...     a[0].append(True)
... except KeyError:
...     a[0] = []
...     a[0].append(True)
...        
>>> a
{0: [True]}
>>>

如上使用try-except结构处理字典中找不到值的结果，如果使用setdefault函数，则可以有效减少代码长度，增加代码可读性。

>>> a = {}
>>> a.setdefault(0, []).append(True)
>>> a
{0: [True]}
>>>

defaultdict可以用于处理字典中缺失的键。准确地说，defaultdict在创建时需要提供一个可调用对象作为参数，字典中找不到键时，defaultdict会通过调用这个可调用对象来得到该键对应的默认值。

>>> from collections import defaultdict
>>> a = defaultdict(list)
>>> a
defaultdict(<class 'list'>, {})
>>> a[False] = {}
>>> a[False]
{}
>>> a[True]
[]
>>> a
defaultdict(<class 'list'>, {False: {}, True: []})
>>>

如果创建defaultdict时没有指定参数，访问不存在的键时仍会抛出KeyError。

事实上，__getitem__通过特殊方法__missing__处理字典中缺失的键。手动调用__missing__方法能实现相同的效果：

>>> from collections import defaultdict 
>>> a = defaultdict(list)
>>> a 
defaultdict(<class 'list'>, {})
>>> a.__missing__(0)  
[]
>>> a
defaultdict(<class 'list'>, {0: []})
>>>

__missing__方法的参数为self, key，其中key为缺失的键。即使__missing__正常执行，返回值也不会被添加到字典中。

>>> class NumDict(dict):
...     def __init__(self, *args, **kwargs):
...             super().__init__(*args, **kwargs)
...     def __missing__(self, key):
...             if isinstance(key, int):
...                     return 0
...             else:
...                     raise KeyError(key)
...
>>> a = NumDict([(1, 2), ("a", "b")])
>>> a
{1: 2, 'a': 'b'}
>>> a[0]
0
>>> a['b']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 8, in __missing__
KeyError: 'b'
>>> a
{1: 2, 'a': 'b'}
>>>

OrderedDict

OrderedDict是严格（在任何版本中）保持顺序的字典。在迭代过程中键的顺序保持一致。

OrderedDict新增了popitem方法，默认移除并返回字典中最后添加的一个元素。如果手动指定last参数为False，则移除并返回字典中第一个添加的元素。同时，move_to_end是与之配合的移动方法，可以将字典中的键值对（由key参数指定）移动到字典一端（由last参数指定）。

ChainMap

ChainMap可以视为一种容纳映射的序列。相比于使用dict.update()或|运算符逐个合并映射，ChainMap有更高的效率。

ChainMap也可以被视为映射，当在ChainMap对象中查询时，ChainMap会逐个查询其中的映射。当同一个键出现在不同的映射中时，ChainMap返回查询到的第一个结果。

>>> from collections import ChainMap
>>> a = ChainMap({'a': 1, 'b': 2}, {'a': 3, 'b': 4})
>>> a['b']
2
>>> a['a']
1
>>>

存储的映射在ChainMap.maps属性中，对该属性的修改会同时反映在ChainMap对象中。parents是一个通过属性方式访问的方法，返回去除原ChainMap中的第一个映射后的新ChainMap，原ChainMap保持不变。

new_child提供了向ChainMap中添加映射的方法。新的映射被添加到ChainMap的开头，如果没有提供映射，则添加一个空字典。

ChainMap并没有合并原有的映射，因此迭代ChainMap对象或对ChainMap对象调用dict()时只会应用到其中包含的第一个映射。

>>> dict(a)
{'a': 1, 'b': 2}
>>>

Counter

Counter提供了对一系列值的统计方法。可以使用可迭代对象初始化Counter类型，Counter会自动统计可迭代对象中每个值的出现顺序。

Counter不会对输入的值进行检查，如果使用字典初始化并提供非整数类型的值，在调用Counter.most_common()方法或迭代Counter.elements()的返回值时会抛出TypeError异常。

>>> from collections import Counter
>>> a = Counter({'0': '0'})
>>> for i in a.elements():
...     pass
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object cannot be interpreted as an integer

这一点在Python文档中有相应说明：

>>> from collections import Counter 
>>> a = Counter([1, 1, 1, 2, 2, 3])          
>>> a
Counter({1: 3, 2: 2, 3: 1})
>>>

更新Counter对象时，计数器会相应地更新：

>>> a.update([3, 3, 3, 2, 2, 1])
>>> a
Counter({1: 4, 2: 4, 3: 4})
>>>

Counter.elements()方法返回一个迭代器，每个元素按照其出现次数重复。Counter.most_common方法返回计数器中出现次数最多的元素。

Counter类型提供了+、-、&和|运算符，分别对应计数器的相加、相减、交和并操作。当+、-被用作一元运算符时，另一个操作数默认为空计数器。

扩展

collections.UserDict类是对dict的Python实现，可以用于自定义映射类型的实现。

UserDict不是dict的子类，但UserDict中有一个dict类型的data属性，是UserDict存储数据的最终位置。相比于直接对dict类型进行扩展，data属性保证了__getitem__方法不会产生循环递归的情况。

UserDict类继承自_collections_abc.MutableMapping与_collections_abc.Mapping类。MutableMapping提供了update()方法。方法的内部实现表明，update()在内部通过__setitem__实现。Mapping提供了get()方法，该方法在内部通过__getitem__实现。

>>> from collections import UserDict
>>> class myDict(UserDict):
...     def __init__(self, *args, **kwargs):
...             super().__init__(*args, **kwargs)  
...     def __setitem__(self, index, value):
...             print("Modification: ", index, ":", value)
...             super().__setitem__(index, value)
... 
>>> a = myDict()
>>> a.update(a=5, b=4)
Modification:  a : 5
Modification:  b : 4
>>>

集合

集合set是一种序列类型，集合中的各个元素最多只能出现一次。任何非空集合可以使用字面表示法{}进行表示，空集只能用set()表示。集合同样适用于与列表推导相似的推导方式。

集合有对应的只读变种frozenset。set可以通过字面表示法进行构造，或使用可迭代对象进行构造。frozenset只能使用可迭代对象构造。

可以利用set中元素的唯一性去除列表中的重复值：

>>> src_list = [1, 1, 2, 3, 4, 2, 3]
>>> list(set(src_list))
[1, 2, 3, 4]
>>>

另一种方法是通过collections.Counter去重。

>>> from collections import Counter
>>> src_list = [1, 1, 2, 3, 4, 2, 3]
>>> list(Counter(src_list).keys())
[1, 2, 3, 4]
>>>

和字典的键一样，集合中的元素必须是可散列的。set类型本身不可散列，frozenset类型可散列。

运算

集合有如下运算，由于集合的底层数据结构是散列表，这些运算方法有较高的计算效率。

• 交集、并集、差集、对称差，即&、|、-与^；
• 子集、真子集、超集、真超集，即<=、<、>=与>；
• 属于，即in

以in操作为例，set可以直接查询散列表获取结果，但list必须扫描一遍列表才能获取结果。对于含有许多元素的序列，两者在执行速度上有明显的差别。

set还支持add、clear、copy、pop、remove等方法。

评论