第五章 集合框架

第四节 Map接口与实现类

---

概述

本节内容聚焦Java集合框架中的Map接口及其主要实现类，深入讲解Map的基本概念、核心方法、内部原理及常用实现类的特点与应用。Map作为Java集合框架的重要组成部分，用于存储键值对映射关系，是程序设计中不可或缺的数据结构。通过本节学习，考生能够系统掌握Map接口的定义、常用操作、HashMap、TreeMap、LinkedHashMap等主要实现类的使用场景和性能特点，提升对Java集合的理解与应用能力，为全国计算机等级考试二级Java语言程序设计部分的Map知识点打下坚实基础。

---

核心概念

1. Map接口：Java集合框架中的一种特殊集合，用于存储键值对（Key-Value）映射。其中，每个键唯一对应一个值，键和值都可以是任意对象。

2. 键（Key）：Map中的唯一标识，用于查找对应的值。键不能重复，但值可以重复。

3. 值（Value）：与键关联的数据，可以重复。

4. Entry接口：Map中键值对的内部表示，包含getKey()和getValue()方法。

5. HashMap：基于哈希表的Map实现，允许键和值为null，非线程安全，查询效率高。

6. TreeMap：基于红黑树实现的有序Map，键按照自然顺序或自定义比较器排序，不能包含null键。

7. LinkedHashMap：基于哈希表和链表实现，保持插入顺序或访问顺序的Map。

8. 负载因子（load factor）：哈希表扩容的阈值指标，当元素个数超过容量乘以负载因子时，哈希表会扩容。

9. 哈希碰撞（Hash Collision）：不同键通过哈希函数映射到相同索引，影响性能。

---

原理分析

1. Map接口设计原理

Map接口设计基于键值对映射思想，允许快速查找、插入和删除某个键对应的值。其核心思想是利用键的唯一性，通过键快速定位对应的值，避免遍历集合。

核心方法包括：

• put(key, value)：添加或修改映射
• get(key)：通过键获取值
• remove(key)：删除指定键及其对应值
• containsKey(key)、containsValue(value)：判断键或值是否存在
• keySet()、values()、entrySet()：分别返回所有键、值和键值对集合

2. HashMap工作原理

HashMap通过哈希函数将键映射到数组索引，实现快速访问。其核心结构是一个数组，每个数组元素是链表或红黑树。

主要步骤：

• 计算键的hashCode()，并通过扰动函数散布哈希值
• 根据哈希值计算数组索引（hash & (capacity - 1)）
• 如果索引处为空，直接插入
• 如果不为空，遍历链表或树，检查键是否存在：
  • 存在则替换值
  • 不存在则追加节点
• 当链表长度超过阈值（默认8），转成红黑树以提升查找效率
• 当元素个数超过负载因子*容量时，触发扩容，容量翻倍

3. TreeMap工作原理

TreeMap基于红黑树实现，保证键值对按照键的自然顺序或Comparator排序。

红黑树是一种自平衡的二叉搜索树，确保插入、删除、查找操作时间复杂度为O(log n)。

注意：

• 键必须实现Comparable接口或在构造时传入Comparator
• 不允许null键

4. LinkedHashMap工作原理

LinkedHashMap继承自HashMap，内部通过双向链表维护元素的插入顺序或访问顺序。

通过重写HashMap的链表结构，保证遍历时顺序一致，适合缓存和顺序访问场景。

---

详细内容

1. Map接口详解

Map接口定义了一组用于存储和访问键值对的方法：

• put(K key, V value)：将指定键映射到指定值，返回旧值或null
• get(Object key)：返回指定键对应的值，找不到则返回null
• remove(Object key)：删除指定键及其对应值，返回被删除的值
• containsKey(Object key)：判断Map是否包含指定键
• containsValue(Object value)：判断Map是否包含指定值
• keySet()：返回包含所有键的Set集合
• values()：返回包含所有值的Collection集合
• entrySet()：返回包含所有键值对的Set集合，元素类型为Map.Entry

Map接口的设计体现了键值映射的核心思想，常用来实现字典、缓存、配置管理等功能。

2. HashMap实现细节

HashMap是最常用的Map实现类，性能优良，适合大部分场景。其重要特性：

• 允许null键和null值
• 非线程安全，多线程环境需用ConcurrentHashMap或同步包装
• 默认初始容量16，负载因子0.75，这意味着当Map中元素超过16*0.75=12时会扩容
• 扩容机制：容量扩大一倍，重新计算所有元素索引
• 哈希函数：通过扰动函数提高哈希值的均匀性，减少碰撞
• 链表转红黑树：当单个桶中元素超过8个时，结构转为红黑树，提升查询效率

使用HashMap时应注意避免自定义对象重写hashCode和equals方法，保证哈希分布均匀。

3. TreeMap使用与特性

TreeMap保证键值对有序，适合需要排序访问的场景。特点：

• 键必须可比较，否则会抛出ClassCastException
• 不支持null键，否则会抛出NullPointerException
• 插入、删除、查询时间复杂度均为O(log n)
• 支持自定义排序规则，通过传入Comparator

由于底层为红黑树，TreeMap的性能在排序操作中优于HashMap，但单纯查找时稍逊。

4. LinkedHashMap的应用优势

LinkedHashMap结合了HashMap的高效查找和链表的顺序维护。特点包括：

• 维护插入顺序或访问顺序，通过构造函数参数accessOrder控制
• 适合实现缓存机制，如LRU缓存
• 遍历顺序固定，便于调试和输出有序数据

使用LinkedHashMap时，可以重写removeEldestEntry方法实现自动淘汰旧元素。

---

实例分析

实例1：使用HashMap统计单词出现次数

背景：统计一段文本中每个单词出现的频率。

代码示例：

import java.util.HashMap;
import java.util.Map;

public class WordCount {
    public static void main(String[] args) {
        String text = "java java map map hashMap treeMap linkedHashMap java";
        String[] words = text.split(" ");
        Map<String, Integer> wordCount = new HashMap<>();

        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

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

分析：

• 利用HashMap的put和getOrDefault方法统计出现次数
• HashMap允许键为字符串，值为计数器
• 性能高效，适合大数据量统计

结论：HashMap是统计频率、计数等映射需求的理想选择。

实例2：TreeMap实现学生成绩排序

背景：按学生姓名排序存储成绩。

代码示例：

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

public class StudentScores {
    public static void main(String[] args) {
        Map<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 85);
        scores.put("Bob", 92);
        scores.put("Charlie", 78);

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

分析：

• TreeMap自动按键（学生姓名）排序
• 不允许null键
• 适合需要顺序访问的场景

结论：TreeMap适合存储需要排序输出的键值对数据。

实例3：使用LinkedHashMap实现简单LRU缓存

背景：限制缓存大小，自动淘汰最久未访问的元素。

代码示例：

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        cache.get(1); // 访问1，使其成为最近使用
        cache.put(4, "D"); // 淘汰2

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

分析：

• LinkedHashMap构造时设置accessOrder为true，维护访问顺序
• 重写removeEldestEntry实现自动淘汰
• 适用于缓存设计

结论：LinkedHashMap是实现缓存策略的理想工具。

---

常见误区

1. 误区：HashMap允许多个null键

   • 实际上，HashMap只允许一个null键，因为键唯一。

2. 误区：TreeMap允许null键

   • 事实：TreeMap不允许null键，否则会抛出NullPointerException。

3. 误区：HashMap线程安全

   • HashMap在多线程下可能导致数据不一致，应使用ConcurrentHashMap或外部同步。

4. 误区：重写equals但未重写hashCode

   • 违反hashCode和equals一致性原则，导致HashMap无法正确工作。

5. 误区：认为LinkedHashMap和HashMap性能一样

   • LinkedHashMap由于维护链表结构，插入和删除性能略低于HashMap。

---

应用场景

1. 缓存系统：利用LinkedHashMap实现LRU缓存，自动淘汰过期数据。

2. 数据统计：使用HashMap高效统计频率、计数，如词频分析、日志统计。

3. 排序映射：TreeMap用于需要有序访问的场景，如按键排序的报表、排行榜。

4. 配置管理：使用Map存储配置信息，方便键值对查找和修改。

5. 去重与映射：利用Map实现复杂数据的唯一标识及快速映射。

---

知识拓展

• ConcurrentHashMap：线程安全的HashMap变种，适合高并发环境。
• WeakHashMap：基于弱引用的HashMap，允许键被垃圾回收。
• EnumMap：专门为枚举类型键设计的高效Map。
• Guava的ImmutableMap：不可变Map，线程安全且性能优。

深入理解这些扩展类，有助于应对更复杂的编程场景。

---

总结回顾

本节全面介绍了Java集合框架中Map接口及其主要实现类：HashMap、TreeMap和LinkedHashMap。重点掌握了：

• Map接口的定义与核心方法
• HashMap的哈希机制、链表与红黑树结构、扩容机制和性能特点
• TreeMap基于红黑树的排序功能与使用限制
• LinkedHashMap的顺序维护及缓存应用
• 典型实例展示了Map在实际编程中的应用
• 常见误区帮助避免使用错误
• 典型应用场景体现Map的实用价值

通过深入学习本节内容，考生能够全面理解Map接口使用及其背后原理，为Java程序设计的集合操作提供有力支持，提升编程能力和考试竞争力。

---