What Is a Hash Table? Fast Lookups, Explained

A hash table is a data structure that stores key-value pairs and gives average-case constant-time lookup, insertion, and deletion, no matter how many entries it holds. It does this by running each key through a hash function that converts it into a number, then uses that number as an index into a plain array. Instead of scanning a list to find a match, the table jumps straight to the slot where the value should be.

Almost every language exposes this structure under a familiar name: a Python dict, a JavaScript Object or Map, a Go map, a Java HashMap. The names differ; the underlying mechanism is the same.

How the lookup actually works

A hash table keeps an underlying array (often called buckets) and a hash function that maps any key to an array index. Inserting "alice": 30 works like this:

1. Run "alice" through the hash function, producing a number like 2385712.
2. Reduce that number modulo the array’s size to get a valid index, say 7.
3. Store the key-value pair at index 7.

Looking up "alice" later repeats steps 1 and 2 to land on the same index and read the value directly — no scanning required. This is why lookup is O(1) on average: the cost doesn’t grow with the number of stored items, unlike a linear scan through an array or linked list, which is O(n). See Big O notation for a deeper look at why that distinction matters as data grows.

A good hash function has two properties: it’s deterministic (the same key always produces the same index) and it distributes keys roughly evenly across the array, so entries don’t pile up in a few slots.

Collisions: when two keys land on the same slot

Because the array has a fixed size and the space of possible keys is effectively infinite, two different keys will eventually hash to the same index. This is called a collision, and every hash table needs a strategy to handle it.

• Separate chaining — each bucket holds a small list (or tree, in some implementations) of all entries that hash to that index. A collision just appends to the list. Lookup still starts with the hash but may need to scan a short chain.
• Open addressing — on a collision, the table probes for the next open slot using a fixed rule (linear probing, quadratic probing, or double hashing) and stores the entry there instead. Lookup follows the same probe sequence to find it again.

Both approaches keep collisions rare in practice by controlling the load factor — the ratio of stored entries to array slots. When the load factor crosses a threshold (commonly around 0.7), the table resizes: it allocates a larger array and rehashes every existing entry into it. This resize is an O(n) operation, but it happens infrequently enough that the amortized cost per insertion stays O(1).

Worst case vs average case

	Average case	Worst case
Lookup	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)
Space	O(n)	O(n)

The worst case happens when many keys collide — for instance, an attacker deliberately choosing keys that all hash to the same bucket, degrading every operation to a linear scan. This is why production hash table implementations seed their hash function with randomness per process, so the mapping from keys to indices isn’t predictable from the outside.

Hash tables vs other structures

A sorted array or a balanced binary search tree also stores key-value pairs, but lookup there costs O(log n) — it has to compare against a sequence of elements to narrow down the position. A hash table trades that ordering away: you can’t efficiently ask “give me all keys between X and Y” from a hash table, because there’s no relationship between a key’s value and where it lives in the array. If you need ordered iteration or range queries, a tree-based structure is the better fit; if you only need “does this key exist, and what’s its value,” a hash table wins on raw speed.

This tradeoff shows up directly in database indexing: B-tree indexes support range scans and sorted output, while hash indexes are faster for pure equality lookups but useless for WHERE x > 5 style queries. Redis is essentially a hash table exposed as a network service — its core data structure maps keys to values with the same O(1) average lookup guarantee, which is a big part of why it’s fast enough to sit in front of a slower database as a cache.

Hash tables also underpin structures you might not immediately associate with hashing — a set is just a hash table that discards the values and keeps only keys, and many vector database implementations use locality-sensitive hashing, a variant that intentionally hashes similar items to the same bucket instead of spreading everything evenly.

The takeaway

A hash table converts keys into array indices with a hash function, giving average O(1) lookup, insertion, and deletion at the cost of losing any natural ordering between keys. Collisions are unavoidable and handled through chaining or open addressing, and the table resizes periodically to keep the load factor — and therefore performance — in check. When you need fast existence checks and key-value lookups without caring about order, a hash table is almost always the right default.