OCR H446 · A Level Computer Science · ~12 min read
Notes
Video
Slides
Worksheet
Quiz
What is a Hash Table?
A hash table (or hash map) is a data structure that maps keys to values using a hash function. The hash function converts a key into an index (bucket/slot) in an array, enabling near-O(1) average-case lookup, insertion, and deletion.
Hash tables power Python dictionaries, Java HashMaps, databases (index lookup), caches, sets, and symbol tables in compilers.
The Hash Function
A hash function takes a key and returns an integer index (hash value) in the range [0, table_size − 1].
-- Simple modular hash function:
hash(key) = key mod table_size
-- Example: table_size = 10
hash(23) = 23 mod 10 = 3 -- store at index 3
hash(47) = 47 mod 10 = 7 -- store at index 7
hash(83) = 83 mod 10 = 3 -- COLLISION with 23!
Properties of a Good Hash Function
Deterministic: same key always produces the same hash value
Uniform distribution: keys spread evenly across all buckets
Fast to compute: O(1) computation
Minimises collisions: different keys rarely map to the same index
Collisions
A collision occurs when two different keys hash to the same index. Collisions are inevitable for any sufficiently large set of keys (Pigeonhole Principle). Two main strategies resolve collisions:
1. Open Addressing (Linear Probing)
When a collision occurs, probe subsequent slots in the array until an empty slot is found:
-- Linear probing: if slot h is taken, try h+1, h+2, ...
Insert 83, table_size=10, 23 already at index 3:
hash(83) = 3 → slot 3 taken
try slot 4 → empty → store 83 at index 4
Drawback:primary clustering — occupied slots clump together, slowing future insertions and lookups near the cluster.
2. Chaining (Separate Chaining)
Each bucket holds a linked list (or another dynamic structure). All keys that hash to the same index are stored in the same bucket's list:
-- Chaining: each slot holds a list
Index 3: [23] → [83] → null
Index 7: [47] → null
Advantage: no clustering; table never "fills up" (can exceed n slots). Drawback: extra memory for pointers; poor cache performance for long chains.
Load Factor
The load factor (α) = n / m where n = number of items stored and m = table size.
Low load factor (α < 0.7): few collisions, fast lookup
High load factor (α > 0.9): many collisions, degraded performance
When load factor exceeds a threshold, the table is rehashed — a new larger table is allocated and all items are reinserted
Hash Table Complexity
Operation
Average Case
Worst Case
Search
O(1)
O(n)
Insert
O(1)
O(n)
Delete
O(1)
O(n)
Worst case O(n) occurs when all keys hash to the same bucket (all in one chain or one long probe sequence) — effectively a linear search. With a good hash function and reasonable load factor, O(1) average is achievable.
Worked Example: Inserting into a Hash Table
-- Table size = 7, hash(k) = k mod 7-- Insert: 10, 22, 31, 4, 15
hash(10) = 10 mod 7 = 3 → store at [3]
hash(22) = 22 mod 7 = 1 → store at [1]
hash(31) = 31 mod 7 = 3 → COLLISION! [3] has 10
Linear probe: try [4] → empty → store 31 at [4]
hash(4) = 4 mod 7 = 4 → COLLISION! [4] has 31
Linear probe: try [5] → empty → store 4 at [5]
hash(15) = 15 mod 7 = 1 → COLLISION! [1] has 22
Linear probe: try [2] → empty → store 15 at [2]
Final table:
[0] empty
[1] 22
[2] 15
[3] 10
[4] 31
[5] 4
[6] empty
Database indexing: hash index for exact-match queries
Caching: cache key → cached value mapping
Symbol tables: compiler stores variable names and their attributes
Sets: fast membership testing
Cryptographic hashing: password storage (SHA-256 etc.) — note: these are one-way hash functions, different from hash table functions
Exam tip: The two main collision resolution methods are (1) open addressing / linear probing and (2) chaining / separate chaining. Know how to trace through insertions using linear probing, showing each probe step.
Exam tip: Hash tables give O(1) average for search, insert, delete — faster than BST O(log n). BUT hash tables do not maintain sorted order. BSTs support in-order traversal for sorted output; hash tables do not. Exam questions often compare these two.
⚠ Common Mistakes
Saying hash tables are always O(1) — worst case is O(n) when all keys collide.
Confusing hashing (for hash tables) with cryptographic hashing (for security) — they share the concept but serve different purposes.
Forgetting to apply modulo to stay within the table bounds when tracing linear probing.
✓ Notes completed!
▶
Video coming soon
Click to advance · Arrow keys also work
Click slide or press arrow keys to navigate
✍
Worksheet — 1.4.2e Hash Tables
8 questions · 20 marks · instantly marked
Q1Explain what a hash table is and what role the hash function plays.[3 marks]
✓ Mark scheme
A hash table is a data structure that maps keys to values using a hash function, storing items in an array for fast access [1]. The hash function takes a key as input and returns an integer index (hash value) that determines where in the array the key-value pair is stored [1]. This allows O(1) average-case lookup: to find an item, compute its hash and go directly to that index [1].
Q2Using the hash function h(k) = k mod 7, insert the following values into a hash table of size 7 using linear probing: 14, 9, 21, 2, 16. Show the final state of the table.[5 marks]
Q3What is a collision in a hash table? Explain why collisions are inevitable for large datasets.[3 marks]
✓ Mark scheme
A collision occurs when two different keys produce the same hash value, mapping to the same index in the table [1]. Collisions are inevitable because the number of possible keys (e.g. all strings) far exceeds the number of slots in the table [1]. By the Pigeonhole Principle, if you have more items than slots, at least two items must share a slot — even a perfect hash function cannot avoid this when n > m [1].
Q4Compare linear probing and separate chaining as collision resolution strategies. Give one advantage and one disadvantage of each.[4 marks]
✓ Mark scheme
Linear probing: Advantage — all data stored in the main array; good cache performance [1]. Disadvantage — primary clustering: occupied slots clump together, increasing probe sequences for future inserts/lookups in that area [1]. Chaining: Advantage — no clustering; easy to handle high load factors as chains simply grow [1]. Disadvantage — extra memory for linked list pointers; poor cache performance as nodes may be scattered in memory [1].
Q5State the average and worst-case time complexity for search in a hash table, and explain what causes the worst case.[3 marks]
✓ Mark scheme
Average: O(1) — hash function directly computes the index, so lookup requires typically one memory access [1]. Worst: O(n) [1] — occurs when all n keys hash to the same index; with chaining, one bucket holds a chain of n items (linear search through all); with linear probing, one long probe sequence through all slots [1].
Q6Define 'load factor' in the context of hash tables. What happens when the load factor becomes too high?[2 marks]
✓ Mark scheme
Load factor α = n / m (number of items / table size) — measures how 'full' the table is [1]. When load factor exceeds a threshold (typically 0.7–0.75), performance degrades due to increased collisions. The table is rehashed: a new larger table is allocated and all items are reinserted using the new hash function [1].
Q7Give two real-world computing applications that use hash tables.[2 marks]
✓ Mark scheme
Any two of [1 each]: Python dictionary / Java HashMap — fast key-value storage; compiler symbol table — maps variable names to their types/addresses; database hash index — fast exact-match queries; web cache — URL to cached page; password storage — hashed password lookup; sets for O(1) membership testing.
Q8State four properties of a good hash function.[4 marks]
✓ Mark scheme
Any four of [1 each]: Deterministic — same key always produces same hash; Uniform distribution — keys spread evenly across all buckets to minimise collisions; Fast to compute — ideally O(1); Minimises collisions — different keys rarely map to same index; Outputs values in valid range [0, table_size − 1]; Sensitive to small changes in key (avalanche effect).
Topic Quiz
1 of 15
You scored
out of 15
🎯
Mini Test — 1.4.2e Hash Tables
10 questions · 10 marks · 10 minutes
5 MCQ + 5 short answer
⏱10:00
10 marks
Section A — Multiple Choice
Q1What is the average-case time complexity for lookup in a hash table?
Q2Using h(k) = k mod 10, what is h(73)?
Q3Which collision resolution technique uses a linked list at each bucket?
Q4What is the load factor of a hash table with 100 slots and 70 items stored?
Q5What is 'primary clustering' in the context of hash tables?
Section B — Short Answer
Q6Define a 'collision' in a hash table.
Mark schemeA collision occurs when two different keys produce the same hash value and therefore map to the same index/bucket in the hash table. Collisions require a resolution strategy to handle the conflicting insertions. [1 mark]
Q7Describe how linear probing resolves a collision.
Mark schemeWhen a collision occurs (the target slot is occupied), linear probing checks the next slot (index + 1), then the next (index + 2), and so on (wrapping around if necessary using modulo) until an empty slot is found, where the item is stored. [1 mark]
Q8What is rehashing?
Mark schemeRehashing is the process of creating a new, larger hash table (typically double the size) and reinserting all existing items using a new hash function. This is done when the load factor exceeds a threshold, to restore efficient O(1) performance. [1 mark]
Q9Give one advantage of a hash table over a Binary Search Tree for lookup.
Mark schemeHash tables provide O(1) average-case lookup, which is faster than BST's O(log n) average. For exact-match key lookups (not range queries), hash tables are significantly faster. [1 mark]
Q10State one property of a good hash function.
Mark schemeAny one of: deterministic (same key always gives same hash); uniform distribution (keys spread evenly across table); fast O(1) computation; minimises collisions. [1 mark]