Lesson 4.3 · Hashing

Counting and Grouping

Use merge to count and computeIfAbsent to group, and choose a key that makes equivalent items collide on purpose.

12 min

Think of it like this

Sorting post into pigeonholes: each letter goes into the hole for its postcode. The trick is choosing the label so that letters that belong together end up in the same hole.

1.Counting with merge

count.merge(x, 1, Integer::sum) adds 1 to x's count, inserting 1 if x is new. It replaces the three-line get-check-put dance.

2.Grouping by a computed key

To group items that are "the same" in some sense, compute a key that's identical for all of them. Anagrams share the same sorted letters ("eat" and "tea" both become "aet"). map.computeIfAbsent(key, k -> new ArrayList<>()).add(item) creates each group on first use.

Group.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        Map<String, List<String>> groups = new TreeMap<>();   // TreeMap: printed in key order
        for (String w : words) {
            char[] cs = w.toCharArray();
            Arrays.sort(cs);
            groups.computeIfAbsent(new String(cs), k -> new ArrayList<>()).add(w);
        }
        System.out.println(groups);
    }
}

Output

{abt=[bat], aet=[eat, tea, ate], ant=[tan, nat]}

Quick check

Sorting each word costs O(k log k) for length k. What key avoids sorting?

Remember

merge for counts, computeIfAbsent for groups.
Pick a key that is equal for exactly the items that belong together.

Common mistakes

Using a char[] or int[] directly as a map key: arrays use identity equality, so equal contents don't match. Convert to a String or List first.

Command Palette

Counting and Grouping

1.Counting with merge

2.Grouping by a computed key