在Python中迭代字典的复杂性

Question

这是一个相当简单的问题，我还没有找到答案。 如果我有一本字典，迭代它的复杂性是什么

换句话说，字典遍历（如for key in my_dict: print(key)）的时间复杂度是多少

我天真的理解是，由于Python中的字典是哈希映射，我们需要迭代字典中所有可能的哈希值

这似乎有点过分了，但也许没关系，因为随着我们添加元素，字典会越来越大，所以我们总是拥有一个几乎装满了恒定负载系数的字典来分摊成本

Answer 1

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

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

In recent versions of Python，字典数据结构的数组只保存另一个数组中每个项的索引，其中另一个数组中的项按插入顺序保存。这个额外的数组可以用于按插入顺序在字典上迭代，仍然是O（n）时间，但不必跳过查找数组中未使用的空格

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

---

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

如果删除了许多项，那么字典项占阵列容量的比例可能比负载系数小得多。在这种情况下，数组可以大于固定常量乘以项数，因此迭代需要的时间超过O（n）

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

在大多数应用程序中，从字典中删除很多项并不常见；如果您需要这样做，并关心如何高效地迭代这些词典，请考虑使用只需要保留的键来构造新字典，而不是将它们从现有字典中删除。p>