在 Python 中使用字典时，this page表示遍历字典元素的时间复杂度为 O(n)，其中 n 是字典的最大大小。
但是，我认为没有明显的方法可以遍历哈希表的元素。在遍历哈希表的元素时，我可以假设 dict.iteritems() 的性能良好，而不会产生太多开销吗？
由于字典在 Python 中被大量使用，我认为这是以某种巧妙的方式实现的。不过，我需要确定一下。
最佳答案
如果您查看 notes on Python's dictionary source code ，我认为相关的要点如下:
Those methods (iteration and key listing) loop over every potential entry
将有多少个潜在条目，作为最大大小(该字典中存储过的最大键数)的函数？查看同一文档中的以下两个部分:
Maximum dictionary load in PyDict_SetItem. Currently set to 2/3
Growth rate upon hitting maximum load. Currently set to *2.
这表明字典的稀疏度将在 1/3~2/3 左右(除非增长率设置为 *4，否则为 1/6~2/3)。所以基本上您将为每个键检查最多 3 个(如果 *4 则为 6 个)潜在条目。
当然，无论是 3 个条目还是 1000 个条目，它仍然是 O(n)，但 3 似乎是一个相当可接受的常数。
顺便说一句，这里是源代码和文档的其余部分，包括 DictObject 的源代码和文档:
关于Python字典迭代器性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31214308/