在 Python 中迭代字典的复杂性

Question

这是一个相当简单的问题，我无法找到答案。如果我有一本字典，迭代它的复杂性是什么？换句话说，字典遍历的时间复杂度是for key in my_dict: print(key)多少？我幼稚的理解是，由于 Python 中的字典是哈希图，我们需要遍历字典的所有可能的哈希值。这看起来有点矫枉过正，但也许没问题，因为随着我们添加元素，字典会逐渐变大，所以我们通过始终拥有一个几乎满载到恒定负载因子的字典来分摊成本？

Answer 1

在大多数情况下，遍历字典总共需要 O(n) 时间，或者每个元素平均需要 O(1) 时间，其中 n 是字典中的项目数。

Python 的字典数据结构有多种不同版本，具体取决于您使用的 Python 版本，但它们都是某种hashtable。哈希表要么具有键/值对数组，要么具有键数组和并行值数组。通常，数组的固定比例（称为负载因子）将包含字典项，其余空格保持为空，因此您需要迭代的数组长度是一个固定常数乘以字典项的数量. 这意味着您可以在 O(n) 时间内进行迭代。

在最新版本的 Python中，字典数据结构的数组只是保存另一个数组中每个项目的索引，其中另一个数组中的项目按插入顺序保存。这个额外的数组可用于按插入顺序迭代字典，仍然在 O(n) 时间内，但不必跳过查找数组中未使用的空格。

请注意，无论哪种方式，我们实际上都不需要计算任何键的哈希值来迭代字典的项目。

---

综上所述，在某些情况下，迭代字典可能需要超过 O(n) 时间。这样做的原因是，虽然哈希表的容量在需要插入更多项目时会扩大，但在删除项目时它不会缩小。（感谢@HeapOverflow 在评论中指出这一点。）

如果删除了很多项，那么字典项占数组容量的比例可能远小于负载因子。在这种情况下，数组可以大于固定常数乘以项目数，因此迭代需要超过 O(n) 时间。

对于最近版本中使用的数据结构也是如此，它使用附加数组而不是查找数组进行迭代。当项目被删除时，它们被简单地替换为NULL( CPython source ); 大概这样做是为了允许在 O(1) 时间内删除，同时保持插入顺序。因此，如果删除了许多项目，附加数组也可能比 O(n) 长。

在大多数应用程序中，从字典中删除大量项目并不常见。如果您需要这样做并且担心有效地迭代这些字典，请考虑仅使用您需要保留的键来构建新字典，而不是从现有字典中删除它们。