Hash Tables: Dictionaries and Sets
A hash table finds data by key almost instantly. It runs the key through a hash function that turns it into a number, and uses the number to pick where to store the value. Looking up the same key later repeats the calculation and goes straight to the spot: O(1) on average, however big the table is.
Python's dict (key to value) and set (just keys, no duplicates) are hash tables. Keys must be unchangeable, such as strings, numbers and tuples, not lists.
Trading memory for speed with a dict or set is the most common way to beat a slow O(n squared) loop.
Why is checking `x in some_set` fast?
Return the first repeated value in the list using a set, and print it.
Finish the quick check (and any code exercise) to complete this lesson, or mark it done yourself.
Tip: use the left and right arrow keys to move between lessons.