内部结构 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 6 typedef 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*/
DK_ENTRIES(dk)可用于获取指向entries的指针。
1 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys); /*PyDictObject *mp*/
在
Objects/dictobjetc.c 中，我们可以看到关于
DK_ENTRIES 的宏定义
1 2 3 4 /*line 312 in bjects/dictobjetc.c*/ #define DK_ENTRIES(dk) \ ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))
重写DK_ENTRIES宏:
1 2 3 4 5 // assume int8_t can fit into the indices array size_t indices_offset = DK_SIZE(dk) * DK_IXSIZE(dk); int8_t *pointer_to_indices = (int8_t *)(dk->dk_indices); int8_t *pointer_to_entries = pointer_to_indices + indices_offset; PyDictKeyEntry *entries = (PyDictKeyEntry *) pointer_to_entries;
因此，PyDictKeysObject结构就很清晰了:
容量策略 split table和combined table
在介绍PyDictObjet的ma_values时，我们曾提到 split
table模式下才使用。那么，什么是plit table和combined table呢？ #####
两者区别：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 /* The DictObject can be in one of two forms. Either: A combined table: ma_values == NULL, dk_refcnt == 1. Values are stored in the me_value field of the PyDictKeysObject. Or: A split table: ma_values != NULL, dk_refcnt >= 1 Values are stored in the ma_values array. Only string (unicode) keys are allowed. All dicts sharing same key must have same insertion order. */
##### 什么情况下，不同的dict对象共享相同的键但值不同 只包含
unicode键而不包含伪键（没有删除的对象） ，并保持
相同的插入顺序 。 如果
同一类有多个实例 ，split table实现
可以节省大量内存 。有关更多详细信息，请参阅
PEP 412
预分配机制 dict 对象也有一种类似 list 对象的 预分配机制 。那么， dict
对象容量管理策略是怎样的呢？
由 Objects/dictobject.c 源文件中的 PyDict_MINSIZE 宏定义，我们知道
dict 内部哈希表最小长度为 8 ：
1 #define PyDict_MINSIZE 8
1/2至2/3 满的哈希表，较好地平衡了
内存开销 与 搜索效率 。
为保证哈希表的稀疏程度，进而控制哈希冲突频率， 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 2 3 4 5 Python 3.7.6 (default, Jan 8 2020, 20:23:39) [MSC v.1916 64 bit (AMD64)] :: Anaconda, Inc. on win32 >>> import sys >>> empty_dict = {} >>> sys.getsizeof(empty_dict) 240
从以上分析，可以看出 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 5 Python 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}\)
\[65536 * \frac{1}{3} * 24 =
524288\]
为了尽量节省内存， Python 将 键值对数组 压缩到原来的
\(\frac{2}{3}\) ，只负责存储，索引由另一个数组负责。由于索引数组只需要保存
键值对数组 的下标，而整数占用的内存空间只是若干字节，因此可以
节约大量内存 。
索引数组每个元素的大小
索引数组 可根据哈希表规模，选择
尽量小的整数类型 。对于规模
不超过 256
的哈希表，选择
8 位整数即可；对于长度
不超过
6553 6 的哈希表，
16 位整数足矣；以此类推。
1 2 3 4 5 6 7 8 9 10 11 12 13 #define DK_SIZE(dk) ((dk)->dk_size) #if SIZEOF_VOID_P > 4 #define DK_IXSIZE(dk) \ (DK_SIZE(dk) <= 0xff ? \ 1 : DK_SIZE(dk) <= 0xffff ? \ 2 : DK_SIZE(dk) <= 0xffffffff ? \ 4 : sizeof(int64_t)) #else #define DK_IXSIZE(dk) \ (DK_SIZE(dk) <= 0xff ? \ 1 : DK_SIZE(dk) <= 0xffff ? \ 2 : sizeof(int32_t)) #endif
哈希表规模
条目表规模
旧方案
新方案
节约内存
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 2 3 4 #ifndef PyDict_MAXFREELIST #define PyDict_MAXFREELIST 80 #endif static PyDictObject *free_list[PyDict_MAXFREELIST];
CPython还使用 free list
重用删除的哈希表 ，避免内存碎片 ，提高性能
每个进程全局变量 都有个 free
list
if we create a new dict object, the memory request is delegate to
CPython's memory management system
如果free list未满, dict类型的析构函数将当前dict存储到free list。
下次创建新的dict对象时，将检查
free list ， 如果有
可用的对象 则从
free
list 分配；如果没有，则从
CPython的内存管理 系统分配。
哈希 可哈希 ( 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
tp_hash 函数指针 。而内置函数 hash
则依赖类型对象中的 tp_hash
函数 ，完成哈希值计算并返回。
以 str 对象为例，其哈希函数位于
Objects/unicodeobject.c 源文件，unicode_hash 是也：
1 2 3 4 5 6 7 8 9 10 11 12 PyTypeObject 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 */ };
hash
魔术方法 ，重写默认哈希值计算方法 。举个例子，假设标签类
Tag 的实例对象由 value 字段唯一标识 ：
1 2 3 4 5 6 7 8 9 10 11 12 class 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
使用频率
较高，而且在对象生命周期内均不变。因此，可以在对象内部
对哈希值进行缓存 ，避免重复计算。以 str
对象为例，内部结构中的 hash
字段便是用于保存哈希值 。
哈希冲突 解决哈希冲突的常用方法有两种：
分离链接法 ( 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 26 static 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') -1023772170
fasion 的哈希值 保存不变：
1 2 3 4 5 >>> import os >>> os.getpid() 2915 >>> hash('fasion') -1023772170
构造出大量哈希值相同的 key
，并提交给服务器，会发生什么事情呢？例如，向一台 Python 2 Web 服务器
post 一个 json 数据，数据包含大量的 key ，所有 key
的哈希值相同 。这意味着
哈希表将频繁发生哈希冲突 ，性能由 \(O(1)\) 急剧下降为 \(O(N)\) ，被活生生打垮！这就是
哈希攻击 。
问题很严重，好在应对方法却很简单:为对象加把
盐(salt) 。具体做法如下： 1. Python 解释器进程启动后，产生一个
随机数作为 盐 ； 2. 哈希函数同时参考
对象本身 以及 随机数 计算哈希值；
这样一来，攻击者无法获悉解释器内部的随机数，也就无法构造出哈希值相同的对象了！Python
自 3.3 以后，哈希函数均采用 加盐模式 ，杜绝了
哈希攻击 的可能性。Python 哈希算法在 Python/pyhash.c
源文件中实现，有兴趣的童鞋可以学习一下，这里就不再展开了。
执行 Python 3.7 解释器，启动一个交互式终端，并计算字符串 fasion
的哈希值：
1 2 >>> hash('fasion') 6950491525924312838
1 2 >>> hash('fasion') -7162025883309105262
dict 2. Python
源码深度剖析/13 dict 对象，高效的关联式容器 2. Python
源码深度剖析/14 dict 哈希表高级知识精讲
