python dict has_key()方法的时间复杂度是多少 [英] What is the time complexity of python dict has_key() method

问题描述

python dict has_key()方法的时间复杂度是多少 是 O(1)还是dict中的键.

What is the time complexity of python dict has_key() method is it O(1) as in case of key in dict.

推荐答案

简短答案: 最坏的情况是 O(n) .但是平均情况时间复杂度是 O(1) .但是，最坏的情况非常 .

Short answer: worst case it is O(n). But the average case time complexity is O(1). The worst case is however very rare.

进行查找时，首先对键进行双哈希处理(一次按键的类型，一次按字典的键).根据该结果，我们知道必须在哪个存储桶中搜索，然后开始搜索.

When you do a lookup, the key is first double hashed (once by the type of the key and once by the dictionary). Based on that result, we know in which bucket we have to search, and we start searching.

但是有可能发生哈希冲突:在这种情况下，多个键位于同一存储桶中，因此我们必须在多个键中进行搜索.最坏的情况是所有键都在相同存储桶中，因此我们退回到线性搜索.

It is however possible that hash collissions occur: in that case multiple keys are in the same bucket, so we have to search among multiple keys. Worst case all the keys are in the same bucket, and thus we fallback on linear search.

(大量键)哈希冲突非常很少.通常可以安全地假设-与字典的大小无关-同一存储桶中的键数将是固定的.

Hash collisions (with a large amount of keys) are however very rare. Usually it is safe to assume that - regardless of the size of the dictionary - the number of keys in the same bucket will be fixed.

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

The fact that it is O(n) had some interesting consequences on security. Say you have a server that stores and retrieves data in a dictionary. Then of course the response time will scale with such a lookup. Now a hacker can design input in such a way that all keys are placed in the same bucket(s). As a result lookup will slow down, and eventually the server will not respond in a reasonable time anymore. That's why Python has a flag -R for hash randomization. This will change the hash function for every run and therefore make it harder for a hacker to design such input.

这篇关于python dict has_key()方法的时间复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！