Frequency counting and deduplication

For this lesson, we'll focus on the two most reusable hash-based patterns: counting with HashMap and arrays, then deduplicating with HashSet, LinkedHashSet, TreeSet, streams and field-based seen sets. Interviewers ask these because the code is short, but the details reveal whether you understand equality, ordering, overflow, tie-breaking and the difference between "same object" and "same key".

01Picture it first: a tally sheet and a guest list

Picture a batch of order IDs coming across your desk. If the question is "how many times did each ID appear?", you add marks to a tally sheet. If the question is "have I seen this ID before?", you check a guest list and add it the first time.

The two diagrams below show the same stream producing different state. Counting stores a number; dedup stores existence.

Fig. 1

A frequency map is built step by step from api, db, api, cache, api with api ending at 3, db at 1 and cache at 1

Fig. 2

A seen set accepts e1 and e2, rejects the second e1, then accepts e3 while preserving the idea of first-seen membership

Notice the shape of the data. In both patterns the key is the value you care about: a word, user ID, event ID, character or field extracted from an object. The difference is the value stored next to it, either a count or nothing more than membership.

02Frequency counting under the hood

Here's how I'd write the loop in production when a plain integer count is enough:

static Map<String, Integer> countServices(List<String> services) {
    Map<String, Integer> frequency = new HashMap<>();
    for (String service : services) {
        frequency.merge(service, 1, Integer::sum);
    }
    return frequency;
}

Notice three things:

• merge stores 1 when the key is absent or mapped to null.
• For an existing non-null count, it calls Integer::sum with the old count and 1.
• The map contains only distinct services, so the extra space is O(u), not O(n), where u is unique services.

The same loop with getOrDefault is a little more explicit:

static Map<String, Integer> countWithGetOrDefault(List<String> words) {
    Map<String, Integer> frequency = new HashMap<>();
    for (String word : words) {
        int next = frequency.getOrDefault(word, 0) + 1;
        frequency.put(word, next);
    }
    return frequency;
}

getOrDefault does not insert the default. It only gives you a value to compute with, then put writes the new count. I like this version when teaching because it shows the read, increment and write steps.

compute is useful when the update logic depends on the old value:

static Map<String, Integer> countWithCompute(List<String> words) {
    Map<String, Integer> frequency = new HashMap<>();
    for (String word : words) {
        frequency.compute(word, (key, old) -> old == null ? 1 : old + 1);
    }
    return frequency;
}

For simple counting, merge is usually cleaner. compute shines when you need to remove a key by returning null, cap a value, or use more involved update logic. In concurrent code, the same method names exist on ConcurrentHashMap, but the thread-safety story is a separate lesson.