面试题：Python字典内存管理 - 扩容与性能

Question

当Python字典的负载因子达到一定阈值时会进行扩容，描述这个过程中内存的重新分配和键值对的重排机制，并且说明这对字典操作性能有何影响。

Answer 1

内存重新分配

1. 确定新容量：当负载因子（键值对数量除以字典当前容量）达到阈值（通常为0.65）时，Python字典会进行扩容。新容量一般是原容量的两倍（如果原容量为2的幂次方，实际新容量是大于原容量两倍的最小2的幂次方）。
2. 申请新内存：在内存中申请一块大小为新容量的内存空间，用于存储新的字典数据。

键值对重排机制

1. 重新计算哈希值：对原字典中的每个键值对，重新计算其键的哈希值。哈希值决定了键值对在新字典中的存储位置。
2. 分配新位置：根据新计算的哈希值，按照字典内部的哈希冲突解决算法（通常是开放寻址法中的二次探测法），将键值对插入到新的内存空间中的相应位置。这可能导致键值对在新字典中的存储顺序与原字典不同。

对字典操作性能的影响

1. 插入操作：扩容前，如果字典接近或达到负载因子阈值，插入操作的性能会因为频繁的哈希冲突而降低。扩容后，新的更大的内存空间减少了哈希冲突的概率，插入操作的平均时间复杂度接近理想的O(1)，性能得到提升。
2. 查找操作：同理，扩容前查找操作可能因哈希冲突需要更多的探测次数，性能下降。扩容后，哈希冲突减少，查找操作的平均时间复杂度接近O(1)，性能提升。
3. 删除操作：删除操作在扩容前后的性能变化趋势与插入和查找类似。扩容后，由于哈希冲突减少，删除操作的平均时间复杂度也接近O(1)，性能得到改善。但扩容过程本身是一个相对耗时的操作，会在扩容瞬间影响字典的操作性能。