为什么dict有这么多操作的最坏情况是O（n）？

Question

dict是如何实现的，它有一个线性的时间查找冲突？我假设它被实现为一个由列表支持的哈希表。对于各种操作，我假设更好的实现应该是O（log（n）），而是使用树来支持表。是否有一些魔术在幕后发生，以保持持续时间查找尽可能长的时间？在

顺便说一下，我的来源是：

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

Answer 1

选择一个实现而不是另一个实现的重点不一定是upper-bound，而是预期的amortized performance。虽然不同的算法可以有退化的情况，但通常“在实践中”比使用具有可证明上下界的方法要好。然而，在某些情况下，结构的设计必须防止病态的不良输入。在

另外，有些语言/库（不确定Python）实际上会更改底层实现，例如当项目数超过一个低n时。这会影响摊余性能（在某些情况下），但不一定是big O。在

最后，“这要看情况而定”。在

快乐的编码。在

Answer 2

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

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

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

Answer 3

甚至考虑银河系中最好的散列函数。仍然有可能有一天你会看到一个值列表，这些值的最佳哈希函数值恰好都是相同的。如果你把它们放在dict中，系统别无选择，只能执行线性搜索。在

使用平衡树可以将最坏情况下的时间保持在O（logn），但维护成本相当高。通常，哈希表的性能相当好。在