Javajava算法
Java Map 常用方法与实现类深度解析
Java Map 集合框架包含多种实现类，其中 HashMap 基于哈希表性能最高但线程不安全，ConcurrentHashMap 支持高并发，TreeMap 基于红黑树实现排序。文章详细解析了各实现类的底层结构、源码逻辑及核心方法，涵盖扩容机制、遍历方式、Java 8+ 新特性及常见陷阱，为开发者提供选型指南与最佳实践建议。
Java Map 集合框架包含多种实现类，其中 HashMap 基于哈希表性能最高但线程不安全，ConcurrentHashMap 支持高并发，TreeMap 基于红黑树实现排序。文章详细解析了各实现类的底层结构、源码逻辑及核心方法，涵盖扩容机制、遍历方式、Java 8+ 新特性及常见陷阱，为开发者提供选型指南与最佳实践建议。
在 Java 集合框架中，Map 是最核心、最常用的数据结构之一。与 Collection 体系下的 List、Set 不同，Map 采用键值对（Key-Value）的存储方式，每个键映射到一个值，键在同一个 Map 中不可重复。这种设计使得 Map 特别适合需要通过键快速查找值的场景，如缓存系统、配置管理、数据索引等。
本文将从 Map 接口的设计哲学出发，深入剖析 HashMap、LinkedHashMap、TreeMap、Hashtable、ConcurrentHashMap 等主要实现类的底层原理、源码实现、性能特性，并结合 Java 8+ 的新特性，帮助读者全面掌握 Map 的使用技巧和选型策略。
Java 中的 Map 体系是一个独立于 Collection 的并行框架，其核心继承结构如下：
Map (interface) ├── HashMap (class) │ └── LinkedHashMap (class) ├── TreeMap (class) ├── Hashtable (class) │ └── Properties (class) └── ConcurrentMap (interface) └── ConcurrentHashMap (class)
equals() 和 hashCode() 保证从数据结构角度看，Map 的存储可以分为三个层面：
Set 集合 → 无序、不可重复，key 所在的类必须重写 equals() 和 hashCode()Collection 集合 → 无序、可重复，value 所在的类需要重写 equals()Entry 对象，所有 entry 构成一个 Set 集合 → 无序、不可重复这种设计体现了 Map 与 Set、List 的内在联系，也为后续的遍历操作奠定了基础。
HashMap 是基于哈希表实现的 Map，它根据键的 hashCode 值存储数据，具有 O(1) 的平均查找时间，是日常开发中使用频率最高的 Map 实现。
HashMap 的底层实现经历了从 JDK 7 到 JDK 8 的重要优化：
| 版本 | 底层结构 | 节点类型 | 特点 |
|---|---|---|---|
| JDK 7 | 数组 + 链表 | Entry | 头插法，扩容时可能产生循环链表 |
| JDK 8+ | 数组 + 链表 + 红黑树 | Node/TreeNode | 尾插法，链表长度>8 且数组长度>64 时树化 |
// 默认初始容量 16，必须是 2 的 n 次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 树化最小数组容量
static final int MIN_TREEIFY_CAPACITY = 64;
为什么默认负载因子是 0.75？
负载因子表示散列表的空间使用程度。0.75 是时间与空间的折中选择：
为什么容量必须是 2 的 n 次幂？
这涉及 HashMap 的核心优化：
(n - 1) & hash 等价于 hash % n，位运算速度远快于取模为什么链表转红黑树的阈值是 8？
这是基于泊松分布的概率统计。在理想随机 hashCode 下，链表节点数出现的概率遵循泊松分布，节点数为 8 的概率接近千万分之六，此时链表查询性能已经很差，转为红黑树可以挽回性能。而树节点占用的空间是普通节点的两倍，当节点数降到 6 时再转回链表，避免频繁转换。
HashMap 的 put 方法是理解其工作原理的关键入口：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 数组延迟初始化：首次 put 时创建数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 计算下标，如果该位置为空直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 3. 处理 Hash 冲突
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 链表遍历
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 尾插法
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 4. 找到相同 key，替换 value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 5. 检查是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
执行流程总结：
(n - 1) & hash 计算数组下标当元素个数超过 threshold = capacity * loadFactor 时，HashMap 会进行扩容：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 计算新容量
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
// ... 初始化逻辑
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 数据迁移
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 单个节点直接重新计算下标
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 红黑树拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 链表拆分：保持原顺序
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 关键优化：根据 hash 值新增位判断新位置
if ((e.hash & oldCap) == 0) {
if (loTail == null) loHead = e;
else loTail.next = e;
loTail = e;
} else {
if (hiTail == null) hiHead = e;
else hiTail.next = e;
hiTail = e;
}
e = next;
} while (e != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead; // 原索引位置
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; // 原索引 + 旧容量
}
}
}
}
}
return newTab;
}
扩容优化点：
e.hash & oldCap 是否为 0，为 0 则留在原位，否则移到 原位置+oldCapHashMap 是线程不安全的，多线程环境下可能出现以下问题：
++size 操作非原子性，多个线程同时 put 可能导致 size 偏小解决方案：
Collections.synchronizedMap(new HashMap<>())ConcurrentHashMap（推荐）LinkedHashMap 继承自 HashMap，在 HashMap 基础上通过双向链表维护元素的顺序。
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after; // 前驱和后继指针
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
LinkedHashMap 在 HashMap 的 Node 基础上增加了 before 和 after 指针，构成了一个双向链表，用于记录元素的插入顺序或访问顺序。
LinkedHashMap 支持两种迭代顺序：
// 指定访问顺序
Map<String,String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("a", "1");
map.put("b", "2");
map.get("a"); // 访问 a，a 会被移动到链表尾部
// 迭代顺序：b, a（最近访问的在最后）
利用访问顺序模式，可以轻松实现 LRU（Least Recently Used）缓存：
class LRUCache<K,V> extends LinkedHashMap<K,V> {
private final int maxCapacity;
public LRUCache(int maxCapacity) {
super(16, 0.75f, true); // 启用访问顺序
this.maxCapacity = maxCapacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > maxCapacity; // 超过容量时移除最久未访问的元素
}
}
TreeMap 实现了 SortedMap 和 NavigableMap 接口，底层基于红黑树实现，能够对键进行排序。
TreeMap 要求键要么实现 Comparable 接口（自然排序），要么在构造时提供 Comparator（定制排序）：
// 自然排序：键必须实现 Comparable
TreeMap<Integer,String> naturalMap = new TreeMap<>();
// 定制排序：提供 Comparator
TreeMap<String,Integer> customMap = new TreeMap<>((s1, s2) -> s2.compareTo(s1)); // 降序
TreeMap 提供了丰富的导航方法：
TreeMap<Integer,String> map = new TreeMap<>();
map.put(1, "one");
map.put(3, "three");
map.put(5, "five");
map.put(7, "seven");
Integer firstKey = map.firstKey(); // 1
Integer lastKey = map.lastKey(); // 7
Integer lowerKey = map.lowerKey(5); // 3（小于 5 的最大键）
Integer floorKey = map.floorKey(4); // 3（小于等于 4 的最大键）
Integer ceilingKey = map.ceilingKey(4); // 5（大于等于 4 的最小键）
Integer higherKey = map.higherKey(5); // 7（大于 5 的最小键）
// 子 Map 视图
SortedMap<Integer,String> headMap = map.headMap(5); // 键<5 的部分
SortedMap<Integer,String> tailMap = map.tailMap(5); // 键>=5 的部分
SortedMap<Integer,String> subMap = map.subMap(3, 6); // 3<=键<6
TreeMap 的核心是比较逻辑，它在 put、get、remove 等操作中都会用到：
final int compare(Object k1, Object k2) {
return comparator == null ? ((Comparable<?superK>)k1).compareTo((K)k2) : comparator.compare((K)k1,(K)k2);
}
如果既没有提供 Comparator，键也没有实现 Comparable，在插入时会抛出 ClassCastException。
字符串键的特殊性：字符串的 compareTo 基于 Unicode 值，数字字符串排序时需注意
// 错误：字符串排序按字典序，"22"会排在"5"前面
TreeMap<String,Integer> map = new TreeMap<>();
map.put("5", 1);
map.put("22", 2);
// 实际顺序：22, 5
// 正确：转为整数比较
TreeMap<String,Integer> map = new TreeMap<>((a, b) -> Integer.parseInt(a) - Integer.parseInt(b));
Hashtable 是 JDK 1.0 就存在的古老实现类，具有以下特点：
2*old+1Hashtable<String,Integer> table = new Hashtable<>();
table.put("key", 1);
// table.put(null, 2); // 运行时异常
性能对比：
Properties 继承自 Hashtable，专门用于处理配置文件，键和值都是 String 类型。
Properties props = new Properties();
props.setProperty("url", "jdbc:mysql://localhost:3306/db");
props.setProperty("username", "root");
props.setProperty("password", "123456");
// 加载配置文件
try(InputStream input = new FileInputStream("config.properties")) {
props.load(input);
String url = props.getProperty("url");
String username = props.getProperty("username");
}
常用方法：
load(InputStream) / store(OutputStream)：加载/存储配置文件getProperty(String key, String defaultValue)：获取属性，可指定默认值list(PrintStream)：打印所有属性ConcurrentHashMap 是 Java 并发包（java.util.concurrent）中提供的线程安全且高性能的 Map 实现。
ConcurrentHashMap 的设计目标是：在保证线程安全的同时，提供比 Hashtable 更高的并发性能。
| 实现类 | 锁策略 | 并发度 | 性能 |
|---|---|---|---|
| Hashtable | 全表锁 | 极低 | 差 |
| Collections.synchronizedMap | 全表锁 | 极低 | 差 |
| ConcurrentHashMap JDK 7 | 分段锁 | 16 | 高 |
| ConcurrentHashMap JDK 8+ | CAS + synchronized + 细粒度锁 | 极高 | 非常高 |
JDK 7 的 ConcurrentHashMap 采用 Segment 分段锁机制：
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile HashEntry<K,V>[] table; // ...
}
JDK 8 对 ConcurrentHashMap 进行了重大重构：
// putVal 核心片段
final V putVal(K key, V value, boolean onlyIfAbsent) {
// ... 非空校验等
for(Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); // 初始化，CAS 保证线程安全
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 该位置为空，CAS 尝试插入
if (casTabAt(tab, i, null, newNode<K,V>(hash, key, value, null)))
break;
} else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f); // 帮助扩容
else {
V oldVal = null;
synchronized(f) { // 锁住链表头节点
// 链表或红黑树操作
}
}
}
}
ConcurrentHashMap 的迭代器是弱一致性的：
ConcurrentHashMap 提供了强大的批量操作 API：
ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
// forEach：遍历每个元素
map.forEach(1, (k, v) -> System.out.println(k + ":" + v));
// search：查找第一个符合条件的元素
String result = map.search(1, (k, v) -> v > 100 ? k : null);
// reduce：累加操作
Integer sum = map.reduceValues(1, Integer::sum);
// 用作频率统计（MultiSet）
ConcurrentHashMap<String,LongAdder> freqs = new ConcurrentHashMap<>();
freqs.computeIfAbsent("word", k -> new LongAdder()).increment();
parallelismThreshold 参数控制并行度：小于阈值时串行执行，大于阈值时并行执行。
| 方法 | 描述 | 返回值说明 |
|---|---|---|
put(K key, V value) | 添加键值对 | 返回该 key 之前的 value，如果没有则返回 null |
get(Object key) | 根据 key 获取 value | 存在则返回 value，否则返回 null |
remove(Object key) | 删除键值对 | 返回被删除的 value |
clear() | 清空所有键值对 | void |
size() | 返回键值对数量 | int |
isEmpty() | 判断是否为空 | boolean |
| 方法 | 描述 |
|---|---|
containsKey(Object key) | 判断是否包含指定键 |
containsValue(Object value) | 判断是否包含指定值（HashMap 中效率较低，需遍历） |
getOrDefault(Object key, V defaultValue) | 获取值，不存在则返回默认值 |
Map 的遍历方式多样，可根据场景选择：
for(Map.Entry<String,Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
for(String key : map.keySet()) {
System.out.println(key + ": " + map.get(key));
}
// 缺点：每次 get 都需要二次查找，效率较低
for(Integer value : map.values()) {
System.out.println(value);
}
Iterator<Map.Entry<String,Integer>> iterator = map.entrySet().iterator();
while(iterator.hasNext()) {
Map.Entry<String,Integer> entry = iterator.next();
if(entry.getValue() < 0) {
iterator.remove(); // 安全删除
}
}
map.forEach((key, value) -> System.out.println(key + ": " + value));
map.entrySet().stream()
.filter(entry -> entry.getValue() > 10)
.forEach(entry -> System.out.println(entry.getKey()));
Java 8 在 Map 接口中增加了多个实用默认方法，极大地简化了代码：
// 如果 key 不存在，则通过函数计算 value 并放入 Map
map.computeIfAbsent("key", k -> new ArrayList<>()).add("value");
// 经典用法：实现多值 Map
Map<String,List<String>> multiMap = new HashMap<>();
multiMap.computeIfAbsent("group1", k -> new ArrayList<>()).add("item1");
// 如果 key 存在，则根据原值计算新值
map.computeIfPresent("key", (k, v) -> v * 2);
// 合并操作：如果 key 不存在则放入给定值，存在则通过合并函数计算新值
map.merge("key", 1, Integer::sum); // 统计功能
// 经典用法：单词计数
String text = "apple banana apple orange apple";
Map<String,Integer> wordCount = new HashMap<>();
for(String word : text.split(" ")) {
wordCount.merge(word, 1, Integer::sum);
}
// 结果：{apple=3, banana=1, orange=1}
// 仅在 key 不存在时放入
map.putIfAbsent("key", "value");
// 替换指定 key 的值（仅当存在时）
map.replace("key", "newValue");
// 对所有 entry 应用替换函数
map.replaceAll((k, v) -> v.toUpperCase());
Java 9 提供了更简洁的 Map 初始化方式：
// 创建不可变 Map（最多支持 10 对键值）
Map<String,Integer> map1 = Map.of("a", 1, "b", 2, "c", 3);
// 任意数量键值对
Map<String,Integer> map2 = Map.ofEntries(
Map.entry("a", 1),
Map.entry("b", 2),
Map.entry("c", 3),
Map.entry("d", 4)
);
| 特性 | HashMap | LinkedHashMap | TreeMap | Hashtable | ConcurrentHashMap |
|---|---|---|---|---|---|
| 顺序 | 无序 | 插入/访问顺序 | 键排序 | 无序 | 无序 |
| null 键 | 允许 1 个 | 允许 1 个 | 不允许 | 不允许 | 不允许 |
| null 值 | 允许 | 允许 | 允许 | 不允许 | 不允许 |
| 线程安全 | 否 | 否 | 否 | 是（全表锁） | 是（分段/CAS） |
| 性能 | 最高 | 略低于 HashMap | 较低（log n） | 读慢写快 | 高并发下最优 |
| 底层结构 | 数组 + 链表 + 红黑树 | 数组 + 链表 + 红黑树 + 双向链表 | 红黑树 | 数组 + 链表 | CAS+ 数组 + 链表 + 红黑树 |
| 适用场景 | 通用缓存 | 需保持顺序 | 需排序/范围查询 | 遗留系统 | 高并发共享数据 |
| 操作 | HashMap | LinkedHashMap | TreeMap | Hashtable | ConcurrentHashMap |
|---|---|---|---|---|---|
| get | O(1) | O(1) | O(log n) | O(1) | O(1) |
| put | O(1) | O(1) | O(log n) | O(1) | O(1) |
| remove | O(1) | O(1) | O(log n) | O(1) | O(1) |
| containsKey | O(1) | O(1) | O(log n) | O(1) | O(1) |
| containsValue | O(n) | O(n) | O(n) | O(n) | O(n) |
根据不同的业务场景，选择合适的 Map 实现：
场景 1：通用缓存，无特殊顺序要求
场景 2：需要保持插入顺序
场景 3：需要按键排序或范围查询
场景 4：实现 LRU 缓存
场景 5：高并发共享数据
场景 6：处理配置文件
根据实际测试（百万级数据）：
| 操作 | HashMap | LinkedHashMap | TreeMap | Hashtable |
|---|---|---|---|---|
| 插入 100 万条 | 1420ms | 1512ms | 3845ms | 797ms |
| 读取 1000 万条 | 188ms | 201ms | 892ms | 265ms |
注：Hashtable 插入快可能是由于其初始容量较小，扩容频率高导致的测试偏差，实际应用中 HashMap 综合性能最优。
// 错误示例
Map<List<String>,String> map = new HashMap<>();
List<String> key = new ArrayList<>();
key.add("a");
map.put(key, "value1");
key.add("b"); // 键被修改，hashCode 改变
map.get(key); // 返回 null，再也找不到
map.containsKey(key); // false
解决方案：使用不可变对象作为键，如 String、Integer，或自定义不可变类。
class User {
String name; // 没有重写 hashCode 和 equals
}
Map<User,Integer> map = new HashMap<>();
User u1 = new User("Alice");
User u2 = new User("Alice");
map.put(u1, 100);
map.get(u2); // 返回 null，虽然内容相同
解决方案：作为键的类必须正确重写 hashCode() 和 equals()。
Map<String,Integer> map = new HashMap<>();
// ... 填充数据
for(String key : map.keySet()) {
if(key.startsWith("temp")) {
map.remove(key); // 抛出 ConcurrentModificationException
}
}
解决方案：
// 方式 1：使用 Iterator 的 remove
Iterator<String> it = map.keySet().iterator();
while(it.hasNext()) {
String key = it.next();
if(key.startsWith("temp")) {
it.remove();
}
}
// 方式 2：使用 removeIf（Java 8+）
map.keySet().removeIf(key -> key.startsWith("temp"));
// 方式 3：使用 ConcurrentHashMap（允许并发修改）
优先使用 Java 8+ 默认方法：让代码更简洁
// 老式
if(!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(value);
// 新式
map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
预估初始容量：如果能预知数据规模，指定初始容量避免频繁扩容
Map<String,Integer> map = new HashMap<>(expectedSize * 4 / 3 + 1);
Java Map 体系经过多年的演进，从最早的 Hashtable，到 JDK 1.2 引入的 HashMap，再到 JDK 1.5 的 ConcurrentHashMap，以及后续的各种优化，已经形成了一套功能完备、性能卓越的数据结构家族。
理解 Map 的核心原理，不仅有助于写出更高效的代码，还能在遇到复杂业务场景时做出正确的技术选型。本文从源码层面剖析了各个 Map 实现类的底层机制，并结合实际场景给出了使用建议。在实际开发中，建议遵循'面向接口编程'的原则，根据具体需求选择最合适的 Map 实现，同时注意线程安全和键的不可变性等关键问题。
Map 的学习是一个循序渐进的过程，掌握基础用法后，深入理解其设计思想和源码实现，才能真正做到'知其然，知其所以然'。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online