# What is open addressing?

> Open addressing stores every entry in the hash table array itself and probes for a free slot on collision. Linear probing, tombstones and load factor.

**Open addressing**: Open addressing is a hash table collision strategy in which every entry lives in the table's own array, and a collision is resolved by probing other slots until a free one is found.

**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](https://cracked.guide/guide/ci-20) with FNV-1a hashing and a 75% load factor. Knuth analyzes it exactly in [§6.4, Hashing](https://cracked.guide/guide/knuth-w097-0): 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.

---

Source: https://cracked.guide/glossary/open-addressing
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.