Python 字典内部实现原理详解

• 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_ 对象。

1.3 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: 值对象指针。

2. 字典初始化

底层结构大致就是这样的，我们结合具体例子看一下。

2.1 空字典创建

# 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

可以看到，大致分两步完成：

1. 创建一个字典对象
2. 在字典对象中添加键值对 '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 的位置。

3. 插入操作

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 便会继续寻找表中空余的位置，直到找到位置为止。

4. 查找操作

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 值；如果不相等，改变策略重新映射（重新计算索引）。

5. 删除操作

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。

6. 哈希表机制

6.1 哈希函数

key = ['age']
d = {key: 18} 
# TypeError: unhashable type: 'list'

可见列表是不可哈希类型。那哪些是可哈希对象呢？

根据哈希表性质，键对象必须满足以下两个条件，否则哈希表便不能正常工作：

• 哈希值在对象的整个生命周期内不能改变。
• 可比较，并且比较结果相等 (使用==操作符结果为 True) 的两个对象的哈希值必须相同。

满足这两个条件的对象便是可哈希（hashable）对象，只有可哈希对象才可作为哈希表的键。在 Python 的内建类型中，不可变对象都是可哈希对象 (整数、浮点数、字符串、元组 (元素也必须是不可变))。

class Demo:
    pass

a = Demo()
b = Demo()
print(hash(a)) # 276116571
print(hash(b)) # 276116529

可以看到自定义的对象是可哈希对象，对象哈希值是根据对象地址计算的。

当然也可以通过 __hash__() 魔法方法重写哈希值计算方法。

class Demo:
    def __hash__(self):
        return 123

a = Demo()
b = Demo()
print(hash(a)) # 123
print(hash(b)) # 123

但是注意这种情况，只是重写了 __eq__() 方法时，将变为不可哈希对象。

class Demo:
    def __eq__(self, other):
        return True
a = Demo()
hash(a) # TypeError: unhashable type: 'Demo'

为啥呢？前面提到 未重写 __hash__() 时，哈希值是根据对象地址计算的，对象相等（使用==操作符结果为 True）时哈希值是一样的，重写了 __eq__(),使得两个对象地址不同，哈希值不同，但对象却相等，造成了矛盾。

6.2 哈希冲突

不同的键在通过哈希函数得到的哈希值相同时，会被映射到哈希表的同一个桶中。由于哈希表采用数组实现，一个桶可能存储多个键值对，因此就出现了冲突。

哈希冲突是不可避免的，因为哈希函数无法保证对于所有的输入都能生成唯一的哈希值。当哈希表中的元素越来越多时，哈希冲突的概率也会随之增加。

哈希冲突的解决方法通常有以下两种：

1. 链接法：将哈希到同一个桶中的键值对存储在一个链表或其他数据结构中，每次查找时遍历这个数据结构。
2. 开放寻址法：当发生冲突时，依次检查哈希表中下一个位置是否为空，直到找到一个空位置为止。当查找元素时，如果发现哈希表中的某个位置不是目标元素，就继续查找下一个位置，直到找到目标元素或者遍历完整个哈希表为止。

Python 字典采用的是开放寻址法（Open Addressing）。具体来说，当发生冲突时，会使用一种特定的探测序列（probing sequence）来寻找下一个可用位置。在 Python 3.6+ 版本中，这种探测序列更加优化，减少了缓存缺失。

6.3 哈希攻击与防御

哈希攻击是指攻击者试图通过修改或伪造哈希值来破坏系统的完整性或欺骗系统。

例如，攻击者可以构造大量哈希碰撞的数据，导致字典操作时间复杂度退化为 O(n)，从而引发拒绝服务攻击（DoS）。为了避免哈希碰撞攻击，应该选择强大的哈希算法，并使用适当的盐值和密钥来加强哈希算法的安全性。此外，还可以使用更复杂的哈希函数，例如 SHA-256 或 SHA-512 等，来防止哈希攻击。

Python 在 3.3 以前，哈希算法只根据对象本身计算哈希值。因此，只要 Python 解释器相同，对象哈希值也肯定相同。为了避免冲突，python 采取的做法是往对象身上撒把盐 (salt)，具体做法：解释器启动时，产生一个随机数，哈希函数使用对象和随机数计算哈希值。

7. 性能特点与最佳实践

7.1 时间复杂度

• 平均情况: 插入、查找、删除的时间复杂度均为 O(1)。
• 最坏情况: 当发生大量哈希冲突时，时间复杂度可能退化为 O(n)。

7.2 空间开销

字典在内存中占用较大空间，因为它需要维护哈希表和额外的索引结构。为了平衡性能和空间，Python 字典采用了动态扩容策略。当字典负载因子（已用槽位数 / 总槽位数）超过一定阈值（通常为 2/3）时，字典会自动扩容。

7.3 最佳实践

1. 使用不可变对象作为键: 确保键的可哈希性，避免使用列表或字典作为键。
2. 避免频繁扩容: 如果已知字典的大致规模，可以在初始化时预留足够空间，减少扩容带来的性能损耗。
3. 注意哈希冲突: 在设计自定义类的哈希函数时，应尽量避免高冲突率，以保证字典操作的高效性。

8. 总结

本文详细解析了 Python 字典的内部实现原理，包括核心数据结构 PyDictObject、PyDictKeysObject 和 PyDictKeyEntry。深入探讨了字典的初始化、插入、查找、删除操作的底层逻辑，以及哈希表机制、哈希冲突处理和哈希攻击防御。理解这些原理有助于开发者编写更高效、更安全的 Python 代码，特别是在处理大规模数据和高并发场景时。