个人网站

面试官问"HashMap 和 TreeMap 的区别"，很多人只能说"HashMap 无序，TreeMap 有序"。但这远远不够——TreeMap 的有序性是怎么实现的？什么场景下 TreeMap 比 HashMap 更好？红黑树到底是什么？这些你都得答上来。

今天咱们把 HashMap 和 TreeMap 的区别彻底对比清楚。

一、先说结论：核心区别一览

维度	HashMap	TreeMap
底层结构	数组+链表+红黑树	红黑树
是否有序	❌ 无序	✅ 按 key 自然排序或自定义排序
null key	✅ 允许 1 个	❌ 不允许（自然排序时）
null value	✅ 允许多个	✅ 允许
查找/插入/删除	O(1) 均摊	O(log n)
实现接口	Map	Map + NavigableMap + SortedMap
线程安全	❌	❌
适用场景	查找为主	需要排序/范围查找

一句话记住：HashMap 是"快递柜"——按编号存取最快；TreeMap 是"图书馆"——按书名排列，方便找范围。

二、底层结构的本质区别

HashMap：散列表

桶[0] → null
桶[1] → Entry → Entry → Entry（链表/红黑树）
桶[2] → Entry
桶[3] → null
...

存储位置由 hash 决定，无序

TreeMap：红黑树

                    5(黑)
                  /      \
               3(红)     8(红)
              /   \     /   \
           1(黑) 4(黑) 6(黑) 9(黑)

按 key 大小排列，中序遍历即有序

红黑树的性质：

1. 节点是红色或黑色
2. 根节点是黑色
3. 红色节点的子节点必须是黑色
4. 从任一节点到其所有叶子节点的路径包含相同数目的黑色节点
5. 这些性质保证了树的高度 ≤ 2log(n+1)，即查找 O(log n)

生活类比： 红黑树像自助餐厅的调料架——辣的在左、甜的在右、中间是咸的，找"辣和甜之间的调料"一划就知道。

三、TreeMap 的排序：自然排序 vs 自定义排序

自然排序（key 实现 Comparable）

TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);

// 遍历结果按 key 字母序排列
// apple=1, banana=2, cherry=3 👈

key 的 Comparable 决定排序规则。 这就是为什么 TreeMap 不允许 null key——null 无法调用 compareTo()。

自定义排序（传入 Comparator）

TreeMap<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);

// 遍历结果按 key 逆序排列
// cherry=3, banana=2, apple=1 👈

传入 Comparator 后，null key 的处理取决于 Comparator 的实现。

四、TreeMap 的独门绝技：范围查找

这是 HashMap 做不到的：

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "一");
map.put(3, "三");
map.put(5, "五");
map.put(7, "七");
map.put(9, "九");

// 范围查找
map.subMap(3, 7);        // {3=三, 5=五}  👈 [3, 7)
map.headMap(5);          // {1=一, 3=三}  👈 < 5
map.tailMap(5);          // {5=五, 7=七, 9=九}  👈 ≥ 5

// 导航方法
map.firstKey();          // 1
map.lastKey();           // 9
map.lowerKey(5);         // 3（严格小于 5 的最大 key）
map.higherKey(5);        // 7（严格大于 5 的最小 key）
map.floorKey(5);         // 5（≤ 5 的最大 key）
map.ceilingKey(5);       // 5（≥ 5 的最小 key）👈

生活类比： TreeMap 像字典——查"ab"到"ac"之间的单词，翻开就能找到范围；HashMap 像散落的卡片，你得一张一张翻。

五、性能对比：什么时候选谁？

场景	推荐	原因
纯查找	HashMap	O(1) vs O(log n)
需要排序遍历	TreeMap	天然有序
范围查询	TreeMap	subMap/headMap/tailMap
key 需要排名	TreeMap	NavigableMap 方法
数据量大且随机访问	HashMap	散列表更快
需要顺序一致性	TreeMap	插入顺序稳定

性能差距示例：

// 100 万次查找
HashMap:   ~5 ms    // O(1)
TreeMap:   ~50 ms   // O(log n)

// 但范围查找 [100, 200]
HashMap:   ~500 ms  // 遍历全部
TreeMap:   ~1 ms    // subMap 直接定位 👈

选错了性能差距可达 10 倍甚至 100 倍！

HashMap vs TreeMap 全景

HashMap vs TreeMap 全景

底层结构
├── HashMap ── 散列表（数组+链表+红黑树）
└── TreeMap ── 红黑树

时间复杂度
├── HashMap ── 查找/插入/删除 O(1)
├── TreeMap ── 查找/插入/删除 O(log n)
└── TreeMap 范围查找 ── O(log n + k)

排序
├── HashMap ── 无序
├── TreeMap ── 自然排序或 Comparator
└── TreeMap 实现了 NavigableMap + SortedMap

TreeMap 独有能力
├── 范围查找 ── subMap/headMap/tailMap
├── 导航方法 ── lower/higher/floor/ceiling
├── 最值 ── firstKey/lastKey
└── 逆序视图 ── descendingMap()

选型建议
├── 默认选 HashMap ── 更快、更通用
├── 需要排序 → TreeMap
├── 需要范围查找 → TreeMap
└── 需要插入顺序 → LinkedHashMap

口诀：HashMap 快如闪电无顺序，TreeMap 有序性能换，
      范围查找是绝活，默认选快特殊选序，
      红黑树保 logn，选错集合差十倍。

回答技巧与点评

标准回答

HashMap 基于散列表，查找插入 O(1)，但无序；TreeMap 基于红黑树，查找插入 O(log n)，但按 key 有序。TreeMap 实现了 NavigableMap 接口，支持范围查找（subMap/headMap/tailMap）和导航方法（lower/higher/floor/ceiling），这是 HashMap 做不到的。默认场景选 HashMap（更快），需要排序或范围查找选 TreeMap。TreeMap 不允许 null key（自然排序时），HashMap 允许一个 null key。

加分回答

1. LinkedHashMap 的定位：如果只需要"按插入顺序遍历"，不需要排序，用 LinkedHashMap——它比 TreeMap 快（O(1) 查找），同时保持插入顺序或访问顺序。LinkedHashMap = HashMap + 双向链表，是 HashMap 和 TreeMap 之间的折中选择
2. 红黑树 vs AVL 树：TreeMap 选择红黑树而非 AVL 树，是因为红黑树在插入/删除时旋转次数更少（最多 3 次 vs AVL 可能 O(log n) 次），更适合频繁修改的场景。AVL 树更平衡，查找略快，但修改代价更大。数据库索引通常用 B+ 树而非红黑树，因为 B+ 树更适合磁盘 I/O
3. ConcurrentSkipListMap：TreeMap 的线程安全替代品是 ConcurrentSkipListMap，基于跳表实现。跳表的查找也是 O(log n)，但插入删除用 CAS 不加锁，并发性能优于加锁的 TreeMap

面试官点评

这道题考的是你对集合选型的理解。能说出"HashMap 无序 O(1)、TreeMap 有序 O(log n)"是基本要求，能讲清楚 TreeMap 的范围查找能力、红黑树的基本性质、什么场景该选谁，才算及格。如果你能提到 LinkedHashMap 的定位、红黑树 vs AVL 的取舍、ConcurrentSkipListMap 的存在，面试官会认为你对集合框架有全面的认识。

原文阅读

---

内容有帮助？点赞、收藏、关注三连！评论区等你 💪