注册
登录控制台
文章目录
- 前言
- 第一章 Map接口概述
- 第二章 HashMap：最常用的Map实现
- 第三章 LinkedHashMap：保持插入顺序
- 第四章 TreeMap：基于红黑树的排序Map
- 第五章 Hashtable与Properties
- 第六章 ConcurrentHashMap：并发编程的利器
- 第七章 Map常用方法详解
- 第八章 实现类对比与选型指南
- 第九章 常见陷阱与最佳实践
- 结语
前言
在Java集合框架中，Map是最核心、最常用的数据结构之一。与Collection体系下的List、Set不同，Map采用**键值对（Key-Value）**的存储方式，每个键映射到一个值，键在同一个Map中不可重复。这种设计使得Map特别适合需要通过键快速查找值的场景，如缓存系统、配置管理、数据索引等。
本文将从Map接口的设计哲学出发，深入剖析HashMap、LinkedHashMap、TreeMap、Hashtable、ConcurrentHashMap等主要实现类的底层原理、源码实现、性能特性，并结合Java 8+的新特性，帮助读者全面掌握Map的使用技巧和选型策略。
第一章 Map接口概述
1.1 Map的继承体系
Java中的Map体系是一个独立于Collection的并行框架，其核心继承结构如下：
Map (interface) ├── HashMap (class) │ └── LinkedHashMap (class) ├── TreeMap (class) ├── Hashtable (class) │ └── Properties (class) └── ConcurrentMap (interface) └── ConcurrentHashMap (class)1.2 Map的核心特性
- 键唯一性：每个键最多映射到一个值，键的不可重复性通过
equals()和hashCode()保证 - 值可重复：不同的键可以对应相同的值
- 元素无序：大部分Map实现（如HashMap）不保证元素的顺序
- 允许null：HashMap允许一个null键和多个null值，但Hashtable和ConcurrentHashMap不允许
1.3 存储结构的理解
从数据结构角度看，Map的存储可以分为三个层面：
- key视角：所有key构成一个
Set集合 → 无序、不可重复，key所在的类必须重写equals()和hashCode() - value视角：所有value构成一个
Collection集合 → 无序、可重复，value所在的类需要重写equals() - entry视角：每个key-value对构成一个
Entry对象，所有entry构成一个Set集合 → 无序、不可重复
这种设计体现了Map与Set、List的内在联系，也为后续的遍历操作奠定了基础。
第二章 HashMap：最常用的Map实现
HashMap是基于哈希表实现的Map，它根据键的hashCode值存储数据，具有O(1)的平均查找时间，是日常开发中使用频率最高的Map实现。
2.1 底层数据结构演进
HashMap的底层实现经历了从JDK 7到JDK 8的重要优化：
版本 底层结构 节点类型 特点 JDK 7 数组 + 链表 Entry 头插法，扩容时可能产生循环链表 JDK 8+ 数组 + 链表 + 红黑树 Node/TreeNode 尾插法，链表长度>8且数组长度>64时树化 2.2 核心源码深度解析
2.2.1 重要成员变量
// 默认初始容量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;2.2.2 设计哲学解读
为什么默认负载因子是0.75？
负载因子表示散列表的空间使用程度。0.75是时间与空间的折中选择：
- 过高（如1）：空间利用率高，但Hash碰撞概率增加，链表变长，查询效率下降
- 过低（如0.5）：Hash碰撞减少，查询快，但空间浪费严重
为什么容量必须是2的n次幂？
这涉及HashMap的核心优化：
- 高效取模：计算数组下标时，
(n - 1) & hash等价于hash % n，位运算速度远快于取模 - 均匀分布：2^n-1的二进制全是1，与运算结果能充分利用hash值的所有位，减少碰撞
- 扩容优化：扩容后元素的新位置要么在原位置，要么在原位置+旧容量，只需看hash值新增位是0还是1
为什么链表转红黑树的阈值是8？
这是基于泊松分布的概率统计。在理想随机hashCode下，链表节点数出现的概率遵循泊松分布，节点数为8的概率接近千万分之六，此时链表查询性能已经很差，转为红黑树可以挽回性能。而树节点占用的空间是普通节点的两倍，当节点数降到6时再转回链表，避免频繁转换。
2.3 put方法执行流程
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; // 第一个节点就是要找的key 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; }执行流程总结：
- 计算key的hash值（扰动函数：高16位与低16位异或）
- 通过
(n - 1) & hash计算数组下标 - 如果该位置为空，直接插入
- 如果该位置不为空，遍历链表或红黑树
- 找到相同key则替换value，否则插入新节点
- 检查是否需要树化或扩容
2.4 扩容机制（resize）
当元素个数超过
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; }扩容优化点：
- JDK 8采用尾插法，避免JDK 7头插法在多线程环境下产生的循环链表问题
- 元素迁移时，无需重新计算hash，只需看
e.hash & oldCap是否为0，为0则留在原位，否则移到原位置+oldCap - 链表保持原顺序，不会倒置
2.5 线程安全问题
HashMap是线程不安全的，多线程环境下可能出现以下问题：
- 数据覆盖：两个线程同时put，计算出的下标相同，一个线程插入的数据可能被另一个覆盖
- size不准确：
++size操作非原子性，多个线程同时put可能导致size偏小 - JDK 7扩容死循环：头插法在并发扩容时可能形成环形链表，导致CPU 100%
解决方案：
- 使用
Collections.synchronizedMap(new HashMap<>()) - 使用
ConcurrentHashMap（推荐）
第三章 LinkedHashMap：保持插入顺序
LinkedHashMap继承自HashMap，在HashMap基础上通过双向链表维护元素的顺序。
3.1 数据结构特点
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指针，构成了一个双向链表，用于记录元素的插入顺序或访问顺序。3.2 两种排序模式
LinkedHashMap支持两种迭代顺序：
- 插入顺序（默认）：按元素首次插入Map的顺序迭代
- 访问顺序：按元素最近被访问（get/put）的时间从旧到新迭代
// 指定访问顺序 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（最近访问的在最后）3.3 实现LRU缓存
利用访问顺序模式，可以轻松实现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; // 超过容量时移除最久未访问的元素 } }3.4 性能特点
- 遍历速度：只与元素个数有关，与HashMap容量无关，因此当HashMap容量大而实际元素少时，LinkedHashMap遍历更快
- 插入性能：略低于HashMap，因为需要维护双向链表
- 内存占用：比HashMap多两个指针的开销
第四章 TreeMap：基于红黑树的排序Map
TreeMap实现了
SortedMap和NavigableMap接口，底层基于红黑树实现，能够对键进行排序。4.1 排序机制
TreeMap要求键要么实现
Comparable接口（自然排序），要么在构造时提供Comparator（定制排序）：// 自然排序：键必须实现Comparable TreeMap<Integer, String> naturalMap = new TreeMap<>(); // 定制排序：提供Comparator TreeMap<String, Integer> customMap = new TreeMap<>( (s1, s2) -> s2.compareTo(s1) // 降序 );4.2 核心方法
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<=键<64.3 源码分析：compare方法
TreeMap的核心是比较逻辑，它在
put、get、remove等操作中都会用到：final int compare(Object k1, Object k2) { return comparator == null ? ((Comparable<? super K>)k1).compareTo((K)k2) : comparator.compare((K)k1, (K)k2); }如果既没有提供Comparator，键也没有实现Comparable，在插入时会抛出
ClassCastException。4.4 注意事项
- 键不能为null：因为无法比较null
- compareTo与equals需一致：当两个键比较结果为0时，TreeMap认为它们相等，即使
equals返回false - 字符串键的特殊性：字符串的
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与Properties
5.1 Hashtable：古老的线程安全Map
Hashtable是JDK 1.0就存在的古老实现类，具有以下特点：
- 线程安全：所有方法都用
synchronized修饰 - 不允许null键和null值：否则抛出NullPointerException
- 初始容量11，扩容为
2*old+1 - 性能较低：全表锁导致并发性能差
Hashtable<String, Integer> table = new Hashtable<>(); table.put("key", 1); // table.put(null, 2); // 运行时异常性能对比：
- 写入速度：Hashtable可能比HashMap快（测试数据：1420ms vs 797ms）
- 读取速度：HashMap比Hashtable快（188ms vs 265ms）
5.2 Properties：处理配置文件
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：并发编程的利器
ConcurrentHashMap是Java并发包（java.util.concurrent）中提供的线程安全且高性能的Map实现。
6.1 设计哲学
ConcurrentHashMap的设计目标是：在保证线程安全的同时，提供比Hashtable更高的并发性能。
实现类 锁策略 并发度 性能 Hashtable 全表锁 极低 差 Collections.synchronizedMap 全表锁 极低 差 ConcurrentHashMap JDK 7 分段锁 16 高 ConcurrentHashMap JDK 8+ CAS + synchronized + 细粒度锁 极高 非常高 6.2 JDK 7实现：分段锁
JDK 7的ConcurrentHashMap采用Segment分段锁机制：
- 将整个Map分成多个Segment（默认16个）
- 每个Segment独立加锁，相当于一个小型的HashMap
- 不同Segment的写操作可以并发执行
- 读操作几乎不加锁（volatile保证可见性）
static final class Segment<K,V> extends ReentrantLock implements Serializable { transient volatile HashEntry<K,V>[] table; // ... }6.3 JDK 8+实现：CAS + synchronized
JDK 8对ConcurrentHashMap进行了重大重构：
- 放弃分段锁，改用CAS + synchronized实现
- 与HashMap结构对齐：数组+链表+红黑树
- 锁粒度更细：只锁住链表或红黑树的头节点
- 读操作完全无锁（volatile保证可见性）
// 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, new Node<K,V>(hash, key, value, null))) break; } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); // 帮助扩容 else { V oldVal = null; synchronized (f) { // 锁住链表头节点 // 链表或红黑树操作 } } } }6.4 弱一致性迭代器
ConcurrentHashMap的迭代器是弱一致性的：
- 迭代器创建后，如果Map发生修改，不会抛出
ConcurrentModificationException - 迭代器反映的是创建时刻或之后某个时刻的数据快照
- 迭代过程中修改Map，迭代器可能看到，也可能看不到修改结果
- 适用于高并发场景，避免了快速失败机制带来的问题
6.5 批量操作
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参数控制并行度：小于阈值时串行执行，大于阈值时并行执行。第七章 Map常用方法详解
7.1 基础操作方法
方法 描述 返回值说明 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 7.2 查询方法
方法 描述 containsKey(Object key)判断是否包含指定键 containsValue(Object value)判断是否包含指定值（HashMap中效率较低，需遍历） getOrDefault(Object key, V defaultValue)获取值，不存在则返回默认值 7.3 遍历方法
Map的遍历方式多样，可根据场景选择：
7.3.1 entrySet遍历（最常用）
for (Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); }7.3.2 keySet + get遍历
for (String key : map.keySet()) { System.out.println(key + ": " + map.get(key)); } // 缺点：每次get都需要二次查找，效率较低7.3.3 values遍历（仅需值时）
for (Integer value : map.values()) { System.out.println(value);这条帮助是否解决了您的问题？ 已解决 未解决 - 线程安全：所有方法都用
