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