前言

python对字典dict的实现做了高度优化，散列表是字典类型性能出众的根本原因
集合set的实现也依赖于散列表

泛映射类型

映射是一种关联式的容器类型,它存储了对象与对象之间的映射关系
collections.abc模块中有Mapping和MutableMapping这两个抽象基类, 它们的作用是为dict和其他类似的类型定义形式接口。非抽象映射类型一般不会直接继承这些抽象基类，它们会直接对dict或是collections.User.Dict进行扩展。这些基类的作用是作为形式化的文档，它们定义了构建一个映射类型所需要的最基本的接口
它们可以和isinstance()一起用于判断某个数据是不是广义上的映射类型：

1
2
3
4

from collections import abc
t = dict()
print(isinstance(t, abc.Mapping))
>>>True

可散列的数据类型

标准库里的所有映射类型都是利用dict实现的，因此它们有个共同的限制，即只有可散列的数据类型才能作为这些映射里的键key

如果一个对象是可以散列的，那么在这个对象的生命周期中，它的散列值是不变的，需要实现__hash__()方法以及__eq__()

python里可散列的类型有str, bytes, frozenset
注意list是不可散列的
元组tuple当其包含的元素都是可散列的情况下，它才可以散列
下面这个列子:

1
2
3
4
5
6
7
8

L = [x for x in range(10)]
print(hash(L))
>>>TypeError: unhashable type: 'list'

# 列表[30, 40]被冻结后可以被散列
t = (1, 2, frozenset([30, 40]))
print(hash(t))
>>>985328935373711578

字典的多种构造方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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([('one', 1), ('two', 2), ('three', 3)])
e = dict({'three':3, 'one':1, 'two':2})

print(a)
print(b)
print(c)
print(d)
print(e)
>>>{'one': 1, 'two': 2, 'three': 3}
>>>{'one': 1, 'two': 2, 'three': 3}
>>>{'one': 1, 'two': 2, 'three': 3}
>>>{'one': 1, 'two': 2, 'three': 3}
>>>{'three': 3, 'one': 1, 'two': 2}

print(a==b==c==d==e)
>>>True

字典推导 注意这个例子的输出…

1
2
3

t = {x:y for x in range(10) for y in range(10)}
print(t)
>>>{0: 9, 1: 9, 2: 9, 3: 9, 4: 9, 5: 9, 6: 9, 7: 9, 8: 9, 9: 9}

dict常用方法

方法 用途
clear() 移除所有元素
copy() 浅复制
get(k, [default]) 获取键k的值, 如果键不存在则返回None或者default
items() 返回字典的所有键值对(key-value)
keys() 返回所有的键key
values() 返回字典的所有值
pop(k, [default]) 删除键为k的键值对, 返回其k对应的值, 若不存在则返回default, default默认为None
setdefault(k, [default]) 将键k的值设置为默认值，并返回这个值
update(m, [**kargs]) m可以是映射或者键值对迭代器

update()方法处理参数m的方式，是典型的鸭子类型，函数首先检测m是否有keys()方法，如果有，则update()把m被当作映射对象进行处理，否则把m当作包含了键值对(key, value)元素的迭代器。python里大多数映射类型的构造方法都采用了类似的逻辑

善用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)

这样写，当key不存在时需要查找3次，当key存在时需要查找两次。
这样写有点类似于空间换时间，要求value的类型为可变容器类型

映射的弹性键查询

  • 使用defaultdict
  • 自定义一个dict子类，在子类中实现__missing__()方法
1
2
3

from collections import defaultdict
d = defaultdict(list)
d['height'].append(1.75)

在实例化一个defaultdict的时候，需要给构造方法提供一个可调用对象，上面这段程序发生了以下操作： (1)键’height’在d中不存在，d调用list()建立一个新的列表 (2)返回这个列表 (3)在返回的这个列表中添加1.75

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

d = StrKeyDict([('2', 'two'), ('4', 'four')])

print(d['2'])
>>>two
print(d[2])
>>>two
print(d[1])
>>>KeyError: '1'

print(2 in d)
>>>True

print(d.get(2))
>>>two

在__getitem__()碰到找不到的键时，会调用__missing__() 上述这个例子，对key进行查找，如果key不存在，则调用__missing__()方法将key转换为str(key)再进行一次查找，若str(key)不存在，则可以认为key不存在于d中

书上说get()和__contains__()不会调用__missing__()我没有理解，可能作者的意思是没有显式调用，而是通过委托的形式用__getitem__()调用

如果要定义一个映射类型，更合适的策略是继承collections.UserDict类

k in my_dict这样的操作在python3中是很快的，dict.keys()的返回在是一个视图，在视图中查找非常快

字典的变种

collections.OrderedDict

OrderedDict在添加键时会保持顺序，popitem()删除并返回最后一个元素,popitem(last=False)删除并返回第一个元素

collections.ChainMap

ChainMap可以容纳数个不同的映射对象，然后在进行键查找操作的时候,这些对象会被当作一个整体被逐个查找,直到键被找到为止

1
2

import builtins
pylookup = ChainMap(locals(), globals(), vars(builtins))

collections.Counter

Counter给每一个键准备一个整数计数器，每次更新一个键时都会更新对应的整数计数器的值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from collections import Counter
ct = Counter('fjasl;dkgjasdlgkh')
print(ct)
ct.update('gjlkdsagjlaskdf')
print(ct)
print(ct.most_common(2))

>>>Counter({'j': 2, 'a': 2, 's': 2, 'l': 2, 'd': 2, 'k': 2, 'g': 2, 'f': 1, ';': 1, 'h': 1})
>>>Counter({'j': 4, 'a': 4, 's': 4, 'l': 4, 'd': 4, 'k': 4, 'g': 4, 'f': 2, ';': 1, 'h': 1})
>>>[('j', 4), ('a', 4)]

collections.UserDict

UserDict是用纯python把标准dict又实现了一遍，是为了让用户继承写子类用的
UserDict并不是dict的子类，UserDict有一个叫作data的属性，是dict的实例，data是UserDict最终存储数据的地方。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

不可变映射类型

从python3.3开始，types模块引入了MappingProxyType， 结合代码十分容易理解其用途

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from types import MappingProxyType
d = {1:'one'}
d_proxy = MappingProxyType(d)
print(d_proxy)
>>>{1: 'one'}

d_proxy[2] = 'two'
>>>TypeError: 'mappingproxy' object does not support item assignment

d[2] = 'two'
print(d_proxy)
>>>{1: 'one', 2: 'two'}

MappingProxyType接受一个映射类型的对象d, 并且可以访问d的内容，但是无法修改d的内容，d的修改会动态的导致MappingProxyType随之变化

集合

中缀运算符|表示并，&表示交, -表示取差运算
空集的构造必须使用如下形式:

1

s = set()

因为s={}表示的是一个空的字典。除了空集外，集合的字符串表示形式总以{···}的形式出现
s = {1, 2, 3}的构造速度比s = set([1, 2, 3])的速度更快

集合推导

1
2
3
4
5
6

from random import randint
s = {randint(0, 10) for x in range(10)}
print(s)
print(type(s))
>>>{0, 3, 4, 6, 7, 9, 10}
>>><class 'set'>

常用方法

略

字典中的散列表

散列表里的单元通常叫作表元(bucket)，在 dict 的散列表当中,每个键值对都占用一个表元,每个表元都有两个部分,一个是对键的引用,另一个是对值的引用

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

如果要把一个对象放入散列表,那么首先要计算这个元素键的散列值。Python用hash()方法来做这件事情

从 Python 3.3 开始,str、bytes 和 datetime 对象的散列值计算过程中多了随机的加盐这一步。所加盐值是 Python 进程内的一个常量,但是每次启动Python 解释器都会生成一个不同的盐值。随机盐值的加入是为了防止 DOS 攻击而采取的一种安全措施

散列的方式给dict带来的优势和限制

限制与劣势

  • 键必须可散列, 要求实现__hash__()和__eq__()
    所有由用户自定义的对象默认都是可散列的,因为它们的散列值由id()来获取,而且它们都是不相等的。
  • 字典在内存上的开销巨大(散列表导致的)
    如果你需要存放数量巨大的记录,那么放在由元组或是具名元组构成的列表中会是比较好的选择;最好不要根据 JSON 的风格,用由字典组成的列表来存放这些记录。用元组取代字典就能节省空间的原因有两个:其一是避免了散列表所耗费的空间,其二是无需把记录中字段的名字在每个元素里都存一遍。

在用户自定义的类型中,__slots__属性可以改变实例属性的存储方式,由dict变 成tuple

优势

  • 查询十分快(字典类型有着巨大的内存开销,但它们提供了无视数据量大小的快速访问)

键的次序取决于添加顺序,两个字典判等取决于内容，不取决于内容的顺序, 之前的例子也提到过

set和frozenset的实现也依赖于散列表

延伸阅读

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

令人震惊，我还以为python额外对json作了调整