Balanced trees

Dan Stromberg drsalists at
Sun Mar 9 23:08:20 CET 2014

On Sun, Mar 9, 2014 at 2:43 PM, Marko Rauhamaa <marko at> wrote:
> Dan Stromberg <drsalists at>:
>> On Sun, Mar 9, 2014 at 2:32 PM, Marko Rauhamaa <marko at> wrote:
>>> There is no O(1) hash table.
> Please elaborate.

A hash table of fixed size is O(1) until you fill it so full that you
start getting enough collisions to make it O(n), as one bucket becomes
a linked list.  This is because the hash function is O(1), and looking
up a value in a C array is O(1).

A more flexible hash table will not have a fixed size; instead it will
grow itself as needed.  This growth operation tends to be O(n), but
happens vanishingly infrequently as the table grows, so it's still
amortized O(1).

More information about the Python-list mailing list