python - 在 Python 3 中调用 dict.keys() 的复杂度是多少？

Question

python 中 dict.keys() 的渐近复杂度是多少？

我找到了 this website但它没有答案。我使用的是 Python 3，但我想这不是特定于版本的。

Answer 1

在 Python 3 中，dict.keys() 返回 view object .本质上，这只是一个直接指向字典键的窗口。例如，没有遍历哈希表来构建新对象。这使得将其称为常数时间，即 O(1) 操作。

字典的 View 对象从 here 开始实现;创建新 View 对象使用 dictview_new .这个函数所做的就是创建指向字典的新对象并增加引用计数(用于垃圾跟踪)。

在 Python 2 中，dict.keys() 返回一个列表对象。要创建这个新列表，Python 必须遍历哈希表，将字典的键放入列表中。这是作为函数 dict_keys 实现的。 .这里的时间复杂度与字典的大小成线性关系，即 O(n)，因为必须访问表中的每个槽。

注意Python 2 中的 dict.viewkeys() 与 Python 3 中的 dict.keys() 功能相同。