Reserving/Preallocating associative array?

Peter Alexander peter.alexander.au at gmail.com
Fri Dec 27 09:35:22 PST 2013


On Friday, 27 December 2013 at 09:37:09 UTC, Benjamin Thaut wrote:
> At this point the profiler looked something like this:
> 50%  find free entry in hashmap

When I'm building large immutable hash tables I do this:

Read in all the unordered key-value pairs into an array of 
Tuple!(Key, Value)

Determine the number of buckets you want (B)

Schwartz sort the array by hash(key) % B (a radix sort will 
probably be efficient here, but any will do)

This groups all items with the same bucket index together. You 
can then easily generate the array of bucket pointers by 
iterating the array.

Of course, you need your own hash table implementation to do 
this. You cannot do it using the built-in hash tables.


More information about the Digitalmars-d mailing list