Proposed implementation for an Ordered Dictionary

[bearophileHUGS at lycos.com]

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.

Bye,
bearophile