第一部分：Map接口概述

理解Java Map接口的基本概念和主要实现

学习目标

掌握Map接口的核心方法，理解键值对存储的基本原理

Map接口核心方法

  • put(K key, V value)：添加键值对
  • get(Object key)：根据键获取值
  • remove(Object key)：删除指定键的映射
  • containsKey(Object key)：检查是否包含指定键
  • keySet()：返回所有键的集合
  • values()：返回所有值的集合
  • entrySet()：返回所有键值对的集合

Map实现的选择依据

  • 是否需要按键排序？
  • 是否需要保持插入顺序？
  • 对性能的要求如何？
  • 是否需要线程安全？
  • 键的类型是什么？

HashMap

  • 基于哈希表
  • 无序存储
  • O(1)时间复杂度
  • 允许null键/值

TreeMap

  • 基于红黑树
  • 按键排序
  • O(log n)时间复杂度
  • 不允许null键

LinkedHashMap

  • 哈希表+双向链表
  • 保持插入顺序
  • O(1)时间复杂度
  • 允许null键/值

第二部分：HashMap详解

最常用的Map实现，基于哈希表实现

学习目标

掌握HashMap的工作原理、使用方法和常见错误

1

HashMap基本使用

创建和操作HashMap的基本方法

// 创建HashMap
import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
	    public static void main(String[] args) {
	    // 创建HashMap实例
Map<String, Integer> scores = new HashMap<>();

	    // 添加键值对
scores.put("Alice", 90);
scores.put("Bob", 85);
scores.put("Charlie", 95);

	    // 获取值
	    int aliceScore = scores.get("Alice");
System.out.println("Alice's score: " + aliceScore); // 输出: Alice's score: 90

	    // 检查键是否存在
	    boolean hasBob = scores.containsKey("Bob"); // true

	    // 遍历HashMap
	    for (Map.Entry<String, Integer> entry : scores.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}

提示：HashMap不保证元素的顺序，迭代顺序可能与插入顺序不同

2

HashMap工作原理

HashMap的内部结构和哈希碰撞处理

键1
桶1
值1
键2
桶2
值2
键3
桶1
值3
  • 基于数组+链表/红黑树实现
  • 使用哈希函数计算键的存储位置
  • 哈希碰撞时使用链表存储（Java 8后使用红黑树优化）
  • 默认初始容量为16，负载因子为0.75

常见错误1：使用可变对象作为键

Map<Student, Integer> studentScores = new HashMap<>();
Student alice = new Student("Alice");
studentScores.put(alice, 90);

// 修改Alice的属性
alice.setName("Alicia");

// 尝试获取值 - 可能失败
Integer score = studentScores.get(alice); // 可能返回null

解决方案：使用不可变对象作为键，或确保对象属性不变

第三部分：TreeMap详解

基于红黑树实现的有序Map

学习目标

掌握TreeMap的排序特性、使用方法和性能特点

1

TreeMap基本使用

创建和操作TreeMap的基本方法

import java.util.TreeMap;
import java.util.Map;

public class TreeMapExample {
	    public static void main(String[] args) {
	    // 创建TreeMap实例（自然顺序）
Map<String, Integer> scores = new TreeMap<>();

scores.put("Charlie", 95);
scores.put("Alice", 90);
scores.put("Bob", 85);

	    // 遍历TreeMap（按键排序）
	    for (Map.Entry<String, Integer> entry : scores.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
	    // 输出顺序: Alice:90, Bob:85, Charlie:95

	    // 使用自定义比较器
Map<String, Integer> reverseScores = new TreeMap<>((a, b) -> b.compareTo(a));
reverseScores.putAll(scores);

	    // 获取第一个和最后一个元素
String firstKey = ((TreeMap<String, Integer>) reverseScores).firstKey();
String lastKey = ((TreeMap<String, Integer>) reverseScores).lastKey();
}
}

提示：TreeMap保证元素按键的自然顺序或自定义比较器顺序排序

2

TreeMap工作原理

红黑树结构和排序机制

键C
根节点
值C
键A
左子节点
值A
键E
右子节点
值E
  • 基于红黑树（自平衡二叉查找树）实现
  • 所有操作的时间复杂度为O(log n)
  • 元素按键排序存储
  • 支持范围查询（subMap, headMap, tailMap）

常见错误2：未实现Comparable接口

class Student {
String name;
	// 未实现Comparable接口
}

Map<Student, Integer> studentScores = new TreeMap<>();
studentScores.put(new Student("Alice"), 90); // ClassCastException

解决方案：键类实现Comparable接口或在构造函数中提供Comparator

第四部分：LinkedHashMap详解

保持插入顺序或访问顺序的Map实现

学习目标

掌握LinkedHashMap的顺序特性及其在LRU缓存中的应用

1

LinkedHashMap基本使用

创建和操作LinkedHashMap的基本方法

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
	    public static void main(String[] args) {
	    // 创建LinkedHashMap（插入顺序）
Map<String, Integer> scores = new LinkedHashMap<>();

scores.put("Charlie", 95);
scores.put("Alice", 90);
scores.put("Bob", 85);

	    // 遍历LinkedHashMap（保持插入顺序）
	    for (Map.Entry<String, Integer> entry : scores.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
	    // 输出顺序: Charlie:95, Alice:90, Bob:85

	    // 创建访问顺序的LinkedHashMap（LRU缓存）
Map<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
	    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
	    return size() > 3; // 最大容量为3
}
};

lruCache.put("A", 1);
lruCache.put("B", 2);
lruCache.put("C", 3);
lruCache.get("A"); // 访问A，使其成为最近使用的
lruCache.put("D", 4); // 移除最老的条目B
}
}

提示：LinkedHashMap在HashMap基础上增加了双向链表维护顺序

2

LinkedHashMap工作原理

哈希表+双向链表的结构

键A
桶1
值A
键B
桶2
值B
键C
桶1
值C
头节点
→
尾节点
  • 继承自HashMap，增加了双向链表
  • 链表维护元素的插入顺序或访问顺序
  • 访问顺序模式适合实现LRU缓存
  • 性能略低于HashMap（维护链表开销）

常见错误3：误解访问顺序

Map<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("A", 1);
map.put("B", 2);
map.get("A"); // 访问A

// 期望顺序: B, A
// 实际顺序: A, B（因为访问A后它成为最近使用的）

解决方案：理解访问顺序模式下，最近访问的元素会移动到链表末尾

第五部分：比较与总结

三种Map实现的对比与选择指南

学习目标

根据需求选择合适的Map实现，避免常见错误

特性 HashMap TreeMap LinkedHashMap
底层实现 哈希表 红黑树 哈希表+双向链表
顺序 无序 按键排序 插入顺序/访问顺序
时间复杂度 O(1) O(log n) O(1)
允许null键 是 否 是
线程安全 否 否 否
使用场景 通用键值存储 需要排序的场景 需要保持顺序或LRU缓存

选择指南

  • 不需要顺序：HashMap
  • 需要按键排序：TreeMap
  • 需要保持插入顺序：LinkedHashMap
  • 实现LRU缓存：LinkedHashMap
  • 性能优先：HashMap

性能优化

  • HashMap：设置合理初始容量和负载因子
  • TreeMap：确保键的hashCode和equals正确实现
  • LinkedHashMap：使用访问顺序实现高效缓存
  • 大集合：考虑ConcurrentHashMap

线程安全

  • 多线程环境使用ConcurrentHashMap
  • 或使用Collections.synchronizedMap()
  • 避免在迭代时修改集合
  • 使用ConcurrentHashMap代替Hashtable

常见错误4：迭代时修改集合

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);

for (String key : map.keySet()) {
	if ("A".equals(key)) {
map.remove(key); // ConcurrentModificationException
}
}

解决方案：使用迭代器的remove方法，或使用ConcurrentHashMap

第六部分：总结与练习

巩固学习成果，通过练习掌握Map实现的使用技巧

学习目标

总结Map实现要点，通过实践加深理解

关键知识点总结

  • HashMap：最高效的通用Map实现，无序存储
  • TreeMap：按键排序的Map实现，基于红黑树
  • LinkedHashMap：保持插入顺序或访问顺序的Map实现
  • 根据需求选择合适的Map实现
  • 避免使用可变对象作为键
  • 在多线程环境中使用线程安全的Map实现

动手练习

  1. 使用HashMap统计一段文本中每个单词出现的次数
  2. 使用TreeMap实现一个按学生成绩排序的成绩单
  3. 使用LinkedHashMap实现一个LRU缓存，最大容量为100
  4. 比较三种Map实现在插入、查找和删除操作上的性能差异
  5. 实现一个线程安全的Map包装器，支持基本的同步操作