Python 的字典（Dict）是如何存储的

Python的字典是一种散列表的实现，它是一个无序的键值对集合，其中可以添加和删除键值对，字典中的键必须唯一且必须是不可变类型（如字符串、元组、数字等），值可以是任何类型，包括列表和其他字典。字典是Python的核心数据类型之一，在实际开发中经常使用。

字典的内部实现

字典的底层是由一个散列表（哈希表）实现的。散列表是一种根据键值直接访问内存位置的数据结构，可以实现高效的查找和插入操作。Python中的字典通过散列表来实现对键值对的存储和访问。

当我们创建一个字典时，Python会在内存中为这个空字典分配一块连续的内存空间，并用一个哈希表（散列表）来存储所有的键值对。哈希表中的每个元素包含了两个重要的部分，即键和值。键通过一个哈希函数计算得到对应的哈希值，在散列表中寻找对应的值。当我们需要查找或者添加一个元素时，Python会根据输入的键值通过哈希函数计算出在散列表中的位置，然后直接访问该位置的元素。因为散列表的访问效率非常高，所以字典的查找、插入、删除等操作都非常快速，是Python中非常优秀的数据结构之一。

下面我们来看一个例子：

d = {"a": 1, "b": 2, "c": 3}

这个字典有三个元素，分别是 "a": 1、"b": 2、"c": 3。当我们创建这个字典时，Python会为其分配一块连续的内存空间，并创建一张散列表来存储所有的键值对。散列表的大小通常会根据字典的元素数量进行动态调整，以保证效率。

假设我们要查询 d 中的 "b" 对应的值。首先，Python会根据 "b" 通过哈希函数计算出对应的哈希值（具体的哈希函数实现细节可以参考Python源代码），然后根据该哈希值在散列表中寻找键值为 "b" 的元素，最终返回其对应的值 2。由于哈希表的访问效率非常高，所以这个操作的时间复杂度为 $O(1)$，非常快速。

字典的哈希冲突

哈希表是一种高效的数据结构，但是在实际应用中，由于哈希函数的设计和数据的特殊性，可能存在多个键值对的哈希值相等的情况。这种情况称为哈希冲突（Collision）。

在Python中，哈希冲突的解决方法采用的是开放地址法，也就是当发生哈希冲突时，在散列表中依次向后寻找空槽位，直到找到一个空槽位来存储对应的键值对，或者直到所有的槽位都被占用。因为散列表的大小通常是动态调整的，所以在哈希冲突比较少的情况下，Python的字典仍然能够保持高效性，但如果哈希冲突比较频繁，那么这个效率就会降低。

下面我们来看一个发生哈希冲突的例子：

d = {0: "a", 1: "b", 2: "c", 3: "d"}
print(d[0], d[1], d[2], d[3])  # 输出：a b c d

这个字典的键是整数类型，Python使用的哈希函数是取模。可以看到，字典中的所有键都是正整数并且连续的，因此哈希值也是连续的，不会发生哈希冲突。

现在，我们在字典中加入一个新元素：

d[4] = "e"

因为散列表的大小是动态调整的，所以当我们加入一个新元素时，Python会根据需要动态地调整散列表的大小。在这个例子中，Python会将散列表大小扩大为 $2^3=8$，并重新哈希所有的元素。

此时，散列表中的所有元素的哈希值均被重新计算：

0: "a"    -->  0
1: "b"    -->  1
2: "c"    -->  2
3: "d"    -->  3
4: "e"    -->  4

可以看到，此时所有元素的哈希值均不会发生冲突，因此字典的效率依然非常高。