Map体系

Java

Map是什么

Map就像一本字典：通过”词条”（key）查找”释义”（value），一个key对应一个value

Map不属于Collection接口，它是集合框架的另一个分支

1
2
3
4
5
6
Map
├── HashMap         ← 最常用，无序，O(1)
├── TreeMap          ← key有序，O(log n)
├── LinkedHashMap    ← 保留插入顺序
├── Hashtable        ← 线程安全但过时
└── ConcurrentHashMap ← 线程安全的现代版

HashMap：最常用的Map

底层是数组 + 链表 + 红黑树（JDK8开始），像一排带抽屉的柜子，每个抽屉里可以挂一串东西

基本用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
@Test
public void testHashMap() {
Map<String, Integer> scores = new HashMap<>();

// 放入键值对
scores.put("张三", 90);
scores.put("李四", 85);
scores.put("王五", 92);

// 通过key获取value
System.out.println(scores.get("张三"));  // 90

// key重复？新值覆盖旧值
scores.put("张三", 95);
System.out.println(scores.get("张三"));  // 95

// 判断是否包含某个key
System.out.println(scores.containsKey("李四"));    // true
System.out.println(scores.containsValue(100));     // false

// 删除
scores.remove("王五");
System.out.println(scores);  // {张三=95, 李四=85}

// getOrDefault：key不存在时返回默认值（避免null）
System.out.println(scores.getOrDefault("赵六", 0));  // 0
}

底层原理简述

初始容量 16，负载因子 0.75（即元素超过 16×0.75=12 个时扩容）

扩容时容量翻倍（16→32→64…），所以容量永远是2的幂

为什么容量要是2的幂？因为计算下标时用的是 hash & (n-1) 而不是 hash % n，位运算更快，而且当n是2的幂时 hash & (n-1) 等价于 hash % n。详见 取余与模运算

当链表长度超过 8 且数组长度超过 64 时，链表转成红黑树（防止极端情况退化成O(n)）

key可以为null

HashMap允许一个null key（存在数组下标0的位置）和多个null value

TreeMap不允许null key（因为要比较排序）

TreeMap：key有序

底层是红黑树，key会自动排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Test
public void testTreeMap() {
Map<String, Integer> map = new TreeMap<>();
map.put("banana", 3);
map.put("apple", 5);
map.put("cherry", 1);

// 按key的自然顺序排列
System.out.println(map);  // {apple=5, banana=3, cherry=1}

// TreeMap特有的方法
TreeMap<String, Integer> treeMap = (TreeMap<String, Integer>) map;
System.out.println(treeMap.firstKey());   // apple
System.out.println(treeMap.lastKey());    // cherry
}

LinkedHashMap：保留插入顺序

HashMap + 双向链表，遍历时按照插入顺序输出

1
2
3
4
5
6
7
8
9
10
11
@Test
public void testLinkedHashMap() {
Map<String, Integer> map = new LinkedHashMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

System.out.println(map);  // {C=3, A=1, B=2} 按插入顺序！

// 还可以设置"访问顺序"模式，用来实现LRU缓存
}

Hashtable：线程安全但过时

方法都加了 synchronized，线程安全但效率低（锁整张表）

不允许null key和null value

别用了！ 要线程安全用 ConcurrentHashMap（分段锁/CAS，效率高得多）

HashMap vs TreeMap vs LinkedHashMap 对比

特性 HashMap TreeMap LinkedHashMap
底层结构 数组+链表+红黑树 红黑树 HashMap+双向链表
key顺序 无序 自然排序/Comparator 插入顺序
性能 O(1) O(log n) O(1)
null key 允许1个 不允许 允许1个
线程安全 否 否 否
适用场景 通用场景 需要key排序 需要保持顺序

常用方法速查

方法 作用 返回值
put(key, value) 放入键值对 旧value或null
get(key) 通过key取value value或null
getOrDefault(key, default) 取不到就返回默认值 value或default
containsKey(key) 是否包含某个key boolean
containsValue(value) 是否包含某个value boolean
remove(key) 删除键值对 被删的value
size() 键值对个数 int
isEmpty() 是否为空 boolean
keySet() 获取所有key的Set Set
values() 获取所有value的Collection Collection
entrySet() 获取所有键值对的Set Set
putIfAbsent(key, value) key不存在才放入 旧value或null

Map的遍历方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Test
public void testMapIteration() {
Map<String, Integer> scores = new HashMap<>();
scores.put("张三", 90);
scores.put("李四", 85);
scores.put("王五", 92);

// 方式1：遍历entrySet（最推荐，一次拿到key和value）
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

// 方式2：遍历keySet，再通过key去get
for (String name : scores.keySet()) {
    System.out.println(name + " : " + scores.get(name));
}

// 方式3：Java8 forEach
scores.forEach((name, score) ->
    System.out.println(name + " : " + score)
);
}

⚠️ 重写equals必须重写hashCode

如果你用自定义对象做HashMap的key，必须同时重写equals()和hashCode()

原因：HashMap先用hashCode()确定”柜子编号”，再用equals()在柜子里精确匹配

如果只重写equals不重写hashCode，两个”相等”的对象可能被分到不同的柜子里，就找不到了

详见 Object类 中的equals和hashCode约定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@Test
public void testEqualsHashCode() {
// 反面教材：没重写hashCode
class BadKey {
    String name;
    BadKey(String name) { this.name = name; }
    @Override
    public boolean equals(Object o) {
        return o instanceof BadKey && ((BadKey) o).name.equals(this.name);
    }
    // 没重写hashCode！
}

Map<BadKey, String> map = new HashMap<>();
map.put(new BadKey("test"), "value");
// 用"相同"的key去取，结果拿到null！
System.out.println(map.get(new BadKey("test")));  // null！因为hashCode不同
}

⭐ 安全角度：哈希碰撞DoS攻击

攻击原理：精心构造大量hashCode相同的key，让HashMap的某个桶变成超长链表，查询从O(1)退化成O(n)

攻击者发送大量这样的key作为HTTP参数，服务器解析参数时HashMap性能急剧下降，导致CPU飙升

JDK8的防御：链表长度超过8就转红黑树，最坏也是O(log n)，大幅缓解了攻击效果

其他防御手段

限制HTTP请求参数个数

使用随机化的hash种子（如String的hash在某些JDK版本支持随机种子）

这也是为什么JDK8要引入红黑树的原因之一，不只是性能优化，还有安全考量

代码综合示例：统计词频

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Test
public void testWordCount() {
String text = "the quick brown fox jumps over the lazy dog the fox";
String[] words = text.split(" ");

Map<String, Integer> wordCount = new HashMap<>();
for (String word : words) {
    // 方式1：传统写法
    // wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);

    // 方式2：Java8 merge写法
    wordCount.merge(word, 1, Integer::sum);
}

System.out.println(wordCount);
// {the=3, quick=1, brown=1, fox=2, jumps=1, over=1, lazy=1, dog=1}

// 找出出现最多的单词
String maxWord = Collections.max(wordCount.entrySet(),
    Map.Entry.comparingByValue()).getKey();
System.out.println("出现最多的单词：" + maxWord);  // the
}

常见坑

坑1：用可变对象做key

如果key放进去之后被修改了，hashCode变了，就再也找不到这个entry了

最佳实践：用String、Integer等不可变对象做key

坑2：HashMap不是线程安全的

多线程并发put可能导致死循环（JDK7的链表头插法）或数据丢失

多线程环境用 ConcurrentHashMap 或者 Collections工具类 中的 Collections.synchronizedMap()

坑3：遍历时修改Map

和 Collection体系 一样，遍历时直接修改会抛 ConcurrentModificationException

要用 Iterator 的 remove()，或者收集要删除的key，遍历结束后再删

练习题

题1：两数之和 —— 给一个整数数组和一个目标值，找出数组中两个数加起来等于目标值的下标

提示：遍历数组，对每个数用HashMap查找 target - 当前数 是否存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Test
public void exercise1() {
int[] nums = {2, 7, 11, 15};
int target = 9;
Map<Integer, Integer> map = new HashMap<>();  // 值 -> 下标
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (map.containsKey(complement)) {
        System.out.println("[" + map.get(complement) + ", " + i + "]");
        // 输出 [0, 1]，因为 nums[0] + nums[1] = 2 + 7 = 9
        return;
    }
    map.put(nums[i], i);
}
}

题2：字符统计 —— 统计一个字符串中每个字符出现的次数，按次数从高到低排序输出

提示：先用HashMap统计，再用TreeMap或Stream排序

题3：分组 —— 给定一个学生列表（姓名+班级），按班级分组输出

提示：Map<String, List<String>>，key是班级，value是该班级的学生列表

上一章 目录 下一章
Collection体系 java基础 Collections工具类