Java Map集合整理
在Java集合框架中，Map接口是一个非常重要的成员，它用于存储键值对（Key-Value）数据。与Collection接口不同，Map不是存储单个元素，而是存储一对一的映射关系。本文将深入探讨三种常用的Map实现：HashMap、TreeMap和HashTable，分析它们的特点、底层原理、扩容机制以及适用场景。
一、Map接口概述
Map接口定义了一组操作键值对的方法，核心特性包括：
每个键最多映射到一个值，键不允许重复，重复的键会覆盖旧值。
值可以重复。
提供了按键查找、插入、删除等操作。
常见的Map实现类有HashMap、LinkedHashMap、TreeMap、HashTable等。下面我们将逐一解析。
二、HashMap：最常用的Map
1. 特点
底层结构：数组 + 链表 + 红黑树（JDK 8 及以后）。当链表长度超过阈值（默认为8）且数组长度大于64时，链表会转换为红黑树，以提高查询效率。
允许null：键最多允许一个
null，值可以多个null。无序：不保证插入顺序和遍历顺序一致，也不保证顺序随时间保持不变。
线程不安全：多线程环境下可能导致数据不一致或死循环（如JDK 7的扩容头插法可能产生环形链表）。
2. 常用方法
put(K key, V value) // 添加或更新键值对 get(Object key) // 根据键获取值，不存在返回null remove(Object key) // 删除指定键的映射 size() // 返回键值对数量 clear() // 清空所有映射 isEmpty() // 判断是否为空 containsKey(Object key) // 判断是否包含指定键 containsValue(Object value) // 判断是否包含指定值 replace(K key, V value) // 替换指定键的值 putAll(Map<? extends K,? extends V> m) // 将另一个Map的所有映射添加到当前Map3. HashMap的扩容流程
触发条件
情况一：当
size > 阈值（threshold）时，阈值 = 当前容量 × 负载因子（默认0.75）。情况二：当某个链表长度超过8，但数组长度小于64时，也会触发扩容（而非树化）。
扩容步骤
创建新数组：新容量为原容量的2倍（
newCap = oldCap << 1）。元素迁移：将旧数组中的元素重新映射到新数组。JDK 1.7和1.8的迁移方式有显著不同。
JDK 1.7 vs JDK 1.8 扩容对比
| 对比项 | JDK 1.7 | JDK 1.8 |
|---|---|---|
| 插入方式 | 头插法（扩容后链表可能倒置） | 尾插法（保持原链表顺序） |
| 迁移方式 | 逐个计算新下标，然后插入新数组（效率较低） | 将链表拆分为两条（低位链和高位链），整体迁移 |
| 并发安全性 | 多线程扩容可能形成环形链表，导致死循环 | 避免了环形链表问题，但仍有数据丢失风险 |
| 红黑树支持 | 无红黑树，链表过长时查询效率下降 | 链表长度>8且数组长度>64时树化，扩容时可能退化 |
在JDK 1.8中，元素迁移利用了哈希值与原容量的与运算（hash & oldCap）：
若结果为0，则元素在新数组中的下标不变（低位链）。
若结果为1，则新下标 = 旧下标 + 旧容量（高位链）。
这种方式避免了重新计算哈希，提升了扩容效率。
三、TreeMap：有序的Map
1. 特点
底层结构：红黑树（一种自平衡的二叉查找树），保证键的自然顺序或自定义顺序。
有序性：键默认按照自然顺序（如数字升序、字母字典序）排序，也可以通过
Comparator实现定制排序。不允许键为null：因为需要比较，但值可以为null。
线程不安全：非同步。
2. 排序方式
自然排序：键必须实现
Comparable接口，例如Integer、String等已经默认实现了该接口。定制排序：在创建
TreeMap时传入一个Comparator对象，自定义比较规则。
示例：
// 自然排序 TreeMap<Integer, String> map1 = new TreeMap<>(); // 定制排序（降序） TreeMap<Integer, String> map2 = new TreeMap<>((a, b) -> b - a);3. 常用方法
除了标准的Map方法外，TreeMap还提供了一些与顺序相关的方法：
firstKey() // 返回第一个（最小）键 lastKey() // 返回最后一个（最大）键 lowerKey(K key) // 返回小于给定键的最大键 higherKey(K key)// 返回大于给定键的最小键 subMap(K fromKey, K toKey) // 返回键范围视图四、HashTable：线程安全的古董
1. 特点
底层结构：哈希表（数组+链表），与
HashMap类似，但所有方法都用synchronized修饰，因此是线程安全的。键值限制：键和值都不允许为null，否则抛出
NullPointerException。性能较低：由于同步开销，单线程环境下不如
HashMap。初始容量：默认11，负载因子0.75。扩容时新容量 = 旧容量 × 2 + 1。
遍历方式：支持
Enumeration和Iterator，但Enumeration是早期遗留接口。
2. 与HashMap的区别
| 特性 | HashMap | HashTable |
|---|---|---|
| 线程安全 | 否 | 是（方法级同步） |
| 键值允许null | 键最多一个null，值多个null | 都不允许null |
| 初始容量 | 16 | 11 |
| 扩容 | 2倍 | 2倍+1 |
| 迭代器 | Iterator（fail-fast） | Iterator或Enumeration（fail-fast? Enumeration不会抛出ConcurrentModificationException） |
| 性能 | 较高 | 较低 |
| 出现时间 | JDK 1.2 | JDK 1.0（遗留类） |
注意：如果需要线程安全的Map，现在更推荐使用ConcurrentHashMap，它采用分段锁或CAS机制，并发性能远高于HashTable。
五、扩展：Set集合与Map的关系
Set接口的实现类（如HashSet、TreeSet）底层其实都使用了对应的Map：
HashSet内部维护一个HashMap，元素作为键，值是一个固定的Object常量。TreeSet内部使用TreeMap，元素作为键。
因此，理解了Map，也就基本理解了Set。
六、如何选择合适的Map？
单线程环境，对顺序无要求：首选
HashMap，性能最高。需要保持插入顺序：使用
LinkedHashMap（本笔记未详述，它继承自HashMap，通过双向链表维护顺序）。需要对键排序：使用
TreeMap。多线程环境，需要线程安全：
如果并发量不高，可用
Collections.synchronizedMap(new HashMap<>())包装。高并发场景，强烈推荐
ConcurrentHashMap（JDK 1.8后采用CAS+synchronized，性能优异）。
不允许null键值的遗留系统：可能仍需使用
HashTable，但建议升级。