Re: avl-trees vs. hashes

[Tel <telford@eng.uts.edu.au>]

>    I thought that was obvious and implicit in the whole discussion.
> 
> Oh come on Per, you know that *nothing* is implicit or obvious
> when there's an opportunity to point out a perceived mistake or
> misconception and play silly games of intellectual one-up-man-ship.  :-)
> Standard Operating Procedure for hackers ...

The issue of matching the size of the hash table to the number of keys
is a bit more subtle that ``obvious and implicit'' would suggest because
basing you calculations on a well chosen hash table size has an underlying
assumption that the user of the hash table is always in a position to know
what such a size would be. Making such an assumption is not ``obviously''
correct in my understanding.

I take back what I said about the resizing hash tables though, I'm convinced
by the calculations (and surprised) that the auto-resize basically triples
the time for an insert but remains O(1).

	- Tel