A hash table by hand, with collisions
Add the key 27 and predict which slot it lands in (27 % 8) before you run.
A dictionary turns each key into a number called a hash, and uses that number to jump straight to a slot in a table, so lookup takes about the same time however big the dictionary is. This is why keys must be hashable (unchanging) and why a list cannot be a key.
Change the code and press Run (Ctrl+Enter). Predict what will happen first, then break it on purpose and read what changes. Your edits are saved and match the lesson page.
Ready for more? This phase has 6 hands-on exercises with automatic checks.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Create d = {1: "int", 1.0: "float", True: "bool"} and print it and its length. Explain why the length is not 3.
Make a dictionary that maps grid coordinates to names: (0, 0) is "start" and (2, 3) is "exit". Print the name at (2, 3).
Write a loop that puts the numbers 10, 17, 25, 33 into a table of 5 slots (lists) using number % 5, then print the table.
Explain it without notes
Why is dictionary lookup O(1) on average?
Why can't a list be a dictionary key, but a tuple can?
What is a hash collision, and how does Python handle it?
If you define __eq__ on a class, why should you also define __hash__?
Is dictionary lookup always O(1)? What could make it slow, and what does Python do about it?
Expected output
slot 0 -> []
slot 1 -> []
slot 2 -> [42]
slot 3 -> [3, 11, 19]
slot 4 -> []
slot 5 -> [5]
slot 6 -> []
slot 7 -> []
looking for 19 in slot 3 -> True
looking for 42 in slot 2 -> True
looking for 7 in slot 7 -> False