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 NodeK,V implements Map.EntryK,V { final int hash; // 保存hash值避免重复计算 final K key; V value; NodeK,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_THRESHOLD8调用treeifyBin方法尝试树化。但如果数组容量还小于MIN_TREEIFY_CAPACITY64会优先扩容而不是树化。第五步检查是否需要扩容。插入完成后如果size threshold触发resize。threshold的值是容量 * 负载因子默认是16 * 0.75 12。这里有一个很多人忽略的细节HashMap的key是可以为null的hash函数对null做了特殊处理返回0。这意味null key会落在数组的0号桶位上。2.3 get流程与hash冲突的解决细节get方法的流程是put的逆过程逻辑相对简单但细节同样值得注意final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,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 ((TreeNodeK,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 thresholdthreshold 容量 * 负载因子。默认容量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 TreeNodeK,V extends LinkedHashMap.EntryK,V { TreeNodeK,V parent; TreeNodeK,V left; TreeNodeK,V right; TreeNodeK,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(n1)也就是最长路径不会超过最短路径的两倍。这个平衡不像AVL树那样严格但已经能保证O(log n)的复杂度而且红黑树在插入和删除时的旋转次数相对较少工程上更适合需要频繁增删的场景。新插入的节点默认是红色的因为插入红节点不会违反黑节点相等这一性质只可能违反不能连续红节点这一性质修复起来相对容易。如果插入的是黑节点会导致路径上的黑节点数不一致修复成本高得多。3.3 put操作中的旋转与变色TreeMap的put方法逻辑清晰分三步查找插入位置、插入新节点、修复红黑树平衡。查找插入位置时从根节点开始通过compare方法比较key小于就走左子树大于就走右子树直到找到null的位置。这个过程中还有一个细节如果找到key相同的节点直接替换value并返回旧value不会创建新节点。插入完成后会调用fixAfterInsertion方法进行修复。修复的逻辑是一系列if-else分支处理不同的情况。核心操作有两种左旋和右旋配合变色来恢复性质。我以最常见的场景来演示左旋的操作逻辑。当一个节点的左子节点是红色、而右子节点是红色时需要把右侧的红色节点翻转到左侧。左旋的本质是把当前节点下沉为左子节点让右子节点成为新的父节点。// TreeMap中左旋的核心逻辑简化版 private void rotateLeft(EntryK,V p) { if (p ! null) { EntryK,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提供了几个关键方法TreeMapInteger, 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) SortedMapInteger, String subMap map.subMap(3, 7); // 获取尾部映射 5 SortedMapInteger, String tailMap map.tailMap(5); // 获取头部映射 5 SortedMapInteger, 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的时间复杂度全面对比在实际选型或者回答面试题时理解时间复杂度的差异是最基础的一步操作HashMapTreeMap说明putO(1) 平均O(log n)HashMap最坏情况是O(n)但实际极少发生getO(1) 平均O(log n)HashMap最坏情况是O(n)removeO(1) 平均O(log n)同上containsKeyO(1) 平均O(log n)两者都是通过key定位遍历顺序无序有序HashMap顺序不确定TreeMap按key排序这里说的平均很关键。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 NodeK,V nextNode() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); // ... } }单线程中在遍历时执行map.put()或map.remove()同样会触发这个异常因为put和remove都会修改modCount。正确的删除方式是用迭代器的remove方法IteratorMap.EntryString, Integer iterator map.entrySet().iterator(); while (iterator.hasNext()) { Map.EntryString, 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的底层数据结构JDK 8后为数组链表红黑树链表长度达8且容量达64时树化HashMap为什么不是线程安全的没有同步控制并发put可能丢数据JDK 7还可能死循环HashMap的长度为什么总是2的幂保证(n-1) hash等价于hash % n且效率更高负载因子为什么默认0.75空间与时间的折中泊松分布下链表长度达8的概率极低为什么树化阈值是8分布均匀时链表长度到8的概率约千万分之六几乎不会发生TreeMap和HashMap的区别底层结构、有序性、性能、是否支持null、线程安全性五方面对比TreeMap的key为什么不能为null红黑树需要比较keynull无法参与比较TreeMap如何实现按范围查询利用红黑树有序性subMap、headMap、tailMap等方法实现如何选择HashMap还是TreeMap需要有序或范围查询用TreeMap否则优先HashMap回答这些问题的技巧是不要只背结论把背后的设计思路讲出来。比如问到负载因子先从泊松分布讲起再解释空间和时间的权衡这样回答的层次感是完全不一样的。写在最后我在实际开发中最深的体会是HashMap和TreeMap的源码不是背下来的而是在反复的阅读和实战中逐渐理解的。第一次看红黑树的旋转逻辑我也觉得头晕目眩画了好几页纸才弄明白几种case的区别。但当你真正理解了设计者的意图会发现这些代码里的每个常量、每个分支都有它的道理。最后分享一个小技巧阅读源码时不要想着每一行都看懂先抓住主流程把主干梳理清楚再回头看细节。比如HashMap的put方法你先画出正常的插入路径计算hash、定位桶位、插入节点、检查树化、检查扩容然后再去看异常分支和边界条件效率会高很多。TreeMap也是这样先把插入路径和修复的几种case理清楚删除操作的复杂度比插入还要高一些等基础打牢了再挑战也不迟。