Look a key up in a Python dict with ten entries and it takes the same time as looking one up in a dict with ten million. That is not an accident of a fast language. Python’s dict, Java’s HashMap and JavaScript’s Map are all hash tables, and the whole design exists to make lookup, insert and delete run in O(1) on average. Big O notation gives that lookup the label “constant time”. Here is the mechanism that earns it.

How a hash table turns a key into an array index

A hash table is an array plus a function that turns a key into a position in that array.

1

bucket index = hash(key) % number_of_buckets

hash() takes a key of any size (a string, a tuple, an object) and returns an integer. Within one run of the program, the same key always produces the same integer, and a good hash function spreads those integers close to evenly across its output range. Take the integer modulo the array’s length and you have a slot. Store the key and value there. A later lookup recomputes the same hash, lands on the same slot and reads the value out. No scan, no comparison against every other key.

Everything else in a real hash table, from collision handling to resizing to the exact probe sequence, is there to keep that one-step lookup working as the table fills up.

A minimal version that ignores collisions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class TinyTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [None] * size

    def put(self, key, value):
        index = hash(key) % self.size
        self.buckets[index] = (key, value)

    def get(self, key):
        index = hash(key) % self.size
        if self.buckets[index] is None:
            raise KeyError(key)
        stored_key, value = self.buckets[index]
        if stored_key != key:
            raise KeyError(key)
        return value

1
2
3
4

>>> t = TinyTable()
>>> t.put("user:42", {"name": "Dana"})
>>> t.get("user:42")
{'name': 'Dana'}

It breaks as soon as two different keys hash to the same index. hash("user:42") % 8 and hash("user:17") % 8 can both come out to 3, and TinyTable has room for only one of them: the second put silently overwrites the first. That is a collision.

How hash tables handle collisions: chaining vs. open addressing

There are two standard ways to keep both keys when they land on the same slot.

Chaining turns each bucket into a small container, usually a linked list. A collision means the bucket holds two entries instead of one, and lookup walks that bucket’s list until it finds a matching key.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class ChainedTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def put(self, key, value):
        index = hash(key) % self.size
        bucket = self.buckets[index]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self.buckets[hash(key) % self.size]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

Java’s HashMap is a chaining table. Each bucket starts as a linked list. If one bucket collects at least 8 entries and the table has at least 64 buckets, that bucket converts into a red-black tree (TREEIFY_THRESHOLD and MIN_TREEIFY_CAPACITY in the JDK source), so a worst-case O(n) scan of one overloaded bucket becomes O(log n). It converts back to a list if a resize leaves it with 6 entries or fewer.

Open addressing keeps every entry directly in the array, with no secondary structure and no pointers. On a collision it probes: it tries another slot, by a fixed rule, until it finds an empty one. CPython’s dict works this way, and the lookup comment in Objects/dictobject.c gives the reason: “Open addressing is preferred over chaining since the link overhead for chaining would be substantial.” CPython also avoids plain linear probing, which clusters badly when keys arrive in a predictable order. Each probe step mixes more bits of the hash into the next index, so two keys that collide on their low bits split up a few probes later.

The two fail differently. A chaining table that fills up gets slower, and in the worst case every entry ends up in one long list. An open-addressing table has nowhere to put an entry once the array is full, so it has to resize before that happens.

What load factor is and why the table resizes before it’s full

Load factor is entries divided by buckets. Both strategies watch it to decide when to resize, and Java and CPython pick different thresholds.

Java’s HashMap resizes once the entry count passes capacity times load factor. The Javadoc for the no-argument constructor gives the defaults: 16 buckets, load factor 0.75, so the first resize fires at 12 entries. A resize roughly doubles the bucket count and rehashes every existing entry into the new array. That is why the Javadoc recommends sizing the map up front with HashMap.newHashMap(expectedSize) (Java 19+) when you know roughly how many entries it will hold: you skip the repeated rehashes.

CPython’s dict resizes later and grows faster. The USABLE_FRACTION comment in the source says the table resizes once it is two-thirds full, and GROWTH_RATE sizes the new table for roughly three times the current number of live entries, not a flat doubling.

Neither number is arbitrary. A load factor near 1 packs the array tight but makes every operation slower as buckets fill; a load factor near 0 wastes memory on slots nobody uses yet. Both designs settle between 0.66 and 0.75, where extra memory stops buying much shorter probes.

Why hash table lookup is O(1) on average, not always

Constant time holds only while hashes spread keys roughly evenly across buckets. Two things break that.

A bad or predictable hash function. If every key you insert hashes to the same bucket, a chaining table degrades into one linked list with O(n) lookup, the exact thing the structure exists to avoid. This happens in production. A server that hashes attacker-controlled input (form field names, HTTP headers, JSON keys) with a predictable function is open to algorithmic complexity attacks: the attacker sends thousands of keys built to collide and forces worst-case behavior on every request. Python has randomized the hash of str and bytes per process since Python 3.3 (controlled by PYTHONHASHSEED) for this reason. The same string hashes differently in two runs of the interpreter, so nobody can precompute a collision set offline.

Mutating a key after it’s inserted. The bucket a key lives in was chosen by its hash, so the table assumes that hash never changes. Python enforces this at the type level: mutable built-ins like list and dict set __hash__ to None, and using one as a key raises TypeError: unhashable type: 'list' before the mistake can happen. Tuples and strings are hashable because they are immutable. For a custom key class, implement __hash__ and __eq__ together and base them only on fields that never change. Otherwise an edited key goes “missing”: the entry is still in the table, sitting in the bucket its old hash pointed to, and the lookup searches somewhere else.

When not to use a hash table

A hash table answers one question fast: does this key exist, and what is its value? Almost everything else it does badly.

  • Range and ordering queries. “All users created this month” or “the next key after this one” need a sorted structure. A hash table has no order. CPython’s dict has guaranteed insertion order since 3.7, but that is iteration order, not sort order, and it does nothing for “everything between X and Y”. That query is what a B-tree does well, which is why most databases default to B-tree indexes over hash indexes. How database indexes work covers the scan-vs-seek tradeoff behind that default.
  • Prefix or fuzzy matching. “Keys starting with user:” means checking every key. A trie, or a sorted structure with binary search, handles it directly.
  • Small integer keys in a tight range. If the key is already a day of the week or an HTTP status class, skip the hash function and index an array directly. One less layer, no collisions.

When a hash table is the right structure, you almost never write one. dict, HashMap, Map and std::unordered_map are already tuned and correct. You also use them indirectly more than you might think: a function wrapped in functools.lru_cache, covered in Python decorators explained, builds a key from the call’s arguments and looks it up in a dict.

So the decision is short. If the operation is “look this up by exact key”, use the built-in hash table and don’t write your own. If the question involves order, ranges or partial matches, pick a sorted structure or a trie from the start, because no hash function fixes a structure that answers the wrong question.