AQA 7517 4.2.6.1: Hash tables
The free BugBot lesson that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
BugBot sees a marker and needs to know where on the mat that marker is. With 1,000 markers in a list, a linear search could take 1,000 comparisons; a binary search on a sorted list takes about 10. A hash table usually takes one. It works out where a record should be from the key itself, and goes straight there.
- The idea
- Good hashing functions
- Collisions
- Load factor and resizing
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A3.5 Hash tables Data structures
Hashing functions, collisions, rehashing by probing, chaining and load factor: finding markers fast.
Try it on a robot
The task from A3.5 Hash tables, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.2.6.1 and is not endorsed by the board.