Hash Map
What it is
A hash map stores a value for each key. A hash chooses a starting slot in an array. If that slot is taken, the table looks for another one. Two keys can choose the same starting slot. This is a collision.
The core idea
When a slot is already taken, the table checks the next slot, and the one after that, until it finds one that is free or that holds the key it wants (people call this linear probing). A slot can be empty, live, or deleted. A deleted marker lets a search continue past a removed key (people call this a tombstone). A key's location depends on the table size, so growth is more than copying an array. Extra empty space keeps searches short, at the cost of more memory.
Example
Keys A and B choose the same starting slot. A goes in that slot. B goes in the next one. Delete A, then search for B. The search must pass the deleted slot and still find B.
Where you meet this
- CPython's
dictuses open addressing. Its source says it prefers that over chaining because of the cost of extra links. Deleted slots get a dummy marker, so searches that pass through them keep going. (dictobject.c) - Go's map is a Swiss Table since Go 1.24, a form of open addressing that checks a small group of slots at once. (Go blog: Swiss Tables)
- Redis has its own hash table (
dict.c). It uses chaining instead, a short list per slot, and moves keys to a bigger table a few at a time ("incremental rehashing"). (Redis dict.c)
When to choose it: you look things up by an exact key and do not need any order.
When not to: you need keys in sorted order or a range ("every key from 10 to 20"). A sorted tree or a sorted array does that, and a hash map cannot. Open addressing also slows down a lot when the table is nearly full, so it has to grow early. Chaining copes better with a full table but costs more memory per key.
Common bugs
- Clearing a deleted slot as if it had always been empty.
- Adding a second copy of a key instead of updating it.
- Treating a stored zero as an empty slot.
- Losing keys on growth, or bringing deleted keys back.
- Counting deleted slots in
Len. - Using a negative array position for a negative key.
Keep it fast
Keep enough empty space to make searches short. How full the table is, compared to its size, is called the load factor. Deleted markers also use search space. Too many of them can make a small table slow.
Learn more
Knuth's hashing chapter explains this in more depth. CPython's dict source and SwissTable design notes show production tables.