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) 删除常量之后）。*：评论似乎已经过时了，我认为使用当前常量会更完整