Topic 4 · Abstract Data Structures (HL)

Chapter 4 · Going deeper & exam practice

📋 Reference · always available

Dictionary / Hash table

Key→value map. Hash function turns key into bucket index. O(1) average lookup, insert, delete.

Hash function

Deterministic map from key to integer; good ones spread keys evenly across buckets.

Collision

Two keys hash to same bucket. Resolved by chaining (linked list per bucket) or open addressing (probe next slot).

Load factor

items / buckets. Above ~0.7 collisions hurt performance — table resizes (doubles).

Hash table vs BST

Hash = O(1) avg, NO order. BST = O(log n), preserves sorted order. Pick by need.

When to use

Stack: undo / call stack / DFS. Queue: print queue / BFS / scheduling. Hash: keyed lookup. BST: ordered + lookup. Array: random access. Linked list: many inserts.

Space-time trade-off

Hash tables sacrifice MEMORY for SPEED. A recurring pattern in CS — caches, indexes, memoisation are all instances.

Big-O hierarchy

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). At n=10⁶, the gap between O(1) and O(n²) is 10⁶.