Hash Tables | OCR H446

Learning Objectives

By the end of this topic you will be able to:

Explain how a hash table stores data using a hash function

Describe what a collision is and methods for resolving collisions

Evaluate the efficiency of hash tables compared to other structures

Give real-world applications of hash tables

Hash Tables

How Hash Tables Work

A hash table is a data structure that maps keys to values using a hash function. The hash function takes the key and computes an index (address) in an array where the value is stored. This allows O(1) average-case insertion, deletion, and lookup.

Hash function example: to store a student ID, compute hash = ID mod table_size. The result is the index in the table array where the record is stored.

Example: table size = 11. Key = 79. Hash = 79 mod 11 = 2. Store at index 2. To retrieve: apply the same hash function — directly jump to index 2, no searching required.

Collisions

Collisions and Resolution

A collision occurs when two different keys hash to the same index. Since arrays can only store one item per slot, a collision handling strategy is required.

Open Addressing (Linear Probing)

If the hash index is already occupied, try the next slot (index+1), then index+2, and so on until an empty slot is found. Simple but can cause clustering — long runs of filled slots that slow down operations.

Chaining

Each table index holds a linked list. All items with the same hash are stored in the list at that index. No limit on items per slot, but memory overhead of pointers. Works well with high load factors.

Efficiency

Efficiency and Applications

Average case: O(1) for insert, search and delete — makes hash tables the fastest lookup structure in practice. No need to scan through items as in linear search, or traverse a path as in BSTs.

Worst case: O(n) if all keys hash to the same index (every lookup degenerates to scanning a list). A good hash function distributes keys uniformly to avoid this.

Applications: database indexing · symbol tables in compilers · password storage (store hash of password, not password itself) · caches (DNS, browser) · Python dictionaries · sets in most languages

Exam Practice

OCR H446 Style · 4 marks

A hash table of size 7 uses the hash function h(k) = k mod 7. Insert the keys 14, 22, 9, 30, 5 in order. Show the final state of the table, explaining how any collision is handled using linear probing.

[4 marks]

Hashes: 14→0, 22→1, 9→2, 30→2 (collision! → probe next empty: index 3), 5→5. Table: [0:14, 1:22, 2:9, 3:30, 4:-, 5:5, 6:-]

Collision for 30: h(30)=2 but index 2 is occupied by 9. Linear probing: try index 3 — empty, so 30 is stored at index 3.

To search for 30: compute h(30)=2, check index 2 (value is 9, not 30) → probe index 3 (value is 30) → found in 2 comparisons.

Common Mistakes

Don't Lose Marks

Saying hash tables always give O(1) search — O(1) is the average case. The worst case (all keys colliding) is O(n). OCR exam answers must state "average case O(1)" — not just "O(1)" — to be precise.

Not continuing the linear probe wrap-around — when probing reaches the end of the table, it should wrap around to index 0. Forgetting this and saying "no space" when empty slots exist at the start of the table is incorrect.

Confusing hashing for storage with hashing for security — hash tables use hash functions for fast data access (not security). Cryptographic hashes (SHA-256, bcrypt) are one-way and used for password storage. These are different contexts — don't mix them up in answers.