logoalt Hacker News

eqvinox12/10/20241 replyview on HN

Well, chained hash maps are significantly slower in the face of collisions due to the memory fetch latency hit to grab the next item... even ignoring the academic O(n) lookup, memory is often the primary perf constraint these days...

And for an exercise, it might be worth implementing linear probing just to get more learning experience out of it(?)


Replies

teo_zero12/10/2024

But in this specific implementation the keys are stored separately, each one at its own malloc()ed address. So its performance is limited by memory latency, cache (non-)locality, etc. just like the chained-lists variety.