Re: avl-trees vs. hashes

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

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?

> Why should it be slow?  You cdr down the list & when you find the item
> to delete you set-cdr! the item in front to cdr of it.  If it's the
> 1st item in the list you have to stick it back into the vector.
> 

yes, you're right.  I'm a moron ;)  I fixed it up and deletion is now
O(1) and (in practice) nearly as fast as insertion.

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

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

	Jay
	jglascoe@jay.giss.nasa.gov