Group Anagrams 是 LeetCode Hot 100 里面一道非常经典的哈希表题。
这道题第一次看上去并不算难，但它特别适合训练一种很重要的算法思维：
如何把“看起来不同，但本质等价”的字符串映射到同一个键上。
因为题目要求我们把所有字母异位词分到同一组里。
-
单词中的字符种类相同
-
每种字符出现次数相同
-
只是顺序不同
例如：
-
"eat" -
"tea" -
"ate"
这三个字符串虽然写法不同，但它们本质上由同样的字符组成，因此应该被分到同一组。
你给出的这份 Java 代码，使用的是这道题最经典、最容易理解的一种解法：
排序 + 哈希表
这种写法的核心思想非常清晰：
-
对每个字符串进行排序
-
把排序后的结果作为哈希表的 key
-
原字符串作为 value 放进对应分组中
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定一个字符串数组 strs，要求你将字母异位词组合在一起，并返回结果。
这里的“字母异位词”指的是：
两个字符串包含完全相同的字母，只是顺序不同。
例如：
-
"eat"和"tea"是字母异位词 -
"tan"和"nat"是字母异位词 -
"bat"只能自己单独成组
所以如果输入是：
["eat","tea","tan","ate","nat","bat"]
那么输出可以是：
[
["eat","tea","ate"],
["tan","nat"],
["bat"]
]
注意，题目并不要求最终答案中分组的顺序固定，也不要求每组内部元素的顺序固定。 只要分组正确即可。
示例
示例 1
输入：strs = ["eat","tea","tan","ate","nat","bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]
这一组数据里：
-
"eat"、"tea"、"ate"是一组 -
"tan"、"nat"是一组 -
"bat"自己单独一组
示例 2
输入：strs = [""]
输出：[[""]]
空字符串本身当然也是一个合法字符串，所以结果里会有一组只包含空串。
示例 3
输入：strs = ["a"]
输出：[["a"]]
只有一个字符串，自然单独成组。
这道题最关键的观察是什么？
这道题真正的关键在于：
如何判断两个字符串是不是字母异位词。
最直观的判断方法就是：
-
如果两个字符串排序后完全一样
-
那它们一定是字母异位词
例如：
"eat" -> "aet"
"tea" -> "aet"
"ate" -> "aet"
排序后都变成了 "aet"，所以它们应该放在同一组。
再比如：
"tan" -> "ant"
"nat" -> "ant"
排序后都变成 "ant"，所以它们也属于一组。
而：
"bat" -> "abt"
和前面都不一样，因此自己成组。
所以整道题的核心，其实就是：
把“排序后的字符串”作为分组依据。
最直接的思路是什么？
如果完全不用哈希表，一个很朴素的想法可能是：
-
取出一个字符串
-
去和后面的每个字符串比较，看是不是字母异位词
-
如果是，就放到同一组
-
然后继续处理剩下的字符串
但这种做法效率比较低。 因为你可能需要频繁地两两比较字符串，而且比较次数会很多。
所以更自然的优化方法就是：
给每个字符串提取一个统一的“特征值”，然后用哈希表按特征值分组。
而这个“特征值”，就是排序后的字符串。
核心思路：排序后的字符串作为 key
你这段代码的核心逻辑非常清楚：
第一步：遍历每个字符串
对于数组中的每个字符串 str：
for (String str : strs)
第二步：把字符串转成字符数组并排序
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String sortedStr = new String(charArray);
这样就得到了它的“标准形态”。
第三步：用标准形态作为哈希表 key
如果哈希表中还没有这个 key，就先创建一个新的列表。 然后把当前原字符串加进去。
这样，所有排序后相同的字符串都会自动进入同一个分组。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
// 把字符串转成字符数组
char[] charArray = str.toCharArray();
// 排序，得到统一形式
Arrays.sort(charArray);
String sortedStr = new String(charArray);
// 如果 map 中还没有这个 key，就先创建一个空列表
if (!map.containsKey(sortedStr)) {
map.put(sortedStr, new ArrayList<>());
}
// 把原字符串加入对应分组
map.get(sortedStr).add(str);
}
// 返回所有分组结果
return new ArrayList<>(map.values());
}
}
代码拆解
这段代码虽然不长，但它把哈希分组这类题目的核心思路体现得非常完整。 下面一步一步来看。
1. 为什么用 Map<String, List<String>>？
Map<String, List<String>> map = new HashMap<>();
这里的哈希表是整道题的核心数据结构。
它的含义是：
-
key：排序后的字符串 -
value：所有属于这个 key 的原始字符串列表
例如遍历到一部分字符串后，哈希表可能长这样：
"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]
这样最终只需要把 map.values() 取出来，就得到了所有分组结果。
所以这道题本质上其实就是一道：
哈希映射分组题。
2. 为什么要先转成字符数组？
char[] charArray = str.toCharArray();
因为 Java 中不能直接对字符串本身排序。 所以要先把字符串转换成字符数组，再调用：
Arrays.sort(charArray);
排序之后，字符数组中的字符就会按字典序排好。
例如：
"tea" -> ['t','e','a'] -> ['a','e','t']
然后再把它重新转回字符串，作为哈希表的 key。
3. 为什么排序后的字符串可以作为分组依据？
String sortedStr = new String(charArray);
这是整道题最核心的一步。
因为对于两个字母异位词来说：
-
它们包含的字符完全一样
-
所以排序后结果一定相同
例如：
"listen" -> "eilnst"
"silent" -> "eilnst"
排序后的 key 一样，所以可以放到同一个桶里。
反过来，如果两个字符串排序后不一样，那它们一定不可能是字母异位词。
所以“排序后字符串相同”这件事，正好给我们提供了一个非常稳定的分组标准。
4. 为什么要先判断 containsKey？
if (!map.containsKey(sortedStr)) {
map.put(sortedStr, new ArrayList<>());
}
因为当某个 key 第一次出现时，哈希表里还没有对应的列表。
这时候必须先创建一个新的 ArrayList，否则下面这句：
map.get(sortedStr).add(str);
就会报空指针异常。
这个逻辑其实很常见，表示：
-
如果当前分组还不存在，就先创建分组
-
然后再把当前元素放进去
当然在 Java 里也可以写成更简洁的：
map.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);
不过你现在这份写法更直观，也更适合写博客讲解。
5. 为什么最后直接返回 map.values()？
return new ArrayList<>(map.values());
因为哈希表里每个 value 本身就是一个分组。
例如：
"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]
那么我们最终只关心这些分组列表本身，而不再关心 key 是什么。
所以直接把所有 value 取出来，转成 List<List<String>> 返回即可。
注意这里返回的是：
new ArrayList<>(map.values())
这是因为 map.values() 返回的是一个集合视图，而题目要求的是 List<List<String>>，所以需要包一层新的 ArrayList。
手动模拟一遍
我们用最经典的示例来走一遍：
strs = ["eat","tea","tan","ate","nat","bat"]
第一步：处理 "eat"
-
转字符数组：
['e','a','t'] -
排序后：
['a','e','t'] -
得到 key：
"aet"
此时哈希表变成：
"aet" -> ["eat"]
第二步：处理 "tea"
-
转字符数组：
['t','e','a'] -
排序后：
['a','e','t'] -
key 仍然是：
"aet"
所以加入同一组：
"aet" -> ["eat","tea"]
第三步：处理 "tan"
-
排序后 key：
"ant"
哈希表变成：
"aet" -> ["eat","tea"]
"ant" -> ["tan"]
第四步：处理 "ate"
-
排序后 key：
"aet"
加入 "aet" 这组：
"aet" -> ["eat","tea","ate"]
"ant" -> ["tan"]
第五步：处理 "nat"
-
排序后 key：
"ant"
加入 "ant" 这组：
"aet" -> ["eat","tea","ate"]
"ant" -> ["tan","nat"]
第六步：处理 "bat"
-
排序后 key：
"abt"
哈希表最终变成：
"aet" -> ["eat","tea","ate"]
"ant" -> ["tan","nat"]
"abt" -> ["bat"]
最后返回所有 value：
[
["eat","tea","ate"],
["tan","nat"],
["bat"]
]
为什么这个方法是正确的？
因为对于字母异位词来说，“排序后的字符串”是它们的统一标准形态。
如果两个字符串是字母异位词
那么它们包含的字符完全一样，排序后一定相同。
如果两个字符串不是字母异位词
那么它们至少有一个字符不同，或者某个字符出现次数不同，排序后结果也一定不同。
因此：
排序后的字符串相同，当且仅当原字符串互为字母异位词。
这就保证了：
-
该放在一起的，一定会被分到一起
-
不该放在一起的，一定不会被误分到一起
所以这个分组标准是完全正确的。
复杂度分析
假设：
-
字符串数组长度为
n -
每个字符串平均长度为
k
时间复杂度
对于每个字符串，我们都要：
-
转成字符数组：
O(k) -
排序：
O(k log k) -
构造新字符串：
O(k)
所以单个字符串的处理代价大约是：
O(k log k)
总共有 n 个字符串，因此总时间复杂度是：
O(n * k log k)
空间复杂度
主要来自：
-
哈希表存储分组结果
-
排序时使用的字符数组
所以空间复杂度可以写成：
O(n * k)
如果把结果集本身算进去，空间还要更大，但通常分析时会单独说明输出空间。
这道题真正想考什么？
这道题表面上是在分组字符串，但本质上考察的是两个很重要的能力。
第一，是否能为“等价类”设计统一表示
这类题最关键的不是遍历和分类本身，而是：
如何找到一个稳定的 key，让所有本质相同的对象映射到同一个桶里。
在这道题里，这个 key 就是排序后的字符串。
这类思维在哈希表题目里非常常见。
第二，是否能把复杂比较转化成哈希分组
如果两两比较字符串是不是异位词，会比较麻烦。 而一旦提取出统一 key，问题就从“复杂比较”变成了“简单分桶”。
这正是哈希表常见的使用方式：
通过构造 key，把问题变成查表和分组。
这题还有别的写法吗？
有。
除了“排序后的字符串作为 key”之外，这题还可以用另一种思路：
字符计数作为 key
例如对每个字符串统计 26 个字母的出现次数，然后把这个计数结果转成字符串作为 key。
这样就不用排序了，时间复杂度可以优化到：
O(n * k)
不过从理解和实现角度来说，你现在这份“排序 + 哈希表”的写法是最经典、也最容易讲清楚的一种。 很适合放在博客里作为主解法。
总结
这道题的核心思想可以概括成一句话：
把每个字符串排序后得到统一形式，用这个统一形式作为哈希表的 key，把所有 key 相同的字符串分到同一组。
具体步骤就是：
-
遍历字符串数组
-
把当前字符串转成字符数组并排序
-
将排序后的字符串作为 key
-
用哈希表把原字符串加入对应分组
-
最后返回所有分组结果
这样就能在：
O(n * k log k)
的时间复杂度内完成分组。
这是一道非常经典、也非常值得反复理解的哈希表题。 因为它会让你真正意识到：
-
哈希表不只是拿来做查找
-
更重要的是学会“设计 key”
-
一旦 key 设计好了，很多分类题都会变得非常简单
把这道题真正吃透之后，再去看：
-
有效的字母异位词
-
最长连续序列
-
两数之和
-
出现次数最多的元素
这些哈希题时，你会更容易抓住它们背后的共同思路。
