The short answer
Quick answer: A hash map stores key-value pairs in an array. To find where a key belongs, it runs the key through a hash function, which turns it into a number, and uses that number to compute an array index. Because computing a hash and jumping to an array position take the same time no matter how many items are stored, lookups, inserts and deletes take constant time on average: O(1). When two keys land on the same index (a collision), the map resolves it by chaining or probing, and it grows the array before collisions become common.
Hash maps go by many names: dict in Python, Map or plain objects in JavaScript, HashMap in Java and Rust, map in Go, unordered_map in C++.
The core idea
Arrays are fast because the computer can jump straight to position i. But arrays are indexed by small integers, and we want to look things up by names, IDs or anything else.
A hash map bridges that gap:
index = hash(key) % number_of_buckets
- Hash the key to get a large integer.
- Reduce it to a valid array index.
- Go to that slot (called a bucket).
Looking up "alice" in a map of ten items or ten million involves the same three steps.
What makes a good hash function
A hash function for a hash map should be:
- Deterministic. The same key always gives the same hash.
- Uniform. Keys spread evenly across buckets, so few share a slot.
- Fast. It runs on every operation.
These are not cryptographic hashes. Functions such as SHA-256 are designed to resist attackers and are far slower. Hash maps use lightweight functions such as wyhash, xxHash or SipHash.
Two rules follow for the keys themselves:
- Keys that are equal must have equal hashes. If you define custom equality on a class, define a matching hash.
- Keys must not change while in the map. If a key's hash changes after insertion, the map looks in the wrong bucket and cannot find it. This is one reason immutability matters.
Collisions are inevitable
There are far more possible keys than buckets, so some keys must share. Thanks to the birthday paradox, collisions appear much sooner than intuition suggests: among just 23 people, two probably share a birthday out of 365 possible days.
There are two main ways to handle collisions.
Separate chaining
Each bucket holds a small list of entries. To look up a key, hash to the bucket, then walk the list comparing keys.
- Simple, and deletion is easy.
- Each entry is a separate allocation, so walking a chain means following pointers, which is hard on the CPU cache.
- Java's
HashMapuses chaining and converts long chains into balanced trees to limit worst-case cost.
Open addressing
All entries live directly in the array. If a slot is taken, the map probes for another:
- Linear probing: try the next slot, then the next.
- Quadratic probing or double hashing: jump further each time to avoid clumps.
Lookups follow the same probe sequence until they find the key or an empty slot.
- Everything is in one contiguous block, which is very cache-friendly.
- Deletion is trickier: removing an entry could break a probe chain, so maps leave a "tombstone" marker or shift later entries back.
- Python's
dict, Rust'sHashMapand Go's map use variations of open addressing. Google's Swiss Tables design, which several of these are based on, stores a byte of each hash in a compact metadata array so it can check many slots at once.
| Separate chaining | Open addressing | |
|---|---|---|
| Where entries live | In lists hanging off buckets | In the array itself |
| Cache behaviour | Poorer | Better |
| Tolerates a full table | Yes, with slower lookups | No, must stay partly empty |
| Deletion | Simple | Needs tombstones or shifting |
Load factor and resizing
The load factor is the number of entries divided by the number of buckets. As it rises, collisions multiply and operations slow down.
So when the load factor passes a threshold (0.75 in Java, about two-thirds in CPython, around 0.875 in Swiss Tables), the map resizes:
- Allocate a bigger array, usually double the size.
- Re-insert every entry, because each index depends on the array size.
A resize costs O(n), but it happens so rarely that the average cost per insert stays constant. This is called amortised O(1). Doubling means that across n inserts, the total copying work is proportional to n.
If you know roughly how many items you will insert, reserve capacity up front and skip the intermediate resizes.
When O(1) stops being true
"Constant time" is an average. The worst case is O(n):
- A bad hash function sends many keys to the same bucket.
- Deliberate attacks. If an attacker can predict the hash function, they can craft thousands of keys that all collide, turning each lookup into a slow scan and stalling a server. This is called hash flooding. Modern languages defend against it by mixing a random per-process seed into the hash.
- Expensive keys. Hashing a very long string takes time proportional to its length.
- Resizes cause occasional slow inserts, which matters in latency-sensitive code.
Hash maps vs other structures
| Need | Best choice |
|---|---|
| Look up by exact key | Hash map |
| Keys in sorted order, or range queries | Balanced tree or B-tree |
| Smallest or largest item quickly | Heap |
| A handful of items | A plain array is often faster |
This is why databases usually use B-trees for indexes: they support range queries such as "between 10 and 20", which a hash cannot. See how database indexes work. A URL shortener is the same lookup in miniature, one code in and one destination out; see how to design a URL shortener. Distributed systems apply the same hashing idea across machines; see consistent hashing.
Does a hash map keep order?
By design, no. But several languages add it:
- Python dictionaries keep insertion order (guaranteed since 3.7).
- JavaScript
Mapiterates in insertion order. - Go deliberately randomises iteration order so nobody relies on it.
- Java offers
LinkedHashMapfor insertion order andTreeMapfor sorted order.
Frequently asked questions
Why is hash map lookup O(1)?
Because finding the bucket is arithmetic on the key's hash, which does not depend on how many items are stored. With few collisions, only one or two comparisons follow.
What is a hash collision?
Two different keys that map to the same bucket. The map handles it by chaining or probing.
What is the difference between a hash map and a hash set?
A set stores only keys; a map stores a value with each key. They work the same way internally.
Can any object be a key?
Only if it has a stable hash and a matching definition of equality. Mutable objects generally make poor keys.
Conclusion
A hash map turns "search for this key" into "compute a position and go there". A good hash function spreads keys out, a collision strategy handles the overlaps, and resizing keeps the table sparse enough to stay fast. It is one of the most useful data structures in programming, and knowing its limits tells you when to reach for a tree instead.
Related articles
- How the CPU Cache Makes Code Fast (and How to Write Cache-Friendly Code)
- How Consistent Hashing Distributes Data Across Servers
- How a Database Index Makes Queries 1000x Faster
- Why Immutability Makes Code Easier to Reason About
Sources and further reading
