On Sunday, 29 March 2015 at 22:32:34 UTC, Martin Nowak wrote:
Always use open addressing when implementing a hash table.
https://github.com/D-Programming-Language/dmd/pull/4088
https://github.com/higgsjs/Higgs/pull/170
Here's a variant of a open addressing hash table (Robin Hood one)
that uses std.container.Array instead of relying on GC:
https://bitbucket.org/infognition/robinhood/src/
(see rbhash.d, the rest is just tests)
Not documented yet, sadly.
Here are some reflections in this, describing the approach and
comparing with other implementations (built-in AAs and linear
probing hashtable from vibe.d):
http://www.infognition.com/blog/2014/on_robin_hood_hashing.html
Apparently with default hash functions for strings such hash
tables get very slow due to clustering. With other key types they
are pretty fast.
