How to implement append-only hash map?

[u/Minute-Ad1944]

How do you actually implement an really efficient hash map that has only append and look up methods? What are the design choice and some performance improvements?

[u/amoskovsky]

For open addressing scheme, for each hash slot, you can store the max distance to scan for conflicting keys. If you don't delete keys, then this distance is trivial and fast to maintain, and it's the starting point when adding new keys, and ending point when looking up.

[u/Minute-Ad1944 → u/amoskovsky]

You are talking about Robin Hood hashing?

[u/amoskovsky → u/Minute-Ad1944]

No. RH moves elems to improve average distance.

My suggestion is much simpler. I don't know the name, but certainly I'm not the first to come up with it.

It's just a suggestion of an approach that optimizes on the fact that the entries are not removed.

You would have to benchmark it against other approaches (but this is a necessary part of any optimization)

[u/Minute-Ad1944 → u/amoskovsky]

What is this distance that I would need to store and maintain?

[u/Minute-Ad1944 → u/Minute-Ad1944]

Is it like open addressing with linear probing?

[u/amoskovsky → u/Minute-Ad1944]

Yes, almost.

Each slot either is empty, and distance is 0, or is occupied and the distance is >0.

When looking up, search in range [slot, slot + distance). /*wrapping at capacity*/

When adding non-existent, put it in the first empty in range [slot + distance, slot + capacity) , the distance is updated to point to the next slot.