Python内建类型dict的源码是什么

Python中的dict（字典）是一种非常常用的内建数据类型，它用于存储键值对（key-value pairs）。dict的实现是基于哈希表（hash table）的，这使得它在大多数情况下能够以O(1)的时间复杂度进行插入、删除和查找操作。本文将简要介绍Python中dict的源码实现，并解释其核心机制。

1. dict的基本结构

Python的dict类型在C语言层面是通过PyDictObject结构体来实现的。这个结构体定义在Objects/dictobject.c文件中。PyDictObject的核心结构如下：

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;  // 已使用的条目数
    Py_ssize_t ma_mask;  // 哈希表的大小减一
    PyDictEntry *ma_table;  // 指向哈希表数组的指针
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];  // 小字典的初始哈希表
} PyDictObject;

1.1 PyDictEntry结构

PyDictEntry是哈希表中的每个条目，它存储了键、值和哈希值。其定义如下：

typedef struct {
    Py_ssize_t me_hash;  // 键的哈希值
    PyObject *me_key;    // 键
    PyObject *me_value;  // 值
} PyDictEntry;

1.2 哈希表

dict的核心是一个哈希表，它由PyDictEntry数组组成。哈希表的大小通常是2的幂次方，这样可以方便地通过位运算来计算索引。哈希表的初始大小为8（PyDict_MINSIZE），当字典中的条目数超过哈希表大小的2/3时，哈希表会进行扩容。

2. 哈希表的插入与查找

2.1 插入操作

当向字典中插入一个新的键值对时，Python会首先计算键的哈希值，然后通过哈希值和哈希表的大小计算出一个索引。如果该索引对应的位置为空，则直接将键值对插入到该位置。如果该位置已经被占用，Python会使用开放寻址法（open addressing）来解决冲突，具体来说，它会使用线性探测法（linear probing）来寻找下一个可用的位置。

2.2 查找操作

查找操作与插入操作类似。Python首先计算键的哈希值，然后通过哈希值和哈希表的大小计算出索引。如果该索引对应的位置的键与查找的键匹配，则返回对应的值。如果不匹配，则继续使用线性探测法查找下一个位置，直到找到匹配的键或遇到空位置为止。

3. 哈希表的扩容

当字典中的条目数超过哈希表大小的2/3时，Python会对哈希表进行扩容。扩容的过程包括创建一个新的更大的哈希表，然后将旧哈希表中的所有条目重新插入到新哈希表中。新哈希表的大小通常是旧哈希表大小的两倍。

3.1 扩容的触发条件

扩容的触发条件是字典中的条目数超过哈希表大小的2/3。这个比例是为了在哈希表中保持一定的空闲位置，以减少冲突的概率。

3.2 扩容的实现

扩容的实现主要包括以下几个步骤：

1. 创建一个新的更大的哈希表。
2. 遍历旧哈希表中的所有条目，重新计算它们的哈希值，并将它们插入到新哈希表中。
3. 释放旧哈希表的内存。

4. 删除操作

删除操作与查找操作类似。Python首先找到要删除的键值对的位置，然后将该位置的键和值设置为NULL，并将该位置标记为“已删除”。为了保持哈希表的性能，Python会在适当的时候对哈希表进行压缩，即将所有“已删除”的条目移除，并将剩余的条目重新排列。

5. 总结

Python的dict类型通过哈希表实现了高效的键值对存储和查找。哈希表的核心机制包括哈希函数、开放寻址法、线性探测法和动态扩容。这些机制使得dict在大多数情况下能够以O(1)的时间复杂度进行插入、删除和查找操作。

通过了解dict的源码实现，我们可以更好地理解Python中字典的工作原理，并在实际编程中更加高效地使用这一数据结构。