为什么'键入d.keys()'在O(n)时完成,而'key in d'在O(1)中完成？

我对这个问题有一个后续问题.原始问题的一位评论者提到他过去曾经误认为人们使用如下语法:

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 usec/0.0449 usec),对于具有1000个密钥的字典,存在400X差异(17.9 usec/0.0453 usec),对于明确构造的搜索,搜索键太大,无法在字典中找到.换句话说,O(n)与O(1),正如评论者所说.

我的问题:为什么会有所不同？这两种语法看起来几乎相同!显然,Python必须在这两种情况之间做一些非常不同的事情,但究竟在内部究竟发生了什么呢？