面试题：Python中字典的内存管理 - 基本原理

Question

请简述Python字典在内存中是如何存储键值对的，以及在添加、删除键值对时内存管理的基本机制。

Answer 1

Python字典在内存中的存储

1. 散列表结构：Python字典使用散列表（哈希表）来存储键值对。散列表是一种基于哈希函数的数据结构。对于字典中的每个键，会通过一个哈希函数计算出一个哈希值，这个哈希值会被用来确定键值对在散列表中的存储位置。
2. 桶（bucket）：散列表由一系列的桶组成。当计算出键的哈希值后，哈希值会被映射到某个桶中。如果多个键的哈希值映射到同一个桶，就会发生哈希冲突。Python字典采用开放寻址法（通常是线性探测法）来解决哈希冲突。即当发生冲突时，会按照一定顺序在散列表中寻找下一个可用的位置来存储键值对。

添加键值对时的内存管理机制

1. 哈希计算：首先计算键的哈希值，确定其在散列表中的初始存储桶位置。
2. 处理冲突：如果该位置已经被占用（哈希冲突），则使用开放寻址法寻找下一个可用位置。
3. 内存动态扩展：当字典中的键值对数量达到散列表容量的一定比例（通常是2/3）时，会触发字典的扩容机制。扩容时，会创建一个更大的散列表，然后将原字典中的所有键值对重新计算哈希值并插入到新的散列表中。这一过程会导致内存的重新分配和数据的重新排列。

删除键值对时的内存管理机制

1. 标记删除：当删除一个键值对时，Python字典通常不会立即释放该键值对所占用的内存空间，而是采用标记删除的方式。即只是在相应的桶位置标记该键值对已删除，这样可以避免频繁的内存释放和重新分配操作，提高效率。
2. 内存回收：在后续的操作中，如果字典的负载因子（已占用桶的数量与总桶数的比例）变得足够低，或者在某些特定情况下（例如垃圾回收机制触发），字典可能会进行内存的收缩操作，释放那些被标记删除的键值对所占用的空间，并重新调整散列表的大小。