4 ms·
> Finally, deletes are hard in hash maps. Deletes are hard in open hash maps like here; they're trivial in chained hash maps. (I'm only posting this because t
by eqvinox 2y ago
> Finally, deletes are hard in hash maps.
Deletes are hard in open hash maps like here; they're trivial in chained hash maps.
(I'm only posting this because this seems to be an exercise/learning-ish HN post and I think it's a relevant point to not forget.)
- teo_zero 2y agoRight. Thinking about it, I don't grasp why the author has opted for linear probing here. Given the amount of malloc(), they might have used linked lists as well.
- eqvinox 2y agoWell, 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(?)
- teo_zero 2y agoBut 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.