Python字典的has_key()方法的时间复杂度是什么？

Question

Python字典的has_key()方法时间复杂度是多少？它是否和字典中的键一样是O(1)？

- PMat

---

是的，虽然时间复杂度为 O(1)，但我只是会使用 key in my_dict。 - jonrsharpe

最坏情况下时间复杂度为*O(n)。实际上已经有黑客通过精心构造的输入来关闭服务器。但这只发生在非常罕见的情况下。平均情况下时间复杂度为O(1)*。 - Willem Van Onsem

has_key()在Python 3.x中已被移除。big-o为O(1)。 - Mr_U4913

@timchap：在这里，https://wiki.python.org/moin/TimeComplexity - Willem Van Onsem

@timchap：在man python的-R标志下已经有了。 - Willem Van Onsem

Answer 1

简短回答：在最坏情况下，时间复杂度为O(n)。但平均情况的时间复杂度为O(1)。但是最坏情况非常少见。

进行查找时，首先对键进行了双重哈希（一次是由键类型哈希，一次是由字典哈希）。基于这个结果，我们知道要搜索哪个桶，并开始搜索。

然而，可能会出现哈希冲突：在这种情况下，多个键位于同一桶中，因此我们必须在多个键中进行搜索。最坏情况下，所有键都在同一个桶中，因此我们采用线性搜索。

然而，哈希冲突（具有大量键）非常罕见。通常可以认为-无论字典的大小如何-在同一个桶中的键数将保持不变。

它是O(n)的事实对安全性产生了一些有趣的影响。假设您有一个服务器，在其中存储和检索数据字典。然后，当然，响应时间将随这样的查找而扩展。现在，黑客可以以这样的方式设计输入，使所有键都放置在相同的桶中。结果查找将变慢，最终服务器将无法在合理时间内响应。这就是Python具有哈希随机化-R标志的原因。这将为每次运行更改哈希函数，因此使黑客更难设计此类输入。

- Willem Van Onsem

---

那么，has_key，key in dict 和 dict[key] 的内部实现或运行时复杂度是相同的吗？ - PMat

@PMat 是的，没错。先哈希，然后检查桶。看看这个视频，它介绍了Python dict的内部机制。虽然有点过时，但基本思路仍然相同。 - juanpa.arrivillaga

@PMat：确实。只有执行d[key]时，才会返回与键相关联的值，因为桶包含具有键和值的元组。 - Willem Van Onsem