Technology
What is A hash table?
A hash table is a data structure that stores items by key for near-instant lookup. It runs each key through a 'hash' function to compute where to put the value, so finding it later takes roughly constant time, no matter how much data you store.
See it, don’t just read it.
Watch a 2-minute lesson with voice + animation that explains a hash table.
Key things to understand
- 1A hash function turns each key into an index in an array.
- 2The value is stored at that index, so lookups jump straight to it.
- 3Average lookup, insert, and delete take roughly constant time.
- 4Two keys landing on the same slot ('collision') are handled by a backup scheme.
- 5It powers dictionaries, database indexes, and caches.
Frequently asked questions
- Why are hash tables so fast?
- The hash function computes an item's location directly, so the program jumps to it instead of searching — usually in constant time.
- What is a hash collision?
- When two different keys hash to the same slot. Hash tables resolve it by chaining items together or probing for the next free slot.
- Where are hash tables used?
- Behind the dictionaries and maps in most programming languages, plus database indexes, caches, and deduplication.