Hash maps, sets, and how caches use them
By the end of today you can explain what hashing actually does, recognise the class of problem where storing what you have already seen collapses a nested loop, and say why a cache is a hash map with a memory limit.
YesterdayOn Day 14 you collapsed a nested loop using two pointers, which needed sorted data. Today you collapse one without that requirement.
TomorrowTomorrow, sets apply the same hashing idea to membership and uniqueness.
Why this matters
The hash map is the single most useful data structure in practical engineering. The same idea appears as a database index on Day 43, a cache on Day 60, and a vector store lookup on Day 74.
- Hashing
- Turning a key into a position, so lookup is direct rather than a search.
- The hash map pattern
- Remember what you have seen, and the inner loop disappears.
- Collisions
- Two keys landing in one place, which is inevitable and handled internally.
- Cache intuition
- A cache is a hash map with a memory limit and permission to forget.
- Set algebra
- Union, intersection and difference, replacing loops that compare collections.
- Membership testing
- Asking whether something is present, cheaply, at any size.
- Deduplication
- Removing duplicates, and doing it while preserving order when order matters.
- Recognising a set problem
- Order and duplicates do not matter, and the question is about overlap.
Learn it
80 minCopy this into Claude or ChatGPT. It quizzes you before it explains anything, which is deliberate. The resources under it are how you check what it told you.
Today's Master Prompt
Free · sign inA prompt written for this day alone: your level, the exact scope, what to leave out, and an instruction to quiz you before it explains anything. Paste it into Claude or ChatGPT and it teaches you today's material.
Check it against something that is not a model
An assistant can be fluent and wrong, and on a topic you met today you will not catch it. These cover the same ground and were made by people who do this for a living, so they are what you hold the explanation up against. They are other people's work and we only link to them, so judge them for yourself.
5 hand-picked resources
Free · sign inVideos, official docs and articles covering the same ground, each opened and annotated by hand. They are what you check the assistant against on a day you cannot yet catch it being wrong.
Build it
50 minSolve two-sum on an unsorted list twice: nested loops, then one pass with a dict. Then write a function that finds the first non-repeating character in a string, and one that groups a list of words by their sorted letters. Time the two-sum versions at 10,000 items.
Recall it
25 minAnswer out loud, reveal, then mark honestly whether you had it. That score is the only thing on this page you do not get to choose.
5 recall questions
Free · sign inQuestions you answer from memory, then grade yourself against the real answer. The score is carried into the mastery rating below it, so an honest miss cannot quietly become a tick.
Rate it
Finishing a day and understanding it are two different things, and this page counts them separately.
Mastery tracking
Free · sign inRate yourself against five named criteria per concept. Completion and mastery are tracked separately, and anything you rate shakily comes back automatically on a spaced schedule.
Recap
- 01Hashing turns a key into a position, so lookup is direct rather than a search
- 02Collisions are inevitable and handled internally
- 03Remembering what you have seen collapses many nested loops into one pass
- 04A cache is a hash map that is allowed to forget
Your progress
Free · sign inMark days complete, pick up where you left off across devices, and watch completion and mastery diverge. Free, and the account exists only so ninety days of work cannot vanish with a cleared browser.