Re: avl-trees vs. hashes

[Maciej Stachowiak <mstachow@mit.edu>]

kwright@tiac.net writes:
> > From: Per Bothner <bothner@cygnus.com>
> > 
> > > Unless I'm mistaken, avl-trees do insertion and retrieval in O(log n)
> > > time.  Whereas hashes can do both in O(1), constant, time.  But it's
> > >  possible avl-trees are faster at deletion? anyone... anyone? :)
> > 
> > Nope;  deletion is O(1) is a properly-implemented hashtable.
> 
> Sorry, both wrong.  The hash table operations appear to be O(1)
> as long as the number of entries (n) is less than the size
> you initially allocated for the table.

A properly implemented hashtable resizes by a given factor when the
buckets get too full, resulting in amortized O(1) access and deletion.

> (B) Make a bigger table and re-hash.  If you double the size of
>   the table on each re-hash, then to add O(2^k) entries you
>   must touch the first entry O(k) times, again giving O(log n)
>   amortised cost.

Your analysis is incorrect.

We have 2^k total operations, at every power of two, we have to pay
the resize cost. The amortized time complexity A is the total of these
resize costs divided by 2^k.
 
     1        k
A = ---  *  sigma resize_cost(2^k)
    2^k      n=1
 
Assume resize_cost(x)=O(x)
 
     1      k
A = --- * sigma O(2^k)
    2^k    n=1
 
 
     1
A = --- * O(2^(k+1) -2)
    2^k
 
A = O(1)
 
 

> The hash table can help with the constants hidden in the big-O
> notation, but it does not improve asymtotic complexity.  (Not
> that this has much to do with Guile.)

Experience shows that pedantic theory discussions are considered
on-topic on this list. :-)

 - Maciej Stachowiak