Python 字典你真的了解吗
字典
PyDictObject
源文件：Include/cpython/dictobject.h
typedef struct {
PyObject_HEAD
/* Number of items in the dictionary */
Py_ssize_t ma_used;
/* Dictionary version: globally unique, value change each time
the dictionary is modified */
uint64_t ma_version_tag;
PyDictKeysObject *ma_keys;
/* If ma_values is NULL, the table is "combined": keys and values
are stored in ma_keys.
If ma_values is not NULL, the table is split:
keys are stored in ma_keys and values are stored in ma_values */
PyDictValues *ma_values;
} PyDictObject;
可以看到使用PyObject_HEAD定长对象头部
- ma_used：表示字典中已经使用的元素数量。
- ma_version_tag：表示字典版本号，每当字典修改时，该值会发生变化。这个标记可用于支持并发操作，例如dict的copy()、update()等操作都可以利用ma_version_tag来检查字典是否被其他线程修改。
- ma_keys：指向PyDictKeysObject类型的指针，表示字典的键(key)集合。
- ma_values：指向PyDictValues类型的指针，表示字典的值(value)集合。
总之，PyDictObject结构体中的ma_keys和ma_values变量分别对应了字典对象的键和值，具体实现方式可以是“combined”(使用同一个数组存储键值对)或者“split”(分别存储键和值)。如果是结合表，那么键值对存在ma_keys里面，此时下面的ma_values为NULL;如果是分离表，那么"键"存在ma_keys里，"value"存在ma_values里而ma_version_tag变量则用于支持并发操作，保证字典修改时的线程安全性。
所以核心秘密应该在PyDictKeysObject中
PyDictKeysObject
Include/internal/pycore_dict.h
struct _dictkeysobject {
Py_ssize_t dk_refcnt;
/* Size of the hash table (dk_indices). It must be a power of 2. */
uint8_t dk_log2_size;
/* Size of the hash table (dk_indices) by bytes. */
uint8_t dk_log2_index_bytes;
/* Kind of keys */
uint8_t dk_kind;
/* Version number -- Reset to 0 by any modification to keys */
uint32_t dk_version;
/* Number of usable entries in dk_entries. */
Py_ssize_t dk_usable;
/* Number of used entries in dk_entries. */
Py_ssize_t dk_nentries;
/* Actual hash table of dk_size entries. It holds indices in dk_entries,
or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
The size in bytes of an indice depends on dk_size:
- 1 byte if dk_size <= 0xff (char*)
- 2 bytes if dk_size <= 0xffff (int16_t*)
- 4 bytes if dk_size <= 0xffffffff (int32_t*)
- 8 bytes otherwise (int64_t*)
Dynamically sized, SIZEOF_VOID_P is minimum. */
char dk_indices[]; /* char is required to avoid strict aliasing. */
/* "PyDictKeyEntry or PyDictUnicodeEntry dk_entries[USABLE_FRACTION(DK_SIZE(dk))];" array follows:
see the DK_ENTRIES() macro */
};
dk_refcnt: 引用计数，用于内存管理。dk_log2_size: 哈希表大小，必须是2的幂次方。dk_log2_index_bytes: 索引存储在哈希表中需要的字节数（2的幂次方）。dk_kind: 键的类型，如字符串、整数等。dk_version: 结构体的版本号，当键的数量发生变化时会被重置为0。dk_usable: 可用的槽位数量，即哈希表大小的一半。dk_nentries: 已使用的槽位数量。dk_indices: 存储哈希值和键的索引，大小取决于dk_size。dk_entries[]: 存储键值对的数组。
一个键值对在底层对应一个PyDictKeyEntry对象
PyDictKeyEntry
typedef struct {
/* Cached hash code of me_key. */
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;
- me_hash：键对象的哈希值，避免重复计算
- me_key：键对象指针
- me_value：值对象指针
字典初始化
底层结构大致就是这样的，我们结合具体例子看一下
demo.py
d = {}
执行python3 -m dis demo.py,输出结果
1 0 BUILD_MAP 0 # 创建一个空字典，并将其存储在名为 d 的变量中
2 STORE_NAME 0 (d)
4 LOAD_CONST 0 (None) # 将 None 压入堆栈
6 RETURN_VALUE # 返回 None
通过字节码输出结果，首先会调用BUILD_MAP来创建一个字典。
在源码中找到BUILD_MAP
Python/ceval.c
TARGET(BUILD_MAP) { // 定义一个名为 BUILD_MAP 的标签(TARGET)
PyObject *map = _PyDict_FromItems( // 调用 CPython API 中的 _PyDict_FromItems 函数创建字典对象
&PEEK(2*oparg), 2, // PEEK(2*oparg) 获取操作数(oparg)指定位置处的键(key)对象，& 操作符获取其地址传递给 _PyDict_FromItems 函数；2 表示有两个参数，因为此时只取了一对键值
&PEEK(2*oparg - 1), 2, // PEEK(2*oparg - 1) 获取操作数指定位置处的值(value)对象，& 操作符获取其地址传递给 _PyDict_FromItems 函数；2 表示有两个参数，因为此时只取了一对键值
oparg); // oparg 是操作数，表示字典元素数量，也即在栈上需要弹出多少个键值对
if (map == NULL) // 如果创建字典对象失败，则跳转到 error 标签
goto error;
while (oparg--) { // 循环弹出栈中的键值对，直到弹出 oparg 个
Py_DECREF(POP()); // 弹出并释放键对象
Py_DECREF(POP()); // 弹出并释放值对象
}
PUSH(map); // 将新创建的字典对象推入栈中
DISPATCH(); // 跳转到下一个指令执行
}
在这段代码中，通过 PEEK 操作获取操作数指定位置处的键值对对象，并将其传递给 _PyDict_FromItems 函数。然后使用 while 循环从栈中弹出刚刚使用的键值对对象，并释放它们占用的内存空间。最后将新创建的字典对象推入栈中，并跳转到下一个指令继续执行。
_PyDict_FromItems
PyObject *
_PyDict_FromItems(PyObject *const *keys, Py_ssize_t keys_offset,
PyObject *const *values, Py_ssize_t values_offset,
Py_ssize_t length)
{
bool unicode = true;
PyObject *const *ks = keys;
for (Py_ssize_t i = 0; i < length; i++) {
if (!PyUnicode_CheckExact(*ks)) {
unicode = false;
break;
}
ks += keys_offset;
}
PyObject *dict = dict_new_presized(length, unicode);
if (dict == NULL) {
return NULL;
}
ks = keys;
PyObject *const *vs = values;
for (Py_ssize_t i = 0; i < length; i++) {
PyObject *key = *ks;
PyObject *value = *vs;
if (PyDict_SetItem(dict, key, value) < 0) {
Py_DECREF(dict);
return NULL;
}
ks += keys_offset;
vs += values_offset;
}
return dict;
}
-
这是一个以 PyObject 指针为返回值的函数，函数名为 _PyDict_FromItems。它接受五个参数，其中：
keys是一个指向 PyObject 指针数组的常量指针，表示字典的键；keys_offset是键列表中相邻两个元素之间的偏移量，也就是键的步长，通常是 1；values是同上类型和作用的常量指针，表示字典的值；values_offset是值列表中相邻两个元素之间的偏移量，也就是值的步长，通常是 1；length表示键值对的数量。
-
定义一个布尔类型变量
unicode并初始化为 true； -
声明一个 PyObject 指针常量
ks，并赋值为keys； -
使用 for 循环遍历键列表，如果某个键不是 PyUnicode 对象，则将
unicode设为 false，并跳出循环； -
键的遍历通过指针加偏移量的方式实现，每次迭代后
ks指向下一个键； -
调用 dict_new_presized 函数创建一个空字典对象，并指定预分配容量为 length；
-
如果创建失败，则返回空指针。
-
将
ks和vs重新赋值为keys和values； -
使用 for 循环遍历所有键值对，每次迭代获取当前键和值，并使用 PyDict_SetItem 函数将其添加到字典对象中；
-
如果添加失败，则释放字典对象并返回空指针；
-
迭代完毕后返回新创建的字典对象。
我们看看创建字典的函数dict_new_presized
Objects/dictobject.c
static PyObject *
dict_new_presized(Py_ssize_t minused, bool unicode)
{
const uint8_t log2_max_presize = 17;
const Py_ssize_t max_presize = ((Py_ssize_t)1) << log2_max_presize;
uint8_t log2_newsize;
PyDictKeysObject *new_keys;
if (minused <= USABLE_FRACTION(PyDict_MINSIZE)) {
return PyDict_New();
}
/* There are no strict guarantee that returned dict can contain minused
* items without resize. So we create medium size dict instead of very
* large dict or MemoryError.
*/
if (minused > USABLE_FRACTION(max_presize)) {
log2_newsize = log2_max_presize;
}
else {
log2_newsize = estimate_log2_keysize(minused);
}
new_keys = new_keys_object(log2_newsize, unicode);
if (new_keys == NULL)
return NULL;
return new_dict(new_keys, NULL, 0, 0);
}
PyDict_MINSIZE值默认为8，可以看到键值对的数量为0时，会调用PyDict_New创建字典
PyObject *
PyDict_New(void)
{
dictkeys_incref(Py_EMPTY_KEYS); // 调用 dictkeys_incref 函数，将 empty_dict_keys 对象的引用计数加一。empty_dict_keys 是一个全局变量，表示一个空字典的键列表，它的值是一个指向 DictKeys 结构体的常量指针。
return new_dict(Py_EMPTY_KEYS, NULL, 0, 0);
}
#define Py_EMPTY_KEYS &empty_keys_struct
static PyDictKeysObject empty_keys_struct = {
1, /* dk_refcnt */
0, /* dk_log2_size */
0, /* dk_log2_index_bytes */
DICT_KEYS_UNICODE, /* dk_kind */
1, /* dk_version */
0, /* dk_usable (immutable) */
0, /* dk_nentries */
{DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
};
#define DKIX_EMPTY (-1)
可以看到最终调用new_dict
- 调用 new_dict 函数，创建一个新的字典对象；
- 第一个参数是键列表，这里传递的是 empty_dict_keys；
- 第二个参数是值列表，这里传递了空指针表示没有值；
- 第三个参数是预分配容量，这里传递 0 表示不预分配；
- 第四个参数是是否使用共享键策略，这里传递 0 表示不使用共享键策略；
- 如果创建成功，则返回新创建的字典对象，否则返回空指针。
这样我们就知道了d = {}底层是如何创建一个空字典的，画个图
如果创建一个有键值对的字典，又是怎样的呢？
d = {'age': 18}
运行得到字节码如下：
1 0 LOAD_CONST 0 ('age')
2 LOAD_CONST 1 (18)
4 BUILD_MAP 1
6 STORE_NAME 0 (d)
8 LOAD_CONST 2 (None)
10 RETURN_VALUE
可以看到，大致分两步完成：
- 创建一个字典对象
- 在字典对象中添加键值对
'age': 18
如何添加键值对，应该在STORE_NAME中可以找到真相
TARGET(STORE_NAME) {
PyObject *name = GETITEM(names, oparg);
PyObject *v = POP();
PyObject *ns = LOCALS();
int err;
if (ns == NULL) {
_PyErr_Format(tstate, PyExc_SystemError,
"no locals found when storing %R", name);
Py_DECREF(v);
goto error;
}
if (PyDict_CheckExact(ns))
err = PyDict_SetItem(ns, name, v);
else
err = PyObject_SetItem(ns, name, v);
Py_DECREF(v);
if (err != 0)
goto error;
DISPATCH();
}
STORE_NAME 是一种用于在本地名称空间中存储变量的指令。
具体来看，这段代码首先从操作数栈上弹出要存储的值 v，并获取当前的本地名称空间 ns。如果本地名称空间不存在，就会引发 SystemError 异常并跳转到 error 标签，后面的代码将不会执行。
然后，代码检查名称空间类型是否是字典类型，如果是，则使用 PyDict_SetItem() 函数将名称和值存储在字典中，否则，使用 PyObject_SetItem() 函数将名称和值存储在一般的映射对象中。最后，使用 Py_DECREF() 函数释放值 v 的引用。
如果存储过程中发生了错误（例如，名称空间中的条目无法设置），则代码跳转到 error 标签处，并清理已经压入堆栈的值 v。
最后，代码调用 DISPATCH() 宏，该宏实际上是一个标记，使解释器跳转到下一条指令。
总体来说，这段代码实现了 STORE_NAME 指令的基本行为，即将给定的值存储在本地名称空间中的给定名称下。
可以看出核心在PyDict_SetItem中，就是调用该函数实现添加键值对的。
Objects/dictobject.c
int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
// ......
return _PyDict_SetItem_Take2((PyDictObject *)op, key, value);
}
int
_PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value)
{
// ......
if (mp->ma_keys == Py_EMPTY_KEYS) {
return insert_to_emptydict(mp, key, hash, value);
}
/* insertdict() handles any resizing that might be necessary */
return insertdict(mp, key, hash, value);
}
可以看到字典为空时，插入键值对调用insert_to_emptydict实现
static int
insert_to_emptydict(PyDictObject *mp, PyObject *key, Py_hash_t hash,
PyObject *value)
{
// ......
PyDictKeysObject *newkeys = new_keys_object(PyDict_LOG_MINSIZE, unicode);
// ......
dictkeys_decref(Py_EMPTY_KEYS);
mp->ma_keys = newkeys;
mp->ma_values = NULL;
MAINTAIN_TRACKING(mp, key, value);
size_t hashpos = (size_t)hash & (PyDict_MINSIZE-1);
dictkeys_set_index(mp->ma_keys, hashpos, 0);
// ......
return 0;
}
关键步骤：
- 将mp->ma_keys设置为指向新keys对象，并将mp->ma_values设置为NULL
- 函数通过对哈希值和PyDict_MINSIZE-1进行与运算来计算键值对的哈希位置。然后调用dictkeys_set_index()在keys对象中设置新键值对的索引。
到这里我们就知道在空字典中是如何添加一个键值对的，上面的图完善一下
- 键值对保存在dk_entries中，初识字典为空，会先从索引为0的位置开始保存
- 计算哈希位置，然后将键值对在dk_entries中的索引保存在
dk_indices中索引为1的位置
插入
d = {}
d['age'] = 18
还是通过字节码，找到STORE_SUBSCR，接着找到PyObject_SetItem
Objects/abstract.c
int
PyObject_SetItem(PyObject *o, PyObject *key, PyObject *value)
{
if (o == NULL || key == NULL || value == NULL) {
null_error();
return -1;
}
PyMappingMethods *m = Py_TYPE(o)->tp_as_mapping;
if (m && m->mp_ass_subscript) {
int res = m->mp_ass_subscript(o, key, value);
assert(_Py_CheckSlotResult(o, "__setitem__", res >= 0));
return res;
}
if (Py_TYPE(o)->tp_as_sequence) {
if (_PyIndex_Check(key)) {
Py_ssize_t key_value;
key_value = PyNumber_AsSsize_t(key, PyExc_IndexError);
if (key_value == -1 && PyErr_Occurred())
return -1;
return PySequence_SetItem(o, key_value, value);
}
else if (Py_TYPE(o)->tp_as_sequence->sq_ass_item) {
type_error("sequence index must be "
"integer, not '%.200s'", key);
return -1;
}
}
type_error("'%.200s' object does not support item assignment", o);
return -1;
}
可以看到，调用了tp_as_mapping 的方法集，并调用了该方法集的 mp_ass_subscript 方法，通过源码可以知道，最终执行的函数为dict_ass_sub
static int
dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
{
if (w == NULL)
return PyDict_DelItem((PyObject *)mp, v);
else
return PyDict_SetItem((PyObject *)mp, v, w);
}
大致过程
- 计算键的哈希值（hash(key)）
- 再和 mask = PyDicMinSize - 1 做与操作，计算这个元素应该插入哈希表的位置 index = hash(key) & mask
- 如果哈希表中此位置是空的，那么这个元素就会被插入其中。
- 如果此位置已被占用，Python 便会比较两个元素的哈希值和键是否相等
若两者都相等，则表明这个元素已经存在，如果值不同，则更新值
若两者中有一个不相等，这种情况我们通常称为哈希冲突（hash collision），意思是两个元素的键不相等，但是哈希值相等。这种情况下，Python 便会继续寻找表中空余的位置，直到找到位置为止。
查找
d = {'age': 18}
d['age']
还是通过字节码，找到BINARY_SUBSCR，接着找到PyObject_GetItem
和PyObject_SetItem类似，最终调用了map方法集的mp_subscript，最终执行的函数为dict_subscript，感兴趣的可以翻阅源码看看，大致查找过程：
- 对key值进行哈希运算得到索引值
- 根据索引在
dk_indices中找到存储的值 - 如果未找到报KeyError，如果找到，根据找到的值在dk_entries中找到键值对，判断已存在的key和指定的key是否相等
- 如果相等，返回key对应的value值；如果不相等，改变策略重新映射（重新计算索引）
删除
d = {'age': 18}
del d['age']
和上面查找源码步骤一样，通过字节码，最终找到PyDict_DelItem
源文件：Objects/dictobject.c
int
PyDict_DelItem(PyObject *op, PyObject *key)
{
Py_hash_t hash;
assert(key);
if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
return _PyDict_DelItem_KnownHash(op, key, hash);
}
主要是计算hash值，先检查键是否为PyUnicode对象，如果是，则使用unicode_get_hash()函数计算其哈希值。如果unicode_get_hash()返回-1，则表示无法计算哈希值，该函数返回-1。
如果键不是PyUnicode对象，或者如果unicode_get_hash()成功，则代码调用PyObject_Hash()来计算键的哈希值。如果PyObject_Hash()返回-1，则该函数返回-1
源文件：Objects/dictobject.c
int
_PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
{
Py_ssize_t ix;
PyDictObject *mp;
PyObject *old_value;
if (!PyDict_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
assert(key);
assert(hash != -1);
mp = (PyDictObject *)op;
ix = _Py_dict_lookup(mp, key, hash, &old_value);
if (ix == DKIX_ERROR)
return -1;
if (ix == DKIX_EMPTY || old_value == NULL) {
_PyErr_SetKeyError(key);
return -1;
}
return delitem_common(mp, hash, ix, old_value);
}
主要使用 _Py_dict_lookup() 函数在字典中查找具有指定键和哈希值的项，并返回其索引，最终调用 delitem_common() 函数来删除该项并返回 0 表示成功
源文件：Objects/dictobject.c
static int
delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
PyObject *old_value)
{
PyObject *old_key;
Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
assert(hashpos >= 0);
mp->ma_used--;
mp->ma_version_tag = DICT_NEXT_VERSION();
if (mp->ma_values) {
assert(old_value == mp->ma_values->values[ix]);
mp->ma_values->values[ix] = NULL;
assert(ix < SHARED_KEYS_MAX_SIZE);
/* Update order */
delete_index_from_values(mp->ma_values, ix);
ASSERT_CONSISTENT(mp);
}
else {
mp->ma_keys->dk_version = 0;
dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
if (DK_IS_UNICODE(mp->ma_keys)) {
PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix];
old_key = ep->me_key;
ep->me_key = NULL;
ep->me_value = NULL;
}
else {
PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
old_key = ep->me_key;
ep->me_key = NULL;
ep->me_value = NULL;
ep->me_hash = 0;
}
Py_DECREF(old_key);
}
Py_DECREF(old_value);
ASSERT_CONSISTENT(mp);
return 0;
}
- 接收一个 PyDictObject 对象 mp、待删除元素的哈希值 hash 和在哈希表中的索引位置 ix 以及代表被删除键对应的值的 PyObject 对象 old_value。
- 在哈希表中查找该键值对应的下标位置 hashpos，并将其断言为非负。
- 减少字典中元素个数，并更新版本号 ma_version_tag。如果有值对象数组 ma_values，将该位置上的值对象置空，并从值对象数组中删除此元素。否则说明该桶的键值对已经全部删除，需要从 key 数组中删除该元素，并释放键对象 old_key。
- 最后释放旧的值对象 old_value 和旧的键对象 old_key，并返回值 0。
哈希表
哈希函数
d = {['age']: 18}
d # TypeError: unhashable type: 'list'
可见列表是不可哈希类型。那哪些是可哈希对象呢？
根据哈希表性质，键对象必须满足以下两个条件，否则哈希表便不能正常工作：
- 哈希值在对象的整个生命周期内不能改变
- 可比较，并且比较结果相等(使用==操作符结果为True)的两个对象的哈希值必须相同
满足这两个条件的对象便是可哈希（hashable）对象，只有可哈希对象才可作为哈希表的键。在Python的内建类型中，不可变对象都是可哈希对象(整数、浮点数、字符串、元组(元素也必须是不可变))。
class Demo:
pass
a = Demo()
b = Demo()
hash(a) # 276116571
hash(a) # 276116529
可以看到自定义的对象是可哈希对象，对象哈希值是根据对象地址计算的。
当然也可以通过__hash__()魔法方法重写哈希值计算方法
class Demo:
def __hash__(self):
return 123
a = Demo()
b = Demo()
hash(a) # 123
hash(a) # 123
但是注意这种情况，只是重写了__eq__()方法时，将变为不可哈希对象
class Demo:
def __eq__(self, other):
return True
a = Demo()
hash(a) # TypeError: unhashable type: 'Demo'
为啥呢？前面提到未重写__hash__()时，哈希值是根据对象地址计算的，对象相等（使用==操作符结果为True）时哈希值是一样的，重写了__eq()__,使得两个对象地址不同，哈希值不同，但对象却相等，造成了矛盾。
哈希冲突
不同的键在通过哈希函数得到的哈希值相同时，会被映射到哈希表的同一个桶中。由于哈希表采用数组实现，一个桶可能存储多个键值对，因此就出现了冲突。
哈希冲突是不可避免的，因为哈希函数无法保证对于所有的输入都能生成唯一的哈希值。当哈希表中的元素越来越多时，哈希冲突的概率也会随之增加。
哈希冲突的解决方法通常有以下两种：
- 链接法：将哈希到同一个桶中的键值对存储在一个链表或其他数据结构中，每次查找时遍历这个数据结构。
- 开放寻址法：当发生冲突时，依次检查哈希表中下一个位置是否为空，直到找到一个空位置为止。当查找元素时，如果发现哈希表中的某个位置不是目标元素，就继续查找下一个位置，直到找到目标元素或者遍历完整个哈希表为止。
哈希攻击
哈希攻击是指攻击者试图通过修改或伪造哈希值来破坏系统的完整性或欺骗系统。
例如，攻击者可以修改一个数据的内容或长度，以使其生成的哈希值与原始数据的哈希值相同，从而伪装成原始数据。这种攻击被称为哈希碰撞攻击。为了避免哈希碰撞攻击，应该选择强大的哈希算法，并使用适当的盐值和密钥来加强哈希算法的安全性。此外，还可以使用更复杂的哈希函数，例如SHA-256或SHA-512等，来防止哈希攻击。
Python 在 3.3 以前， 哈希算法只根据对象本身计算哈希值。因此，只要 Python 解释器相同，对象哈希值也肯定相同。为了避免冲突，python采取的做法是往对象身上撒把盐(salt)，具体做法：解释器启动时，产生一个随机数，哈希函数使用对象和随机数计算哈希值
想要第一时间看到最新文章，可以关注公众号：郝同学的测开日记