Jse*_*mol 1 python dictionary time-complexity
这是一个相当简单的问题，我一直无法找到答案。如果我有一本字典，迭代它的复杂性是多少？
换句话说，诸如 之类的字典遍历的时间复杂度是多少for key in my_dict: print(key)？
我天真的理解是，由于 Python 中的字典是哈希图，因此我们需要迭代字典的所有可能的哈希值。
这看起来有点矫枉过正，但也许没问题，因为随着我们添加元素，字典会逐渐变大，所以我们通过始终拥有一个几乎满到恒定负载因子的字典来摊销成本？
在大多数情况下，迭代字典总共需要 O(n) 时间，或者每个元素平均需要 O(1) 时间，其中 n 是字典中的项目数。
Python 的字典数据结构有各种不同的版本，具体取决于您使用的 Python 版本，但它们都是某种哈希表。哈希表要么具有键/值对数组，要么具有键数组和并行值数组。通常，数组的固定比例（称为加载因子）将包含字典项，其余空间保留为空，因此需要迭代的数组的长度是固定常数乘以字典项的数量。这意味着您可以在 O(n) 时间内迭代。
在最新版本的 Python 中，字典数据结构的数组仅保存另一个数组中每个项目的索引，其中另一个数组中的项目按插入顺序保存。这个附加数组可用于按插入顺序迭代字典，仍然需要 O(n) 时间，但不必跳过查找数组中未使用的空格。
请注意，无论哪种方式，我们实际上都不需要计算任何键的哈希值来迭代字典的项目。
综上所述，在某些情况下，迭代字典可能需要超过 O(n) 的时间。这样做的原因是，尽管当需要插入更多项时哈希表的容量会扩大，但当删除项时它不会缩小。（感谢@HeapOverflow 在评论中指出了这一点。）
如果删除了许多项目，则字典项目占数组容量的比例可能远小于负载因子。在这种情况下，数组可能大于固定常数乘以项目数，因此迭代需要的时间超过 O(n) 。
对于更新版本中使用的数据结构来说也是如此，它使用附加数组而不是查找数组进行迭代。当项目被删除时，它们只需替换为NULL（CPython 源代码）；据推测，这样做是为了允许在 O(1) 时间内删除，同时保持插入顺序。因此，如果删除许多项，附加数组也可能比 O(n) 长。
在大多数应用程序中，从字典中删除大量项目并不常见。如果您需要执行此操作并且担心有效地迭代这些字典，请考虑仅使用您需要保留的键构建新字典，而不是从现有字典中删除它们。