When a Loop Inside a Loop Is Too Slow: Hash Tables at Work
Turn the gym's slow year-end reports into one pass: count each member's visits, find the first member to come back, and stop asking a slow server the same question twice. Then choose a list, a set or a dictionary for a job, and say why.
Journeyman · Data Structures · Updated
After this lesson you can
- Count how often each item appears with a dictionary, in one pass
- Find duplicates in one pass with a set instead of comparing every pair
- Explain how a cache uses a dictionary to skip slow work it has already done
- Choose a list, a set or a dictionary for a job, and say why
Key takeaways
- Counting each member by reading the whole log is a loop inside a loop; a dictionary from item to count does it in one pass, O(n).
- To find duplicates, walk the list once with a set of what you've seen: O(n), where comparing every pair is O(n²).
- A cache is a dictionary of answers already worked out: look there first, and do the slow work only on a miss.
- All three trade a little memory for a lot of time.
- Choose by the question asked most: everything in order, repeats included, is a list; "have I seen it?" is a set; a value under a key is a dictionary.
Before this: The Front Desk Finds You in One Scan: Dictionaries and Have I Seen This Before? Sets, where a dictionary and a set each answered one question in one step. A report asks thousands of questions at once.
It's the end of the year at the gym, and the owner wants a report: how many times each of the 20,000 members came in. The check-in log holds a million lines, one name per visit. The report runs overnight, and by morning it still hasn't finished.
Reports like this are everywhere: page views per page, votes per song, orders per customer, errors per server. So are its two cousins: finding the same email signed up twice, and asking a slow server the same question all day. Each one is a few lines of code, and each one is a classic interview question.
What would you try?
Take each member, and count them through the whole log. It's the first idea most people write: a loop over the 20,000 members, and inside it a loop over the million check-ins. That's 20,000 × 1,000,000 = 20 billion name checks: a loop inside a loop, O(n × k) for n check-ins and k members. This is the report that ran all night.
Sort the log, then count each run of equal names. Sorted, all of Maya's visits sit together, so one walk counts them. Sorting a million lines takes about a million × 20 steps, 20 million in all: O(n log n). It works, and it's a thousand times less work. But it sorts a million lines to count 20,000 names, and the log has to be kept in order to do it.
Walk the log once, and keep a count for each name. For each check-in, find that member's count and add 1. With the counts in a dictionary, finding one is O(1) on average, so the whole report is one pass: about a million steps, O(n).
The gym's other two slow jobs fail in the same way, and are fixed in the same way:
| Job | A loop inside a loop | Sort first | Write it down once |
|---|---|---|---|
| Visits per member | read the log once per member: 20 billion steps | sort the log, count each run: about 20 million | a dictionary of counts, one pass: about 1 million |
| The first member to come back | compare every pair of check-ins: up to half a trillion | about 20 million, but sorting loses who came back first | a set of names seen, one pass: up to 1 million |
| "When is Spin?" in the app | ask the schedule server every time: 1,000 trips for 1,000 questions | doesn't apply | a dictionary of answers: one trip per class |
The questions that lead to it
What work is repeated? Every slow try does the same work over and over: it reads the whole log once per member, compares each check-in with every other one, and asks the server a question it has already answered.
What could we write down once? A count for each member. The names seen so far. The answer to each question. Write each one down where it can be found again in one step, in a dictionary or a set, and the repeated work disappears.
How it got its name
These three patterns come up so often that each has a name. Keeping a count for each different item is a frequency count. Remembering what you've already seen is the "seen set" you met in Have I Seen This Before? Sets. And a dictionary of answers already worked out is a cache.
Counting in one pass
Here is the frequency count on a small log of six check-ins. Each check-in adds 1 to that member's count, starting from 0 the first time. It's the pattern behind every "top 10" list you've seen.

Duplicates in one pass
The gym also gives a free smoothie to the first member who comes back for a second visit. In Exercise: Find the Duplicate Songs, finding duplicates meant comparing every pair, O(n²), or sorting first, O(n log n). With a set, it's one walk, O(n): for each name, ask "have I seen you?", and the first yes is the answer.
This code does both, on one week's log:
string[] checkIns = { "Maya", "Leo", "Maya", "Priya", "Maya", "Priya" };
Dictionary<string, int> counts = new Dictionary<string, int>();
foreach (string name in checkIns)
{
counts[name] = counts.GetValueOrDefault(name, 0) + 1;
}
List<string> names = new List<string>(counts.Keys);
names.Sort();
foreach (string name in names)
{
Console.WriteLine(name + ": " + counts[name]);
}
HashSet<string> seen = new HashSet<string>();
foreach (string name in checkIns)
{
if (!seen.Add(name))
{
Console.WriteLine("First to come back: " + name);
break;
}
}
Leo: 1
Maya: 3
Priya: 2
First to come back: Maya
void main() {
String[] checkIns = { "Maya", "Leo", "Maya", "Priya", "Maya", "Priya" };
Map<String, Integer> counts = new HashMap<>();
for (String name : checkIns) {
counts.put(name, counts.getOrDefault(name, 0) + 1);
}
List<String> names = new ArrayList<>(counts.keySet());
Collections.sort(names);
for (String name : names) {
IO.println(name + ": " + counts.get(name));
}
Set<String> seen = new HashSet<>();
for (String name : checkIns) {
if (!seen.add(name)) {
IO.println("First to come back: " + name);
break;
}
}
}
Leo: 1
Maya: 3
Priya: 2
First to come back: Maya
check_ins = ["Maya", "Leo", "Maya", "Priya", "Maya", "Priya"]
counts = {}
for name in check_ins:
counts[name] = counts.get(name, 0) + 1
for name in sorted(counts):
print(f"{name}: {counts[name]}")
seen = set()
for name in check_ins:
if name in seen:
print(f"First to come back: {name}")
break
seen.add(name)
Leo: 1
Maya: 3
Priya: 2
First to come back: Maya
const checkIns = ["Maya", "Leo", "Maya", "Priya", "Maya", "Priya"];
const counts = new Map();
for (const name of checkIns) {
counts.set(name, (counts.get(name) ?? 0) + 1);
}
for (const name of [...counts.keys()].sort()) {
console.log(`${name}: ${counts.get(name)}`);
}
const seen = new Set();
for (const name of checkIns) {
if (seen.has(name)) {
console.log(`First to come back: ${name}`);
break;
}
seen.add(name);
}
Leo: 1
Maya: 3
Priya: 2
First to come back: Maya
const checkIns: string[] = ["Maya", "Leo", "Maya", "Priya", "Maya", "Priya"];
const counts = new Map<string, number>();
for (const name of checkIns) {
counts.set(name, (counts.get(name) ?? 0) + 1);
}
for (const name of [...counts.keys()].sort()) {
console.log(`${name}: ${counts.get(name)}`);
}
const seen = new Set<string>();
for (const name of checkIns) {
if (seen.has(name)) {
console.log(`First to come back: ${name}`);
break;
}
seen.add(name);
}
Leo: 1
Maya: 3
Priya: 2
First to come back: Maya
The line that does the counting is the same idea in every language: read the count, or 0 if there's none yet, and add 1. Some languages have a shortcut for the whole pattern: Python's collections.Counter(check_ins), C#'s checkIns.CountBy(name => name), and Java's counts.merge(name, 1, Integer::sum). They do exactly this loop.
Caches: write the answer down
The gym's app shows when each class meets. The schedule lives on another server, and asking it takes a moment: a trip across the network. Members ask about the same ten classes all day, a thousand times or more. Asking the server every time is slow work done over and over, for answers that hardly change.
A cache is a dictionary of answers already worked out. Before doing the slow work, look in the cache. If the answer is there (a cache hit), use it. If not (a cache miss), do the slow work once, and write the answer in the cache for next time. Here askSchedule stands in for the slow trip to the server and counts how often it runs:
Dictionary<string, string> schedule = new Dictionary<string, string> { ["Spin"] = "Mon 6 pm", ["Yoga"] = "Tue 7 am" };
Dictionary<string, string> cache = new Dictionary<string, string>();
int slowLookups = 0;
string AskSchedule(string className)
{
slowLookups++;
return schedule[className];
}
string WhenIs(string className)
{
if (cache.TryGetValue(className, out string? time))
{
return time + " (from the cache)";
}
string answer = AskSchedule(className);
cache[className] = answer;
return answer + " (slow lookup)";
}
string[] questions = { "Spin", "Yoga", "Spin", "Spin", "Yoga" };
foreach (string className in questions)
{
Console.WriteLine(className + ": " + WhenIs(className));
}
Console.WriteLine("Slow lookups: " + slowLookups + " of " + questions.Length);
Spin: Mon 6 pm (slow lookup)
Yoga: Tue 7 am (slow lookup)
Spin: Mon 6 pm (from the cache)
Spin: Mon 6 pm (from the cache)
Yoga: Tue 7 am (from the cache)
Slow lookups: 2 of 5
Map<String, String> schedule = Map.of("Spin", "Mon 6 pm", "Yoga", "Tue 7 am");
Map<String, String> cache = new HashMap<>();
int slowLookups = 0;
String askSchedule(String className) {
slowLookups++;
return schedule.get(className);
}
String whenIs(String className) {
String time = cache.get(className);
if (time != null) {
return time + " (from the cache)";
}
String answer = askSchedule(className);
cache.put(className, answer);
return answer + " (slow lookup)";
}
void main() {
String[] questions = { "Spin", "Yoga", "Spin", "Spin", "Yoga" };
for (String className : questions) {
IO.println(className + ": " + whenIs(className));
}
IO.println("Slow lookups: " + slowLookups + " of " + questions.length);
}
Spin: Mon 6 pm (slow lookup)
Yoga: Tue 7 am (slow lookup)
Spin: Mon 6 pm (from the cache)
Spin: Mon 6 pm (from the cache)
Yoga: Tue 7 am (from the cache)
Slow lookups: 2 of 5
schedule = {"Spin": "Mon 6 pm", "Yoga": "Tue 7 am"}
cache = {}
slow_lookups = 0
def ask_schedule(class_name):
global slow_lookups
slow_lookups += 1
return schedule[class_name]
def when_is(class_name):
if class_name in cache:
return f"{cache[class_name]} (from the cache)"
answer = ask_schedule(class_name)
cache[class_name] = answer
return f"{answer} (slow lookup)"
questions = ["Spin", "Yoga", "Spin", "Spin", "Yoga"]
for class_name in questions:
print(f"{class_name}: {when_is(class_name)}")
print(f"Slow lookups: {slow_lookups} of {len(questions)}")
Spin: Mon 6 pm (slow lookup)
Yoga: Tue 7 am (slow lookup)
Spin: Mon 6 pm (from the cache)
Spin: Mon 6 pm (from the cache)
Yoga: Tue 7 am (from the cache)
Slow lookups: 2 of 5
const schedule = new Map([["Spin", "Mon 6 pm"], ["Yoga", "Tue 7 am"]]);
const cache = new Map();
let slowLookups = 0;
function askSchedule(className) {
slowLookups++;
return schedule.get(className);
}
function whenIs(className) {
if (cache.has(className)) {
return `${cache.get(className)} (from the cache)`;
}
const answer = askSchedule(className);
cache.set(className, answer);
return `${answer} (slow lookup)`;
}
const questions = ["Spin", "Yoga", "Spin", "Spin", "Yoga"];
for (const className of questions) {
console.log(`${className}: ${whenIs(className)}`);
}
console.log(`Slow lookups: ${slowLookups} of ${questions.length}`);
Spin: Mon 6 pm (slow lookup)
Yoga: Tue 7 am (slow lookup)
Spin: Mon 6 pm (from the cache)
Spin: Mon 6 pm (from the cache)
Yoga: Tue 7 am (from the cache)
Slow lookups: 2 of 5
const schedule = new Map<string, string>([["Spin", "Mon 6 pm"], ["Yoga", "Tue 7 am"]]);
const cache = new Map<string, string>();
let slowLookups = 0;
function askSchedule(className: string): string {
slowLookups++;
return schedule.get(className) ?? "not on the schedule";
}
function whenIs(className: string): string {
const time = cache.get(className);
if (time !== undefined) {
return `${time} (from the cache)`;
}
const answer = askSchedule(className);
cache.set(className, answer);
return `${answer} (slow lookup)`;
}
const questions: string[] = ["Spin", "Yoga", "Spin", "Spin", "Yoga"];
for (const className of questions) {
console.log(`${className}: ${whenIs(className)}`);
}
console.log(`Slow lookups: ${slowLookups} of ${questions.length}`);
Spin: Mon 6 pm (slow lookup)
Yoga: Tue 7 am (slow lookup)
Spin: Mon 6 pm (from the cache)
Spin: Mon 6 pm (from the cache)
Yoga: Tue 7 am (from the cache)
Slow lookups: 2 of 5
Five questions, two trips to the server. With a thousand members asking about the same ten classes, it's a thousand questions and ten trips. A cache works because checking a dictionary is O(1) and much faster than the slow work it saves.
A cache has one hard question: when is a written-down answer out of date? If Spin moves to Wednesday, the cache still says Monday. Real caches forget answers after a while, or are cleared when the data changes. When a function's answer can never change, such as a math result, a cache is always safe, and that's Asking the Same Question Twice: Memoization.
Memory for time
All three patterns spend memory, a dictionary or a set as big as the data, to save time: one pass instead of a loop inside a loop, one trip instead of many. That's the trade from Answer It in One Step: Trading Memory for Time, and it's nearly always worth it. When someone in a code review or an interview asks "can we do better than O(n²)?", the answer is very often "yes, with a hash table".
When sorting wins. If the data is too big to fit in memory, a dictionary of every name can't fit either. That's when sorting comes back: a database answers "visits per member" with GROUP BY, and on a big table it may sort, a piece at a time on disk. Sorting also wins when you need the answer in order anyway, though even then it's usually cheaper to count in a dictionary first and sort only the k different names.
List, set or dictionary?
Every job in this chapter came down to one choice. Ask what the job does most, and pick the structure whose one-step answer is that question:
| The job does most | Choose | Why |
|---|---|---|
| Keep everything in order, repeats included, and read it through | a list | It keeps order and repeats; a set or a dictionary doesn't promise either |
| Ask "have I seen this before?" | a set | One step to check, and no value to store |
| Find a value by its key: a count, a locker, an answer | a dictionary | One step to the value, however many keys |
Two of the gym's jobs need two structures together: the first member to come back reads the log in order (a list) and remembers who's been seen (a set), and the year-end report counts in a dictionary, then sorts its keys for the printout.
Check yourself
2 questions to try on the lesson page.
So what
Counting, duplicates and caching are three of the hash table's most common jobs. Spot a loop inside a loop that counts, compares or repeats slow work, and one of these patterns usually makes it O(n): the gym's all-night report takes well under a second.