使用 HashMap 解决 Java 计数问题

1. 概述

计数问题（counting problem）随处可见：统计字符频率、查找出现次数最多的元素、计算满足条件的数对、分组相似的元素。HashMap 几乎是这类问题的“默认”工具，因为查询和更新的平均时间复杂度都是 O(1)。

读完这篇文章，你将学会如何使用 HashMap（以及 Map.merge、getOrDefault）解决 4 种常见的计数问题，理解时间/空间复杂度，以及避免在计数问题中使用 HashMap 时常见的错误。

2. 为什么 HashMap 适合计数问题

计数问题的通用思想：对于每个元素，你需要知道“出现过多少次”或“是否出现过”。HashMap<K, V> 提供了以下特性：

• 平均 O(1) 时间查询 key — 无需排序。
• 平均 O(1) 时间更新值（增加计数器）。
• 使用 containsKey 或计数值 > 0 来记录“已见”状态。

相比计数数组（counting array）只能在值域小且事先已知时使用（例如字符 a-z），HashMap 更通用：key 可以是 String、Integer 或任意对象。

3. 统计元素频率

3.1. 使用 getOrDefault

这是在列表中统计每个元素频率的经典方法。

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FrequencyCounter {

    public static Map<String, Integer> countFrequency(List<String> words) {
        Map<String, Integer> freq = new HashMap<>();
        for (String word : words) {
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }
        return freq;
    }
}

freq.getOrDefault(word, 0) 如果 word 已存在则返回当前值，否则返回 0 — 避免了必须写 if (map.containsKey(...))。对于列表 ["cam", "xoai", "cam", "cam", "xoai"]，结果是：

{cam=3, xoai=2}

3.2. 使用 Map.merge（更简洁）

从 Java 8 开始，Map.merge 将检查和更新操作合并为一次调用。

public static Map<String, Integer> countFrequencyMerge(List<String> words) {
    Map<String, Integer> freq = new HashMap<>();
    words.forEach(word -> freq.merge(word, 1, Integer::sum));
    return freq;
}

freq.merge(word, 1, Integer::sum) 的意思是：如果 word 不存在，设置值为 1；如果已存在，通过 Integer::sum 函数将旧值加 1。这种方式稍微快一点，而且当累加逻辑简单时，代码读起来更自然。

3.3. 使用 JUnit 5 + AssertJ 测试

import org.junit.jupiter.api.Test;
import java.util.List;
import java.util.Map;
import static org.assertj.core.api.Assertions.assertThat;

class FrequencyCounterTest {

    @Test
    void shouldCountFrequencyCorrectly() {
        Map<String, Integer> result = FrequencyCounter.countFrequency(
                List.of("cam", "xoai", "cam", "cam", "xoai"));

        assertThat(result)
                .containsEntry("cam", 3)
                .containsEntry("xoai", 2);
    }
}

注意： getOrDefault 如果 key 不存在时不会修改 map — 它只是读取。不要与 putIfAbsent 混淆，后者用于在 key 不存在时分配默认值。

4. 查找出现次数最多的元素

有了频率表后，查找出现次数最多的元素就只需要遍历一次 entrySet() 了。

import java.util.Map;
import java.util.Optional;

public class MostFrequentFinder {

    public static Optional<String> findMostFrequent(Map<String, Integer> freq) {
        return freq.entrySet().stream()
                .max(Map.Entry.comparingByValue())
                .map(Map.Entry::getKey);
    }
}

Map.Entry.comparingByValue() 按 value（出现次数）比较各 entry，.max(...) 获取 value 最大的 entry。如果有多个元素排名并列最高，max 只返回其中之一 — 由于 HashMap 不保持插入顺序，顺序不受保证。

Input:  {cam=3, xoai=2}
Output: Optional[cam]

注意： 如果需要保持插入顺序以便在有多个并列元素时结果稳定，使用 LinkedHashMap 而不是 HashMap。

5. 计算满足条件的元素对（计数形式的 Two Sum）

一个常见的变体：计算满足 arr[i] + arr[j] == target 的对数 (i, j)。与其使用蛮力 O(n²) 的方法，不如使用 HashMap 将复杂度降低到 O(n)。

import java.util.HashMap;
import java.util.Map;

public class PairCounter {

    public static int countPairsWithSum(int[] numbers, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        int count = 0;

        for (int number : numbers) {
            int complement = target - number;
            count += seen.getOrDefault(complement, 0);
            seen.merge(number, 1, Integer::sum);
        }
        return count;
    }
}

逐行解释：

• complement = target - number：与 number 相加得到 target 所需的值。
• count += seen.getOrDefault(complement, 0)：加上 complement 之前出现的次数 — 每次都形成一个有效的数对。
• seen.merge(number, 1, Integer::sum)：将当前 number 记录到计数表中，以便后续元素可以与之配对。

对于 numbers = [1, 2, 3, 2, 4] 和 target = 5：数对为 (1,4)、(2,3)、(3,2) → 但由于我们只按之前出现的顺序计数，请通过测试验证。

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class PairCounterTest {

    @Test
    void shouldCountPairsWithGivenSum() {
        int[] numbers = {1, 2, 3, 2, 4};

        int result = PairCounter.countPairsWithSum(numbers, 5);

        assertThat(result).isEqualTo(3);
    }
}

这三对分别是：遇到数字 3 时的 (2,3)、遇到第二个 2 时的 (2,3)（与已见的 3 配对），以及遇到 4 时的 (1,4)。

6. 分组相似的元素（Anagram 组）

一个更高级的计数问题：分组互为 anagram 的单词（具有相同字符集但顺序不同），然后计算组数或每组中的元素数。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AnagramGrouper {

    public static Map<String, List<String>> groupAnagrams(List<String> words) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String signature = new String(chars);

            groups.computeIfAbsent(signature, key -> new ArrayList<>())
                  .add(word);
        }
        return groups;
    }
}

关键点在于 signature：排序每个单词的字符以生成所有 anagram 的公共“签名”。computeIfAbsent(signature, key -> new ArrayList<>()) 如果签名还没有对应的 key，就创建一个新列表，然后将当前单词添加到其中。

对于输入 ["eat", "tea", "tan", "ate", "nat", "bat"]，结果为：

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

import org.junit.jupiter.api.Test;
import java.util.List;
import java.util.Map;
import static org.assertj.core.api.Assertions.assertThat;

class AnagramGrouperTest {

    @Test
    void shouldGroupAnagramsTogether() {
        Map<String, List<String>> groups = AnagramGrouper.groupAnagrams(
                List.of("eat", "tea", "tan", "ate", "nat", "bat"));

        assertThat(groups.values())
                .anySatisfy(group -> assertThat(group).containsExactlyInAnyOrder("eat", "tea", "ate"));
    }
}

computeIfAbsent 比手动写 containsKey + put 更简洁，特别是当 value 是需要延迟初始化的集合时。

7. 时间和空间复杂度

问题	时间复杂度	空间复杂度
统计频率	O(n)	O(k) — k 为不同元素的数量
查找最频繁的元素	O(n)	O(k)
计算和为 target 的数对	O(n)	O(n)
分组 anagram	O(n · m log m) — m 为最长单词的长度	O(n)

与先排序再遍历的解决方案（O(n log n)）相比，HashMap 在时间复杂度上通常更快，但代价是额外消耗 O(n) 或 O(k) 的空间。如果内存空间受限且值域较小，计数数组（counting array）仍然是更节省的选择。

8. 常见错误

• 使用可变对象作为 key 但未覆盖 equals/hashCode：如果你按自定义类（例如 Point）计数，忘记覆盖这两个方法会导致 HashMap 无法识别两个“相同”的对象是同一个 key。

public record Point(int x, int y) {}

record 会根据所有字段自动生成正确的 equals/hashCode — 完全避免这个错误。

• 期望迭代顺序（iteration order）稳定：HashMap 不保证顺序。如果需要插入顺序，使用 LinkedHashMap；如果需要按 key 升序排列，使用 TreeMap。

• 遍历 entrySet() 时修改 map：会引发 ConcurrentModificationException。如果需要在遍历时删除 entry，使用 Iterator.remove() 或 removeIf。

• 在大循环中不谨慎地使用 Integer 装箱：每次 getOrDefault + + 1 都会因自动装箱创建新的 Integer 对象。对于非常大的数据集（数百万个元素），考虑使用 Map<String, int[]> 或基本类型 map 库（例如 Eclipse Collections）来减少开销。

注意： 如果 key 的范围只是 26 个字母 a-z 或一个小的固定整数范围，数组（int[26]）总是比 HashMap 更快且更节省内存。只有当 key 的范围很大、事先未知或不连续时，才使用 HashMap。

9. 总结

HashMap 将计数问题 — 统计频率、查找突出元素、计算数对、分组相似元素 — 转变为简单的 O(n) 循环，这得益于 O(1) 的查询。方法 getOrDefault、merge、computeIfAbsent 使代码比手动检查 containsKey 更简洁、更清晰。记住：HashMap 不保持顺序，对于对象 key 需要正确的 equals/hashCode，而且对于小值域，计数数组仍然是更轻量的选择。