Hash Tables

Why it exists (motivation)

You already know a core tradeoff:

• •Array: O(1) access by index, but if you want “find by name/key”, you don’t have an index—you end up searching O(n).
• •Linear search: works for any key type, but pays O(n) time.

A hash table is a data structure that tries to keep the array’s speed while supporting associative mapping: store and retrieve values by a unique key.

Instead of asking “where is this key in the array?”, we compute where it should go.

Definition

A hash table stores key-value pairs (key → value) using:

1. 1)An underlying array A of size m (often called the number of buckets/slots)
2. 2)A hash function h(key) that maps keys to indices:

• •h(key) → i, where i ∈ {0, 1, 2, …, m−1}

Then we store the pair in A[i] (or in some structure associated with A[i]).

The idealized picture

If every key mapped to a unique index, operations would be trivial:

• •insert(key, value): compute i = h(key), store at A[i]
• •get(key): compute i = h(key), return A[i]

That would be O(1) worst-case. But reality is messier.

Collisions: the central problem

A collision happens when two different keys map to the same index:

• •key₁ ≠ key₂ but h(key₁) = h(key₂)

Collisions are unavoidable because:

• •The set of possible keys can be huge (e.g., all strings)
• •The array has only m slots

By the pigeonhole principle, if you insert more than m distinct keys, at least one collision must occur.

So a hash table is really:

• •An array A
• •Plus a collision-handling strategy

Average-case O(1) (what it really means)

When people say “hash tables have O(1) lookup,” the precise claim is:

• •Expected/average time is O(1) under assumptions about the hash function and table’s load.

The common performance lever is the load factor:

• •α = n / m

where n = number of stored elements, m = number of buckets.

Rough intuition:

• •If α is small, collisions are rare → operations are fast.
• •If α grows large, collisions become frequent → operations slow down.

Hash tables keep α under control by resizing (rehashing) when the table gets too full.

Why hashing works as a strategy

Arrays are fast because indexing is direct. Hashing tries to manufacture an index from a key.

So the goal of h(key) is not “cryptographic security”—it’s:

• •deterministic: same key → same index
• •fast to compute
• •spreads keys out “evenly” across indices

The basic mapping

We typically think of hashing in two stages:

1) Map key to an integer (a hash code):

• •hashCode(key) → large integer

2) Compress that integer into the array range:

• •h(key) = hashCode(key) mod m

So indices always land in 0…m−1.

Determinism and equality

Hash tables assume a consistent relationship between equality and hashing:

• •If key₁ = key₂, then h(key₁) = h(key₂)

The reverse is not required (and generally false):

• •h(key₁) = h(key₂) does not imply key₁ = key₂

That’s exactly collisions.

A concrete example: hashing strings

A common approach is a polynomial rolling hash. For a string s with characters s[0], s[1], …, s[k−1], interpret each character as a number cᵢ (e.g., ASCII code).

One form:

• •hashCode(s) = ∑(i=0…k−1) cᵢ · pᶦ

Then compress:

• •h(s) = (hashCode(s)) mod m

You don’t need to memorize this. The idea is:

• •Each character influences the final number
• •Order matters
• •Small changes in the key tend to change the output a lot

What makes a “good” hash function (practically)

A hash function is “good” for hash tables if it:

• •distributes typical keys uniformly
• •avoids obvious patterns (e.g., many keys mapping to same index)
• •is cheap enough to compute

If h is poor (e.g., always returns 0), performance collapses to O(n).

The role of m (table size)

The modulus m matters. Many implementations choose m carefully (often prime, or a power of 2 with bit-mixing).

What you should remember at difficulty 2:

• •h(key) usually ends with “mod m” or equivalent.
• •if m is small or α is large, collisions increase.

A small derivation: why collisions become likely

Suppose keys distribute uniformly across m buckets.

• •Expected bucket size ≈ n/m = α

That’s not a proof of O(1), but it builds the intuition: average work per bucket is proportional to α.

So keeping α bounded (e.g., α ≤ 0.75) is a strategy to keep operations near constant time.

Collisions are not an edge case—they are the normal case once the table has enough items. Two main families of strategies dominate.

Strategy A: Separate chaining

Idea: A[i] stores a collection (often a linked list, dynamic array, or small balanced tree) of all entries whose keys hash to i.

• •A[i] is called a bucket
• •Each bucket holds 0 or more (key, value) pairs

Operations (high-level):

• •insert(key, value):

1) i = h(key)

2) search bucket A[i] for key

3) if found, update value; else append new pair

• •get(key):

1) i = h(key)

2) search bucket A[i] for matching key

• •delete(key):

1) i = h(key)

2) remove entry from bucket if present

Cost intuition:

• •Hashing to index is O(1)
• •Searching within a bucket costs O(bucket size)
• •Expected bucket size ≈ α

So average time is often described as O(1 + α). If α is kept constant by resizing, that becomes O(1) average.

Strategy B: Open addressing

Idea: Store entries directly in the array. If A[i] is occupied, probe other indices according to a rule until you find an empty slot.

Common probing methods:

• •Linear probing: i, i+1, i+2, … (wrap around mod m)
• •Quadratic probing: i, i+1², i+2², … (mod m)
• •Double hashing: i + j·h₂(key) (mod m)

Cost intuition:

• •No extra lists
• •But performance can degrade when the table becomes crowded

Also, deletion is trickier: you often need a special “tombstone” marker so searches don’t stop early.

Comparison table

At this level, separate chaining is easiest to reason about and is common in teaching.

Resizing (rehashing): keeping α under control

To keep operations fast, hash tables resize when α crosses a threshold.

Typical policy (example):

• •If α > 0.75, allocate a new array A′ with size m′ ≈ 2m
• •Recompute positions for all existing keys:
• •for each entry (key, value): place into A′[h′(key)]

This is called rehashing because h depends on m.

Amortized cost intuition

A resize costs O(n) because you reinsert all elements.

But it happens infrequently (e.g., when the table doubles). Over many inserts, the average extra cost per insert stays small.

You don’t need full amortized analysis yet—just remember:

• •Individual insert can be expensive during resize
• •Over time, average insert remains near O(1)

Common uses

Hash tables appear any time you need fast “lookup by key”:

• •Dictionaries / maps: username → user record
• •Caches: URL → page contents
• •Counting frequencies: word → count
• •Sets: store keys only (value can be a dummy)
• •Graphs: adjacency via map(node → neighbors)

Why they’re so popular

Hash tables hit a sweet spot:

• •Fast average operations
• •Simple API (put/get/delete)
• •Work well for many key types (strings, integers, tuples)

Limitations (important to know)

Hash tables are not always the best choice:

1) No ordering by default

• •Iterating keys comes out in an arbitrary order (some languages preserve insertion order, but that’s an extra feature).

2) Worst-case can be O(n)

• •If many keys collide, buckets become long (or probing becomes long).

3) Prefix/range queries are awkward

• •Example: find all keys starting with "pre"
• •Hash tables don’t group related strings near each other.

Connection to Tries

A trie is a tree specialized for strings (or sequences). It supports operations in O(k) where k = length of the string, and it naturally supports prefix queries.

So the mental transition is:

• •Hash table: fast exact match key → value
• •Trie: fast exact match + fast prefix operations

If your next goal is autocomplete, dictionary prefix search, or storing many strings with shared prefixes, tries are a natural unlock.