Re: avl-trees vs. hashes

[Maciej Stachowiak <mstachow@mit.edu>]

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

If you grow by a factor of K>1 only whenever the hashtable has more
than E/F (where E is the maximum number of elements and F >= 1)
elements, and shrink by a factor of M>1 whenever the hashtable has
fewer than E/G elemenets where G>F, I believe you will get amortized
constant time (assuming your hash function distributes well enough
that collisions are not a significant factor). F and G should
obviously be picked such that the difference between thresholds is
considerably less than one element for common sizes, or you will get
crappy performance anyway for the sizes you care about, regardless of
the asymptotic complexity.

If you rehash based on the max bucket size it becomes more
questionable and depends even more strongly on how good your hash
function is. 

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