I submitted my container library to code.dlang.org

w0rp via Digitalmars-d digitalmars-d at puremagic.com
Fri Apr 3 09:11:58 PDT 2015


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.


More information about the Digitalmars-d mailing list