• =?UTF-8?B?Tm9yZGzDtnc=?= (14/14) Feb 19 2018 I'm currently developing a combined HashMap and HashSet with open
• Nathan S. (4/6) Feb 19 2018 You might want to consider using Robin Hood hashing to reduce the

=?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:

I'm currently developing a combined HashMap and HashSet with open 
addressing at

https://github.com/nordlow/phobos-next/blob/master/src/open_hashmap_or_hashset.d

with probing using steps of triangular numbers when length is a 
power of two at

https://github.com/nordlow/phobos-next/blob/master/src/probing.d

I've read that for small tables (where the size of the entire 
array Element[] is smaller than a certain threshold) a linear 
search is usually faster. Is this threshold somehow related to 
the sizes of cache-line?

Suggestions for compile-time or run-time logic that decides when 
to use linear search are very welcome!

My current proposal is to use linear search when 
ElementType.sizeof*length <= byte-size of a cache-line.

Nathan S. <no.public.email example.com> writes:

On Monday, 19 February 2018 at 10:22:12 UTC, Nordlöw wrote:
 I'm currently developing a combined HashMap and HashSet with 
 open addressing

You might want to consider using Robin Hood hashing to reduce the 
worst-case length of collision chains, regardless of what kind of 
probing scheme you use.