在 Python 中使用字典时，这一页表示迭代字典元素的时间复杂度是O(n), where n是字典的最大尺寸。
但是，我认为没有一种明显的方法可以迭代哈希表的元素。我可以假设性能良好吗dict.iteritems()当迭代哈希表的元素时，没有太多开销？
由于 Python 中大量使用字典，我认为这是以某种聪明的方式实现的。不过，我还是需要确认一下。
如果你看一下Python字典源码注释，我认为相关要点如下：
这些方法（迭代和关键列表）循环每个潜在的条目
作为最大大小（该字典中存储的最大键数）的函数，将有多少个潜在条目？查看同一文档中的以下两个部分：
PyDict_SetItem 中的最大字典负载。目前设置为 2/3
达到最大负载时的增长率。当前设置为*2。
这表明字典的稀疏度将在 1/3~2/3 左右（除非增长率设置为 *4，则为 1/6~2/3）。因此基本上您将检查每个键的最多 3 个（或 6 个，如果 *4）潜在条目。
当然，无论是 3 个条目还是 1000 个条目，它仍然是 O(n)，但 3 似乎是一个相当可接受的常数因子。
顺便说一句，这里是其余的源代码和文档，包括 DictObject 的源代码和文档：
http://svn.python.org/projects/python/trunk/Objects/
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
