I submitted my container library to code.dlang.org

[w0rp via Digitalmars-d]

On Friday, 3 April 2015 at 20:35:40 UTC, Martin Nowak wrote:
> On 04/03/2015 06:11 PM, w0rp wrote:
>> 
>> 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.
>
> You should use triangular numbers and power of 2 bucket sizes 
> instead of
> quadratic numbers and prime sized buckets, because that 
> guarantees full
> utilisation of the buckets and a minimal period of the numbers.
>
> The necessary loop is really trivial.
>
> https://github.com/D-Programming-Language/dmd/blob/f234c39a0e633fc9a0b5474fe2def76be9a373ef/src/root/stringtable.c#L162
>
> If you replace
>
>     i = (i + j) & (tabledim - 1);
>
> with this
>
>     i = (i + 1) & (tabledim - 1);
>
> you get linear probing btw.

I have pushed again, and now the hashmap uses powers of two and 
triangular numbers, per your suggestion. I noticed a small 
improvement in speed, probably coming from the & for modulo 
trick. If you would like to test the maps with the benchmark 
program you can run the following:

dub run -q --build=release --config=benchmark_hashmap

You can use the --compiler switch for dub to try different 
compilers.