A hash table (also called a hash map) is a data structure that stores key-value pairs. It uses a hash function to compute an index (the hash value) into an array of buckets, from which the desired value can be found. Goal: O(1) average-case lookup.
A hash function takes a key and returns an integer index within the table size.
// Simple modulo hash function: hash(key) = key MOD tableSize // Example: tableSize = 10 hash(23) = 23 MOD 10 = 3 → store at index 3 hash(47) = 47 MOD 10 = 7 → store at index 7 hash(33) = 33 MOD 10 = 3 → COLLISION! index 3 already used
A good hash function: fast to compute, distributes keys uniformly, minimises collisions.
A collision occurs when two different keys produce the same hash value (same index). Collisions are inevitable — the hash function maps a large key space to a small index space.
If the desired slot is occupied, check the next slot sequentially until an empty slot is found.
// Linear probing with tableSize = 10 hash(23) = 3 → store at index 3 hash(33) = 3 → index 3 occupied, try 4 → store at index 4 hash(43) = 3 → index 3 occupied, try 4 occupied, try 5 → store at index 5
Problem: clustering — long sequences of filled slots form, degrading performance.
Each slot in the table holds a linked list (or another structure). Colliding items are added to the same list.
// Chaining: index 3 → [23] → [33] → [43] → null
Advantage: table never "fills up". Disadvantage: extra memory for linked lists; cache-unfriendly.
| Operation | Average | Worst case |
|---|---|---|
| Search | O(1) | O(n) — if many collisions |
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |
8 questions · instantly marked · AQA 7517 standard
| Term | Definition |
|---|
10 questions · 10 minutes