Proposed implementation for an Ordered Dictionary

[Steve Holden]

bearophileHUGS at lycos.com wrote:
> Paul Rubin:
>> I don't see how to delete a randomly chosen node if you use that trick, since the hash lookup doesn't give you two consecutive nodes in the linked list to xor together.<
> 
> Thank you, I think you are right, I am sorry.
> So on 32-bit CPUs you need to add 8 bytes to each value.
> 
> On 64-bit CPUs you may use a double indexed list, instead of a double
> linked list. And each index can be stored in 6 bytes instead of 8
> (281_474_976_710_656 buckets may be enough for most people), so you
> need only 12 bytes for two indexes instead of 16 bytes, this helps the
> L1 cache (and the small L2 cache too on Core i7) a bit. But this may
> slow down too much the ordered iteration.
> 
A sort of premature pessimization, then.

regards
 Steve
-- 
Steve Holden        +1 571 484 6266   +1 800 494 3119
Holden Web LLC              http://www.holdenweb.com/