Python 中的字典是如何实现的？

Python 中的字典（dictionary）是一种非常常用的数据类型，它可以快速地存取和操作数据。与其他语言不同的是，Python 中的字典实现方式是哈希表（hash table）。

什么是哈希表？

哈希表是一种通过计算值在数组中的存储位置而直接访问数据的数据结构。它的基本思想是将关键字映射到一个固定大小的表中，以便能够快速查找记录。哈希表的查找、插入和删除的时间复杂度都是 O(1)。

Python 中的字典采用了哈希表的实现方式，使用哈希函数将键（key）映射到哈希表中的下标（index），可以快速地查找字典中的值（value）。

字典的创建和访问

Python 中的字典是用花括号 {} 来表示的，键值对之间用冒号 : 连接。

# 创建字典
my_dict = {'apple': 5, 'banana': 2, 'orange': 8}

# 访问字典
print(my_dict['apple']) # 输出 5

在访问字典时，如果键不存在，会抛出 KeyError 异常。可以使用 get() 方法来避免这种情况。

# 使用 get() 方法访问字典
print(my_dict.get('watermelon', 0)) # 输出 0

字典的添加、修改和删除

向字典中添加新的键值对，可以使用赋值语句。如果字典中已经存在该键，赋值语句会更新该键对应的值。

# 添加键值对
my_dict['watermelon'] = 3
print(my_dict)

# 修改键值对
my_dict['apple'] = 6
print(my_dict)

可以使用 del 语句从字典中删除键值对。

# 删除键值对
del my_dict['orange']
print(my_dict)

字典的遍历

字典中的键值对是无序的，我们可以使用 for 循环遍历字典中的所有键值对。可以用 items() 方法获取键值对。

# 遍历字典
for key, value in my_dict.items():
    print(key, value)

字典的实现方式

Python 中的字典不是数组的实现方式，而是哈希表的实现方式。在 Python 源代码中，字典的实现可以在 dictobject.c 文件中找到。

字典的主要结构是 PyDictObject，它包含了一个指针 d_table，指向一个哈希表结构体 PyDictKeysObject。哈希表结构体中包含了一个指针 dk_entries，指向 PyDictKeyEntry 结构体数组，每个 PyDictKeyEntry 结构体储存了哈希表中一个格子里的信息。

以下是哈希表结构体 PyDictKeysObject 的定义：

typedef struct {
    Py_ssize_t dk_refcnt;               /* 引用计数 */
    Py_ssize_t dk_size;                 /* 哈希表大小 */
    dictentry dk_lookup[PyDict_MINSIZE]; /* 最小哈希表大小 */
    PyDictKeyEntry *dk_entries;         /* 格子信息 */
    Py_ssize_t dk_usable;               /* 实际可用的哈希表大小 */
} PyDictKeysObject;

dk_lookup 数组用来实现哈希表中的冲突解决。当哈希表中的一个格子已经被占用时，就会使用线性探测来从 dk_lookup 数组中找到下一个空闲的位置。

dk_entries 数组中保存了所有的键值对信息。每个 PyDictKeyEntry 结构体都包含了键和值的信息，以及哈希表中的位置。以下是 PyDictKeyEntry 结构体的定义：

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

在哈希表中查找一个键值对时，首先计算键的哈希值，然后根据哈希值计算键在哈希表中的位置。如果该位置上的键值对不是要查询的键值对，就继续向后查找，一直到找到该键值对或者遇到空位置。

哈希表的大小不是固定的，而是会根据需要动态地调整。当哈希表中的键值对数量达到了一定的比例时，Python 会自动扩大哈希表的大小，以便更好地分配键值对。