HashingData structureaka hash, associative array, dictionary

Hash Table

An array of buckets indexed by a hash of the key, giving expected O(1) insert, lookup, and delete.

▶ Visualize Pattern: Hashing Practice (6)

Progress

Definition

A hash table maps keys to values by computing h = hash(key) mod capacity and storing the entry in bucket h. Because the bucket index is computed rather than searched for, lookups take expected O(1) time, independent of the number of stored keys.

Two keys can hash to the same bucket — a collision. Every hash table must resolve them, either by Separate Chaining (each bucket holds a linked list) or by Open Addressing (probe other slots in the same array). See Collision Handling.

The ratio load factor = n / capacity governs performance. When it exceeds a threshold (0.75 for Java HashMap, ~0.67 for CPython dicts), the table resizes to a larger capacity and rehashes every entry. Resizing costs O(n) but happens rarely enough that inserts remain O(1) amortized.

Hash Map and Hash Set are the two interfaces built on this structure: a map stores key → value pairs, a set stores keys only.

O(1) averagehash functionbucketsload factorunordered

Intuition

A mental model before the formal terms.

A coat check with numbered hooks. Instead of searching every hook for your coat, the attendant computes a hook number from your ticket and walks straight to it. If two tickets map to the same hook, the attendant hangs both coats there and checks the tags (chaining), or uses the next free hook (open addressing).

The hash function is a "random-looking" but deterministic scatter: similar keys should land in unrelated buckets so no bucket becomes crowded.

How it works

Allocate an array of capacity buckets (a power of two or a prime).
Compute idx = hash(key) & (capacity - 1) (or % capacity).
put(key, value): go to bucket idx; if the key exists, overwrite; otherwise append a new entry. Increment size.
get(key): go to bucket idx and compare keys with equals until found or the chain/probe ends.
remove(key): locate the entry as in get and unlink it (chaining) or mark it deleted (open addressing).
After an insert, if size / capacity > maxLoad, double the capacity and reinsert every entry (rehash).

Why it works

If the hash function distributes keys uniformly, the expected chain length is the load factor α = n / m. With α bounded by a constant, expected work per operation is O(1 + α) = O(1).

Doubling on resize spreads the O(n) rehash over the n/2 inserts that preceded it, giving O(1) amortized insert.

The worst case is O(n) when all keys collide — mitigated by good hash functions, randomized seeds (hash flooding defence), and, in Java 8+, converting long chains to red-black trees.

Operations

Operation	Description	Cost
put(key, value)	Insert or overwrite the value for key.	O(1) average
get(key)	Return the value for key or absent.	O(1) average
remove(key)	Delete the entry for key.	O(1) average
contains(key)	Membership test.	O(1) average
resize()	Double capacity and rehash all entries.	O(n)
iterate	Visit every entry in arbitrary order.	O(n + capacity)

Recognition

How to tell a problem wants this.

You need to check membership, count occurrences, or look up by key in O(1).
The problem says "find two elements that sum to…", "group by…", "first unique/duplicate…", "have we seen this before?".
Constraints of n ≤ 10^5 or more with a nested-loop brute force suggest replacing the inner loop with a hash lookup.
Keys are unordered and no range queries are required.

“have you seen this before” → Hashing

Interactive demo

Play, step, change the input. ← → and space work too.

Commands — insert N, search N, delete N — m = 7 buckets, hash = key % 7

∅

bucket 0

∅

bucket 1

∅

bucket 2

∅

bucket 3

∅

bucket 4

∅

bucket 5

∅

bucket 6

∅

1/41Empty table with m = 7 buckets. Colliding keys share a bucket as a linked chain, so the table never "fills up" — only the chains grow.

Hashed bucketChain node comparedMatchInserted / removed

PseudocodeLearn Hash Table →

1h = key % m
2insert: scan bucket[h]; if key present: done, else append to the chain
3search: scan bucket[h] comparing each key
4delete: scan bucket[h]; unlink the matching node

Variables

size0

load0.00

Complexity

access O(1)

search O(1)

insert O(1)

delete O(1)

Speed

Pseudocode

1class HashTable:
2  buckets = array of capacity empty lists; size = 0
3  index(key): return hash(key) mod capacity
4  put(k, v): b = buckets[index(k)]; for e in b: if e.key == k: e.val = v; return
5             b.append((k, v)); size++; if size > 0.75 * capacity: resize()
6  get(k): for e in buckets[index(k)]: if e.key == k: return e.val; return null
7  remove(k): b = buckets[index(k)]; unlink entry with key k; size--
8  resize(): old = buckets; capacity *= 2; buckets = new array; reinsert all entries of old

Implementation

1from typing import Generic, Hashable, Optional, TypeVar
2 
3K = TypeVar("K", bound=Hashable)
4V = TypeVar("V")
5 
6 
7class HashTable(Generic[K, V]):
8    """Chained hash table with a 0.75 load-factor resize (dict does this for you)."""
9 
101 · Storage and hash
11    def __init__(self, capacity: int = 8) -> None:
12        self._buckets: list[list[tuple[K, V]]] = [[] for _ in range(capacity)]
13        self._size = 0
14 
15    def _index(self, key: K) -> int:
16        return hash(key) % len(self._buckets)  # Python's % is never negative
17 
182 · Put (update or append)
19    def put(self, key: K, value: V) -> None:
20        bucket = self._buckets[self._index(key)]
21        for i, (k, _) in enumerate(bucket):
22            if k == key:
23                bucket[i] = (key, value)
24                return
25        bucket.append((key, value))
26        self._size += 1
27        if self._size > 0.75 * len(self._buckets):
28            self._resize()
29 
303 · Get and contains
31    def get(self, key: K, default: Optional[V] = None) -> Optional[V]:
32        for k, v in self._buckets[self._index(key)]:
33            if k == key:
34                return v
35        return default
36 
37    def __contains__(self, key: K) -> bool:
38        return any(k == key for k, _ in self._buckets[self._index(key)])
39 
404 · Remove
41    def remove(self, key: K) -> bool:
42        bucket = self._buckets[self._index(key)]
43        for i, (k, _) in enumerate(bucket):
44            if k == key:
45                bucket.pop(i)
46                self._size -= 1
47                return True
48        return False
49 
50    def __len__(self) -> int:
51        return self._size
52 
535 · Resize (rehash every entry)
54    def _resize(self) -> None:
55        old = self._buckets
56        self._buckets = [[] for _ in range(len(old) * 2)]
57        self._size = 0
58        for bucket in old:
59            for k, v in bucket:
60                self.put(k, v)

Walkthrough

hash(key) works for any hashable key; Python's % always returns a non-negative result so the index is valid.
put replaces the tuple in place when the key already exists, otherwise appends and checks the load factor.
get mirrors dict.get with a default; __contains__ enables the in operator.
remove pops the tuple out of the bucket list.
_resize doubles the bucket list and reinserts through put.

Complexity (this implementation)

time O(1) average, O(n) worst per operation · space O(n + capacity)

Tuples are immutable, so updating means replacing the tuple (cheap).

Language notes

dict is a highly tuned open-addressing hash table that also preserves insertion order (3.7+); use it unless asked to build one.
Keys must be hashable: tuples of immutables yes, lists and dicts no.
Defining __eq__ without __hash__ makes a class unhashable.

Common mistakes in this language

Using a list as a key (TypeError: unhashable type).
Relying on hash() of strings being stable across runs — it is randomized per process.
Mutating the table inside a for k in table loop.

Language differences that matter here

C++ std::unordered_map and this class use separate chaining; Python dict uses open addressing — both are O(1) average.
Iteration order: Python dict and JS Map are insertion-ordered; C++ unordered_map order is unspecified and changes on rehash.
JS objects coerce keys to strings; Map keeps key types (1 and "1" are different keys).
Negative modulus: Python % is always non-negative; C++ and JS need unsigned hashes (size_t, >>> 0).

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(n)	By key; no positional access.
Search	O(1)	O(n)	Worst case when all keys collide.
Insert	O(1)	O(n)	Amortized; O(n) on resize or full collision.
Delete	O(1)	O(n)
Update	O(1)	O(n)
Resize / rehash	O(n)	O(n)
Iterate	O(n + m)	O(n + m)	m = capacity.
Space	O(n)		Actual memory is O(capacity) ≈ n / load factor plus per-entry overhead.

Advantages & disadvantages

Advantages

Expected O(1) for insert, lookup, and delete — the fastest general-purpose dictionary.
Works with any hashable key type: strings, integers, tuples, custom objects.
Built into every mainstream language with highly tuned implementations.

Disadvantages

No ordering: cannot answer min/max, predecessor, or range queries.
Worst-case O(n) under adversarial or poorly distributed keys.
Memory overhead from empty buckets and per-entry metadata; resizes cause latency spikes.
Iteration order is unspecified (except insertion-ordered implementations such as Python 3.7+ dicts and LinkedHashMap).

Use cases

Symbol tables in compilers and interpreters.
Caches and memoization tables (Memoization (Top-Down DP), LRU Cache).
Counting frequencies, deduplication, indexing by id.
Database indexes for equality lookups, sets in graph algorithms (visited sets).

Use it when

Fast key-based lookup, insertion, and deletion with no ordering requirement.
Counting, deduplicating, grouping, or caching.
Replacing an O(n) inner search loop with an O(1) lookup.

Avoid it when

You need ordered iteration, min/max, floor/ceiling, or range queries — use a balanced BST (AVL Tree, Red-Black Tree) or a sorted array with Binary Search.
Keys are small dense integers — a plain Array indexed by key is faster and smaller.
Prefix queries on strings — use a Trie.
Hard real-time constraints where an O(n) resize spike is unacceptable (use incremental rehashing or pre-size).

Alternatives

Array Binary Search Tree AVL Tree Trie Bloom Filter

Common mistakes

Using a mutable object as a key (a list in Python, an object whose hashCode depends on mutable fields in Java) — the entry becomes unreachable after mutation.
Overriding equals without hashCode (Java) or __eq__ without __hash__ (Python) — equal keys land in different buckets.
Applying % to a negative hash in Java/C++/Go, yielding a negative index; mask with & 0x7fffffff first.
Modifying the table while iterating over it.
Assuming O(1) under adversarial input in security-sensitive code — use a seeded hash.

Interview patterns

Two Sum: store value → index, check target - x before inserting x.
Group Anagrams: key by sorted string or 26-letter count tuple.
Longest consecutive sequence: put all numbers in a set, extend runs only from numbers with no predecessor.
Design HashMap from scratch: array of buckets with chaining, explain the load factor and resize policy.

Interview questions on this