I submitted my container library to code.dlang.org

Martin Nowak via Digitalmars-d digitalmars-d at puremagic.com
Tue Mar 31 14:17:03 PDT 2015

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.

More information about the Digitalmars-d mailing list