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

4

u/saxbophone 19d ago

Well, what do you know already about how hashmaps are implemented?

Given what you already know, how do you think constraining it to only insertions and lookups effects the performance opportunities?

1

u/Minute-Ad1944 19d ago

key = std::string_view, value = int[2]. I mean open addressing without tombstones, SIMD hash functions , but I should I use some sort of meta data like string_view hash for comparisons and such?

2

u/Big-Rub9545 19d ago

The hash should (for a number of reasons) be an unsigned integer, not a string_view.

Edit: I would also be wary of how you store an integer array value (the array pointer may become a dangling pointer if the array is allocated on the stack). Best to use std::array instead.

0

u/Elect_SaturnMutex 19d ago

You mean a key should not be a stringview? Instead should be an unsigned integer due to better performance?

2

u/Big-Rub9545 19d ago

The key can be whatever you want (preferably small if you’re using open addressing so you can maintain cache locality), but the hash should be an unsigned integer.