python - Why does dict have worst case O(n) for so many operations?

Question

How exactly is dict implemented that it has a linear time lookup for collisions? I would assume that it is implemented as a hashtable backed by a list. I would presume that a better implementation would be O(log(n)) for various operations, using a tree to back the table instead. Is there some magic happening behind the scenes to keep the constant time lookups alive for as long as possible?

My source for this, by the way, is this:

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

Answer 1

Dict is O(1) for most operations, except for operations that touch all elements, such as iteration and copy (in which case, it's obviously O(n)).

See: http://wiki.python.org/moin/TimeComplexity

It has O(n) worst case, because you can always contrive a pathological example where all the keys have the same hash value.