Kevin Wampler wrote:
> outweighed it's somewhat higher inefficiency,

Actually, thinking on it, it doesn't need to be noticeably less efficient. 
You can just implement it as a regular hashtable except have a head and tail 
pointer in the top-level structure, and a couple of pointers in each entry. 
Adding a new index also links it to the tail of the linked list, deleting an 
entry takes it out of the linked list and the hashtable, etc. So there 
doesn't seem to be more than a handful of machine instructions on an insert 
or delete to maintain this extra information, and it's certainly not wasting 
a lot of space compared to keeping a hashtable sufficiently below full that 
you avoid too many collisions.

-- 
   Darren New, San Diego CA, USA (PST)
   There's no CD like OCD, there's no CD I knoooow!

Post a reply to this message