内部结构#
C++ 标准模板库中的 map 是一种关联式容器，内部基于 红黑树 实现。红黑树是一种 平衡 二叉树，插入、删除、查找 等关键操作的时间复杂度均为 O(logn)。
Python 虚拟机的运行依赖 dict 对象，包括 名字空间 以及 对象属性空间 等底层都由 dict 实现的。因此Python 中的 dict 对象基于查找效率更高的 hash table 实现的。
PyDictObject#
首先来看看dict的结构，PyDictObject 在头文件 Include/dictobject.h 中定义：
dict 对象 理论上应该是一种变长对象，但从 PyObject_HEAD 可以看出，它是基于 不可变长对象实现。 除了PyObject_HEAD外， PyDictObject 还包括以下几个字段：
- Py_ssize_t ma_used ，对象当前所保存的 键值对个数 ；
- uint64_t ma_version_tag ，对象当前 版本号 ，每次 修改时更新；
- PyDictKeysObject *ma_keys ，指向按键对象映射的 哈希表 结构；
- PyObject ** ma_values ， split table模式下指向由所有 值对象 组成的数组。
_dictkeysobject#
然后我们再看看 PyDictKeysObject 的源码，在Objects/dict-common.h 头文件中的 **_dictkeysobject**:
- Py_ssize_t dk_refcnt ，引用计数，跟 映射视图 的实现有关，有点类似对象引用计数；
- Py_ssize_t dk_size ，哈希表大小，必须是 \(2^n\)，这样可将模运算优化成 按位与 运算；
- dict_lookup_func dk_lookup ， 哈希查找函数 指针，可根据 dict 当前状态选用最优函数版本；
- Py_ssize_t dk_usable ，键值对数组 可用个数 ；
- Py_ssize_t dk_nentries ，键值对数组 已用个数 ；
- char dk_indices[] ，哈希表 起始地址 ，哈希表后紧接着 键值对数组 dk_entries。 char is required to avoid strict aliasing.
PyDictKeyEntry#
键值对结构体 PyDictKeyEntry 就非常直白了，除了保存键对象和值对象的指针外，缓存着键对象的哈希值： 1
2
3
4
5
6typedef struct {
/* Cached hash code of me_key. */
Py_hash_t me_hash; /* 键对象的 哈希值 ，避免重复调用 __hash__ 计算哈希值*/
PyObject *me_key; /* 键对象指针*/
PyObject *me_value; /* 值对象指针 This field is only meaningful for combined tables */
} PyDictKeyEntry;1
#define USABLE_FRACTION(n) (((n) << 1)/3) /*line 413 in bjects/dictobjetc.c*/
1 | PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys); /*PyDictObject *mp*/ |
1 | /*line 312 in bjects/dictobjetc.c*/ |
1 | // assume int8_t can fit into the indices array |
容量策略#
split table和combined table#
在介绍PyDictObjet的ma_values时，我们曾提到 split table模式下才使用。那么，什么是plit table和combined table呢？ ##### 两者区别：1 | /* |
预分配机制#
dict 对象也有一种类似 list 对象的 预分配机制 。那么， dict 对象容量管理策略是怎样的呢？
由 Objects/dictobject.c 源文件中的 PyDict_MINSIZE 宏定义，我们知道 dict 内部哈希表最小长度为 8 ： 1
#define PyDict_MINSIZE 8
为保证哈希表的稀疏程度，进而控制哈希冲突频率， Python 通过 USABLE_FRACTION 宏将哈希表内元素控制在2/3以内。USABLE_FRACTION 宏根据哈希表规模 n ，计算哈希表 可存储元素个数，也就是 键值对数组 的长度。以长度为 8 的哈希表为例，最多可以保持 5 个键值对，超出则需要扩容。USABLE_FRACTION 在indices and entries小节已经展示过了。
哈希表规模一定是 \(2^n\) (熟悉C++ unordered_map的都知道，哈希扩容时只是 近似翻倍的质数) ，也就是说 Python 采用 翻倍扩容 策略。
为什么python3.7中空dict占用了240字节？#
1 | Python 3.7.6 (default, Jan 8 2020, 20:23:39) [MSC v.1916 64 bit (AMD64)] :: Anaconda, Inc. on win32 |
从以上分析，可以看出 Python 为空 dict 对象分配了一个 长度为 8 的哈希表，因而也要占用相当多的内存，主要有以下几个部分组成：
- 可收集对象链表节点，共 24 字节，在此不再展开， 垃圾回收机制 讲解中有详细介绍；
- PyDictObject 结构体，6 个字段，共 48 字节；
- PyDictKeysObject 结构体，除两个数组外有 5 个字段，共 40 字节；
- 哈希索引数组，长度为 8 ，每个槽位 1 字节，共 8 字节；
- 键值对数组，长度为 5(用USABLE_FRACTION算出来的，限制在2/3之内) ，每个 PyDictKeyEntry 结构体 24 字节，共 120 字节。
内存优化#
python2.7空dict占用272字节，而python3.7只占用240！！！ 1
2
3
4
5Python 2.7 (r27:82525, Jul 4 2010, 07:43:08) [MSC v.1500 64 bit (AMD64)] on win32
>>> import sys
>>> empty_dict = {}
>>> sys.getsizeof(empty_dict)
272
python3.6之前#
如果有许多大的稀疏哈希表，则会浪费大量内存。
python3.6之后#
为了以更紧凑的方式表示哈希表，可以在哈希表中 拆分 indices 和real key-value。
indices 指向一个 索引数组，索引项指向原始内容存储的位置。可以将索引视为更简单的版本哈希表，将entries视为数组，数组将每个 哈希值、key和value(PyDictKeyEntry)存储为一个元素。
每当 搜索或插入 一个元素时，根据hash value 和 indices的大小，就可以在indices数组中得到一个索引，并根据新得到的索引从entries中得到结果。
为优化内存使用， Python 将 dict 哈希表分为 哈希索引(indices) 和 键值对(entries) 两个数组来实现。例如，在64字大小的操作系统中，每个指针需要8个字节，原来需要 \(8 * 3 * 8 = 192\) ，而优化后只需 $8 * 3 * 3 + 1 * 8 = 80 $ ，节省了大约58%的内存使用。
为什么遍历字典python3.6之前是无序的，python3.6之后有序？#
因为entries 按插入顺序存储元素，所以可以 按插入项的相同顺序遍历哈希表。在旧版本的实现中，按hash key的顺序存储元素，遍历哈希表时会出现无序。这就是为什么dict在python3.6之前是无序的，而在python3.6之后是有序的
优化计算#
由于哈希表必须保持 稀疏 ，最多只有 2/3 满，这意味着要浪费至少 \(\frac{1}{3}\) 的内存空间。更雪上加霜的是，一个键值对条目 PyDictKeyEntry 大小达 24 字节，试想一个规模为 65536 的哈希表，将浪费高达 512KB 的内存空间：
\[65536 * \frac{1}{3} * 24 = 524288\]
为了尽量节省内存， Python 将 键值对数组压缩到原来的 \(\frac{2}{3}\)，只负责存储，索引由另一个数组负责。由于索引数组只需要保存 键值对数组 的下标，而整数占用的内存空间只是若干字节，因此可以 节约大量内存。
索引数组每个元素的大小#
索引数组 可根据哈希表规模，选择 尽量小的整数类型。对于规模 不超过 256 的哈希表，选择 8 位整数即可；对于长度 不超过 65536 的哈希表， 16 位整数足矣；以此类推。1 | #define DK_SIZE(dk) ((dk)->dk_size) |
| 哈希表规模 | 条目表规模 | 旧方案 | 新方案 | 节约内存 |
|---|---|---|---|---|
| 8 | 8 * 2 / 3 = 5 | 24 * 8 = 192 | 1 * 8 + 24 * 5 = 128 | 64 |
| 256 | 256 * 2 / 3 = 170 | 24 * 256 = 6144 | 1 * 256 + 24 * 170 = 4336 | 1808 |
| 65536 | 65536 * 2 / 3 = 43690 | 24 * 65536 = 1572864 | 2 * 65536 + 24 * 43690 = 1179632 | 393232 |
free list#
1 | #ifndef PyDict_MAXFREELIST |
CPython还使用 free list 重用删除的哈希表，避免内存碎片，提高性能
每个进程全局变量都有个 free list
1 | d = dict() |
1 | del a |
如果free list未满, dict类型的析构函数将当前dict存储到free list。
1 | d = dict() |
哈希#
可哈希 ( hashable )对象#
根据哈希表性质， key对象 必须满足以下两个条件，否则哈希表便不能正常工作：
- 哈希值在对象整个生命周期内 不能改变； ( list 、dict 等 可变对象均不能作为哈希key)
- 可比较，且比较相等的对象哈希值必须相同； 满足这两个条件的对象便是 可哈希 ( hashable )对象，只有 可哈希对象才可作为哈希表的键。因此，诸如 dict 、set等底层由哈希表实现的容器对象，其键对象必须是可哈希对象。
而用户自定义的对象默认便是可哈希对象，对象哈希值由对象地址计算而来，且任意两个不同对象均不相等： 1
2
3
4
5
6
7
8
9
10>>> class A:
... pass
>>>
>>> a = A()
>>> b = A()
>>>
>>> hash(a), hash(b)
(2852108, 2852116)
>>> a == b
False
以 str 对象为例，其哈希函数位于 Objects/unicodeobject.c 源文件，unicode_hash 是也： 1
2
3
4
5
6
7
8
9
10
11
12PyTypeObject PyUnicode_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"str", /* tp_name */
sizeof(PyUnicodeObject), /* tp_size */
// ...
(hashfunc) unicode_hash, /* tp_hash*/
// ...
unicode_new, /* tp_new */
PyObject_Del, /* tp_free */
};1
2
3
4
5
6
7
8
9
10
11
12class Tag:
def __init__(self, value, title):
self.value = value
self.title = title
def __hash__(self):
"""value 字段唯一标识,根据 value 字段实现 哈希函数"""
return hash(self.value)
def __eq__(self, other):
"""根据 value 字段实现 相等性 判断"""
return self.value == other.value
哈希冲突#
解决哈希冲突的常用方法有两种：
- 分离链接法 ( separate chaining ) ；
- 开放地址法 ( open addressing )；
分离链接法#
开放地址法#
- 线性探测 ，顾名思义， \(d_i\)是一个线性函数，例如 \(d_i = 2 * i\)
- 平方探测 ，顾名思义， \(d_i\)是一个平方函数，例如 \(d_i = i^2\) 线性探测 和 平方探测 很简单，平方探测似乎更胜一筹。如果哈希表存在局部热点，探测很难快速跳过热点区域，而 平方探测 则好很多。然而，这两种方法都不够好——因为固定的探测序列加大了冲突的概率。
Python 探测方法在 lookdict 函数中实现，位于 Objects/dictobject.c 源文件内。关键代码如下： 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
26static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key,
Py_hash_t hash, PyObject **value_addr)
{
size_t i, mask, perturb;
PyDictKeysObject *dk;
PyDictKeyEntry *ep0;
top:
dk = mp->ma_keys;
ep0 = DK_ENTRIES(dk);
mask = DK_MASK(dk);
perturb = hash;
i = (size_t)hash & mask;
for (;;) {
Py_ssize_t ix = dk_get_index(dk, i);
// 省略键比较部分代码
// 计算下个槽位
// 由于参考了对象哈希值，探测序列因哈希值而异
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
}
Py_UNREACHABLE();
}
哈希攻击#
Python 在 3.3 以前， 哈希算法 只根据对象本身计算哈希值。因此，只要 Python 解释器相同，对象哈希值也肯定相同。我们执行 Python 2 解释器启动一个交互式终端，并计算字符串 fasion 的哈希值： 1
2
3
4
5>>> import os
>>> os.getpid()
2878
>>> hash('fasion')
-10237721701
2
3
4
5>>> import os
>>> os.getpid()
2915
>>> hash('fasion')
-1023772170
问题很严重，好在应对方法却很简单:为对象加把 盐(salt)。具体做法如下： 1. Python 解释器进程启动后，产生一个 随机数作为 盐 ； 2. 哈希函数同时参考 对象本身 以及 随机数 计算哈希值； 这样一来，攻击者无法获悉解释器内部的随机数，也就无法构造出哈希值相同的对象了！Python 自 3.3 以后，哈希函数均采用 加盐模式，杜绝了 哈希攻击 的可能性。Python 哈希算法在 Python/pyhash.c 源文件中实现，有兴趣的童鞋可以学习一下，这里就不再展开了。
执行 Python 3.7 解释器，启动一个交互式终端，并计算字符串 fasion 的哈希值： 1
2>>> hash('fasion')
69504915259243128381
2>>> hash('fasion')
-7162025883309105262