为什么dict在这么多操作中都具有最差情况O(n)?

发布于 2021-01-29 17:25:01

dict如何实现线性的线性时间查找冲突?我假设它被实现为由列表支持的哈希表。我以为更好的实现是对各种操作使用O(log(n)),而是使用树来支持表。幕后是否发生了一些不可思议的事情,以保持恒定时间的查找尽可能长的生命?

顺便说一下,我的来源是:

http://www.google.com/search?sourceid=chrome&ie=UTF-8&q=python+complexity

关注者
0
被浏览
48
1 个回答
  • 面试哥
    面试哥 2021-01-29
    为面试而生,有面试问题,就找面试哥。

    除接触所有元素的操作(例如迭代和复制)(在这种情况下,显然是O(n))之外,大多数操作的Dict为O(1)。

    请参阅:http
    //wiki.python.org/moin/TimeComplexity

    它具有O(n)最坏的情况,因为您总是可以构造一个病理示例,其中所有键都具有相同的哈希值。



知识点
面圈网VIP题库

面圈网VIP题库全新上线,海量真题题库资源。 90大类考试,超10万份考试真题开放下载啦

去下载看看