字母异位词分组：HashMap 分组模式的经典应用

一句话结论（30s）

字母异位词分组的本质是”找等价类”，因为只要给每个词找一个唯一的规范表示（排序 or 字符计数）作 HashMap 的 key，同 key 即同组，一次遍历即可完成分组。

核心原理（2min）

两个 key 方案：①排序作 key——每词排序为规范表示，O(nk log k)；②字符计数作 key——26 位计数数组转字符串，O(nk) 但 key 较长。泛化为 Map<CanonicalKey, List<Element>>，适用于所有同构/分组问题。

底层深入（5-10min）

问题

给定字符串数组，将字母组成相同的字符串分到同一组。

输入: ["eat","tea","tan","ate","nat","bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

本质

找到一个能唯一标识”字母构成”的 key，同 key 的字符串归为一组。

这不是”找配对问题”，而是”找等价类问题”——所有字母异位词共享同一个规范表示（canonical representation）。怎么想到”规范表示”这条路的？ 因为直接两两比较字母构成是 O(n²·k)，代价太高；而如果每个词都能被压缩成一个”标准形态”，那么”是否同组”就退化成”key 是否相等”，HashMap 一次查找搞定。

方法一：排序作 key（O(nk log k)）

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);  // "eat"→"aet"
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

💭 思考：为什么「排序后的字符串」能当 key？—— 问的是「怎么保证同组的词拿到同一个 key」。异位词的定义是「字母及出现次数完全相同，只差顺序」，那把它们按同一规则排好序，顺序的差异就被抹平了，结果必然相同；反过来，排序结果相同也说明字母构成相同。所以「排序」就是给每个词找一个「与顺序无关」的标准形态，把「两两比较构成」降成了「key 是否相等」。

每个词排序为规范表示，同规范表示 = 同字母构成。

方法二：字符计数作 key（O(nk)）

String key = new String(count); // 不好直接用 char[] 作为 key（hashCode 不对）
// 改用 String
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
String key = Arrays.toString(count);
// "eat" → "[1,0,0,...,1,1,...]"

💭 思考：既然排序能做，为什么还要折腾「字符计数」当 key？—— 排序法每词要 O(k log k)，瓶颈在「排序」本身。换个思路：异位词的本质是「每个字母出现的次数相同」，那干脆把 26 个字母的计数直接作为 key，构造 key 只需 O(k) 扫一遍，省掉了排序。代价是 key 变长（26 个数串成字符串）、哈希计算变贵。所以这是「构造 key 的时间」和「key 的长度 / 哈希开销」之间的权衡——字符串很长时，省下的 O(k log k) 才划算。

当字符串很长时，计数法 O(k) 优于排序法 O(k log k)。但 key 较长（26个 int 的字符串表示），hash 计算开销大。为什么计数数组不能直接当 HashMap 的 key？ 因为 Java 数组的 hashCode/equals 是继承自 Object 的”引用身份”，两个内容相同的数组会被判成不同 key；所以必须转成 String（或自定义包装类）才能按内容相等。

这一模式泛用在哪？

任何**“找等价类/分组”**问题，只要可以给每个元素找到一个”规范表示”（canonical key），都可用 HashMap 模式：Map<CanonicalKey, List<Element>>。

同构字符串、同构数字、同构树结构……所有同构问题都适用这个模板。

💭 思考：这类「规范表示」模式什么时候能套用？—— 关键看题目问的是不是「把等价的元素分到一组」。如果是，别去两两比较，而是问一句：能不能给每个元素算出一个「与顺序 / 表示无关」的固定 key？只要这个 key 满足「等价 ⇔ key 相同」，剩下的就是 Map<key, List<元素>> 一次遍历。字母异位词用「排序 / 计数」当 key，同构字符串用「映射签名」当 key，换汤不换药——先找「不变的标准形态」，再 map 分组。

章末提问

为什么字母异位词能用”排序后的字符串”当 key 就能正确分组？ 结论：因为异位词的字母组成完全相同，排序后必然得到同一个字符串；所以”排序结果相等”等价于”字母构成相同”，key 相等即同组。
排序作 key 和计数作 key 各有什么优缺点？ 结论：排序法简单直观但每个词要 O(k log k)；计数法 O(k) 更快，但 26 位计数数组转成的 key 更长、哈希计算开销更大——是”排序时间”和”key 长度”的权衡。
这类”找等价类”问题的通用套路是什么？ 结论：给每个元素构造一个规范表示（canonical key），让”同组”等价于”key 相等”，再用 Map<CanonicalKey, List<Element>> 一次遍历完成分组。

字母异位词分组——HashMap处理集合分组的经典模式