Glossary
What is open addressing?
Open addressing is a way to build a hash table with no linked lists: all entries live in one array, and when two keys hash to the same slot, the second one probes other slots in a fixed order until it finds an empty one. Linear probing, the simplest order, just tries the next slot.
Tombstones and load factor
Deleting an entry cannot simply empty its slot, or a later lookup would stop early and miss keys that probed past it. Instead the slot gets a tombstone: treated as occupied when searching, reusable when inserting. The table also grows when its load factor (entries divided by capacity) passes a limit, because probe sequences get long as it fills.
Where it is taught
Crafting Interpreters builds one in chapter 20 with FNV-1a hashing and a 75% load factor. Knuth analyzes it exactly in §6.4, Hashing: how many probes linear probing and double hashing take on average, and why clustering makes linear probing worse than it looks.
Questions
Open addressing or chaining?
Open addressing is cache friendly and avoids allocations; chaining tolerates high load factors and simpler deletes. Knuth's §6.4 compares them with exact numbers.