Balanced trees

[Ian Kelly]

On Sun, Mar 9, 2014 at 4:08 PM, Dan Stromberg <drsalists at gmail.com> wrote:
> 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).

A hash table can also only ever be O(1) in the average case.  Worst
case, everything you put into the hash table has the same hash value,
and so the time to fetch an item is entirely dependent on the
collision resolution scheme -- e.g. O(n) if a linked list or linear
probe is used, or perhaps O(log n) if each bucket is a balanced binary
tree.

There are schemes such as cuckoo hashing that allow true O(1) worst
case access, but they have other drawbacks -- inserts with cuckoo
hashing are amortized O(1), and it is even possible for an insert to
fail entirely after spending exponential time trying to find a way to
arrange things.