Python 字典内部结构详解
Python 字典（dict）是用来存储键值对的一种数据结构。它是哈希表的一种实现方式，因此字典的查找、插入、删除操作的时间复杂度平均为 O(1)，性能非常高效。Python 字典的内部结构随着 Python 版本的变化有所优化，尤其是从 Python 3.6 开始，字典的实现发生了显著变化。
1. 字典的基础结构
在 Python 3.6 之前，字典是无序的。从 Python 3.6 开始，字典保持了插入顺序，这是由于内部结构的优化。Python 字典的内部实现主要依赖哈希表。
字典的核心结构包括：
- 哈希表（Hash Table）：字典的核心是哈希表，用于存储键值对。
- 数组（Array）：字典的内部使用了一个数组，这个数组中存储了所有的键值对。数组的每个元素称为 桶（bucket）。
- 哈希函数：每个键通过哈希函数映射到哈希表的某个索引上，从而快速找到对应的值。
当字典发生冲突（即不同的键映射到了相同的哈希值）时，Python 使用开放地址法来解决冲突问题。
2. Python 3.6+ 的优化
在 Python 3.6 及其后续版本中，字典的数据结构进行了优化，称为 紧凑字典（Compact Dict）。这种优化的目的是为了节省内存和提高性能。
优化后的字典由两个数组组成：
- 动态数组（动态散列表）：存储键值对的哈希值及索引信息。
- 实体数组：存储实际的键和值。
这种设计将原来的稀疏数组（即包含了很多空槽的数组）优化为更加紧凑的数组结构，这不仅减少了内存使用，还保持了插入顺序。
3. 字典扩展与收缩
字典在容量达到一定阈值时会自动扩展，以减少哈希冲突。扩展过程中，字典的容量通常会翻倍，并重新计算所有键的哈希值并放入新的哈希表中。
相对的，如果大量键值对被删除，字典不会立即收缩，而是会在满足一定条件时触发内存回收机制。
4. 字典查找的过程
字典查找的过程如下：
- 通过哈希函数计算键的哈希值。
- 使用哈希值定位到哈希表中的某个槽位。
- 如果槽位为空，则查找失败。如果槽位不为空，则比较存储在该槽位的键是否与查询的键相等。
- 如果相等，则返回对应的值；否则，继续查找下一个槽位（即处理冲突）。
5. 删除操作
删除键值对时，Python 并不会立即清除槽位，而是将该槽位标记为“已删除”。在后续的查找或插入过程中，如果遇到这种标记的槽位，则跳过该槽位。最终，通过扩展或收缩操作来实际清理已删除的槽位。
6. 性能与空间复杂度
字典的查找、插入和删除操作的平均时间复杂度为 O(1)，但是在最坏情况下（如哈希冲突非常严重时），复杂度可能退化为 O(n)。通过哈希函数的设计和哈希表扩展机制，Python 字典能够在大多数场景下提供非常高效的性能。
字典的空间复杂度取决于存储键值对的数量以及哈希表的大小。紧凑字典的设计使得 Python 3.6 及以后的字典在空间利用率上有了显著提高。
总结
Python 字典的内部实现基于哈希表，通过哈希函数实现快速的键值对存取。Python 3.6 及其之后的版本通过紧凑字典的设计，大大提升了字典的性能与内存效率。理解字典的内部结构，有助于更好地使用和优化 Python 代码，尤其是在处理大规模数据时。
