logoalt Hacker News

e-dant12/08/20242 repliesview on HN

Good catch! Yes, that looks like a bug :)


Replies

attractivechaos12/09/2024

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

munificent12/09/2024

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-e...