Java Map 核心实现与常用方法详解

HashMap 的底层实现经历了从 JDK 7 到 JDK 8 的重要优化：

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 的核心优化：

1. 高效取模：计算数组下标时，(n - 1) & hash 等价于 hash % n，位运算速度远快于取模
2. 均匀分布：2^n-1 的二进制全是 1，与运算结果能充分利用 hash 值的所有位，减少碰撞
3. 扩容优化：扩容后元素的新位置要么在原位置，要么在原位置 + 旧容量，只需看 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;
        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;
}

执行流程总结：

1. 计算 key 的 hash 值（扰动函数：高 16 位与低 16 位异或）
2. 通过 (n - 1) & hash 计算数组下标
3. 如果该位置为空，直接插入
4. 如果该位置不为空，遍历链表或红黑树
5. 找到相同 key 则替换 value，否则插入新节点
6. 检查是否需要树化或扩容

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 是线程不安全的，多线程环境下可能出现以下问题：

1. 数据覆盖：两个线程同时 put，计算出的下标相同，一个线程插入的数据可能被另一个覆盖
2. size 不准确：++size 操作非原子性，多个线程同时 put 可能导致 size 偏小
3. 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 支持两种迭代顺序：

1. 插入顺序（默认）：按元素首次插入 Map 的顺序迭代
2. 访问顺序：按元素最近被访问（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<=键<6

4.3 源码分析：compare 方法

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。

4.4 注意事项

1. 键不能为 null：因为无法比较 null
2. 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 更高的并发性能。

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 进行了重大重构：

1. 放弃分段锁，改用 CAS + synchronized 实现
2. 与 HashMap 结构对齐：数组 + 链表 + 红黑树
3. 锁粒度更细：只锁住链表或红黑树的头节点
4. 读操作完全无锁（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, newNode<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((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 基础操作方法

7.2 查询方法

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);
}

7.3.4 Iterator 遍历（支持 remove）

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(); // 安全删除
    }
}

7.3.5 Java 8 forEach（最简洁）

map.forEach((key, value) -> System.out.println(key + ": " + value));

7.3.6 Stream API 遍历（支持链式操作）

map.entrySet().stream()
    .filter(entry -> entry.getValue() > 10)
    .forEach(entry -> System.out.println(entry.getKey()));

7.4 Java 8+ 新增的默认方法

Java 8 在 Map 接口中增加了多个实用默认方法，极大地简化了代码：

7.4.1 computeIfAbsent / computeIfPresent

// 如果 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);

7.4.2 merge 方法

// 合并操作：如果 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}

7.4.3 putIfAbsent

// 仅在 key 不存在时放入
map.putIfAbsent("key", "value");

7.4.4 replace / replaceAll

// 替换指定 key 的值（仅当存在时）
map.replace("key", "newValue");
// 对所有 entry 应用替换函数
map.replaceAll((k, v) -> v.toUpperCase());

7.5 Java 9 的 Map.of 工厂方法

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));

第八章 实现类对比与选型指南

8.1 核心特性对比

8.2 时间复杂度对比

8.3 选型建议

根据不同的业务场景，选择合适的 Map 实现：

场景 1：通用缓存，无特殊顺序要求

• ✅ 首选：HashMap（性能最高）
• 如果线程安全要求：ConcurrentHashMap

场景 2：需要保持插入顺序

• ✅ 首选：LinkedHashMap
• 案例：实现 FIFO 队列、记录操作日志

场景 3：需要按键排序或范围查询

• ✅ 首选：TreeMap
• 案例：排行榜、日程表、字典序输出

场景 4：实现 LRU 缓存

• ✅ 首选：LinkedHashMap（访问顺序模式）
• 案例：内存缓存、最近访问记录

场景 5：高并发共享数据

• ✅ 首选：ConcurrentHashMap
• 案例：全局配置、在线用户统计

场景 6：处理配置文件

• ✅ 首选：Properties
• 案例：读取 application.properties

8.4 性能测试数据参考

根据实际测试（百万级数据）：

注：Hashtable 插入快可能是由于其初始容量较小，扩容频率高导致的测试偏差，实际应用中 HashMap 综合性能最优。

第九章 常见陷阱与最佳实践

9.1 陷阱一：可变对象作为键

// 错误示例
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，或自定义不可变类。

9.2 陷阱二：自定义类未重写 hashCode 和 equals

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()。

9.3 陷阱三：并发修改导致 ConcurrentModificationException

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（允许并发修改）

9.4 最佳实践总结

1. 使用泛型：指定键值类型，避免运行时类型转换异常
2. 选择合适的实现：根据业务需求而非习惯选择
3. 注意线程安全：多线程环境优先使用 ConcurrentHashMap
4. 避免使用 Hashtable：除非维护遗留代码

优先使用 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 的学习是一个循序渐进的过程，掌握基础用法后，深入理解其设计思想和源码实现，才能真正做到'知其然，知其所以然'。