Re: avl-trees vs. hashes

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

On Sun, 25 Oct 1998, Jay Glascoe wrote:

> Keeping track of the total number of entries (and using this for re-size
> purposes) would be a BIG win for the deletion procedure, but a small
> loss for insertion.  So, in your opinion, should I make the switch? 
> 
> 	Jay

done!  I made the switch and it was a HERUGE win for deletion.  I then
noticed, hey! I don't need to cons the bucket size onto the front of the
bucket any more.  And thus the change was a win for insertion and
(hence) resize. 

deletion is still slower than insertion, but not by much.  (I still
maintain it's because of gc).

also, my buckets are now true alists (as God intended):

(list (cons hash1 (cons key1 value1)) (cons hash2 (cons key2 value2)))