Everything else is ready: study the parts, the key terms and the quiz below.
Hash Tables
See why a dict lookup is fast, and use that to speed up an algorithm.
In this lesson8 parts
- 01Products both shops sell
- 02With a set
- 03The hash function
- 04A hash table by hand
- 05Keeping the buckets short
- 06O(1) on average
- 07Rules a hash table needs
- 08Recap, your challenge, and the track
Key terms
The words this lesson introduces, each in one line. The module’s glossary collects them all.
- bucket
- One slot in a hash table. A key's hash, modulo the number of buckets, chooses its bucket.
- collision
- Two keys in the same bucket, such as
46and22in a table of eight buckets. - hash function
- A function that turns a value into an int, the same int every time for the same value. Python's is
hash(). - hash table
- A list of buckets, where a value's hash decides its bucket, so a lookup compares only with the keys in one bucket. Every Python
setanddictis one. - load factor
- The number of keys divided by the number of buckets. A lookup's work grows with it.
Quiz 5 questions
Your first pick on each question is the one that counts, and a right one earns a coin. Getting one wrong here is how the lesson sticks.
Practice
Problems to solve in your own notebook. Each states the problem, not the steps: working out the steps is the exercise. Level A applies the lesson, B combines it with earlier ones, C stretches it.
The self-checking notebook for this lesson is Notebook 3 · Hash Tables.
Common mistakes
What you will see when it goes wrong, why it happens, and the fix.
Where it’s used
Where this lesson’s ideas turn up in real work.