On Friday, 2 September 2016 at 19:38:34 UTC, Illuminati wrote:
I am trying to create a hash table and would like an efficient
way to be able to know if an element exists to test for
collisions.
I could keep a bitarray, but wasting around 12% space. I could
use pointers(null check) to elements but this creates
fragmentation. It is not terrible, just curious if anyone has a
better way?
fragmentation is a consequence of the hash function. You should
set the hasher as a template parameter so that, according to the
value type, the best hash fun (the one that creates less
clustering) can be supplied.
But otherwise the buckets is almost always an array of
ReturnType!hashFun with the max value wrapped around the next
power of two value following entry count.
