为什么 'key in d.keys()' 是 O(n) 而 'key in d' 是 O(1)？

Question

我有一个后续问题，关于这个问题。在原问题的评论中，有人提到他见过一些人错误地使用了这样的语法：

key in d.keys()

这种写法的运行时间是O(n)，而不是

key in d

这种写法的运行时间是O(1)。他们没有意识到这两者之间的区别。直到今天（我在试图理解为什么我的代码运行得这么慢时偶然发现了这个原问题），我也是其中之一。我尝试用Python 2.7.5来验证这个评论的准确性，结果果然，以下是timeit的结果：

$ python -m timeit -s 'd=dict.fromkeys(range(100))' '1000 in d.keys()'
100000 loops, best of 3: 2.18 usec per loop
$ python -m timeit -s 'd=dict.fromkeys(range(100))' '1000 in d'
10000000 loops, best of 3: 0.0449 usec per loop
$ python -m timeit -s 'd=dict.fromkeys(range(1000))' '10000 in d.keys()'
100000 loops, best of 3: 17.9 usec per loop
$ python -m timeit -s 'd=dict.fromkeys(range(1000))' '10000 in d'
10000000 loops, best of 3: 0.0453 usec per loop    

对于一个有100个键的字典，速度差大约是50倍（2.19微秒 / 0.0449微秒），而对于一个有1000个键的字典，速度差则是400倍（17.9微秒 / 0.0453微秒），这些搜索都是特意构造的，使得搜索的键在字典中找不到。换句话说，就是O(n)和O(1)的区别，正如评论者所说。

我的问题是：为什么会有这样的区别？这两种语法看起来几乎一模一样！显然，Python在这两种情况下的内部处理是非常不同的，但到底发生了什么，才导致了这种区别呢？

Answer 1

字典使用一个叫做key的东西的哈希值来查找键。如果这个索引存在，你只需要比较一次，这个过程的复杂度是O(1)，也就是很快。

但是如果你使用d.keys()，首先你会得到所有键的一个列表副本，然后你需要把这个列表里的每个元素都和你的key进行比较，所以这个过程的复杂度是O(n)，也就是比较慢。

Answer 2

d.keys() 会返回一个字典键的列表，这个列表是键的副本，而不是一个视图。生成这个列表需要 O(n) 的时间，查找的时候也一样，因为它使用了 list.__contains__，也就是要遍历所有的键。

另一方面，key in d 实际上是调用了

d.__contains__(key)

这个 dict.__contains__ 方法是通过 O(1) 的哈希查找来高效实现的，专门用于字典的键。这正是字典这种数据结构存在的原因，也是你在用 d[key] 访问字典时能快速查找的原因。

总的来说，在 Python 2 中，key in d.keys() 是不合适的用法。

_{注意：在 Python 3 中，这种情况有所改变，使用 key in d.keys() 和 key in d.viewkeys() 基本上是等价的，后者是 Python 2 的用法。}