Java TreeMap 与 HashMap 深度对比分析

1. 引言

TreeMap 和 HashMap 是 Java 集合框架中两种重要的 Map 实现。它们都用于存储键值对（key-value pairs），但在底层实现、性能特性和使用场景上存在显著差异。本文将深入剖析两者的核心区别，帮助开发者根据实际需求做出合理选择。

2. 差异

2.1. 实现原理

HashMap 基于哈希表实现，继承自 AbstractMap 并实现 Map 接口。其核心工作原理是哈希（hashing）：

内部采用桶数组（bucket array）存储数据
当桶内元素过多时（超过阈值 TREEIFY_THRESHOLD=8），链表结构会转换为红黑树结构（类似 TreeMap 的节点）
这种设计在 Java 8 后显著优化了哈希冲突场景下的性能

TreeMap 基于红黑树实现，继承自 AbstractMap 并实现 NavigableMap 接口：

使用自平衡二叉搜索树（Self-Balancing Binary Search Tree）存储元素
所有操作（增删改查）都需维护树的平衡性

2.2. 排序特性

HashMap 不保证任何顺序：

@Test
public void whenInsertObjectsHashMap_thenRandomOrder() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(3, "TreeMap");
    hashmap.put(2, "vs");
    hashmap.put(1, "HashMap");
    
    assertThat(hashmap.keySet(), containsInAnyOrder(1, 2, 3));
}

TreeMap 按自然顺序排序：

@Test
public void whenInsertObjectsTreeMap_thenNaturalOrder() {
    Map<Integer, String> treemap = new TreeMap<>();
    treemap.put(3, "TreeMap");
    treemap.put(2, "vs");
    treemap.put(1, "HashMap");
    
    assertThat(treemap.keySet(), contains(1, 2, 3));
}

可通过 Comparator 或 Comparable 自定义排序规则
✅ 适合需要范围查询或有序遍历的场景

2.3. 空值处理

HashMap：

允许一个 null 键和多个 null 值

@Test
public void whenInsertNullInHashMap_thenInsertsNull() {
  Map<Integer, String> hashmap = new HashMap<>();
  hashmap.put(null, null);
  
  assertNull(hashmap.get(null));
}

TreeMap：

❌ 不允许 null 键（会抛 NullPointerException）

允许多个 null 值

@Test(expected = NullPointerException.class)
public void whenInsertNullInTreeMap_thenException() {
  Map<Integer, String> treemap = new TreeMap<>();
  treemap.put(null, "NullPointerException");
}

⚠️ 使用自定义 Comparator 时，null 处理取决于 compare() 方法的实现

3. 性能分析

3.1. HashMap

核心性能特征：

平均时间复杂度：O(1)（增删改查）
最坏情况：O(n)（哈希冲突严重时）→ Java 8 后优化为 O(log n)
内存占用较高（需预留桶空间）

关键优化点：

if(binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash); // 链表转红黑树
}

当桶内节点数 ≥ 8 时，链表转为红黑树
当节点数 ≤ 6 时，红黑树退化为链表

调优参数：

initialCapacity：初始容量（默认16）
loadFactor：负载因子（默认0.75）
建议容量设置：预期元素数 / 0.75 + 1

适用场景： ✅ 元素数量大致确定
✅ 无需有序遍历
✅ 追求极致性能

3.2. TreeMap

核心性能特征：

时间复杂度：O(log n)（所有操作）
内存占用更紧凑（仅需存储实际元素）
维护树平衡需额外开销

适用场景： ✅ 需要有序遍历或范围查询
✅ 内存敏感环境
✅ 元素数量动态变化大
✅ 可接受 O(log n) 的查询开销

4. 相似之处

4.1. 唯一键约束

两者均不允许重复键，重复插入会覆盖旧值：

@Test
public void givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique() {
    Map<Integer, String> hashMap = new HashMap<>();
    hashMap.put(1, "Baeldung");
    hashMap.put(1, "Baeldung"); // 覆盖旧值
    assertTrue(hashMap.size() == 1);

    Map<Integer, String> treeMap = new TreeMap<>();
    treeMap.put(1, "Baeldung");
    treeMap.put(1, "Baeldung"); // 覆盖旧值
    assertTrue(treeMap.size() == 1);
}

4.2. 并发访问

均非线程安全：

多线程并发修改时需外部同步

推荐使用 Collections.synchronizedMap() 包装：

Map<Integer, String> syncMap = Collections.synchronizedMap(new HashMap<>());

4.3. 快速失败迭代器

迭代器均支持快速失败（fail-fast）机制：

@Test
public void whenModifyMapDuringIteration_thenThrowExecption() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(1, "One");
    hashmap.put(2, "Two");
    
    Executable executable = () -> hashmap
      .forEach((key,value) -> hashmap.remove(1)); // 迭代中修改
 
    assertThrows(ConcurrentModificationException.class, executable);
}

迭代期间结构性修改会抛 ConcurrentModificationException
仅允许使用迭代器的 remove() 方法安全删除元素

5. 如何选择？

根据实际需求决策：

需求场景	推荐实现	原因
需要有序遍历/范围查询	TreeMap	天然排序支持
追求极致性能	HashMap	O(1) 平均时间复杂度
内存敏感环境	TreeMap	内存占用更紧凑
元素数量动态变化大	TreeMap	无需扩容开销
需要插入顺序遍历	LinkedHashMap	继承 HashMap 特性

特殊场景建议：

当需要排序且性能敏感时：优先考虑 TreeMap
当数据量极大且哈希冲突严重时：HashMap 的红黑树优化仍优于 TreeMap
当需要并发安全时：考虑 ConcurrentHashMap（基于 HashMap 优化）

6. 总结

TreeMap 和 HashMap 的核心差异可概括为：

维度	HashMap	TreeMap
数据结构	哈希表（数组+链表/红黑树）	红黑树
时间复杂度	O(1) 平均 / O(log n) 最坏	O(log n)
内存占用	高（预留桶空间）	低（紧凑存储）
排序支持	❌ 无序	✅ 自然排序/自定义排序
空值支持	✅ 1个null键/多个null值	❌ 禁止null键/允许多个null值

选择口诀：

要排序用 TreeMap，
讲性能选 HashMap，
保顺序用 LinkedHashMap，
并发场景 ConcurrentHashMap。

本文所有示例代码可在 GitHub 获取。

Persistence

REST

Security