On Monday, 30 March 2015 at 11:23:13 UTC, thedeemon wrote:
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.
You shouldn't write when you read. Robin Hood sounds like a good
idea, but it really isn't. Keep your load factor reasonable and
distribute values evenly, then you don't need a LRU lookup.
Apparently with default hash functions for strings such hash
tables get very slow due to clustering. With other key types
they are pretty fast.
That's one reason why you should use quadratic probing for hash
tables, but you should also use a good hash function. MurmurHash2
(not 3) is particularly fast, even for very small keys.
The simplest and most efficient way to do quadratic probing is to
use triangular numbers and a power of 2 sized hash table.
