Skip to content

Hashing#

Hash tables map keys to values using a hash function to index into an array. Average-case O(1) lookup, insert, and delete make them the default tool for frequency counting, caching, and deduplication in interviews.

When to use hashing#

Scenario Structure
Count occurrences dict or Counter
Check if seen before set
Group items by key defaultdict(list)
O(1) lookup by arbitrary key dict
Two-sum style complement lookup dict while scanning
Graph adjacency (sparse) dict of lists

Avoid hashing when: you need sorted order (use BST or sort), range queries on keys (use segment tree / sorted structure), or prefix matching on strings (use trie).

Complexity#

Operation Average Worst case
Insert O(1) O(n)
Search O(1) O(n)
Delete O(1) O(n)
Space O(n) O(n)

Worst case occurs when many keys collide into the same bucket (adversarial inputs or poor hash function). Python's dict and set use open addressing with a high-quality hash and resize when load factor grows — worst case is rare in practice.

Hash table with separate chaining

Open addressing with linear probing

How hashing works#

  1. Hash function h(key) → integer index in [0, table_size).
  2. Store (key, value) at that index (or in a chain at that index).
  3. Lookup: compute h(key), probe bucket, compare keys (must handle collisions).

Load factor α = n / table_size. When α is too high, resize and rehash (Python dicts do this automatically).

Python built-ins (use these in interviews)#

Dictionary#

freq: dict[str, int] = {}
for word in words:
    freq[word] = freq.get(word, 0) + 1

# membership is by key
if target in index_map:
    ...

Set#

visited: set[tuple[int, int]] = set()
if (r, c) in visited:
    continue
visited.add((r, c))

defaultdict and Counter#

from collections import defaultdict, Counter

graph = defaultdict(list)
graph[u].append(v)

counts = Counter(nums)          # element → frequency
most_common = counts.most_common(3)

Time: same as dict — O(1) average per operation.
Space: O(n) for n stored keys.

When to pick which#

Type Keys Values Duplicates
dict unique any keys unique
set unique none no
defaultdict unique default factory keys unique
Counter unique integer counts multiset semantics

Hash collisions#

Two keys can map to the same index. Resolution strategies:

Strategy Idea Trade-off
Chaining Each bucket is a list of entries Simple; extra pointer overhead
Open addressing Probe to next empty slot (linear, quadratic, double hashing) Cache-friendly; clustering possible

Python 3.7+ dict uses open addressing (not chaining). Understanding chaining below still helps whiteboard questions.

Implementation: separate chaining#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class HashTableChaining:
    def __init__(self, size: int = 11):
        self.size = size
        self.table: list[list[tuple]] = [[] for _ in range(size)]

    def _hash(self, key) -> int:
        return hash(key) % self.size

    def insert(self, key, value) -> None:
        idx = self._hash(key)
        for i, (k, _) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        self.table[idx].append((key, value))

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

    def remove(self, key) -> bool:
        idx = self._hash(key)
        for i, (k, _) in enumerate(self.table[idx]):
            if k == key:
                del self.table[idx][i]
                return True
        return False

Time: O(1) average if load factor bounded and hash spreads keys; O(n) worst if all keys collide.
Space: O(n + table_size).

Implementation: open addressing (linear probing)#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class HashTableLinearProbing:
    def __init__(self, size: int = 11):
        self.size = size
        self.table: list[tuple | None] = [None] * size
        self.count = 0

    def _hash(self, key) -> int:
        return hash(key) % self.size

    def insert(self, key, value) -> None:
        if self.count / self.size >= 0.7:
            self._resize()
        idx = self._hash(key)
        start = idx
        while self.table[idx] is not None:
            if self.table[idx][0] == key:
                self.table[idx] = (key, value)
                return
            idx = (idx + 1) % self.size
            if idx == start:
                raise OverflowError("table full")
        self.table[idx] = (key, value)
        self.count += 1

    def get(self, key):
        idx = self._hash(key)
        start = idx
        while self.table[idx] is not None:
            if self.table[idx][0] == key:
                return self.table[idx][1]
            idx = (idx + 1) % self.size
            if idx == start:
                break
        return None

    def _resize(self) -> None:
        old = self.table
        self.size = self._next_prime(self.size * 2)
        self.table = [None] * self.size
        self.count = 0
        for item in old:
            if item is not None:
                self.insert(item[0], item[1])

    def _next_prime(self, n: int) -> int:
        while any(n % i == 0 for i in range(2, int(n ** 0.5) + 1)):
            n += 1
        return n

Time: O(1) average with low load factor; degrades as table fills (clustering).
Space: O(table_size).

Hash function properties (conceptual)#

A good hash function should:

  • Spread keys uniformly across buckets
  • Be deterministic (same key → same index)
  • Be O(1) to compute

Built-in hash() in Python is salted per process (not stable across runs) — fine for dicts, not for serializing hash values.

Hashing vs other structures#

Need Use
Exact key lookup, no order Hash map / set
Sorted keys, predecessor/successor BST or sorted array + binary search
String prefixes Trie
Priority by value Heap