Re: avl-trees vs. hashes

[hjstein@bfr.co.il (Harvey J. Stein)]

Jay Glascoe <jglascoe@jay.giss.nasa.gov> writes:

 > On 20 Oct 1998, Harvey J. Stein wrote:
 > 
 > > What the tree based stuff does that hash tables don't do is ordering.
 > > You need a less-than operator as well as an equal operator & then you
 > > can also do the following operations in O(log n):
 > > 
 > >    Get the smallest item.
 > >    Get the largest item.
 > >    Get the next item.
 > >    Get the previous item.
 > > 
 > 
 > I've never used trees in everyday programming.  Could you give me an
 > example of how the above procedures might be useful to me?

Databases - maintaining ordered lists.

 > > And although it'd be nice to have the functionality of
 > > shrinking/reforming the hashtable, I don't expect it to get much use.
 > > In particular, I wouldn't automatically call it in the delete
 > > function.
 > 
 > I call it when the largest bucket size is less than one quarter the
 > maximum bucket size.  The vector size is then halved.  This seems
 > to work well.

Well, except that someone who's doing something like putting lots of
things, then deleting a lot of them, then putting new things in,
etc. will get a lot of overhead from the continual growing & shrinking
of the hash table.  You might want to make the shrinking part
optional.

 > > Also, why isn't shrinking the hashtable identical to growing it?
 > 
 > Garbage collection.
 > 
 > > I'd think you'd just have a fcn like move-hashtable-data which takes a
 > > hashtable & a vector & moves the data from the hashtable to the vector. 
 > > Then this would handle both growing & shrinking by just passing it
 > > vectors of different sizes. 
 > > 
 > 
 > yes, that's essentialy what I do.  I actually create a whole new hashtable
 > with the correct vector size, and then insert all entries from the old
 > hashtable into the new one.  (For some reason, Guile tries to gc bits of
 > my old hashtable if I simply hold on to the old vector, and then give the
 > hashtable a new vector.)  I then set-c[ad]r! on the old hashtable to give
 > it the c[ad]r of the new table.

I keep forgetting the code's in C.  What'd be interesting would be to
see if the scheme version compiled by hobbit is as fast as your C
version.  Probably some business of appropriately flagging it as in
use is needed.

I'm still not sure exactly what you mean about shrinking & growing
being different, but I'm sure it'll become clear when I see the code.

When you say "insert", I assume that's using the stored hash values
as opposed to using a hashtable-put! function...

-- 
Harvey J. Stein
BFM Financial Research
hjstein@bfr.co.il