Topic B4 is Higher Level only. This unit explains hash tables, the ADT behind fast key-value lookup, and how sets relate to them. You need to understand the three things that decide a hash table's performance: the hashing function, the collision resolution strategy and the load factor. A collision is not a bug, it is expected, so knowing how to resolve one is the key idea here.
Slide 1 / 4
What is a hash table
A hash table stores key-value pairs and is built for fast lookup, insertion and deletion, with an average time complexity of O(1).
A hashing function takes a key and calculates an integer index that decides which bucket (slot) the key-value pair is stored in.
To find a value again, the same key is hashed to jump straight to its bucket, instead of searching through every entry.
In Java a hash table is used through HashMap (and HashSet); in Python the equivalents are dict (and set).
Check you've got it
0/4
1. In a hash table, what is a collision?
2. A hash table has 12 buckets and currently stores 9 entries. What is its load factor?
3. A hash table resolves collisions by making each bucket a linked list, so several entries that hash to the same index are all kept in that bucket and searched in turn. Which strategy is this?
4. Which property must a good hashing function always have?
Free revision content. Multiple-choice answers are marked instantly. Written answers are marked by AI on /free-mark.