Python dictionary inspired hash table implementation

[Moritz Warning]

I like to share a hash table implementation inspired by Pythons Dictionary.

It's a so called closed hashing table, that is, keys and elements are stored in the table.
Pointers are avoided when possible.
The table size is 2**n and the used load factor is 0.75.

It works for most key types (also static arrays).
All kind of values types should be supported.

For comparison, I did a simple/stupid benchmark,
adding 10.000.000 uint pairs and looking them up
in consecutive order (see attached file).

The build-in AA uint[uint]:
inserts:  1901966/s (5.26s) lookups: 8065673/s (1.24s)

tango.util.container.HashMap!(uint, uint, ..):
inserts:  6346664/s (1.58s) lookups: 23780047/s (0.42s)

The above implementation, Dict!(uint, uint):
inserts:  8199181/s (1.22s) lookups: 34506306/s (0.29s)

This implementation is far from perfect and has room for improvements.
E.g., it is twice as slow for lookups of ulong keys compared to Tango HashMap
(3 times slower for insertion). It's also slower for arrays.
But that's likely to change with some more tweaking.

The attached code is placed into Public Domain.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dict3.d
Type: text/x-dsrc
Size: 14564 bytes
Desc: not available
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20080702/f9fef8d8/attachment.d>