A hash table is a data structure that stores key-value pairs in an array of slots and uses a hash function to compute, from each key, the index where its value belongs. Because the position is calculated rather than searched for, a well-built hash table delivers average O(1) lookup, insertion and deletion, which makes it one of the most widely used data structures in programming.
Hash tables sit behind dictionaries in Python, maps in Java and Go, objects and Map in JavaScript, database indexes, caches, symbol tables in compilers and deduplication logic in data pipelines. Their speed depends on three design choices: the quality of the hash function, the collision resolution strategy and the load factor at which the table resizes.
How a hash table turns a key into a position
A hash table locates data in two steps: it hashes the key into a large integer, then reduces that integer to a bucket index within the current array size. The reduction is usually a modulo operation by the table size or, when the size is a power of two, a bitwise mask of the lowest bits, which is faster but more sensitive to weak hash functions.
A good hash function for a hash table must be deterministic, fast and uniformly distributed, so that similar keys such as user1 and user2 land in unrelated buckets. It does not need to be cryptographically secure, but it must be consistent with key equality: two equal keys must produce the same hash. Breaking that rule, for example by overriding equality without overriding the hash method, makes stored entries impossible to find.
Two different keys can still map to the same index, an event called a collision. Collisions are unavoidable because the key space is far larger than the array, so every practical hash table needs a policy for storing several keys that compete for one slot.
Collision resolution strategies
Collision handling falls into two families: separate chaining, which keeps a small collection in each bucket, and open addressing, which stores every entry directly in the array and probes for another free slot. The choice affects memory layout, cache behavior and how deletion works.
| Strategy | How it places a colliding key | Strengths | Weaknesses |
|---|---|---|---|
| Separate chaining | Appends to a linked list or small tree in the bucket | Simple deletion, tolerates high load | Pointer chasing, extra memory per entry |
| Linear probing | Tries the next slot, then the next | Excellent cache locality | Primary clustering at high load |
| Quadratic probing | Jumps by growing square offsets | Less clustering than linear | May miss free slots if size is badly chosen |
| Double hashing | Steps by a second hash of the key | Very even probe sequences | Two hash computations, weaker locality |
| Robin Hood hashing | Displaces entries closer to their home slot | Low variance in probe length | More complex insertion and deletion |
| Cuckoo hashing | Moves residents between two candidate tables | Worst-case O(1) lookup | Insertion may loop and force a rebuild |
Deletion in open addressing needs care: simply emptying a slot would break the probe chain for keys inserted after it. Implementations either write a tombstone marker or shift later entries backward, as Robin Hood and linear probing variants do. Java’s HashMap uses chaining and converts long chains into balanced trees once a bucket holds eight entries, which limits the damage of many collisions.
Load factor, resizing and real complexity
The load factor is the number of stored entries divided by the number of buckets, and it is the main parameter that keeps a hash table fast. When the load factor passes a threshold, the table allocates a larger array, typically twice the size, and rehashes every entry into it. A single resize costs O(n), but spread over many insertions the amortized cost stays O(1).
| Design | Typical resize threshold | Reason |
|---|---|---|
| Separate chaining | 0.75 to 1.0 | Short chains remain cheap to scan |
| Linear probing | About 0.5 to 0.7 | Clusters grow quickly above this range |
| SIMD-probed open addressing | About 0.875 | Metadata bytes allow fast group scanning |
| Cuckoo hashing | About 0.5 per table | Insertion failures rise sharply beyond it |
The famous constant-time figure is an average-case guarantee, not a worst-case one. If many keys collide, operations degrade toward O(n). This matters for security: an attacker who knows the hash function can submit crafted keys that all collide, a hash flooding attack that can stall a web server. Modern runtimes defend against it with randomly seeded hash functions such as SipHash, chosen at process start.
Hash tables compared with neighboring structures
Within data structures, a hash table is the default choice for exact-match lookup by key, but it gives up ordering. An array offers faster access when keys are small dense integers, and a balanced search tree is preferable when the program needs sorted iteration or range queries.
| Structure | Lookup by key | Ordered traversal | Best fit |
|---|---|---|---|
| Hash table | Average O(1) | No | Fast membership and key lookup |
| Array | O(1) by index only | By index | Dense integer keys, sequential data |
| Linked list | O(n) | Insertion order | Frequent splicing, rarely searched |
| Balanced search tree | O(log n) | Yes | Range queries, sorted output |
| Sorted array | O(log n) with binary search | Yes | Read-heavy data that rarely changes |
Hash tables also underpin hash sets, which store only keys, and many graph implementations use them as adjacency maps keyed by vertex. A frequent design is a hash table combined with a doubly linked list, which yields an LRU cache with constant-time access and eviction.
Practical pitfalls and design advice
Most production bugs with hash tables come from key design rather than the table itself. The following table lists the symptoms practitioners meet most often.
| Symptom | Cause | Fix |
|---|---|---|
| Stored entry cannot be found | Mutable key changed after insertion | Use immutable keys only |
| Lookups slow despite small size | Weak hash puts keys in few buckets | Combine all equality fields in the hash |
| Latency spikes during inserts | Large resize and rehash at once | Presize the table or use incremental resizing |
| Iteration order differs between runs | Randomized seeds and resizing | Never rely on hash table order |
| Server stalls under crafted input | Hash flooding attack | Seeded hash functions, request size limits |
- Presize the table when the expected number of entries is known, which avoids repeated rehashing.
- Keep equality and hashing consistent, and include exactly the fields that define identity.
- Prefer open addressing with compact layouts when memory locality dominates performance.
- Choose a tree-based map whenever sorted keys or range scans are a requirement.
Stripped to the essentials
Picture a coat check with numbered hooks. Instead of searching every hook for your coat, the attendant uses a fixed rule to turn your name into a hook number, so they walk straight to the right spot. A hash table works the same way: a formula converts each key into a position, and the value is stored there.
Sometimes two names point to the same hook, so the system needs a simple rule for sharing it. When the room gets too crowded, it moves everything to a bigger room. The key takeaway is speed: finding something takes about the same time whether the table holds ten items or ten million.
Where it is applied
A payment service receives retried requests from mobile clients with unreliable connections, and each request carries a unique idempotency key. Before charging a card, the service checks a hash table in memory, keyed by that identifier, to see whether the request was already processed in the last 24 hours. A hit returns the stored response; a miss processes the payment and inserts the result.
The team presizes the table for about two million keys and uses a seeded hash function so that hostile clients cannot force collisions. Lookups take well under a microsecond regardless of traffic volume. The outcome is that duplicate charges disappear while the check adds no measurable latency to each payment.