Re: avl-trees vs. hashes

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

Tel <telford@eng.uts.edu.au> writes:

 > > 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.
 > 
 > It should all be optional but still, if you don't know the number of keys
 > that you expect to handle then you will be better off with the auto-resize.

The issue was not auto-resize so much as whether or not to shrink the
table.

Also, I just realized that shrinking the table can cause substantially
worse than O(1) behavior.  It can be O(n) if done improperly - if you
add an element causing the hash table to double in size & then you
delete said item & the code decides because of the deletion to shrink
the hash table again.  Then you'll get O(n).  In general, it's
important to only do these resizing operations every power of 2
insertions to preserve the O(1) insertion/deletion speed.

Also, I just realized that all the complexity arguments about resizing
were wrong.  One doesn't resize the hash table every power of 2
insertions.  One resizes when the max bucket size reaches some fixed
constant.  In the worst case, all insertions will be into the same
bucket, in which case there'll be a resize every max-bucket-size
insertions, making insertions O(n) in the worst case.  O(1) insertions
are actually the best case behavior, and probably average case
behavior also, given reasonable distribution assumptions on the
hashing function.

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