Re: avl-trees vs. hashes

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

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

 > People earlier said that hash tables are faster with insertion and
 > deletion but this is only true if you have chosen the size of the table
 > to suit the number of keys, if you choose the size badly then hash table
 > performance drops off. If you use auto-resize on hash tables then your
 > insertion is no longer O(1) but it tends towards O(log N). This probably
 > doesn't matter in most cases because insertion speed is not as important
 > as the speed of a read-only lookup since most applications do a lot more
 > reads than inserts or deletes.

Nope.  Resizing hashtables are still O(1) for insertions.  See the
previous discussions & 3 independently posted analyses.  God, I wish
this list had a shorter turn-around time.

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