Hashing Quiz
Test yourself.
Hash tables are the most useful tool in this course so far. Let's make sure you're comfortable with them. Pause, answer, then listen.

- The most useful tool
- Check yourself
- Pause, answer, listen
Question 1
What's the average cost of checking whether an item is in a set? The answer is O of one. Sets are hash tables, so they jump straight to the right bucket.
Question 2
Which of these can't be a dictionary key? A string, a tuple, or a list? The answer is a list. Keys must never change, and lists can change.
Question 3
In two sum, what does the dictionary store? The answer is each number we've seen, and its position. Then we can find a partner in O of one.
Question 4
Which technique finds the longest substring without repeats? The answer is a sliding window, which grows and shrinks as we scan.
Summary
Brilliant. Next, a new section. Stacks, queues, and linked lists, the structures that keep things in order.
Key takeaways- Sets: O(1) membership
- Keys must not change
- Windows for substrings