Programming · concepts · data structures
What is a hash table?
A hash table (also called a hash map) is a data structure that stores key-value pairs and lets you find any value by its key in, on average, constant time - no matter how much data it holds. It is one of the most useful structures in all of programming, and it is what powers the dictionaries and maps built into nearly every language. Once you see how it works, a lot of "how is this so fast?" moments make sense.
The problem it solves
Imagine storing a phone book as a plain list. To find one person, you might have to scan every entry - slow work that gets slower as the book grows, an O(n) operation. A hash table's promise is different: give it the key and it jumps more or less directly to the value, without scanning. That is the difference between checking every entry and knowing exactly where to look.
How it works: the hash function and buckets
Underneath, a hash table is backed by an array of slots called buckets. The magic ingredient is the hash function: it takes your key and turns it into a number, which is mapped to an index in that array.
index = hash(key) % number_of_bucketsTo store a value, you hash the key to get an index and place the value in that bucket. To read it back, you hash the same key again, land on the same index, and pick the value up. Because computing the hash and indexing an array are both fast, fixed-cost steps, lookups do not get slower as the table grows. That is the whole trick.
Collisions, and how they are handled
Two different keys can hash to the same bucket. That is called a collision, and every real hash table has to deal with it. There are two common strategies:
- Chaining: each bucket holds a small list, and colliding entries are stored together in that list. Lookups then check the (usually very short) list in the right bucket.
- Open addressing: if a bucket is taken, the table probes for the next free slot according to a fixed rule, and searches follow the same rule.
With a good hash function and enough buckets, collisions stay rare and those lists stay tiny, so lookups remain fast.
What about performance?
This is where hash tables shine, and where the honest caveat lives. On average, insert, lookup and delete are all O(1) - constant time. In the worst case, if a bad hash function or hostile input dumps every key into one bucket, those operations degrade to O(n), because you are back to scanning a single long list. Good implementations avoid this by using solid hash functions and by resizing (rehashing into a bigger array) when the table gets too full, which keeps performance at amortised O(1). If you want a refresher on this notation, see our guide to Big O notation.
Where you already use one
You use hash tables constantly, often without naming them. The dictionary and map types in most languages are hash tables under the hood: Python's dict, Java's HashMap, JavaScript's Map and object, Ruby's Hash, Go's map. They are also the go-to tool for caches, de-duplicating items, and counting occurrences. The classic optimisation of turning a slow, nested-loop search into a fast one - dropping from O(n²) to O(n) - is almost always done by replacing repeated scans with a hash-table lookup.
The trade-offs
- Fast, but unordered. A basic hash table does not keep keys in any sorted or insertion order (though some language versions add ordering on top).
- Uses extra memory. Keeping collisions rare means keeping spare buckets, so a hash table trades some memory for its speed.
- Worst case is real. The O(1) is an average; adversarial input can force the slow path, which matters for security-sensitive code.
FAQ
Is a hash table the same as a dictionary? In everyday terms, yes - a dictionary or map is the general idea (key to value), and a hash table is the most common way to implement it. When someone says Python "dict" or Java "HashMap", they are using a hash table.
Why is lookup O(1) on average? Because you compute the key's hash and index straight into an array, rather than scanning entries. Both steps take constant time regardless of how many items are stored, so the average cost does not grow with the data.
What is a collision? When two different keys hash to the same bucket. It is normal and expected; hash tables handle it with chaining or open addressing, and keep it rare with a good hash function and resizing.
When should I not use a hash table? When you need keys kept in sorted order, or ordered-range queries - a tree-based structure fits better. Also when memory is extremely tight, since hash tables keep spare space to stay fast.