Hash tables

How hashing turns a key into a slot, what collisions and load factor do to performance, and what makes a key usable.

From key to slot

A hash table runs the key through a hash function, reduces the result modulo the number of slots, and stores the entry there. That is why lookup, insert and delete are O(1) on average: no searching, just arithmetic and one comparison. When two keys land in the same slot, a collision, the table either probes for the next free slot (open addressing) or walks a chain of entries (separate chaining).

from collections import Counter, defaultdict

words = 'the cat sat on the mat the cat'.split()

# Lookup, insert and delete: O(1) average, O(n) worst case
counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1
print(counts['the'])                    # 3

# The same thing, with the bookkeeping already written
print(Counter(words).most_common(2))

groups = defaultdict(list)
for word in words:
    groups[word[0]].append(word)        # a missing key creates an empty list
print(dict(groups)['c'])

# Membership: a set turns an O(n) scan into an O(1) average test
allowed = set(words)
print('mat' in allowed, 'dog' in allowed)

• Insert and lookup are O(1) on average; if every key collides, the table degrades to a linear scan.
• Resizing doubles the table and rehashes everything, an O(n) operation that happens rarely enough to amortise to O(1) per insert.
• Open addressing (used by Python's dict) keeps entries in the table itself, which is cache-friendly; separate chaining stores a list per slot and tolerates a higher load factor.
• Deletion in an open-addressed table cannot simply blank a slot, because that would break probe chains, so entries are tombstoned.
• dict.fromkeys(keys) builds a table with the same value for every key, which is the fastest way to deduplicate while keeping order.

Collisions, load factor and keys

class Point:
    __slots__ = ('x', 'y')

    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))       # must be consistent with __eq__

    def __eq__(self, other):
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)

    def __repr__(self):
        return 'Point(%r, %r)' % (self.x, self.y)

seen = {Point(1, 2)}
print(Point(1, 2) in seen)                  # True: equal and equally hashed

# A mutable key breaks the table: the entry stays in its old slot
coords = [1, 2]
d = {}
d[tuple(coords)] = 'ok'                     # tuples are safe
# d[coords] = 'bad'                         # TypeError: unhashable type: 'list'

# NaN is hashable but never equal to itself, so it can be lost
bad = {float('nan'): 1}
print(bad.get(float('nan')))                # None, despite the key being present

# Custom hash functions must be cheap and spread keys out
class AlwaysSame:
    def __hash__(self):
        return 0                            # every key collides: O(n) per lookup

    def __eq__(self, other):
        return isinstance(other, AlwaysSame)

When a hash table is the wrong choice

import bisect
from collections import OrderedDict

# Need order or ranges: a hash table cannot answer either
d = {'b': 2, 'a': 1}                  # insertion order is preserved, but not sorted
print(list(d))                        # ['b', 'a'] - insertion, not sorted

# Sorted keys with balanced-tree-like search: keep a sorted list of keys
keys, values = [], {}
def put(k, v):
    values[k] = v
    i = bisect.bisect_left(keys, k)
    if i == len(keys) or keys[i] != k:
        keys.insert(i, k)             # O(n) insert: fine for small, static sets

def range_query(lo, hi):
    left = bisect.bisect_left(keys, lo)
    right = bisect.bisect_right(keys, hi)
    return [(k, values[k]) for k in keys[left:right]]

put('m', 1)
put('a', 2)
put('z', 3)
print(keys, range_query('a', 'm'))

# Counting and ordering in one pass: hash for tally, heap for the top-k
import heapq
tally = Counter('mississippi')
print(heapq.nlargest(2, tally, key=tally.get))

• Ordered iteration by key: use a sorted structure or a B+tree, not a hash table.
• Range queries such as "all rows between these dates": hash tables cannot localise a range, so the whole table would be scanned.
• Repeated nearest-neighbour or similarity search: a hash function destroys locality, unless you use a locality-sensitive hash designed for it.
• Keys with a terrible hash: a deliberately colliding hash function turns every operation into a scan, and it is a denial-of-service vector for user-supplied keys.
• Very small collections: a linear scan of five items is faster than hashing each one, which is why production implementations switch to a list below a threshold.

Python's dict keeps insertion order as an implementation guarantee since 3.7. That is not sorted order, and it is not a substitute for a tree: you can rely on iteration matching insertion, but you cannot ask for a range of keys efficiently.

FAQ

Related

Trees and choosing a structure Arrays, linked lists, stacks and queues

Last refreshed 2026-09-18.