3 ms·

Row 100 of hm_put() clears all contents of the item struct, thus losing the pointer to where the previous value was stored. But then row 107 needs this pointer

Row 100 of hm_put() clears all contents of the item struct, thus losing the pointer to where the previous value was stored. But then row 107 needs this pointer to pass it to realloc(). Additionally, in case of overwrite, the memory previously allocated for the key is leaked. All in all, I don't think row 100 is really needed, and removing it wouldn't do any harm. Finally, deletes are hard in hash maps. Either you decide that deletes are not allowed, or you implement them with tombstones or re-insertions. A half-backed solution is not an option. Hope these suggestions help you.

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 ago
  Right. 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 ago
    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(?)
    - teo_zero 2y ago
      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.
acmj 2y ago
I agree. How to deal with deletions is a 101 of hash table implementation. Many CS majors could get it right or at least know about the caveat. It is amusing that many high-quality posts on hash tables are buried in the "new" section of HN while this half-baked toy floats to the front page, with 83 github stars at the moment. People don't know what they are upvoting for.

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 ago
Right. 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 ago
  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(?)
  - teo_zero 2y ago
    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.

acmj 2y ago

I agree. How to deal with deletions is a 101 of hash table implementation. Many CS majors could get it right or at least know about the caveat. It is amusing that many high-quality posts on hash tables are buried in the "new" section of HN while this half-baked toy floats to the front page, with 83 github stars at the moment. People don't know what they are upvoting for.