Re: avl-trees vs. hashes

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

> Note the example does not show the re-hashing nor does it handle
> deletions.  (If you delete en entry, you have to leave a mark,
> so the code can distinguish between an empty slot, and a deleted
> one.  Deleted slots can be re-used, but they don't stop the search
> for a match.)

Leaving a mark has the problem that a lot of insertions and deletions
which don't substantially change the number of keys (i.e. which don't
force a rehash) cause all the empty slots to change over to marks.
Then when you search for a key which is not present there is a long
search required to prove that the key really isn't there.
I guess you can just force a rehash now and then to clean it all up
or you can not use marks and instead get deletions to scan ahead, dropping
the last value with the current hash back into the empty slot (messy I
know but usually the scan is quite short).

Anyhow, point is that delete code is always kinda complicated with this
method. Generally the non-linked hash table is more memory efficient
but slower (considering garbage collection overhead, maybe faster).

	- Tel