Python字典的
has_key()
方法时间复杂度是多少?它是否和字典中的键一样是O(1)?has_key()
方法时间复杂度是多少?它是否和字典中的键一样是O(1)?简短回答:在最坏情况下,时间复杂度为O(n)。但平均情况的时间复杂度为O(1)。但是最坏情况非常少见。
进行查找时,首先对键进行了双重哈希(一次是由键类型哈希,一次是由字典哈希)。基于这个结果,我们知道要搜索哪个桶,并开始搜索。
然而,可能会出现哈希冲突:在这种情况下,多个键位于同一桶中,因此我们必须在多个键中进行搜索。最坏情况下,所有键都在同一个桶中,因此我们采用线性搜索。
然而,哈希冲突(具有大量键)非常罕见。通常可以认为-无论字典的大小如何-在同一个桶中的键数将保持不变。
它是O(n)的事实对安全性产生了一些有趣的影响。假设您有一个服务器,在其中存储和检索数据字典。然后,当然,响应时间将随这样的查找而扩展。现在,黑客可以以这样的方式设计输入,使所有键都放置在相同的桶中。结果查找将变慢,最终服务器将无法在合理时间内响应。这就是Python具有哈希随机化-R
标志的原因。这将为每次运行更改哈希函数,因此使黑客更难设计此类输入。
dict
的内部机制。虽然有点过时,但基本思路仍然相同。 - juanpa.arrivillagad[key]
时,才会返回与键相关联的值,因为桶包含具有键和值的元组。 - Willem Van Onsem
O(1)
,但我只是会使用key in my_dict
。 - jonrsharpeman python
的-R
标志下已经有了。 - Willem Van Onsem