How Hash Tables Work: Average Constant-Time Lookups Explained

A hash table stores key and value pairs and finds any key in roughly constant time on average. Dictionaries in Python, Map objects in JavaScript, and HashMap in Java all rely on this idea. The trick is to convert each key into an array index with a hash function, so the program can jump straight to the right slot instead of searching through the data.

This article explains how that conversion works, why two keys sometimes land in the same slot, and how the table keeps itself fast as it grows. It uses a small Python sketch so the mechanics are visible.

From key to array index

An ordinary array lets you read element 7 in one step, because the address of element 7 can be computed directly. A hash table borrows that property. It runs each key through a hash function, which returns a whole number, and then reduces that number to the size of the underlying array, usually with the modulo operator.

If the table has 8 slots and the hash of the key "apple" is 1234, the slot index is 1234 mod 8, which is 2. Storing and reading "apple" both start by computing that index. No scan of the other keys is needed.

A good hash function spreads keys evenly across the slots and gives the same output for the same input every time. It also needs to be fast, because it runs on every lookup.

Collisions are unavoidable

Two different keys can map to the same index. This is called a collision. It is not a rare accident. With 8 slots and 9 keys, at least one collision must happen, because the pigeonhole principle forces two keys into the same slot.

Hash tables handle collisions with one of two broad strategies. The choice affects speed, memory use and how the table behaves under load.

Strategy	How it stores colliding keys	Main advantage	Main cost
Separate chaining	Each slot holds a small list of entries	Simple, tolerates high load	Extra pointers and memory per entry
Linear probing	Try the next slot, then the next, until a free one is found	Good cache locality	Clusters form and slow lookups
Quadratic probing	Try slots at growing offsets	Fewer clusters than linear probing	Must keep table size chosen carefully
Double hashing	Second hash function sets the step size	Spreads probes well	Needs a second hash function

Many modern runtimes use open addressing, which means probing inside the array itself. CPython dictionaries are one example. Java's HashMap uses separate chaining, and it converts a long chain into a balanced tree when the chain grows past a threshold, which keeps the worst case from degrading to a linked list scan.

A small chaining example

The sketch below uses separate chaining. Each slot holds a list of key and value pairs, and lookups scan only the short list in one slot.

class TinyHashMap:
    def __init__(self, size=8):
        # One bucket per slot; each bucket is a list of (key, value) pairs.
        self.buckets = [[] for _ in range(size)]

    def _index(self, key):
        # Reduce Python's hash to a valid slot number for this table.
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)   # overwrite an existing key
                return
        bucket.append((key, value))        # new key, possibly sharing the slot

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default                     # key absent from this bucket

This code omits resizing, which real tables need. It shows the essential path: hash the key, pick a bucket, then compare keys inside that bucket.

Load factor and why it matters

The load factor is the number of stored entries divided by the number of slots. A table with 6 entries in 8 slots has a load factor of 0.75. As the load factor rises, collisions become more frequent and lookups slow down, because each probe or chain scan has more work to do.

Most implementations therefore set a maximum load factor. Java's HashMap uses 0.75 by default and starts with 16 buckets. When the number of entries exceeds the threshold, the table allocates a larger array and moves every entry into it. The size is usually doubled, so the cost of each resize is spread over many insertions.

This is why the usual claim is "average constant time" rather than "always constant time." An insertion that triggers a resize takes longer, but the average cost over a long sequence of insertions stays constant. Engineers call this amortized constant time.

What can make a table slow

The average case assumes that keys spread evenly. Three situations break that assumption.

A poor hash function can send many keys to the same slot. A table of user IDs that all end in zero, hashed with a function that ignores the last digit, may place thousands of them in a handful of buckets.

An adversary who knows the hash function can craft keys that collide on purpose. This is a known denial-of-service technique against web frameworks that accepted attacker-controlled form fields. Modern languages randomize their hash seeds to make such attacks much harder.

A table that never resizes will eventually hold long chains or dense probe sequences. Lookups then degrade toward linear time, which is the worst case.

Choosing a hash table in practice

Use a hash table when you need fast membership checks, counting, caching or lookups by a unique key. Use a sorted structure, such as a balanced tree or a sorted array with binary search, when you need keys in order, range queries or the smallest and largest entries.

Keys must also be stable. If a key changes after it is stored, the table computes the wrong slot and the entry becomes unreachable. Immutable types such as strings and tuples in Python are common keys for this reason.

Deletion deserves care too. With chaining, removing an entry simply unlinks it from its short list. With open addressing, clearing a slot could break the probe sequence for other keys that passed through it, so implementations usually leave a marker, often called a tombstone, that says the slot was used once. Lookups skip over tombstones, and inserts may reuse them. Many tombstones pile up over time, so tables eventually rebuild themselves to clear them out, just as they do when the load factor grows too high.

Key takeaways

A hash table converts each key into an array index with a hash function. Good hashing spreads keys evenly, and collisions are handled by chaining or probing. Average lookup, insert and delete operations take constant time.

The guarantee depends on a controlled load factor, regular resizing and a hash function that does not cluster real data. When those conditions hold, the hash table is one of the most practical structures in everyday software.