本篇文章来剖析一下字典的底层结构,看看它是怎么设计的,以及在设计的过程中都需要做哪些考量。另外字典是基于哈希表实现的,而传统的哈希表存在内存浪费的问题,那么字典又是如何优化的呢?带着这些问题,开始今天的内容。
字典的底层结构
Python 一切皆对象,字典也不例外,它在底层也由某个结构体表示。
// Include/cpython/dictobject.h
typedef struct {
PyObject_HEAD
Py_ssize_t ma_used;
uint64_t ma_version_tag;
PyDictKeysObject *ma_keys;
PyDictValues *ma_values;
} PyDictObject;
解释一下里面的字段的含义:
- PyObject_HEAD:对象的头部信息,里面包含了对象的引用计数和类型。
- ma_used:字典的长度,它充当了 ob_size。
- ma_version_tag:字典的版本号,对字典的每一次修改都会导致其改变。
- ma_keys:从定义上来看它是一个指针,指向了 PyDictKeysObject。而 Python 里面的哈希表分为两种,分别是 combined table 和 split table,即结合表和分离表。如果是结合表,那么键值对全部由 ma_keys 维护,此时 ma_values 为 NULL。
- ma_values:如果是分离表,那么键由 ma_keys 维护,值由 ma_values 维护。而 ma_values 是一个二级指针,指向 PyObject * 类型的指针数组的首元素;
这里先解释一下结合表和分离表的由来。结合表的话,键和值会存在一起;分离表的话,键和值会存在不同的地方。那么问题来了,为什么要将哈希表分为两种呢?事实上,早期的哈希表只有结合表这一种,并且现在创建一个字典使用的也是结合表。
from ctypes import *
class PyObject(Structure):
_fields_ = [("ob_refcnt", c_ssize_t),
("ob_type", c_void_p)]
class PyDictObject(PyObject):
_fields_ = [("ma_used", c_ssize_t),
("ma_version_tag", c_uint64),
("ma_keys", c_void_p),
("ma_values", c_void_p)]
d = {"a": 1, "b": 2}
print(
PyDictObject.from_address(id(d)).ma_values
) # None
我们看到 ma_values 打印的结果是一个 None,证明是结合表,值不是由 ma_values 维护,而是和键一起,都由 ma_keys 负责维护。
而分离表是在 PEP-0412 中被引入的,主要是为了提高内存使用率,也就是让不同的字典共享相同的一组 key。比如自定义类的实例对象,它们默认都有自己的属性字典,如果对某个类多次实例化,那么改成分离表会更有效率。因为它们的属性名称是相同的,完全可以共享同一组 key;如果是结合表,那么每个实例的属性字典都要将相同的 key 单独保存一次,这显然是一种浪费。
from ctypes import *
class PyObject(Structure):
_fields_ = [("ob_refcnt", c_ssize_t),
("ob_type", c_void_p)]
class PyDictObject(PyObject):
_fields_ = [("ma_used", c_ssize_t),
("ma_version_tag", c_uint64),
("ma_keys", c_void_p),
("ma_values", c_void_p)]
class A:
pass
a1 = A()
a2 = A()
# 因为类型指定的是 void *,所以打印的结果是一串地址
# 但我们看到输出不为 None,说明采用的确实是分离表
print(
PyDictObject.from_address(id(a1.__dict__)).ma_values,
PyDictObject.from_address(id(a2.__dict__)).ma_values
) # 140291010752544 140291010877520
# 然后再查看 ma_keys,既然是共享同一组 key
# 那么打印的地址应该是一样的
print(
PyDictObject.from_address(id(a1.__dict__)).ma_keys,
PyDictObject.from_address(id(a2.__dict__)).ma_keys
) # 94312886214288 94312886214288
# 结果确实是一样的,不同实例对象的属性字典里面的 key 是共享的
# 因为是同一个类的实例对象,属性字典的 key 是相同的,所以没必要将同一组 key 保存多次
以上就是结合表和分离表之间的区别,只需要知道分离表是 Python 为了提高内存使用率而专门引入的即可。我们平时自己创建的字典,使用的都是结合表,因此我们的重点也将会放在结合表身上。
而结合表的话,键值都由 ma_keys 维护,它是一个指向 PyDictKeysObject 的指针,因此玄机就隐藏在这个结构体里面。
// Include/cpython/dictobject.h
typedef enum {
DICT_KEYS_GENERAL = 0,
DICT_KEYS_UNICODE = 1,
DICT_KEYS_SPLIT = 2
} DictKeysKind; // 键的种类,下面会用到
typedef struct _dictkeysobject PyDictKeysObject;
// Include/internal/pycore_dict.h
struct _dictkeysobject {
// key 的引用计数,也就是 key 被多少个字典所使用
// 如果是结合表,那么该成员始终是 1,因为结合表独占一组 key
// 如果是分离表,那么该成员大于等于 1,因为分离表可以共享一组 key
Py_ssize_t dk_refcnt;
// 1 << dk_log2_size 便是哈希表的大小、或者说长度
// 因此可以看出哈希表的大小满足 2 的 n 次方,这样可以将取模运算优化成按位与运算
// 比如 size 满足 2 的 n 次方,那么整数 num % size 等价于 num & (size - 1)
uint8_t dk_log2_size;
// 通过 1 << dk_log2_index_bytes 可以计算出哈希索引数组总共占多少字节
// 关于什么是哈希索引数组,稍后解释
uint8_t dk_log2_index_bytes;
// 键的种类,有三个可选值,分别是 0、1、2
// 如果字典的键可以是任意类型,那么 dk_kind 为 0,即 DICT_KEYS_GENERAL
// 如果字典的所有键都是 unicode 字符串,那么 dk_kind 为 1,即 DICT_KEYS_UNICODE
// 以上两种取值,不论是哪一种,都表示字典使用的是结合表
// 如果是分离表,那么 dk_kind 为 2,即 DICT_KEYS_SPLIT,这里分离表不做过多讨论
// 那么问题来了,为什么要对键(key)做这种区分呢?
// 首先一个键值对就是一个 entry,它里面包含了键和值,而它的类型有两种
// 如果 dk_kind == 0,那么 entry 由 PyDictKeyEntry 结构体表示
// 如果 dk_kind == 1,那么 entry 由 PyDictUnicodeEntry 结构体表示
uint8_t dk_kind;
// 字典的版本号,如果字典被修改,那么会重置为 0
// 通过该字段,可以检测字典是否在迭代过程中被修改
uint32_t dk_version;
// 键值对数组的长度,说白了就是键值对数组可以容纳多少个 entry(键值对)
// 关于什么是键值对数组,以及它和哈希索引数组之间有什么区别,稍后会解释
Py_ssize_t dk_usable;
// 键值对数组里面已经存储了多少个键值对
Py_ssize_t dk_nentries;
// 哈希索引数组
char dk_indices[];
// 注:dk_indices 后面其实还有一个字段 dk_entries,只不过没有写在结构体里面
// 从字段名也可以看出,它表示键值对数组,因此它的类型就是个数组
// 然后数组里面存储的是键值对,即 entry,而根据 dk_kind 的不同
// entry 可以是 PyDictKeyEntry 结构体实例,也可以是 PyDictUnicodeEntry 结构体实例
};
字典的定义还是稍微有点复杂的,如果目前感到困惑,没有关系,稍后我们会一点点解释清楚。这里再来看看键值对长什么样子。
// Include/internal/pycore_dict.h
typedef struct {
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictKeyEntry;
typedef struct {
PyObject *me_key;
PyObject *me_value;
} PyDictUnicodeEntry;
如果对象要作为字典的 key,那么它一定是可哈希的,所以 PyDictKeyEntry 里面除了键和值(指针)之外,还包含了键的哈希值。并且在 3.8 版本的时候,键值对统一使用 PyDictKeyEntry 结构体表示。
但在 3.12 的时候,又设计出了 PyDictUnicodeEntry,它的使用场景是字典里面的 key 全部都是字符串。相比 PyDictKeyEntry ,它内部不再保存 me_hash 字段,因为字符串内部已经维护了哈希值。所以通过该设计,可以更加节省内存,不得不说,Python 底层为了优化真的是殚精竭虑。
至此,字典的整个底层结构就非常清晰了,我们画一张图,然后再来从头解释一下,并解答之前留下的疑问。
图片
字典的真正实现藏在 PyDictKeysObject 中,它的内部包含两个关键数组:一个是哈希索引数组 dk_indices,另一个是键值对数组 dk_entries。
字典维护的键值对(entry)会按照先来后到的顺序保存在键值对数组中,而哈希索引数组则保存键值对在键值对数组中的索引。另外,哈希索引数组中的一个位置我们称之为一个槽,比如图中的哈希索引数组便有 8 个槽,其数量由 1 << dk_log2_size 维护。
比如我们创建一个空字典,注意:虽然字典是空的,但是容量已经有了,然后往里面插入键值对 "komeiji":99 的时候,Python 会执行以下步骤:
- 将键值对保存在 dk_entries 中,由于初始字典是空的,所以会保存在 dk_entries 数组中索引为 0 的位置。
- 通过哈希函数计算出 "komeiji" 的哈希值,然后将哈希值映射成索引,假设是 6。
- 将 "键值对" 在 "键值对数组" 中的索引 0,保存在哈希索引数组中索引为 6 的槽里面。
然后当我们在查找键 "komeiji" 对应的值的时候,便可瞬间定位。过程如下:
- 通过哈希函数计算出 "komeiji" 的哈希值,然后映射成索引。因为在设置的时候索引是 6,所以在获取时,映射出来的索引肯定也是 6。
- 找到哈希索引数组中索引为 6 的槽,得到其保存的 0,这里的 0 对应键值对数组的索引。
- 找到键值对数组中索引为 0 的位置存储的 entry,然后判断 entry->me_key 和查找的 key 是否一致,不一致则重新映射。如果一致,则取出 me_value,然后返回。
由于哈希值计算以及数组索引查找均是 O(1) 的时间复杂度,所以字典的查询速度才会这么快。
另外前面介绍哈希表的时候,为了避免牵扯太多,说得相对简化了。比如:"xxx": 80,假设 "xxx" 映射出来的索引是 2,那么键值对就直接存在索引为 2 的地方。这实际上是简化了,因为这相当于把哈希索引数组和键值对数组合在一块了,而早期的 Python 也确实是这么做的。
但是从上面字典的结构图中我们看到,实际上是先将键值对按照先来后到的顺序存在一个数组(键值对数组)中,然后再将它在键值对数组中的索引存放在另一个数组(哈希索引数组)的某个槽里面,因为 "xxx" 映射出来的是 2,所以就存在索引为 2 的槽里面。
而在查找的时候,映射出来的索引 2 其实是哈希索引数组的索引。然后索引为 2 的槽又存储了一个索引,这个索引是键值对数组的索引,会再根据该索引从键值对数组里面获取指定的 entry。最后比较 key 是否相同、如果相同则返回指定的 value。
所以能看出两者整体思想是基本类似的,理解起来区别不大,甚至第一种方式实现起来还更简单一些。但为什么要采用后者这种实现方式,以及这两者之间的区别,我们下面来专门分析,之所以采用后者主要是基于内存的考量。
哈希表的内存优化
在早期,哈希表并没有分成两个数组实现,而是只由一个键值对数组实现,这个数组也承担哈希索引数组的角色。
图片
我们看到这种结构不正是我们在介绍哈希表时说的吗?键值对数组不仅负责存储 entry,同时也负责承载映射后的索引,而无需分成两个数组,这种方式似乎更简单、更直观。没错,Python 在早期确实是通过这种方式实现的哈希表,只是这种实现方式有一个弊端,就是太耗费内存了。
前面说了,基于 key 映射出的索引是随机的,所以肯定会存在索引冲突的情况,即不同的 key 映射到了同一个槽。并且随着存储的 entry 增多,冲突也会越频繁,性能也就越差。因此哈希表必须要预留一定的空间,而经过实践表明,预留的空间至少要占总容量的 1/3。
换句话说,哈希表存储的 entry 的数量不能超过总容量的 2/3。
// Objects/dictobject.c
#define USABLE_FRACTION(n) (((n) << 1)/3)
宏 USABLE_FRACTION 会根据哈希表的长度,或者说容量,计算出哈希表可存储的元素个数。以长度为 8 的哈希表为例,最多可以保存 5 个键值对,超出则需要扩容,显然这存在严重的内存浪费。
所以 Python 为了节省内存,想出了一个妙招。既然只能用 2/3,那就将键值对数组的空间变为原来的 2/3,只用来存储键值对(entry),而对 key 进行映射得到的索引则由另一个数组(哈希索引数组)来承载。假设映射出的索引是 4,那么就去找哈希索引数组中索引为 4 的槽,该槽存储的便是键值对在键值对数组中的索引。
之所以这么设计,是因为键值对数组里面一个元素要占用 24 或 16 字节,而哈希索引数组在容量不超过 255 的时候,里面一个元素只占一个字节,容量不超过 65535 的时候,里面一个元素只占两个字节,其它以此类推。
所以哈希索引数组里面的元素大小比键值对数组要小很多,将哈希表分成两个数组(避免键值对数组的浪费)来实现会更加节省内存。我们可以举个例子计算一下,假设有一个容量为 65535 的哈希表。
如果是通过第一种方式,只用一个数组来存储的话:
# 总共需要 1572840 字节
>>> 65535 * 24
1572840
# 除以 3, 会浪费 524280 字节
>>> 65535 * 24 // 3
524280
>>>
如果是通过第二种方式,使用两个数组来存储的话:
# 容量虽然是 65535
# 但键值对数组是容量的 2 / 3
# 然后加上哈希索引数组的大小
>>> 65535 * 24 * 2 // 3 + 65535 * 2
1179630
>>>
所以一个数组存储比两个数组存储要多用 393210 字节的内存,因此 Python 选择使用两个数组来存储。
我们再以长度为 8 的哈希表为例,画一张图对比一下,由于哈希表长度为 8,那么它最多存储 5 个键值对。
图片
如果哈希表只使用一个键值对数组,那么基于 key 映射出的索引就是键值对数组的索引,这种方式简单直观,但内存浪费严重,因为要浪费掉 1/3 的空间。于是为了解决这个问题,哈希表选择使用两个数组实现,分别是哈希索引数组和键值对数组。
哈希索引数组的长度就是哈希表的长度,key 映射之后的索引也是哈希索引数组的索引,只不过它存储的不再是键值对,而是键值对在键值对数组中的索引。那么问题来了,明明多了一个数组,为啥内存占用反而变少了呢?很明显,由于引入了哈希索引数组,键值对数组的长度可以减少到原来的 2/3。
因为相比键值对数组,哈希索引数组的内存占用非常低,引入它需要的成本远小于避免键值对数组浪费 1/3 所带来的收益,所以使用两个数组来实现哈希表是更加合理的。
然后我们再来回顾一下 PyDictKeysObject 结构体,此时里面的字段就非常清晰了。
图片
哈希表本质上就是个数组,只不过 Python 选择使用两个数组实现,其中哈希索引数组的长度便是哈希表的容量,而该长度由 1 << dk_log2_size 表示。然后 1 << dk_log2_index_bytes 则表示哈希索引数组占的内存大小,之所以要维护这个大小信息,是为了能够快速定位到位于哈希索引数组之后的键值对数组。
由于哈希表最多使用 2/3,那么就只为键值对数组申请 2/3 容量的空间。对于容量为 8 的哈希表,那么哈希索引数组的长度就是 8,键值对数组的长度就是 5。而键值对数组的长度由 dk_usable 字段维护,所以它的值是 5。
假设哈希表,或者说键值对数组存储了 3 个键值对,那么 dk_nentries 就是 3,因为该字段负责维护当前已存在的键值对的数量。咦,前面介绍 PyDictObject 的时候,看到里面有一个 ma_used 字段,表示字典的长度。那么 dk_nentries 和 ma_used 有啥区别呢,从字面意思上看,两者的含义貌似是等价的,关于这一点后续再解释。
最后就是 dk_indices 和 dk_entries,它们表示哈希索引数组和键值对数组。到此我们就把每个字段的含义又重新回顾了一遍,现在再来看是不是就清晰多了呢。
字典遍历的有序性
我们知道 Python 从 3.6 开始,字典的遍历是有序的,那么这是怎么实现的呢?
其实很简单,在存储时,虽然映射之后的索引是随机的,但键值对本身始终是按照先来后到的顺序被添加进键值对数组中。而字典在 for 循环时,会直接遍历键值对数组,所以遍历的结果是有序的。但即便如此,我们也不应该依赖此特性。
还是以之前的图为例,我们顺序写入三个键值对,key 分别是 "a"、"b"、"c":
图片
早期的哈希表只有一个键值对数组,键值对在存储时本身就是无序的,那么遍历的结果自然也是无序的。对于当前来说,遍历的结果就是 "b"、"a"、"c"。
但从 3.6 开始,键值对数组中的键值对,和添加顺序是一致的。而遍历时,会直接遍历键值对数组,因此遍历的结果是有序的。对于当前来说,遍历的结果就是 "a"、"b"、"c"。
当然,如果你是 Python 的设计者,希望遍历依旧不保持有序的话,那么该怎么做呢?很简单,可以先遍历哈希索引数组,将存储的有效索引依次取出,对于当前来说就是 1、0、2。然后基于这些索引,从键值对数组中获取键值对,那么遍历的结果也是 "b"、"a"、"c"。
字典的内存大小
下面来分析一下字典占用的内存大小,首先字典和列表一样都有容量的概念,由于空间已经申请了,不管有没有使用,大小都必须算进去。而字典的容量策略相比列表要简单很多,因为大小要满足 2 的 n 次方,所以容量一定按照 8、16、32、64、······ 进行变化。
注意:字典的容量(或者说哈希表的容量)指的是内部哈希索引数组的长度,它要满足 2 的 n 次方,从而将取模运算优化成按位与运算。当哈希索引数组存储的元素(键值对数组的索引)个数达到了总长度的 2/3,同时也意味着键值对数组已经满了,那么说明字典(哈希表)该扩容了。
知道了容量规则,我们来看一下字典的内存大小怎么计算。
typedef struct {
PyObject_HEAD // 16 字节
Py_ssize_t ma_used; // 8 字节
uint64_t ma_version_tag; // 8 字节
PyDictKeysObject *ma_keys; // 8 字节
PyDictValues *ma_values; // 8 字节
} PyDictObject;
// 所以 PyDictObject 实例占 48 字节
struct _dictkeysobject {
Py_ssize_t dk_refcnt; // 8 字节
uint8_t dk_log2_size; // 1 字节
uint8_t dk_log2_index_bytes; // 1 字节
uint8_t dk_kind; // 1 字节
uint32_t dk_version; // 4 字节
Py_ssize_t dk_usable; // 8 字节
Py_ssize_t dk_nentries; // 8 字节
char dk_indices[];
// 隐藏字段 dk_entries
};
// 如果不算哈希索引数组 dk_indices 和键值对数组 dk_entries
// 那么 PyDictKeysObject 实例占 31 + 1 = 32 个字节
// 注意:结构体会因内存对齐而多出 1 字节的空洞,所以是 32 字节
// 另外事实上在计算 PyDictKeysObject 的大小时,两个数组并没有被包含在内
// 因为 dk_indices 是灵活数组,它在结构体定义中没有固定的大小,所以相当于是 0
// 至于 dk_entries 更不用说了,它压根就没有定义在结构体中
// 因此 sizeof(PyDictKeysObject) 返回的结果就是 32
// 但在申请内存的时候,是要根据字典的容量,为两个数组申请内存的
所以一个字典的大小至少是 48 字节,如果大小等于 48,说明字典为空,它的 ma_keys 为 NULL。
图片
但如果字典里面存在元素,那么还需要计算 PyDictKeysObject 的大小。
图片
手动创建的字典使用的都是结合表,因此它的 ma_keys 字段指向的 PyDictKeysObject 实例负责存储键值对,而如果忽略掉内部的两个数组,那么它的大小为 32 字节。
所以当字典不为空时,其内存大小等于 48 + 32 + 哈希索引数组的内存大小 + 键值对数组的内存大小。有了这个公式,如果再能分析出两个数组的长度,那么任何一个字典,我们都可以计算出它的内存大小。
我们以容量为 8 的字典为例,值得一提的是,当字典不为空时,它的容量至少是 8。
// Objects/dictobject.c
#define PyDict_LOG_MINSIZE 3
#define PyDict_MINSIZE 8
从这个宏定义中我们可以得知,一个字典的最小容量是 8,即 1 << 3,或者说内部哈希索引数组的长度最小是 8。
那么我们来算一下容量为 8 的字典的内存大小,字典的容量是 8 说明哈希索引数组的长度是 8,每个元素占 1 字节,因此哈希索引数组的大小是 8 字节。然后键值对数组的长度是 (8 << 1) / 3 = 5,每个元素可能占 16 或 24 字节。
- 如果所有 key 都是字符串,那么键值对用 PyDictUnicodeEntry 表示,一个 entry 占 16 字节,那么字典的内存大小为 48 + 32 + 8 + 5 * 16 = 168 字节。
- 否则键值对使用 PyDictKeyEntry 表示,一个 entry 占 24 字节,那么字典的内存大小为 48 + 32 + 8 + 5 * 24 = 208 字节。
我们来测试一下,看看是不是这个样子。
图片
结果和我们分析的一样,那么问题来了,如果一个字典有 7 个键值对,那么这个字典的内存大小是多少呢?
长度为 8 的哈希表,键值对数组的长度是 5,最多能容纳 5 个键值对。长度为 16 的哈希表,键值对数组的长度为 10,最多能容纳 10 个键值对。所以对于键值对个数为 7 的字典,它内部哈希表的长度为 16。
字典是翻倍扩容的,因为容量要满足 2 的 n 次方。
因此当键值对的个数为 7 时,字典的内存大小等于 48 + 32 + 16 + 10 * entry_size。如果 entry_size 为 16,那么大小就是 256,如果 entry_size 为 24,那么大小就是 336。
图片
结果没有问题,以上我们就计算出了字典的内存大小,你也可以自己创建个字典测试一下。
小结
通过研究字典的具体实现,我们可以得出以下结论:
- 字典是一种高效的映射型容器,能够以 O(1) 的时间复杂度执行查询和写入操作;
- 字典之所以这么快,是因为它由哈希表实现。但快是要付出代价的,哈希表必须保证一定的稀疏性,否则会频繁出现索引冲突,导致哈希表性能下降,因为索引映射是随机的;
- 既然哈希表要保证稀疏性,就意味着内存开销大,因为存在内存浪费。
- 但 Python 为优化内存使用,选择基于两个数组来实现哈希表,通过避免键值对数组的浪费,来减少内存占用;
- 键值对数组里的 entry 除了保存 key 和 value 之外,还保存了 key 的哈希值。但如果所有的 key 都是字符串类型,那么为优化内存使用,会选择不再保存哈希值,因为字符串本身已经维护了自身的哈希值。