What is a hash table?
A hash table is a data structure that maps keys to values. A hashing algorithm turns each key into an index (a slot) in the table, so items can be stored and found quickly. A collision happens when two keys give the same hash. It is handled by rehashing, for example by checking the next free slot. Example: Table size 7, hash = key MOD 7. Insert 15, 22, 9. 15 MOD 7 = 1 β slot 1 22 MOD 7 = 1 β collision, rehash to slot 2 9 MOD 7 = 2 β collision, rehash to slot 3 Answer: 15 in slot 1, 22 in slot 2, 9 in slot 3.
AQA A-level Computer Science expects you to know what a hash table is, apply simple hashing algorithms, and explain collisions and how rehashing handles them. Hash tables give fast average look-up because the index is calculated directly rather than searched for. A good hash function spreads keys evenly to reduce collisions.
Worked example
A hash table has 7 slots (0 to 6). The hash function is key MOD 7, and collisions are handled by moving to the next free slot. Insert the keys 15, 22 and 9 in that order.
- Insert 15: 15 MOD 7 = 1. Slot 1 is empty, so store 15 in slot 1.
- Insert 22: 22 MOD 7 = 1. Slot 1 is full (collision), so rehash to slot 2.
- Insert 9: 9 MOD 7 = 2. Slot 2 is full (collision), so rehash to slot 3.
- To search for 9 later, hash to slot 2, then probe forward until 9 or an empty slot is found.
Answer: 15 is stored in slot 1, 22 in slot 2 and 9 in slot 3.
Want one-to-one help? Find an online Computer Science tutor with ExpertTutor.
Want one-to-one support?
One-to-one online tuition can help you build confidence in your subject. Find a tutor who teaches your course.
Find a TutorLearn face to face in Glasgow
Prefer in-person lessons? Visit the ExpertTutor Glasgow Southside centre.
See the centre