On Wednesday, 1 April 2015 at 06:31:28 UTC, thedeemon wrote:
On Tuesday, 31 March 2015 at 21:17:04 UTC, Martin Nowak wrote:
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.
Is there a D version of a hash table with open addressing and
quadratic probing? It would be interesting to compare speeds.
I like Robin Hood for cache-friendliness, and it works quite
well for many combinations of key-value types.
Now there is. I just changed the hashmap in my container library
to use open addressing and quadratic probing. There's a benchmark
program in the library for testing it in comparison to the
standard associative array. I tested using 2.066 with
optimisations on, and it seems to be about the same.
https://github.com/w0rp/dstruct/blob/master/source/dstruct/map.d
Now, I am not the most fantastic Computer Science guy in the
world, and I probably got a few things wrong. If anyone would
like to look at my code and point out mistakes, please do. I will
add any improvements suggested.
