This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: avl-trees vs. hashes


> 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.  But then, most anything
not willfully stupid is O(1) if you put a fixed bound on n.

As soon as n exceeds the size of the table you have two choices
(A) use some kind of balanced tree for the buckets resulting
  in O(log n) behaviour.  (Or worse if you use a linear search.)
(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.

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.)

-- 
     --Keith

This mail message sent by GNU emacs and Linux.
Food, Shelter, Source code.