4 ms·

A bug, I believe: If you "put" three colliding strings A and then B and then C, and then "delete" B, you won't be able to find C anymore.

• e-dant 2y ago
  Good catch! Yes, that looks like a bug :)
  • attractivechaos 2y ago
    You are implementing a closed hash table with linear probing. You need tombstones to mark deleted items, or better, move other items to replace deleted items [1]. Currently your library doesn't have either mechanism. [1] https://en.wikipedia.org/wiki/Linear_probing#Deletion https://en.wikipedia.org/wiki/Linear_probing#Deletion
  • munificent 2y ago
    If it helps, my book Crafting Interpreters walks through a linear probing hash table implementation in C including handling deletion: https://craftinginterpreters.com/hash-tables.html#deleting-entries https://craftinginterpreters.com/hash-tables.html#deleting-e...