Balanced trees

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


On Sun, Mar 9, 2014 at 2:43 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
> Dan Stromberg <drsalists at gmail.com>:
>
>> On Sun, Mar 9, 2014 at 2:32 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
>>> There is no O(1) hash table.
>>
>> http://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o1
>
> 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