# 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 November 17, 2026

By Gregor Dzierzon

## 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.

![The six check-ins counted one at a time, Maya, Leo, Maya, Priya, Maya, Priya: after each one the dictionary shows that member's count going up by one, ending at Maya 3, Leo 1 and Priya 2, in a single pass over the log](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/bad57e1cba2a457385512cdb280fa54a.webp)

## 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:

```csharp
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;
    }
}
```

```text
Leo: 1
Maya: 3
Priya: 2
First to come back: Maya
```

```java
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;
        }
    }
}
```

```text
Leo: 1
Maya: 3
Priya: 2
First to come back: Maya
```

```python
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)
```

```text
Leo: 1
Maya: 3
Priya: 2
First to come back: Maya
```

```javascript
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);
}
```

```text
Leo: 1
Maya: 3
Priya: 2
First to come back: Maya
```

```typescript
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);
}
```

```text
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:

```csharp
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);
```

```text
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
```

```java
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);
}
```

```text
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
```

```python
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)}")
```

```text
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
```

```javascript
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}`);
```

```text
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
```

```typescript
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}`);
```

```text
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.

## Key terms

- [Frequency Count](https://www.ask-codey.com/glossary/frequency-count)
- [Cache](https://www.ask-codey.com/glossary/cache-software-development)
- [Cache Hit](https://www.ask-codey.com/glossary/cache-hit)
- [Cache Miss](https://www.ask-codey.com/glossary/cache-miss)

## Cheat sheets

- [When a Loop Inside a Loop Is Too Slow: Hash Tables at Work](https://www.ask-codey.com/cheat-sheets/ds-hash-tables-at-work-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-hash-tables-at-work
