为什么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 个回答
-
除接触所有元素的操作（例如迭代和复制）（在这种情况下，显然是O（n））之外，大多数操作的Dict为O（1）。
请参阅：http：
//wiki.python.org/moin/TimeComplexity它具有O（n）最坏的情况，因为您总是可以构造一个病理示例，其中所有键都具有相同的哈希值。
