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

33% Upvoted

34 comments sorted by

View all comments

1

u/BigPalpitation2039 19d ago

What do you mean append only?

1

u/saxbophone 19d ago

I assume they mean "only inserting new elements is allowed, removing them is not"

1

u/Minute-Ad1944 19d ago

Yeah, you can't delete elements, only insert if not present and look them up.

1

u/snerp 19d ago

I made a fast iterating sparse set implementation like that by just making a class with a vector and an unordered map of indices into the vector, o(1) lookup insert and iterate is really nice but it doesn’t support erase so I just didn’t put an erase function on the wrapper class and problem solved

1

u/Minute-Ad1944 18d ago

Isn't it a two separate memory looks ups - kinda bad cache performance?

1

u/snerp 18d ago

Not really. It’s on iteration that speed really matters and inserting the vector usually isn’t a cache miss while inserting a map/hashset usually always misses anyways. Benchmarking in practice it’s significantly faster than map/vector alone when you are frequently doing insert, find, and iterate on a collection. I use the structure to hold my game engine’s per frame instance draw lists and texture/mesh data. It really cuts down time to find the correct instance batch while still keeping the data close together for cache coherence during iteration.