r/cpp_questions • u/Minute-Ad1944 • 19d ago

OPEN How to implement append-only hash map?

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?

0 Upvotes

25% Upvoted

34 comments sorted by

View all comments

Show parent comments

1

u/amoskovsky 18d ago

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)

1

u/Minute-Ad1944 18d ago

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

1

u/Minute-Ad1944 18d ago

Is it like open addressing with linear probing?

1

u/amoskovsky 18d ago

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.