企业官网建设流程全解析

HashMap和TreeMap应该是Java集合框架里被问得最频繁的两个类，尤其是HashMap，几乎是面试必考。但说实话，很多人对这两个类的理解停留在"HashMap是无序的，TreeMap是有序的"这种层面，真要问到底层怎么实现的、为什么JDK 8之后性能提升了、什么时候该用TreeMap，就答不上来了。

这篇文章我从源码层面把这两个类彻底拆开来讲，JDK版本以8u202为准。不管你是准备校招社招的Java开发者，还是工作中想真正搞懂集合原理、避免线上事故的同学，这篇都能给你一些参考。

1. 先把整体设计思路捋清楚

1.1 两个Map在Java集合框架里的定位

Map接口本身定义的是键值对映射的规范，但落地到具体实现，JDK提供了非常多的选择。HashMap、TreeMap、LinkedHashMap、Hashtable、ConcurrentHashMap，它们各自解决不同的问题。

从数据结构上看，HashMap底层是哈希表，核心是"通过hash值快速定位"，理论上能做到O(1)的查找；TreeMap底层是红黑树，核心是"让元素始终保持有序"，查找、插入、删除都是O(log n)。

这两者的差异从名字上也能看出来。HashMap的"Hash"强调的是散列定位的能力，而TreeMap的"Tree"强调的是树形结构带来的有序性。这是两个完全不同的设计哲学，一个追求极致的速度，一个牺牲一部分速度换取有序的能力。

1.2 看源码前必须建立的核心认知框架

很多人看HashMap源码看得一头雾水，原因不是看不懂代码，而是不知道看什么。我建议带着这几个问题去读源码，会清晰很多：

第一，数据是怎么存进去的？put方法执行时，从key到存储位置，到底经历了哪些步骤？第二，存满了怎么办？哈希冲突和容量扩容这两个核心问题是怎么解决的？第三，JDK 8相比JDK 7做了哪些优化，为什么性能提升明显？第四，TreeMap的有序性是怎么维护的？每次插入删除时，红黑树的平衡是如何调整的？

有了这个框架，你再去看源码，会发现每一段代码都在回答其中一个问题。源码不是天书，它只是把很朴素的思路用工程化的方式表达出来了。

2. HashMap源码拆解：数组、链表与红黑树的演进逻辑

2.1 底层数据结构：为什么是数组加链表

HashMap最底层的存储结构其实就是一个Node数组，每个数组元素又是一个链表的头节点。这个设计思路用生活化的例子来类比，就像图书馆的索引柜：你根据书名的hash值找到对应的抽屉，抽屉里挂了一串小卡片，每张卡片记录一本书的信息。如果两本书算出来的抽屉号一样，就在同一个抽屉里排队。

// JDK 8中的Node结构 static class Node<K,V> implements Map.Entry<K,V> { final int hash; // 保存hash值，避免重复计算 final K key; V value; Node<K,V> next; // 指向链表下一个节点 }

为什么要数组加链表，而不是单纯的数组？因为hash函数无法保证不同的key算出的索引完全不同，必然存在冲突。冲突了怎么办？最简单的办法就是链地址法，把冲突的元素挂在同一个桶位上，用链表串起来。

那为什么不直接用链表数组，而要引入红黑树？这就涉及链表的性能瓶颈了。当大量元素落在同一个桶位上时，链表会变得很长，查找退化成O(n)的线性扫描。JDK 8中，当链表长度超过阈值8，并且数组容量达到64时，链表会树化，查找复杂度从O(n)降到O(log n)。

2.2 put流程全解析：从hash计算到扩容触发

HashMap的put方法是整个类的核心。我把它拆成几个关键步骤来讲：

第一步，计算hash值。很多人以为put进去的就是key.hashCode()，其实JDK 8做了一次扰动处理：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

这里为什么要做异或和右移16位？因为数组的容量是有限的，定位桶位时只会用到hash值的低位（通过(n - 1) & hash计算索引），高位的信息就浪费了。把高16位异或到低16位，相当于把高位的信息混入低位，让低位的随机性更强，从而减少hash冲突。

第二步，定位桶位。使用(n - 1) & hash而不是hash % n，是因为当n是2的幂次方时，位运算与取模结果等价，但位运算效率更高。这也是为什么HashMap的容量始终是2的幂次方。

第三步，判断冲突类型。如果桶位为空，直接创建新节点放入；如果桶位不为空，说明发生了hash冲突，这时候要分三种情况处理：节点是红黑树节点，走红黑树的插入逻辑；链表头节点存在，遍历链表找有没有相同的key，有就覆盖，没有就追加到链表尾部。

第四步，检查是否需要树化。链表追加成功后，如果链表长度达到TREEIFY_THRESHOLD（8），调用treeifyBin方法尝试树化。但如果数组容量还小于MIN_TREEIFY_CAPACITY（64），会优先扩容而不是树化。

第五步，检查是否需要扩容。插入完成后，如果++size > threshold，触发resize。threshold的值是容量 * 负载因子，默认是16 * 0.75 = 12。

这里有一个很多人忽略的细节：HashMap的key是可以为null的，hash函数对null做了特殊处理，返回0。这意味null key会落在数组的0号桶位上。

2.3 get流程与hash冲突的解决细节

get方法的流程是put的逆过程，逻辑相对简单，但细节同样值得注意：

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 先检查第一个节点 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 遍历后续节点 if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

你会发现一个关键点：判断key是否相同，必须先比较hash值，再比较equals。两层判断缺一不可。hash值相同说明落在同一个桶位，但同一个桶位上的元素hash值可能不同（因为高位可能不同），所以还要用equals精确匹配。

这也是为什么我们自定义对象作为key时，必须同时重写hashCode和equals方法。只重写equals不重写hashCode，会导致两个equals相等的对象hashCode不同，在HashMap中被当成不同key存放；只重写hashCode不重写equals，会导致hash值相同但equals不同，产生误匹配的隐患。

2.4 扩容机制：resize到底做了什么

扩容是HashMap源码里最需要耐心看的部分，因为涉及链表的拆分和元素的重新定位。

触发时机是size > threshold，threshold = 容量 * 负载因子。默认容量16，负载因子0.75，意味着存到第12个元素时就会触发扩容，扩容后容量翻倍到32。

扩容的核心逻辑是：创建一个容量为原来两倍的新数组，然后把旧数组中的元素转移到新数组中。转移过程不是简单地复制，而是重新计算每个元素在新数组中的位置。

JDK 8对转移逻辑做了一次重要优化。因为容量是2的幂次方，元素在新数组中的位置只有两种可能：要么索引不变，要么索引变成"原索引 + 旧容量"。判断依据是元素的hash值在和旧容量做与运算时，结果是否为0。

// JDK 8扩容时链表拆分的核心逻辑 if ((e.hash & oldCap) == 0) { // hash值的第oldCap位为0，索引不变 loTail.next = e; } else { // hash值的第oldCap位为1，索引变为原索引+oldCap hiTail.next = e; }

这个优化的价值在于，JDK 7的扩容会重新对每个元素做一次hash和取模运算，而JDK 8只需要一次位运算就能确定元素的新位置，省了不少计算开销。同时，JDK 8避免了JDK 7在多线程扩容时可能出现的循环链表问题（当然，HashMap本身就不是线程安全的，并发场景还是得用ConcurrentHashMap）。

2.5 红黑树化的阈值与触发条件

链表树化的条件有两个，必须同时满足：链表长度达到8，数组容量达到64。为什么是这两个数字？

链表长度阈值定为8，是因为在hash函数设计合理的情况下，泊松分布计算出的概率表明，链表长度达到8的概率极低，大约只有千万分之六。这意味正常情况下不应该出现这么长的链表，一旦出现，说明要么hash函数有问题，要么数据分布极度不均匀，此时引入红黑树来兜底是合理的。

数组容量必须达到64，是因为如果容量还很小，扩容的成本远低于树化的成本。在容量为16或32时，链表长度达到8说明负载已经很高了，此时更应该做的是扩容，让元素分散到更多的桶位中，而不是维护一棵复杂的红黑树。

红黑树的结构相比链表复杂得多，每个节点有父指针、左右子节点、颜色标记。JDK 8中使用TreeNode来包装：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; boolean red; }

这里有个有趣的细节：TreeNode继承了LinkedHashMap.Entry，而LinkedHashMap.Entry又继承了HashMap.Node。这意味着TreeNode本身也是一个Node，可以复用链表的结构。红黑树还保留着链表的前后指针（prev），这是为了在扩容时方便做链表拆分，不需要重新遍历树。

当容量扩容后，原本树化的桶位如果元素变少，节点数下降到小于等于6，树又会退化回链表。树化和退化的阈值分别是8和6，中间留了1个缓冲区间，避免元素在边界来回震荡导致频繁的结构转换，这个设计思路在很多别的地方也值得借鉴。

3. TreeMap源码拆解：红黑树的工程实现

3.1 TreeMap与HashMap的核心差异

TreeMap和HashMap的差异不仅体现在数据结构上，更体现在设计目标和适用场景上。TreeMap底层是一棵完整的红黑树，所有元素按照key的自然顺序或者构造时传入的Comparator进行排序。

它不支持null作为key。原因很直接：红黑树需要比较key的大小来决定插入方向和调整策略，null无法参与比较。如果你尝试treeMap.put(null, "value")，会直接抛出NullPointerException。

TreeMap也没有扩容的概念，因为树的容量天然就是动态的，节点是散落分配在堆内存中的，通过指针链接起来。每次put新增一个节点，都会从根节点开始，通过比较确定插入位置，然后执行红黑树的平衡修复。

时间复杂度方面，TreeMap的put、get、remove都是O(log n)，相比HashMap的O(1)均值要慢一些。但TreeMap强在不仅支持单个键的增删查，还支持范围操作，比如获取子映射、查找大于某个key的最小节点等。

3.2 红黑树的五大性质与TreeMap的维护

红黑树的关键在于五个性质，TreeMap中的所有旋转和变色操作，都是围绕这五个性质展开的：

性质一，每个节点要么是红色，要么是黑色。性质二，根节点是黑色的。性质三，每个叶子节点（NIL节点）是黑色的，但工程实现中通常省略NIL节点，用null来表示。性质四，红色节点的两个子节点必须是黑色的，也就是说，红节点的父节点不能是红的，不能出现连续的红节点。性质五，从任一节点到其每个叶子的所有路径，包含相同数目的黑节点。

这五个性质共同保证了红黑树的平衡性，使得树的高度不会超过2 * log(n+1)，也就是最长路径不会超过最短路径的两倍。这个平衡不像AVL树那样严格，但已经能保证O(log n)的复杂度，而且红黑树在插入和删除时的旋转次数相对较少，工程上更适合需要频繁增删的场景。

新插入的节点默认是红色的，因为插入红节点不会违反黑节点相等这一性质，只可能违反"不能连续红节点"这一性质，修复起来相对容易。如果插入的是黑节点，会导致路径上的黑节点数不一致，修复成本高得多。

3.3 put操作中的旋转与变色

TreeMap的put方法逻辑清晰，分三步：查找插入位置、插入新节点、修复红黑树平衡。

查找插入位置时，从根节点开始，通过compare方法比较key，小于就走左子树，大于就走右子树，直到找到null的位置。这个过程中，还有一个细节：如果找到key相同的节点，直接替换value并返回旧value，不会创建新节点。

插入完成后会调用fixAfterInsertion方法进行修复。修复的逻辑是一系列if-else分支，处理不同的情况。核心操作有两种：左旋和右旋，配合变色来恢复性质。

我以最常见的场景来演示左旋的操作逻辑。当一个节点的左子节点是红色、而右子节点是红色时，需要把右侧的红色节点翻转到左侧。左旋的本质是把当前节点下沉为左子节点，让右子节点成为新的父节点。

// TreeMap中左旋的核心逻辑（简化版） private void rotateLeft(Entry<K,V> p) { if (p != null) { Entry<K,V> r = p.right; // r为p的右子节点 p.right = r.left; // r的左子树过继给p当右子树 if (r.left != null) r.left.parent = p; r.parent = p.parent; // r提升为原p的位置 if (p.parent == null) root = r; // p原来是根节点，r成为新根 else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; // p成为r的左子节点 p.parent = r; } }

右旋的逻辑完全对称，不再赘述。修复过程中变色的核心思路是：把红色节点从某一侧"翻转"到另一侧，通过颜色调整保持黑节点数的相对平衡，只有颜色调整无法解决时才使用旋转。

我建议你把红黑树的插入修复过程分成几种情况来记：插入节点的叔叔节点是红色，只需要变色；叔叔节点是黑色且插入的是RL型，需要先右旋再左旋；叔叔节点是黑色且插入的是RR型，直接左旋。把这几种case画成图来理解，比死记代码有效得多。

3.4 有序性带来的独特能力：范围查询

要说TreeMap相对HashMap最大的实用优势，就是范围查询能力。HashMap查找单个key很快，但它答不了"从某个key起往后取5个元素"这类问题。TreeMap则可以高效地做到。

TreeMap提供了几个关键方法：

TreeMap<Integer, String> map = new TreeMap<>(); map.put(5, "five"); map.put(1, "one"); map.put(9, "nine"); map.put(3, "three"); map.put(7, "seven"); // 获取子映射 [3, 7) SortedMap<Integer, String> subMap = map.subMap(3, 7); // 获取尾部映射 >= 5 SortedMap<Integer, String> tailMap = map.tailMap(5); // 获取头部映射 < 5 SortedMap<Integer, String> headMap = map.headMap(5); // 返回大于等于4的最小key Integer ceilingKey = map.ceilingKey(4); // 返回小于等于4的最大key Integer floorKey = map.floorKey(4); // 返回大于7的最小key Integer higherKey = map.higherKey(7); // 返回小于7的最大key Integer lowerKey = map.lowerKey(7);

这些方法的底层实现都是利用红黑树的有序特性，通过树上的搜索和遍历来完成。比如ceilingKey，就是在查找第一个大于等于给定key的节点，过程中利用key的比较结果决定向左还是向右搜索。

有一类业务场景非常适合TreeMap：需要维持数据有序，同时频繁查询临近值。比如统计每个成绩段有多少学生，或者实现一个基于时间戳的事件调度器，需要找到最近的下一个事件。这些场景用TreeMap比手动维护一个排序列表要高效得多。

4. 源码之外的思考：性能对比与选型指南

4.1 两个Map的时间复杂度全面对比

在实际选型或者回答面试题时，理解时间复杂度的差异是最基础的一步：

这里说的"平均"很关键。HashMap只有在hash函数合理、数据分布均匀的前提下才有O(1)的表现。如果代码写得差，大量key算出的hash值相同，全部堆积在一个桶位，那么HashMap会退化，尤其在JDK 7中链表不树化，性能会严重劣化。

TreeMap的O(log n)是稳定上界，不管数据分布如何，红黑树的平衡性保证了树高始终在一个可控的范围内。对于对延迟敏感但数据规模可预见的场景，TreeMap的表现是可预期的。

4.2 实际场景中的选型建议

场景一：缓存数据需要快速读写，不需要有序遍历。使用HashMap是最自然的选择。绝大多数业务缓存场景都用HashMap或者它的并发版本。

场景二：需要按key的范围批量查询。比如查某个时间段的日志，查库存编号在某区间的商品，用TreeMap一次就能搞定，用HashMap得遍历所有元素再过滤。

场景三：数据需要排序展示。如果数据量不大，且更新不频繁，可以直接用TreeMap，插入时就保持有序，展示时直接遍历即可。但要注意，TreeMap是按key排序的，如果你要按value排序，它做不到，那还是得另想办法。

场景四：频繁的插入和删除，同时需要不断获取最大或最小元素。TreeMap的firstKey、lastKey在O(log n)内就能拿到，比PriorityQueue更灵活，因为PriorityQueue虽然能O(1)拿到堆顶，但拿不到第二大、第三大。

我在实际项目中还踩过一个TreeMap的坑：如果key是自定义对象，用自然排序必须实现Comparable接口，用Comparator排序则必须在构造TreeMap时传入。这两者都不做，put的时候会抛ClassCastException。

5. 源码之外的实战：常见问题与排查技巧

5.1 ConcurrentModificationException：遍历时的删改问题

这是HashMap使用中最常见的运行时异常之一。在通过迭代器遍历HashMap的过程中，如果有其他线程在结构上修改了map（增删节点，修改已有value不算结构修改），会抛出ConcurrentModificationException。

这个机制的实现思路是：迭代器内部维护一个期望的modCount值，每次迭代时校验当前modCount与期望值是否一致，不一致就说明Map的集合结构被修改过了。

// HashMap迭代器中的校验逻辑（简化版） abstract class HashIterator { int expectedModCount = modCount; // 记录创建迭代器时的modCount // 每次next时都会检查 final Node<K,V> nextNode() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); // ... } }

单线程中在遍历时执行map.put()或map.remove()，同样会触发这个异常，因为put和remove都会修改modCount。正确的删除方式是用迭代器的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(); // 正确，通过迭代器删除，不会触发fast-fail } }

JDK 8之后还有一种更简洁的写法：使用map.entrySet().removeIf()方法，底层同样是利用迭代器的remove机制。

5.2 自定义对象作为key的equals与hashCode约定

自定义对象作为HashMap的key，是面试中几乎必考的考点，也是实际开发中最容易出bug的地方。约法三章：

equals相等的两个对象，hashCode必须相等。这个约定保证了HashMap能正确地找到它们。但如果只重写equals不重写hashCode，两个逻辑相等的对象可能会被分到不同的桶位，导致get不到数据或者数据重复存储。

hashCode相等的两个对象，equals不一定相等。这是可以的，因为hash冲突是允许的，正是链表和红黑树存在的意义。

另外还有一个重要约束：作为key的对象的hashCode不能依赖会变化的状态。如果对象的某个字段参与了hashCode计算，而这个字段在放入Map后被修改了，会导致旧的hashCode和新的hashCode不同，get时算出不同的桶位，再也找不到之前存的值了。

class Person { private String name; private int age; // 只重写equals和hashCode @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Person)) return false; Person person = (Person) o; return age == person.age && Objects.equals(name, person.name); } @Override public int hashCode() { return Objects.hash(name, age); } }

这个Person类的hashCode依赖age字段，一旦放入Map后修改age，就会产生"存得进去、取不出来"的诡异问题。解决方案有两种：要么把key设计为不可变对象，要么保证对象的参与hashCode计算的字段在生命周期内不变。Integer、String这些常见key本身就是不可变的，所以不会踩坑。

5.3 初始容量和负载因子的合理设置

很多人new HashMap时不传参数，直接用默认容量16和负载因子0.75。这在数据量不大时没有问题，但如果预先知道数据量，提前设置合适的初始容量能避免多次扩容，显著提升性能。

初始容量的估算有一个简单的规律：HashMap能存放的元素数上限是容量乘负载因子。如果你知道一 共要存100个元素，最优的初始容量不是100，而是能容纳100元素的最小2的幂，即128（因为100 / 0.75约等于133.3，往上传到128不满足，256满足，更严谨地说，100 / 0.75 = 133.3，所以容量至少要134，向上取到256）。实际使用中，如果你确定初始就有100个元素，直接设置new HashMap<>(134)或者更稳妥的new HashMap<>(256)。

JDK 8之后有个辅助方法可以帮你计算这个值：

// Java 8中HashMap提供的threshold计算方法 static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

这个方法返回的是大于等于cap的最小2的幂次方。你传入100，它会返回128。

负载因子0.75是空间和时间之间的经典折中：太小会导致频繁扩容，浪费空间但hash冲突少；太大会降低扩容频率但可能导致链表过长。如果你对时间敏感且内存充足，可以适当调到0.6，减少hash冲突；如果内存紧张且对时间不敏感，可以调到0.8或0.9，但要注意链表长度。

5.4 HashMap多线程并发下的问题

HashMap是线程不安全的，这个大家都知道。但具体在并发下会出现什么问题，值得展开讲讲。

JDK 7中，并发put可能导致死循环。原因是扩容时链表采用头插法转移元素，两个线程同时扩容时，链表可能形成环，get操作进入死循环。这算是JDK 7 HashMap的著名bug。

JDK 8修复了死循环问题，改用了尾插法，元素相对位置不变。但JDK 8也没有解决数据丢失的问题：并发put时，两个线程同时往数组的同一个空位写入，后写入的会覆盖先写入的，导致其中一个数据丢失。另外一个问题是size计数不准确，即使不是并发敏感的逻辑，也会因为竞态条件导致size与实际情况不符。

并发场景直接用ConcurrentHashMap。ConcurrentHashMap的锁粒度更细，JDK 8中取消了分段锁，改用了CAS加synchronized锁住桶位头节点，并发性能比Hashtable好得多。Hashtable的锁是整个Map对象，并发度完全串行化，早已被淘汰了。

6. 面试高频问题快问快答

结合这些年的面试经验，我把HashMap和TreeMap相关的常见面试问题整理成一份速查表，方便大家复习时快速过一遍：

回答这些问题的技巧是：不要只背结论，把背后的设计思路讲出来。比如问到负载因子，先从泊松分布讲起，再解释空间和时间的权衡，这样回答的层次感是完全不一样的。

写在最后

我在实际开发中最深的体会是，HashMap和TreeMap的源码不是背下来的，而是在反复的阅读和实战中逐渐理解的。第一次看红黑树的旋转逻辑，我也觉得头晕目眩，画了好几页纸才弄明白几种case的区别。但当你真正理解了设计者的意图，会发现这些代码里的每个常量、每个分支都有它的道理。

最后分享一个小技巧：阅读源码时不要想着每一行都看懂，先抓住主流程，把主干梳理清楚，再回头看细节。比如HashMap的put方法，你先画出正常的插入路径：计算hash、定位桶位、插入节点、检查树化、检查扩容，然后再去看异常分支和边界条件，效率会高很多。TreeMap也是这样，先把插入路径和修复的几种case理清楚，删除操作的复杂度比插入还要高一些，等基础打牢了再挑战也不迟。