Python内建类型dict源码分析

1. 引言

Python中的字典（dict）是一种非常常用的数据结构，它提供了高效的键值对存储和查找功能。字典的实现涉及到许多底层的数据结构和算法，理解这些内容对于深入掌握Python的内部机制非常有帮助。本文将深入分析Python中dict类型的源码实现，探讨其内部结构、哈希表的工作原理、冲突解决策略、内存管理以及性能优化等方面。

2. 字典的基本概念

在Python中，字典是一种可变容器模型，可以存储任意类型的对象。字典中的每个元素都是一个键值对，键必须是不可变类型，而值可以是任意类型。字典的主要操作包括插入、删除、查找等，这些操作的平均时间复杂度都是O(1)。

2.1 字典的创建

字典可以通过多种方式创建，最常见的方式是使用花括号{}或dict()构造函数：

# 使用花括号创建字典
d1 = {'name': 'Alice', 'age': 25}

# 使用dict()构造函数创建字典
d2 = dict(name='Bob', age=30)

2.2 字典的基本操作

字典支持多种操作，包括插入、删除、查找、更新等：

# 插入
d1['gender'] = 'female'

# 删除
del d1['age']

# 查找
name = d1['name']

# 更新
d1['name'] = 'Alice Smith'

3. 字典的内部结构

Python中的字典是通过哈希表（Hash Table）实现的。哈希表是一种通过哈希函数将键映射到索引的数据结构，它能够在平均情况下提供O(1)的查找、插入和删除操作。

3.1 哈希表的基本概念

哈希表的核心思想是通过哈希函数将键转换为一个整数索引，然后将键值对存储在该索引对应的位置。哈希函数的设计对于哈希表的性能至关重要，一个好的哈希函数应该能够将键均匀地分布在整个哈希表中，从而减少冲突的发生。

3.2 Python字典的哈希表实现

Python中的字典是通过一个名为PyDictObject的结构体实现的。该结构体定义在Include/cpython/dictobject.h文件中：

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;  // 已使用的条目数
    Py_ssize_t ma_version_tag;  // 版本标签，用于快速失败
    PyDictKeysObject *ma_keys;  // 键对象
    PyObject **ma_values;  // 值数组
} PyDictObject;

PyDictObject结构体包含以下几个重要字段：

• ma_used：表示字典中已使用的条目数。
• ma_version_tag：用于快速失败的版本标签。
• ma_keys：指向键对象的指针。
• ma_values：指向值数组的指针。

3.3 哈希表的存储结构

Python的哈希表是通过一个名为PyDictKeysObject的结构体实现的。该结构体定义在Include/cpython/dictobject.h文件中：

typedef struct {
    Py_ssize_t dk_refcnt;  // 引用计数
    Py_ssize_t dk_size;  // 哈希表的大小
    Py_ssize_t dk_usable;  // 可用的条目数
    Py_ssize_t dk_nentries;  // 已使用的条目数
    uint8_t dk_indices[];  // 索引数组
} PyDictKeysObject;

PyDictKeysObject结构体包含以下几个重要字段：

• dk_refcnt：引用计数，用于内存管理。
• dk_size：哈希表的大小。
• dk_usable：可用的条目数。
• dk_nentries：已使用的条目数。
• dk_indices：索引数组，用于存储哈希表的索引。

3.4 哈希表的索引数组

哈希表的索引数组dk_indices是一个动态数组，它存储了哈希表的索引。每个索引对应一个哈希表的槽位，槽位中存储了键值对的索引。如果槽位为空，则存储一个特殊的值DKIX_EMPTY（通常为-1）。

3.5 哈希表的键值对存储

哈希表的键值对存储在ma_values数组中。每个键值对由一个PyObject指针和一个PyObject指针组成，分别指向键和值。

4. 哈希函数与冲突解决

哈希函数是哈希表的核心，它将键转换为一个整数索引。Python中的哈希函数是通过PyObject_Hash函数实现的，该函数定义在Objects/object.c文件中：

Py_hash_t
PyObject_Hash(PyObject *v)
{
    PyTypeObject *tp = Py_TYPE(v);
    if (tp->tp_hash != NULL)
        return (*tp->tp_hash)(v);
    if (tp->tp_dict == NULL) {
        if (PyType_Ready(tp) < 0)
            return -1;
        if (tp->tp_hash != NULL)
            return (*tp->tp_hash)(v);
    }
    return PyObject_HashNotImplemented(v);
}

PyObject_Hash函数首先检查对象的类型是否定义了哈希函数，如果定义了则调用该哈希函数，否则返回PyObject_HashNotImplemented。

4.1 哈希冲突

哈希冲突是指两个不同的键通过哈希函数计算得到相同的索引。哈希冲突是不可避免的，因为哈希函数的输出空间通常小于键的空间。Python中的哈希表通过开放寻址法（Open Addressing）来解决哈希冲突。

4.2 开放寻址法

开放寻址法是一种解决哈希冲突的方法，当发生冲突时，它会尝试在哈希表中寻找下一个可用的槽位。Python中的开放寻址法是通过线性探测（Linear Probing）实现的。

线性探测的基本思想是，当发生冲突时，依次检查下一个槽位，直到找到一个可用的槽位为止。Python中的线性探测是通过lookdict函数实现的，该函数定义在Objects/dictobject.c文件中：

static Py_ssize_t
lookdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr)
{
    PyDictKeysObject *dk = mp->ma_keys;
    Py_ssize_t i, perturb;
    PyObject *k;
    Py_ssize_t mask = DK_SIZE(dk) - 1;
    i = hash & mask;
    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
        Py_ssize_t ix = dk->dk_indices[i];
        if (ix == DKIX_EMPTY) {
            *value_addr = NULL;
            return i;
        }
        if (ix >= 0) {
            k = DK_ENTRIES(dk)[ix].me_key;
            if (k == key || (dk->dk_lookup == lookdict && PyObject_RichCompareBool(k, key, Py_EQ))) {
                *value_addr = &DK_ENTRIES(dk)[ix].me_value;
                return i;
            }
        }
        i = (i << 2) + i + perturb + 1;
        i &= mask;
    }
}

lookdict函数首先计算键的哈希值，然后通过哈希值计算索引。如果索引对应的槽位为空，则返回该槽位的索引。如果槽位不为空，则检查键是否匹配，如果匹配则返回该槽位的索引，否则继续探测下一个槽位。

4.3 哈希表的扩容

当哈希表中的条目数超过一定阈值时，哈希表需要进行扩容。Python中的哈希表扩容是通过dictresize函数实现的，该函数定义在Objects/dictobject.c文件中：

static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
    PyDictKeysObject *oldkeys = mp->ma_keys;
    Py_ssize_t oldsize = DK_SIZE(oldkeys);
    Py_ssize_t newsize = PyDict_MINSIZE;
    while (newsize <= minused && newsize > 0)
        newsize <<= 1;
    if (newsize <= 0)
        return -1;
    PyDictKeysObject *newkeys = new_keys_object(newsize);
    if (newkeys == NULL)
        return -1;
    mp->ma_keys = newkeys;
    mp->ma_values = NULL;
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    if (oldkeys->dk_nentries > 0) {
        Py_ssize_t i;
        for (i = 0; i < oldsize; i++) {
            Py_ssize_t ix = oldkeys->dk_indices[i];
            if (ix >= 0) {
                PyObject *key = DK_ENTRIES(oldkeys)[ix].me_key;
                PyObject *value = DK_ENTRIES(oldkeys)[ix].me_value;
                Py_INCREF(key);
                Py_INCREF(value);
                if (insertdict(mp, key, value, oldkeys->dk_indices[i]) < 0) {
                    Py_DECREF(key);
                    Py_DECREF(value);
                    return -1;
                }
            }
        }
    }
    Py_DECREF(oldkeys);
    return 0;
}

dictresize函数首先计算新的哈希表大小，然后创建一个新的哈希表，并将旧的哈希表中的条目插入到新的哈希表中。最后，释放旧的哈希表。

5. 字典的内存管理

Python中的字典是通过引用计数进行内存管理的。每个字典对象都有一个引用计数，当引用计数为0时，字典对象会被释放。

5.1 引用计数

引用计数是Python内存管理的核心机制之一。每个Python对象都有一个引用计数，表示有多少个指针指向该对象。当引用计数为0时，对象会被释放。

字典对象的引用计数是通过Py_INCREF和Py_DECREF宏进行管理的。Py_INCREF宏用于增加引用计数，Py_DECREF宏用于减少引用计数。

5.2 字典的内存释放

当字典对象的引用计数为0时，字典对象会被释放。字典对象的内存释放是通过dict_dealloc函数实现的，该函数定义在Objects/dictobject.c文件中：

static void
dict_dealloc(PyDictObject *mp)
{
    PyDictKeysObject *keys = mp->ma_keys;
    PyObject **values = mp->ma_values;
    Py_ssize_t i, n;
    PyObject_GC_UnTrack(mp);
    if (values != NULL) {
        n = DK_SIZE(keys);
        for (i = 0; i < n; i++) {
            Py_XDECREF(values[i]);
        }
        PyMem_FREE(values);
    }
    if (keys != NULL) {
        n = DK_SIZE(keys);
        for (i = 0; i < n; i++) {
            Py_XDECREF(DK_ENTRIES(keys)[i].me_key);
            Py_XDECREF(DK_ENTRIES(keys)[i].me_value);
        }
        PyMem_FREE(keys);
    }
    Py_TYPE(mp)->tp_free((PyObject *)mp);
}

dict_dealloc函数首先释放字典对象的值数组，然后释放字典对象的键数组，最后释放字典对象本身。

6. 字典的性能优化

Python中的字典在实现上进行了一些性能优化，以提高字典的操作效率。

6.1 快速失败机制

Python中的字典通过ma_version_tag字段实现了快速失败机制。快速失败机制是指在字典发生修改时，会更新ma_version_tag字段，从而使得在迭代字典时能够快速检测到字典的修改。

6.2 小字典优化

Python中的字典在实现上进行了一些小字典优化。当字典的条目数较少时，字典会使用一种更紧凑的存储结构，以减少内存的使用。

6.3 哈希表的预分配

Python中的字典在创建时会预分配一定大小的哈希表，以减少哈希表的扩容次数。预分配的大小是根据字典的条目数进行计算的。

7. 字典的源码分析

7.1 字典的创建

字典的创建是通过PyDict_New函数实现的，该函数定义在Objects/dictobject.c文件中：

PyObject *
PyDict_New(void)
{
    PyDictObject *mp;
    if (numfree) {
        mp = free_list[--numfree];
        _Py_NewReference((PyObject *)mp);
    } else {
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        if (mp == NULL)
            return NULL;
    }
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    mp->ma_keys = new_keys_object(PyDict_MINSIZE);
    if (mp->ma_keys == NULL) {
        Py_DECREF(mp);
        return NULL;
    }
    mp->ma_values = NULL;
    return (PyObject *)mp;
}

PyDict_New函数首先检查是否有空闲的字典对象，如果有则从空闲列表中获取一个字典对象，否则创建一个新的字典对象。然后初始化字典对象的字段，并创建一个新的哈希表。

7.2 字典的插入

字典的插入是通过PyDict_SetItem函数实现的，该函数定义在Objects/dictobject.c文件中：

int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
    PyDictObject *mp;
    Py_hash_t hash;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    mp = (PyDictObject *)op;
    if (value == NULL) {
        value = Py_None;
    }
    hash = PyObject_Hash(key);
    if (hash == -1)
        return -1;
    return insertdict(mp, key, value, hash);
}

PyDict_SetItem函数首先检查字典对象是否有效，然后计算键的哈希值，最后调用insertdict函数插入键值对。

7.3 字典的查找

字典的查找是通过PyDict_GetItem函数实现的，该函数定义在Objects/dictobject.c文件中：

PyObject *
PyDict_GetItem(PyObject *op, PyObject *key)
{
    PyDictObject *mp;
    Py_hash_t hash;
    PyObject **value_addr;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    mp = (PyDictObject *)op;
    hash = PyObject_Hash(key);
    if (hash == -1)
        return NULL;
    if (lookdict(mp, key, hash, &value_addr) < 0)
        return NULL;
    return *value_addr;
}

PyDict_GetItem函数首先检查字典对象是否有效，然后计算键的哈希值，最后调用lookdict函数查找键值对。

7.4 字典的删除

字典的删除是通过PyDict_DelItem函数实现的，该函数定义在Objects/dictobject.c文件中：

int
PyDict_DelItem(PyObject *op, PyObject *key)
{
    PyDictObject *mp;
    Py_hash_t hash;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    mp = (PyDictObject *)op;
    hash = PyObject_Hash(key);
    if (hash == -1)
        return -1;
    return dict_delitem(mp, key, hash);
}

PyDict_DelItem函数首先检查字典对象是否有效，然后计算键的哈希值，最后调用dict_delitem函数删除键值对。

8. 总结

本文详细分析了Python中dict类型的源码实现，探讨了其内部结构、哈希表的工作原理、冲突解决策略、内存管理以及性能优化等方面。通过深入理解字典的源码实现，我们可以更好地掌握Python的内部机制，从而编写出更高效、更可靠的代码。

字典作为Python中最常用的数据结构之一，其高效的实现对于Python的性能至关重要。通过本文的分析，我们可以看到Python在字典的实现上进行了许多优化，包括快速失败机制、小字典优化、哈希表的预分配等。这些优化使得Python的字典在实际应用中表现出色，能够满足大多数场景的需求。

希望本文能够帮助读者更好地理解Python中字典的实现原理，并在实际编程中灵活运用这些知识。