Python 的内置字典如何跟踪已插入的键？

Question

我理解哈希表：原则上，您将键的数据存储在一个固定大小的数组中，并使用键的哈希给出要使用的索引/槽。但是，Python 的 dict 类具有返回 dict 键列表的方法。这份名单从何而来？（此外，迭代字典隐式迭代其键）。dict.keys()我试图自己思考这个问题，并确定了以下要求：插入 O(1)O(1) 中的删除O(n) 中的迭代我想也许我们可以为每个插槽存储下一个和上一个非空插槽的索引，这样我们就可以跳到 O(1) 中的 next/prev 元素并清除 O(1) 中的一个插槽（只需更新 prev 的下一个索引和下一个的上一个索引）。问题是插入将在 O(log n) 那里，因为我们必须对“下一个”索引进行二分搜索。我考虑的另一种解释是，也许我们只是遍历所有插槽，而忽略空插槽并接受每次迭代键时重复检查空插槽的运行时惩罚。这样做的一个缺点是哈希表需要非常满才能有效，这会减慢插入速度。相关的问题“Python 的内置字典如何实现”从未提及字典的这一方面。

Answer 1

我在这里查看了 CPython 源代码，虽然我仍然不是 100% 确定我认为我的第二个猜测是正确的：我们只是遍历所有插槽。我们忽略空槽并返回非空槽中的所有键。

Python 字典在满2/3 时调整大小并且（假设没有删除）大小加倍，之后它们将是 2/6 = 1/3 满*，这意味着我们可以在 O(3n) 中进行迭代（这是 O( n) 删除常量之后）。

*：评论似乎已经过时了，我认为使用当前常量会更完整