Re: avl-trees vs. hashes

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

On Mon, 26 Oct 1998, Maciej Stachowiak wrote:

> 
> hjstein@bfr.co.il writes:
> > Per Bothner <bothner@cygnus.com> writes:
> > 
> >  > Yes.  All of these points are inherent in the whole concept of
> >  > hashing.  Re-sizing has nothing to do with it, as long as the
> >  > expected bucket size is O(1), which it *has* to be, for hashing
> >  > to "work".
> > 
> > Not exactly true.  If you resize too frequently then you'll end up
> > with worse than O(1).
> > 

yes, this is true.  But, I just want to say a few things about resizing
hash tables.  Resizing a hash table of, say 1000 entries, is significantly
faster than inserting 1000 entries into a new hash table (with an
appropriately large vector) for 2 reasons: 

1. No need to rehash each entry's key, that info is stored in the entry

2. Each key from the old hash table is unique.  When inserting an entry
from the old hash table into the new one, we simply cons the whole entry
onto the front of the new bucket.  We needn't look at the entry's key,
much less the keys of the other entries in the new bucket. 

In short, although resizing is an O(n) procedure, it is very, very fast.
Also, resize just isn't called that often: the bigger the table the less
often it's called.

> Another thing I just thought of: Guile's weak hash tables are
> extremely useful (at least to me), is it remotely plausible that they
> could be implemented in this resizing version?
> 
>  - Maciej
> 

I looked at weaks.[ch] in libguile but I still haven't a clue what weak
hash tables are.