Concurrent HashMap

[dadhi]

1. Fix concurrent update to work as expected in all cases, proove it
2. Improve on current linear probing version to the max
3. Experiment with new impl., e.g. leap-frog probing

Update

Here is the existing implementation to copy and adapt Ariadne

Test and verify via RelaSharp.

Update 2

Here is the Fibonacci Hashing reveal to fit hash into smaller space, instead of current modulo approach:
https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/

[dadhi]

Results so far:

[dadhi]

Concurrent HashMaps are hard, harder and hardest.

1.

How to calculate original slots count (capacity) from capacity+1/4buffer.

Say the count is 32+8==40, 0b101000
Then the original count 32 == 40 & (40 << 2)

2.

How to put an item into map during resizing without loss:

• Check if transit slots exist, then Remove from current slots and insert into transit. The copying thread will do that backwards: will copy into transit slot, than remove from old.

• Remove is similar: remove from current slots first then remove transit slot if copied.

[dadhi]

3.

Double expand size is simple.:

Given 32+8==40, do 40 << 1 == 64+16 == 80

[dadhi]

Not now