The Dictionary Problem | Algorithms I

The Dictionary ADT

A dictionary (also called a map or associative array) stores a set of (key, value) pairs and supports three core operations:

INSERT(key, value): add a new pair, or update the value if key already exists.
DELETE(key): remove the pair with the given key.
SEARCH(key): return the value associated with the key, or indicate absence.

The dictionary is one of the most fundamental abstract data types in computing. It underpins symbol tables in compilers, routing tables in networks, caches in operating systems, and database indices.

Naive Implementations

Unsorted Array

Keep pairs in an array in any order.

INSERT: append to end, $O(1)$ .
SEARCH: linear scan, $O(n)$ .
DELETE: find then remove (or mark as deleted), $O(n)$ .

Sorted Array

Keep pairs sorted by key. SEARCH uses binary search: $O(\log n)$ . But INSERT requires shifting elements to maintain sorted order: $O(n)$ . DELETE also $O(n)$ .

Balanced BST (e.g. Red-Black Tree)

All three operations in $O(\log n)$ . This is the best worst-case guarantee among comparison-based structures.

The Hash Table Promise

Hash tables aim for $O(1)$ expected time for all three operations. The core idea: compute an array index directly from the key using a hash function, then store the pair at that position.

Given key "Cambridge", compute h("Cambridge") = 3, and store the value at table slot T[3]. Future searches for "Cambridge" go directly to slot 3 without comparing against other keys (unless there is a collision).

The Inevitability of Collisions

By the pigeonhole principle: the number of possible keys vastly exceeds the number of table slots. Even for integer keys: if UUIDs (128-bit) are keys and the table has $10^6$ slots, $2^{128}$ keys map into $10^6$ slots; many keys must share the same index.

A collision occurs when two distinct keys $k_1 \neq k_2$ produce the same hash value: $h(k_1) = h(k_2)$ . Collision resolution is the central design challenge of hash tables.

Key Design Decisions

Building an effective hash table requires choosing:

Hash function: maps keys to table indices. Must be fast to compute and produce a uniform distribution across the table.
Collision resolution strategy: what to do when two keys map to the same slot. Two main families: chaining (linked lists per slot) and open addressing (probing for an empty slot).
Load factor management: when to grow (or shrink) the table to maintain performance.

Example: Collision in Practice

Hash function $h(k) = k \bmod 10$ , table size $m = 10$ .

INSERT(23, "Alice"):  h(23) = 3  → T[3] = ("Alice")
INSERT(47, "Bob"):    h(47) = 7  → T[7] = ("Bob")
INSERT(13, "Carol"):  h(13) = 3  → COLLISION with Alice!

The hash table must now resolve what happens at slot 3. With chaining, both entries live in a linked list at T[3]. With open addressing, Carol probes for the next empty slot.

Summary

Implementation	INSERT	SEARCH	DELETE
Unsorted array	$O(1)$	$O(n)$	$O(n)$
Sorted array	$O(n)$	$O(\log n)$	$O(n)$
Balanced BST	$O(\log n)$	$O(\log n)$	$O(\log n)$
Hash table (expected)	$O(1)$	$O(1)$	$O(1)$
Collision	Two keys map to same slot
Load factor $\alpha$	$\alpha = n/m$ , $n$ keys, $m$ slots