Re: hash tables, non-random keys


"Aaron Brady" <castironpi@xxxxxxxxx> wrote in message
news:6c7752cb-9341-4a3a-bfa1-b108b5297ac2@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Hello,

I have a hash table that will be containing a non-uniform distribution
of keys. The keys will be inserted sequentially, not always starting
from 0. Over time, they will be removed about at random, though there
may be a pattern there as well. I expect the lower indices to be
rather sparsely populated after large numbers of insertions, or I
would just use an array.


this does not sound like a good task for hash tables...

(IMO, hashes are not ideal either for numeric keys, or for cases where
deletion is common, as these foul up some major ways to optimize hash
tables).

my suggestion here would be more to support a "sliding" array, where items
are added to the end (and generally kept sorted), and when a key is removed,
the whole rest of the array is slid over. (this way, binary lookups can be
used, ...).

a slight variation here is to simply mark keys as deleted (somehow) and
delay compacting the array until later (there are pros and cons to this).

another possibility is an AVL tree (again, more pros and cons, namely higher
overhead, but also higher scalability, as sliding array elements can
eventually become expensive).


hashes still have an advantage though that if done well, they can have an
average O(1) lookup time, whereas most of the others have an O(log2 n)
time...

something I also sometimes do is to use a small hash to optimize lookups
into an array, where one can first check if the item is in the hash
(typically a single-step pass/fail), and if not, they can fetch it from the
array (usually though, this is done if the lookup would be O(n) or more...).



.

Relevant Pages