python - 为什么 dict 有这么多操作的最坏情况 O(n)？

Question

dict 究竟是如何实现的，它具有线性时间查找冲突？我假设它是作为一个列表支持的哈希表实现的。我认为更好的实现是 O(log(n)) 用于各种操作，而是使用树来支持表。幕后是否发生了一些神奇的事情来尽可能长时间地保持不断的时间查找？

顺便说一下，我的来源是这样的:

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

Answer 1

对于大多数操作，Dict 是 O(1)，除了涉及所有元素的操作，例如迭代和复制(在这种情况下，它显然是 O(n))。

参见:http://wiki.python.org/moin/TimeComplexity

它有 O(n) 最坏的情况，因为你总是可以设计一个病态的例子，其中所有键都具有相同的哈希值。