HashMap

介绍

HashMap 是最直接的”空间换时间”体现。它把键映射到值，大多数操作（get、put）都是 O(1) 时间。

核心思想：用额外的存储空间，换取常数时间的查找速度。当你面对一个 O(n²) 的暴力解时，想想能否用一个 HashMap 把其中一层循环替换成 O(1) 查找。

HashMap vs Hashtable：HashMap 非线程安全但更快；Hashtable 线程安全（已过时，用 ConcurrentHashMap 替代）。

什么时候会退化？

HashMap 的 O(1) 是有前提的：好的哈希函数 + 低负载因子。当哈希碰撞严重时（比如所有 key 都 hash 到同一个 bucket），查找退化为 O(n)。Java 8+ 做了优化：单个 bucket 内元素超过 8 个时，链表转为红黑树，退化下限控制在 O(log n)。

HashMap vs TreeMap

	HashMap	TreeMap
底层	哈希表	红黑树
查找	O(1) 平均	O(log n)
顺序	无序	按 key 自然排序
适用	纯 KV 查找	需要有序遍历 key

面试关键：如果只需要存 key 不需要 value，用 HashSet（底层就是 HashMap）。

模式识别

当你看到这些信号，优先想 HashMap：

• “找两个数的和为 target”（用 map 存已遍历的值）
• “某个元素出现过吗？“（O(1) 存在性检查）
• “需要建立映射关系”（two-pass 替换、字符频率统计）
• O(n²) 暴力解中有一层是在”查找”（用 HashMap 替换那层查找）

Java 常用方法

V   put(K key, V value)        // insert or update
V   get(Object key)             // retrieve, null if not found
V   remove(Object key)          // remove entry
int size()                      // entry count
boolean isEmpty()
boolean containsKey(Object key)
boolean containsValue(Object value)

// Iteration
for (Map.Entry<K, V> entry : map.entrySet()) { ... }
for (K key : map.keySet()) { ... }
for (V value : map.values()) { ... }

代码挑战

1. Two Sum

问题：给定一个整数数组和一个目标值，找出两个数使它们的和等于目标值，返回索引。

暴力解：两层 for 循环 → O(n²) time, O(1) space

HashMap 优化：遍历数组，对于每个元素 nums[i]，检查 target - nums[i] 是否已在 map 中。在同一个 for 循环中边查边建 map。O(n) time, O(n) space。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int remaining = target - nums[i];
        if (map.containsKey(remaining)) {
            return new int[]{map.get(remaining), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

关键技巧：在同一个循环中构建 HashMap — 不需要预处理，边遍历边查边存。

2. Group Anagrams

问题：给定一个字符串数组，将字母异位词（相同字母不同排列）分到同一组。

HashMap 思路：遍历每个字符串，将其排序后作为 key，原字符串追加到对应的 list 中。HashMap 在这里建立”排序形式 → 原始字符串”的映射关系。

public 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);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

关键技巧：computeIfAbsent 是 HashMap 的实用方法 — 如果 key 不存在则创建默认值，避免手写 if-contains-then-put-else-get 的样板代码。

关键技巧

• “找配对” → HashMap — 看到 two-sum、对称映射、互补关系就建 map
• 边遍历边构建 — 不需要预处理，同一个循环里查 + 存，一次 pass
• 退化场景要知道 — 哈希碰撞严重时退化为 O(n)，Java 8+ 用红黑树缓解到 O(log n)
• computeIfAbsent 省代码 — 分组/计数场景比手写 if-contains 简洁得多
• 用 containsKey 判断存在 — 比 get() == null 更语义清晰（key 的值可能就是 null）

参考资料

• HashMap — Java Docs