ArrayList和LinkedList的区别是什么HashMap的底层结构长什么样HashSet为什么能保证元素不重复这几个问题几乎是Java面试必问的基础题也是很多人在准备校招和社招时最先背的“八股文”。可一旦面试官追问到“ArrayList扩容具体怎么扩”“HashMap在JDK 8里put一个key经历了哪几步”不少人就卡住了。老实说这些问题背后有一个共同的核心——数据结构。数组怎么存、链表怎么串、哈希冲突怎么解决、树怎么平衡这些大学里学过的理论在Java集合框架的源码里被体现得淋漓尽致。把集合源码吃透其实就是在把数据结构和Java语言特性结合起来做一次“硬核复习”这也是今天这篇文章想帮大家解决的问题。我会从底层数组、链表讲起一直拆到HashMap、TreeMap、PriorityQueue的关键源码逻辑最后用面试题和排查经验收尾尽量让这篇复习笔记既有理论高度又能直接用在面试答题上。1. 集合源码复习前先建立一张数据结构认知地图1.1 接口、抽象类、实现类为什么Java集合要设计成三层结构在打开源码之前我建议先看一眼整个集合框架的设计骨架。Java集合的顶层接口主要分两条线一条是Collection一条是Map。Collection下面又分出List、Set、Queue三个子接口。List是有序可重复的集合Set是无序不可重复的集合Queue是队列语义的集合。Map则是独立的键值对体系它并不继承Collection这一点很多入门教程讲得比较模糊。实际看源码时你会发现接口之下还有一层抽象类比如AbstractList、AbstractSet、AbstractMap。这层抽象类的存在价值是“模板化复用”。以AbstractList为例它把get、add、remove等方法的通用逻辑先写了一遍子类只需要按自己的数据结构去实现最小必要的方法集合。比如ArrayList继承AbstractList后只需要实现get(int index)和size()以及自己的扩容方法剩下的indexOf、contains、addAll等通用逻辑抽象类已经帮它处理好了。三层结构的好处在哪里主要是面向接口编程的灵活性。你写代码时声明List接口类型运行时可以换成ArrayList也可以换成LinkedList调用方的代码不用改动。这在面试里也是一个高频考点List list new ArrayList()和ArrayList list new ArrayList()有什么区别。前者是面向抽象编程以后想替换实现类不需要改方法签名后者绑死具体类扩展性差。这一个点就能看出你有没有真正的工程经验而不仅仅是会写crud。1.2 数据结构是集合底层的地基数组、链表、哈希、树的关系数组和链表是所有数据结构里最基础的两个物理存储结构。数组在内存中是连续空间通过下标访问是O(1)复杂度但插入和删除需要搬移元素平均O(n)。链表在内存中是分散节点每个节点保存下一个节点的引用插入删除只需要改指针是O(1)复杂度可是要查找某个节点就麻烦了得从头遍历是O(n)复杂度。Java集合框架里很多实现类就是围绕这两个基础结构做了组合。比如HashMap在JDK 8里的结构本质是“数组 链表 红黑树”当多个key的哈希冲突时冲突的key以链表形式挂在同一个数组下标上当链表过长影响查询性能时链表又转换成一棵红黑树来加速查找。ArrayList是纯数组实现LinkedList是纯双向链表实现它们正好是数组和链表两种基础结构最典型的学习样例。从宏观上看复习集合源码一定要带着这张“结构地图”去看看到ArrayList你就知道人家复习的是“动态数组怎么扩容”看到LinkedList你复习的是“链表的插入删除开销与随机访问短板”看到HashMap你复习的是“散列函数 哈希冲突处理 动态扩容”这三大经典问题。这样复习下来代码是代码数据结构原理是原理两者一对照记忆会深很多。我自己带新人的时候有个习惯先让他们在白板上把ArrayList的成员变量画一遍再画HashMap的结构图结构图画不明白的源码看再多也记不住几天。2. ArrayList源码逐段拆解动态数组扩容原理与越界问题2.1 成员变量和懒加载机制默认容量10到底是什么时候分配ArrayList应该是大多数人接触的第一个集合类但越是最基础的东西越容易被问出细节。先看它几个核心成员变量底层存储是Object[] elementData数组元素个数是int size另外还有一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA的空数组常量。JDK 7的时候new ArrayList()会直接初始化一个容量为10的Object数组。但JDK 8之后改成了懒加载new ArrayList()只是把elementData指向一个空的数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA真正申请容量10的数组是在第一次add元素的时候才发生的。这个改动的原因很容易想到——很多场景下new一个集合根本不会放数据与其白白浪费10个对象的空间不如等到真正要用的时候再分配。第一次add时ensureCapacityInternal方法会计算minCapacity然后调用ensureExplicitCapacity如果minCapacity比当前数组长度大就进入grow方法扩容。这里有个容易踩坑的点如果你提前知道会存大量数据最好在创建ArrayList时直接指定初始容量否则默认从10开始一直扩容到很大容量时会反复发生数组复制白白浪费时间。举个例子你要存100万个元素如果不指定初始容量ArrayList会从10开始连续扩容十几次每次扩容都申请新数组并System.arraycopy一次累计拷贝次数是很可观的。指定new ArrayList(1000000)就直接清零了扩容开销。2.2 扩容算法的核心为什么扩容到1.5倍而不是2倍ArrayList的扩容逻辑在grow方法里源码核心就三行int newCapacity oldCapacity (oldCapacity 1); if (newCapacity - minCapacity 0) newCapacity minCapacity; if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity); elementData Arrays.copyOf(elementData, newCapacity);oldCapacity 1是位运算表示除以2所以新容量是旧容量的1.5倍。很多人会问为什么不是翻倍也不是加固定长度这里有两个层面的原因。第一直接乘1.5而不是乘2是为了避免空间浪费。如果你每次翻倍ArrayList作为List容器可能存10个元素就分配了16个容量的数组接近40%是闲置的。第二扩容不能太频繁如果每次只加1个容量add n个元素就要扩容n次每次都是O(n)的数组复制整体复杂度退化成O(n²)。1.5倍这个数值是时间复杂度和空间复杂度之间的平衡点。等比扩容保证了均摊add操作的时间复杂度是O(1)因为容量按比例增长扩容次数约等于log n。而选择1.5这个比例通常认为相较于2倍能更早释放不用的空间减少内存碎片。实际工程中这个比例可以适当调。比如大家常用的HikariCP连接池它的默认连接池扩容策略也是类似思路按比例而不是按固定量扩容这就是算法思想在工程上的泛化应用。另外有一个隐藏细节ArrayList的最大容量是Integer.MAX_VALUE - 8为什么减8因为有些JVM实现里数组对象头占据一定空间如果数组长度接近Integer.MAX_VALUE可能连对象头都放不下导致OOM。所以源码里定义了一个MAX_ARRAY_SIZE Integer.MAX_VALUE - 8的常量。面试里如果被问到“ArrayList最多能存多少元素”能说出这个细节是很加分的。2.3 删除元素时的坑没有缩容、remove遍历容易出问题ArrayList删除元素有几个实际开发经常遇到的问题。第一remove(int index)和remove(Object o)的重载迷惑性。当你有一个List 如果你写成list.remove(2)它调用的是remove(int index)删除的是下标为2的元素而不是把值为2的元素删掉。要删除值为2的元素你得用list.remove(Integer.valueOf(2))。这个是高频面试题也是真实开发里容易犯的低级错误。第二ArrayList没有自动缩容机制。删除元素后底层数组长度不变只是size减了数组尾部空出来的位置会置为null方便GC回收对象但数组本身的空间不会释放。如果一个大ArrayList删到只剩几个元素内存依然被大数组占用。要主动缩容可以调用trimToSize()方法它会把elementData复制成正好等于size长度的新数组。第三边遍历边删除会遇到ConcurrentModificationException。这是因为ArrayList内部维护了一个modCount字段修改次数每次结构变更add、remove、clear等都会加1。迭代器创建时会记录expectedModCount modCount迭代过程中每走一步都会检查modCount是否等于expectedModCount不等于就抛出异常。这也是fail-fast机制的由来。安全的删除方式是使用Iterator的remove方法或者用JDK 8的removeIf方法。绕开这个坑不止是背概念更要理解修改计数器的思路后面讲HashMap的遍历删除时会遇到同一套机制。3. LinkedList双向链表的实现真相与使用场景3.1 内部节点结构不是简单链表是双向的LinkedList是List接口下另一个经典实现它的底层是双向链表。源码里有个私有静态内部类Nodeprivate static class NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }每个节点有三个字段存数据的item指向前一个节点的prev指向后一个节点的next。LinkedList内部还有first和last两个指针分别指向链表的头尾节点。为什么做成双向而不是单向因为Java集合框架给List定义了太多需要从尾部操作的方法。比如get(int index)在ArrayList里直接按下标拿但在LinkedList里你需要从头或尾遍历才能拿到。有了last指针和prev指针getLast、removeLast这类操作就能做到O(1)。再比如add(int index, E e)中间插入时双向链表可以快速定位要插入位置的前驱和后继。单链表如果要在指定位置插入你得先拿前一个节点而前一个节点在单链表里要额外遍历才能找到双向链表直接用prev指针就能回去非常方便。实现了Deque接口这一点也很关键。LinkedList不仅是个List还是个双端队列既能当栈用push/pop又能当队列用offer/poll。源码里addFirst是linkFirst方法直接在first前面插一个新节点addLast是linkLast方法在last后面追加。这些方法全是常数时间。3.2 插入删除真的比ArrayList快吗面试官会追问的真相很多人背面试题时都记着一句话“LinkedList适合频繁插入删除ArrayList适合随机访问。”这个说法本身不算错但不严谨。如果你在原list中间位置做插入LinkedList确实只需要修改前后节点的引用不需要搬移元素。可是在中间插入之前你得先通过getNode方法遍历找到那个位置。也就是说LinkedList的中间插入实际时间复杂度是O(n)定位 O(1)插入综合起来还是O(n)。相比之下ArrayList在中间插入确实需要搬移后半部分元素平均O(n)。但ArrayList的定位是O(1)综合也是O(n)。单纯对比复杂度两者似乎是打平的。真正的差异出现在数据量级上。当n很大时ArrayList的批量搬移用的是System.arraycopy这是JVM底层的本地方法经过高度优化速度非常快。而LinkedList的遍历是逐节点跳转每跳一次都要经历一次指针解引用缓存命中率也不高。所以实测下来在大规模数据中间插入ArrayList反而经常比LinkedList更快这一点很多老手都不一定知道。从内存占用的角度LinkedList每个节点都要额外存prev和next两个引用比ArrayList多出约两个指针的开销。综合来看LinkedList真正高效的使用场景是“对头尾操作频繁”的场景比如实现队列、双端队列、栈。如果你需要在中间频繁插入删除更合适的做法是使用ArrayList 二分查找定位或者用CopyOnWriteArrayList应对并发读多写少的场景。这个认知现在很多一线技术方案里都在强调面试时你能主动说清楚“LinkedList并不是所有插入都快”会显得你对底层机制是真理解而不是背了结论。3.3 LinkedList的get效率为什么低从源码看node(int index)的二分优化LinkedList获取指定下标的元素调用的是node(int index)方法NodeE node(int index) { if (index (size 1)) { NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { NodeE x last; for (int i size - 1; i index; i--) x x.prev; return x; } }注意这里源码做了一个小优化如果index小于size的一半就从头开始往后找否则从尾部开始往前找。这其实就是一个二分思想的简化版让链表随机访问的最坏耗时缩短到原来的一半量级。复杂度依然是O(n)但常数项降低了。我在实际写代码时不会频繁对LinkedList做get操作但这种“从两端同时逼近”的思路值得借鉴。比如你在写一些需要遍历定位的数据结构时可以想想能不能利用首尾指针减少一半搜索路径这在工程里是很常见的优化思路。4. HashMap源码精读上篇数组与链表的结构配合和扰动函数4.1 核心成员变量解析table、size、threshold、loadFactor之间的关系HashMap是面试中的重头戏源码逻辑也明显比List复杂。先看几个核心字段NodeK,V[] table哈希桶数组真正存储数据的地方每个桶可以放一个节点也可以通过链表或树放多个节点。int size表示当前存储的键值对数量。int threshold扩容阈值当size超过threshold时触发扩容。threshold 负载因子 * 当前容量。final float loadFactor负载因子默认0.75。int modCount结构性修改次数服务于fail-fast机制。节点结构在JDK 8里长这样static class NodeK,V implements Map.EntryK,V { final int hash; final K key; V value; NodeK,V next; }注意这里的hash字段它在节点创建时就固定了不是每次使用时才计算。原因是后续扩容、查找都可能重新用到这个hash值提前存下来可以避免重复计算。这在设计上是一个很微妙的细节面试官如果问“HashMap的Node为什么要保存hash字段”能答出这个点的候选人不多。Java 8里的Node被设计成一个单向链表的节点next指针指向同一个桶中的下一个节点。这个table数组的每个下标位置上要么是null要么是一个Node节点链表头要么是一棵红黑树的根节点TreeNode。不同桶之间的数据是完全独立的。4.2 哈希函数与扰动函数为什么hash值要无符号右移16位HashMap在put值时第一步是计算key的hashCode然后做一次扰动处理static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }扰动函数干的事情很清晰把hashCode的高16位与低16位做一次异或运算。为什么要这样做因为HashMap根据hash定位桶下标时用的不是hash的完整值而是hash (n - 1)其中n是table数组长度。当数组长度比较小时比如默认16参与运算的只有hash的低4位高位信息完全不参与下标计算发生哈希冲突的概率急剧上升。通过将高16位异或到低16位相当于把高位的特征“混入”低位让即使是相似的低位模式也能因为高位不同而得到不同的最终hash。这样即使你的key的hashCode高16位变化大、低16位都一样经过扰动后分布仍然会相对均匀。这个操作在散列函数设计里可以理解为“信息折叠”。如果HashMap直接使用原始hashCode在桶数量较少时由于高位信息完全丢弃很多hashCode虽然不同低位却相同会导致严重的hash碰撞把HashMap退化成链表。有一个经典例子是Integer类型的key如果key是连续的整数1、2、3……它们的hashCode就是数值本身低位天然不同扰动函数影响不大。但如果key是一些自定义对象hashCode实现不好低16位完全一样只有高16位不同不扰动必定冲突。所以扰动函数就像一道保险丝让哈希分布不至于因为糟糕的hashCode而彻底崩盘。4.3 桶下标计算与put流程全解HashMap计算桶下标的核心代码if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null);这里用了tab[(n - 1) hash]代替hash % n的取模运算。为什么能用位运算替代取模因为table数组的长度n一定是2的幂当n是2的幂时hash % n等于hash (n - 1)。机器做位运算远快于取模运算这是HashMap性能优化里很关键的一环。所以你会看到HashMap的初始容量和扩容容量全是2的幂——这不是凑巧而是为了保证这种位运算等价替换成立。同时要注意一个问题如果hash是负数(n - 1) hash结果会是什么由于hash是int类型二进制的最高位是符号位但按位与后因为(n - 1)的高位是0所以最终下标一定落在0到n-1区间不会出现负数。这也是位运算求模设计巧妙的地方。完整的put流程我认为是面试必须能背下来的一个核心链条。它大致分为这么几步计算key的扰动hash值。如果table数组为null或长度为0先调用resize()完成初始化。根据(n - 1) hash定位桶下标如果该位置为空直接放入新Node。如果该位置不为空说明发生哈希冲突。先判断该位置第一个节点p的hash和key是否与待插入的key相等相等则直接覆盖value。如果p是红黑树节点TreeNode走红黑树的putTreeVal逻辑插入。否则说明p是链表头节点遍历链表判断是否存在相同key存在则覆盖找不到相同key则在链表尾部插入新节点。链表插入新节点后如果链表长度超过阈值8尝试调用treeifyBin将链表转为红黑树。最后检查size是否超过threshold超过则调用resize()扩容。细节在于TreeifyBin里还有个前置判断如果table长度小于64不会真正树化而是先扩容。这个逻辑下面再展开。4.4 加载因子0.75的统计学依据和threshold变化为什么HashMap的默认负载因子是0.75而不是0.5或者1.0这是面试中一个很有深度的问题。官方注释给出的解释是在理想情况即哈希均匀分布的假设下当负载因子为0.75时桶中出现链表长度超过8的概率极低。0.75这个值的含义是空间和时间的折中负载因子越高空间利用率越大但哈希冲突概率也随之上升get和put的耗时变长负载因子越低冲突概率降低但数组空置率提高浪费内存。0.75的推导背景其实与统计学中的泊松分布有关。我们设单个桶中的节点数量为k当HashMap容量为默认值且有0.75负载因子时单个桶出现k个节点的概率约等于P(k) (0.5^k) * e^(-0.5) / k!当k8时这个概率约为千万分之六。也就是说在随机哈希函数理想的前提下一个桶里出现8个节点的概率微乎其微。一旦真的出现链表长度达到8往往是hash函数出了问题或者key的hashCode分布极度不均匀这种情况下单纯加长链表已经无法保证查询性能于是选择引入红黑树来做兜底。另外要区分threshold和loadFactor的关系。threshold是resize的触发点它等于capacity * loadFactor。比如默认容量16负载因子0.75threshold 12也就是HashMap里元素超过12个就会触发扩容。如果你自定义初始容量时传了一个不是2的幂的数HashMap的构造函数会调用tableSizeFor方法将它调整为大于等于该数的最小2的幂次方。源码里tableSizeFor用的是连续无符号右移和或运算最后加1这也是一个位运算的经典题目。5. HashMap源码精读下篇树化、扩容与并发问题5.1 链表转红黑树的条件为什么TREEIFY_THRESHOLD取8UNTREEIFY_THRESHOLD取6链表转红黑树不是链一长就立刻转而是有两个必要条件和一条隐藏路线。源码里定义了三个常量static final int TREEIFY_THRESHOLD 8;static final int UNTREEIFY_THRESHOLD 6;static final int MIN_TREEIFY_CAPACITY 64;树化条件有两个第一链表节点数量超过8第二当前table数组的长度达到64。如果链表节点数超过8但table长度小于64HashMap会优先执行resize扩容而不是树化。理由是当桶数组很小的时候即使出现了较长的链表往往是因为桶数太少导致所有数据挤在一起而不是key的hashCode真的有问题。这时候通过扩容把桶数变大把链表“摊薄”比把链表转成红黑树更合理毕竟红黑树的节点TreeNode大概比普通Node大两倍内存开销不小树化本身是一种高成本操作。为什么阈值是8和6而不是8和7主要是为了避免震荡。如果阈值设在8和7当链表长度在8和7之间反复横跳时会导致频繁的树化和反树化操作开销很大。所以JDK使用了8和6这对阈值让树化和反树化之间留出一个缓冲区域。链表长度达到8时转树但树在删除元素导致节点数降到6以下时才会转回链表这样在7附近不会出现来回震荡。这是一个“延迟决策 滞后区间”的经典思路在很多系统的容量策略里都有类似设计。5.2 resize扩容机制为什么HashMap容量始终是2的幂HashMap扩容的核心方法是resize它有两个触发时机初始化时table为null以及size超过threshold时。扩容的规则是把旧数组长度扩大一倍。关键点在于扩容后元素在新的table中如何分布JDK 7是重新计算每个元素的hash和桶下标然后插入新数组头插法容易形成环JDK 8对这一块做了巨大优化。JDK 8在扩容时会遍历原数组的每个桶。如果桶里只有一个节点直接用新的数组长度重新计算下标放过去。如果桶里是链表会用两个临时链表来拆一个是loHead低位链表一个是hiHead高位链表。遍历链表时通过判断(e.hash oldCap) 0来区分结果为0说明该节点的hash在oldCap这一位上为0扩容后下标保持不变应该放入低位链表。结果不为0说明该节点在新数组中的下标是“原下标 旧容量”放入高位链表。这个技巧非常巧妙。因为当数组长度翻倍后新下标和旧下标之间的差异正取决于hash值在新增的那一位二进制上是0还是1。如果为0下标不变如果为1新下标等于旧下标加oldCap。这个判断只需要一次位运算避免了像JDK 7那样对每个元素重新计算hash、重新取模性能大幅提升。扩容的同时也会更新threshold newCap * loadFactor。整个扩容过程会创建一个容量翻倍的新数组然后把旧数组中的数据按上面逻辑搬运过去最终table指向新数组。由于扩容涉及数组复制和旧数据的重排它是一个相对耗时的操作。所以在使用HashMap时如果能预估到数据规模应该通过构造函数指定初始容量避免扩容多次。结合负载因子0.75如果你要存放100个数据初始容量最好设置成100 / 0.75 1 134再去tableSizeFor取最近的2次幂也就是256。这个“容量向上取整”的技巧很多人不知道但很有用。5.3 HashMap为什么线程不安全JDK 8改进了什么HashMap线程不安全是老生常谈但面试喜欢问“具体是哪种不安全”。首先推演一下JDK 7的扩容并发死循环问题。JDK 7的resize在迁移链表时采用头插法代码在将旧桶的链表元素迁移到新桶时新节点会插在链表头部并把已经迁移的节点通过next指针串起来。两个线程同时扩容时如果线程A迁移到一半被挂起线程B完成了整个扩容线程A恢复后可能把已经迁移到新数组的链表再次反向链接形成环形链表。环形链表的next永不为nullget时遍历链表就会陷入死循环。JDK 8对resize做了两个关键改进。第一链表迁移改成尾插法。扩容时旧链表的元素按照原有相对顺序被拆入低位链表和高位链表不再倒序插入所以不会出现新老节点互相倒挂形成环的情况。第二引入了高低位拆分规则避免重新hash。这两点让JDK 8的HashMap在并发扩容下不会死循环了但这不代表它是线程安全的。JDK 8的HashMap线程不安全主要体现在数据覆盖上。举个例子两个线程同时put一对key不同、但桶下标相同的键值对线程A和线程B都读到了该桶为null各自创建新节点最后后写入的一方会覆盖先写入的一方。比如线程A的put结果直接丢失。再比如size这个操作不是原子的两个线程同时size可能只加了一次导致size计数不准确影响后续是否触发扩容的判断。所以多线程下应该使用ConcurrentHashMap或者用Collections.synchronizedMap包装一层。要让HashMap线程安全且读写性能都不错直接上ConcurrentHashMap是最常见的方案它的实现里面也有数据结构的思想后面如果有机会可以单独写一篇细聊。6. 红黑树与TreeMap源码逻辑有序数据结构背后的平衡艺术6.1 为什么TreeMap用红黑树而不是ArrayList加排序TreeMap是有序Map它的底层数据结构是一棵红黑树。为什么需要有序Map因为现实中有些场景需要按key顺序遍历。比如统计每日访问量key是日期date自然有大小顺序用TreeMap可以天然按日期排序输出。普通HashMap的桶下标由哈希函数决定无法保证遍历顺序。一个很简单粗暴的方案是所有键值对放到数组里每次插入后排序查询用二分查找。这种方案在插入量不大的时候速度确实不错。但TreeMap面向的是动态插入、动态删除、随时查询有序集合的场景。如果每次插入都排序平均复杂度是O(n log n)而红黑树在插入删除时通过旋转和变色在O(log n)时间内维持树的平衡明显更高效。红黑树本质是一棵自平衡的二叉搜索树它不追求绝对的平衡像AVL树那样严格要求左右子树高度差不超过1而是通过节点颜色约束确保从根节点到叶子节点的最长路径不超过最短路径的两倍。这个松弛的平衡条件让红黑树的插入、删除、查找在均摊情况下都维持在O(log n)并且插入删除时的旋转次数相对AVL更少。所以JDK选择用红黑树作为TreeMap的底层实现而不是AVL树也不是完全平衡的B树是综合考虑插入删除频率后的选择。6.2 红黑树五大性质与树化源码实战红黑树的五条性质我建议用口诀去记忆每个节点要么是红色要么是黑色。根节点必须是黑色。每个叶子节点NIL节点空节点是黑色。如果一个节点是红色那么它的两个子节点必须是黑色也就是不能有两个连续的红色节点。从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。这五条性质是保证红黑树平衡的核心。性质4限制了红色节点不能连续出现性质5保证了每条路径的黑色节点数量一致。这两条合起来能推导出红黑树从根到叶子的最长路径不会超过最短路径的两倍简单推演一下最短路径全是黑节点最长路径是黑节点和红节点交替由于红色不能连续红色节点数最多等于黑色节点数所以最长路径长度最多是最短路径的两倍。HashMap的TreeNode是红黑树节点它继承自LinkedHashMap.Entry增加了parent、left、right、prev属性和red布尔标记。树化的核心方法balanceInsertion和balanceDeletion负责在插入和删除节点后修复红黑树性质修复手段主要是左旋、右旋和变色。拿插入举例。插入的新节点初始是红色因为插入红色节点不会影响性质5黑色节点数量相比直接插入黑色节点破坏性质的概率更低需要的修复操作更少。如果插入后父节点是红色就存在连续红节点的问题需要分类处理叔叔节点是红色执行变色叔叔节点是黑色根据当前节点是父节点的左孩子还是右孩子再做左旋或右旋。这个规则看起来复杂但理解了红黑树的修复节奏实际操作是很机械的。面试不会要求默写balanceInsertion全过程但能把“插入红节点、父红叔红就变色、父红叔黑就旋转”这个思路说清楚已经能体现源码阅读深度了。6.3 TreeMap面试考点Comparator与Comparable怎么选TreeMap要求key必须是可以比较的要么key实现了Comparable接口自然排序要么在创建TreeMap时传入Comparator自定义排序。如果两者都没有put时会抛出ClassCastException。实际代码里判断逻辑在compare方法中。如果构造时传入了Comparator就用Comparator去比较否则把key强转为Comparable再调用compareTo。这里要区分Comparable和Comparator的区别面试也很喜欢问Comparable是内部比较器比较逻辑写在实体类内部意味着只能有一种排序规则Comparator是外部比较器可以定义多种排序规则更符合策略模式的思想也符合开闭原则。在写排序代码时能用Comparator尽量用Comparator这样实体类不用频繁改动。TreeMap的遍历输出的key是按升序排列的。如果key是字符串按字典序排列是Integer按数字大小排列。它内部的Entry迭代器会对红黑树做中序遍历所以输出的顺序天然是有序的。TreeSet的底层和TreeMap是同一个套路它用一个TreeMap来存元素元素作为keyvalue是同一个占位对象PRESENT这是组合复用思路的体现。7. HashSet、LinkedHashMap与PriorityQueue值得一提的其他集合背后数据结构7.1 HashSet内部持有HashMap那HashMap的value是什么很多人以为HashSet自己实现了去重逻辑源码翻出来会惊讶HashSet内部居然直接持有一个HashMapprivate transient HashMapE,Object map; private static final Object PRESENT new Object(); public boolean add(E e) { return map.put(e, PRESENT) null; }你往HashSet里add的元素实际是当作HashMap的key存进去的。HashMap本身就有key去重的功能HashSet只是借用了这个能力value统一用一个常量PRESENT占位。由于PRESENT是静态常量所有HashSet实例共用一个占位对象不会占用额外堆内存。这也解答了一个经典问题HashSet为什么能保证元素不重复因为HashMap的key不允许重复判断重复的逻辑是先比较hash再比较equals重复时新值会覆盖旧值add方法返回false。由此可以推导出使用HashSet时必须重视的一个点放入HashSet的对象一定要正确重写hashCode和equals方法。equals相等时hashCode必须相等否则同一个对象可能被放进两个桶里HashSet的去重功能直接失效。我在一次代码评审里就遇到过有人往Set里存一个只重写了equals字段的实体导致同一逻辑对象在集合里出现了两份排查了很久才发现是hashCode没重写。7.2 LinkedHashMap如何实现访问顺序以及LRU缓存LinkedHashMap是HashMap的子类它在HashMap的基础上把所有节点串成了一条双向链表。节点除了HashMap.Node的内容还多了before和after两个指针static class EntryK,V extends HashMap.NodeK,V { EntryK,V before, after; }这条双向链表有两种维护模式插入顺序模式和访问顺序模式。构造时传入accessOrder参数默认false表示按插入顺序遍历true表示按访问顺序遍历。每次调用get或put访问某个已有key时LinkedHashMap会通过afterNodeAccess方法把这个节点移到链表尾部。于是链表头部的节点就是最久未访问的链表尾部的就是最近访问的。这正是LRU缓存淘汰策略的语义。好处是我们可以基于LinkedHashMap快速实现一个最精简的LRU缓存。只需要覆写removeEldestEntry方法设定一个缓存容量上限当链表节点数超过上限时返回trueLinkedHashMap在每次put后会自动把最老的节点删除。源码里removeEldestEntry默认返回false也就是不淘汰覆写后要求size() maxSize时淘汰头节点。class LRUCacheK, V extends LinkedHashMapK, V { private final int maxSize; public LRUCache(int maxSize) { super(maxSize, 0.75f, true); this.maxSize maxSize; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() maxSize; } }这里构造函数传true设置成访问序并且用initialCapacity / loadFactor / accessOrder三个参数构造。因为LinkedHashMap的removeEldestEntry在afterNodeInsertion里被调用而afterNodeInsertion会在put新节点后执行。我在这类缓存实现上踩过的坑是忘记开启访问顺序模式结果缓存变成了FIFO淘汰不是真正的LRU。7.3 PriorityQueue的小顶堆原理offer和poll如何维护堆结构PriorityQueue是一个优先级队列底层用数组实现了一个小顶堆。它不保证队列里所有元素有序只保证每次出队的元素是当前队列中优先级最高的元素默认是值最小的。数组里保存堆结构有一个很巧妙的规律下标为i的节点它的左孩子下标是2i 1右孩子下标是2i 2父节点下标是(i - 1) / 2。这样用扁平数组就能表示一棵完全二叉树不需要额外指针。offer插入新元素时会调用siftUp方法做“上浮”操作。新元素先放在数组末尾然后和父节点比较如果比父节点小就交换一路向上直到满足堆序。poll弹出堆顶时把最后一个元素挪到堆顶然后执行siftDown“下沉”操作不断和两个孩子中较小的那个交换直到恢复堆序。这两个操作的时间复杂度都是O(log n)。PriorityQueue是不允许插入null元素的因为它需要调用compareTo或compare方法做比较null无法参与比较。这一点是PriorityQueue和其他Queue实现比如LinkedList作为队列的区别NullPointerException陷阱很常见。7.4 集合的遍历与fail-fast机制易错点小结从ArrayList到HashMap遍历过程中都存在fail-fast机制问题。用普通的for-each遍历HashMap时如果在循环体里调用了put或remove方法会导致modCount增加迭代器在后续取next时检测到expectedModCount不一致立即抛出ConcurrentModificationException。这里除了Iterator.remove之外还有一个常见的坑即使在单线程下用foreach遍历时修改了集合内部结构也会抛异常。原因是foreach语法糖底层用的就是迭代器。还有一个HashMap相关的细节当HashMap扩容导致链表节点重新分布时遍历顺序会改变。这意味着不要依赖HashMap的遍历顺序做任何业务逻辑。如果你需要稳定顺序就用LinkedHashMap或TreeMap。整体上集合遍历注意事项我建议结合源码的modCount机制去理解而不是死记“不能在遍历中修改”这个结论。理解了修改次数计数器的设计你就知道哪些操作会修改结构哪些操作只更新值不会触发异常。8. 高频面试考点串讲与复习路线建议8.1 从数据结构视角看集合面试真题速答表到这里数据结构与集合源码的核心逻辑基本拆完了。我最后整理一份高频面试真题速答表你可以用来快速自查。面试题核心考点速答要点ArrayList和LinkedList区别底层结构、复杂度ArrayList是动态数组随机访问O(1)扩容1.5倍中间插入要搬移LinkedList是双向链表头尾操作O(1)随机访问O(n)需额外存前后指针ArrayList扩容过程扩容倍数、懒加载从空数组开始首次add创建容量10的数组之后扩容为1.5倍用Arrays.copyOf复制最大容量Integer.MAX_VALUE - 8HashMap底层结构哈希表结构JDK 8是数组 链表 红黑树链表长度超过8且数组长度超过64时树化红黑树节点少于6时退化回链表HashMap为什么用2次幂位运算代替取模长度是2的幂时hash % length可等价替换为hash (length - 1)位运算更快且能保证下标不越界HashMap默认容量为何是16空间和性能折中16在负载因子0.75下能存12个元素才扩容满足大部分场景又不会占用太多空间加载因子为什么是0.75泊松分布0.75时单个桶出现链表长度8的概率约为千万分之六空间和时间达到平衡同时留出缓冲避免频繁扩容HashMap为何线程不安全并发覆盖、modCountJDK 7头插法扩容会形成环形链表JDK 8改为尾插还会出现数据覆盖和size计数不准应使用ConcurrentHashMapHashSet如何保证去重组合复用内部是HashMap元素作为keyvalue统一是PRESENT占位对象重复判断依赖equals和hashCodeTreeMap底层原理红黑树key必须支持比较插入删除查找都是O(log n)遍历输出中序序列天然有序PriorityQueue底层原理堆结构默认小顶堆offer和poll分别执行上浮和下沉操作基于数组存储完全二叉树8.2 面试答题的结构化技巧从背结论到讲原理能答出速答表上的内容说明你基础扎实。但要在面试中脱颖而出还需要懂得把结论组织成“结论 原理 场景”的结构。这里我以自己的辅导经验举个例子。面试官问“ArrayList和LinkedList有什么区别”普通回答是“ArrayList适合随机访问LinkedList适合插入删除。”这个回答太轻了面试官几乎得不到有效信息。高分回答的框架是先用一句话给结论“两者分别基于动态数组和双向链表实现所以综合复杂度不同。”再讲原理“ArrayList扩容时是1.5倍扩随机访问通过数组下标直接定位O(1)LinkedList的node方法从两端开始遍历随机访问O(n)。”再做对比延展“虽然大家常说LinkedList插入快但从源码上看中间插入要先O(n)定位再O(1)修改指针所以大数据量下不一定比ArrayList快。我实际测试过百万级别的数据在ArrayList中间插入可能反而更快因为System.arraycopy是JVM优化过的本地方法。”最后落到使用建议“日常开发如果头尾插入删除比较多我倾向于用LinkedList或ArrayDeque如果主要是随机访问或尾部追加ArrayList是更合适的选择同时要预估容量减少扩容。”这个回答里体现了阅读源码的深度、对JDK行为的认知以及项目实战经验。面试官想看到的就是这种能对源码机制做出合理解释的候选人而不是只会背答案的复读机。8.3 复习路线建议源码精读不要死磕全部抓主干即可如果你想系统性复习Java集合源码建议不要从AbstractCollection这些冷门类开始啃。最实用的路线是ArrayList → LinkedList → HashMap → LinkedHashMap → TreeMap → HashSet → PriorityQueue。这个顺序基本覆盖了80%面试考点代码体量也不算太大。HashMap的源码算是这里面最复杂的可以先看put和resize两个方法把整体流程理清再去看balanceInsertion这类具体实现。红黑树这块遇到看不明白的旋转操作可以先拿笔画一画节点关系图确认好左旋右旋的语义再回到代码里找爷爷节点、父节点、叔叔节点的处理分支就容易理解了。一个最高效的面试准备技巧是“口述法”把自己当成面试老师对着空房间讲一遍某个集合的实现原理。如果哪个环节讲着讲着卡住了大概率就是理解不够深的地方赶紧回去看源码。我当年准备面试就是用这个方法吃饭路上嘴里嘀咕着HashMap的put流程讲到树化条件时突然想到“链表长度超过8但数组长度小于64时先扩容”的细节回去核对后彻底记住了。官方文档是Javadoc原汁原味但很多解释藏在注释里。比Javadoc更好用的是IDE的源码阅读功能直接点进去看类定义和方法实现。读源码时建议带着问题去读这个类为什么继承这个父类这个方法为什么这么写逐个追问收获会成倍增加。另外还有一个值得花时间琢磨的类是Collections工具类里面的synchronizedMap、unmodifiableMap等方法本质上都是通过包装器模式给集合增加新特性源码很精巧也经常在面试中作为扩展题出现。我自己在实际项目里有一个经验当定位到某个集合操作的性能瓶颈时一定要先想想底层结构在做什么。比如有一次我负责的业务接口发现CPU很高Dump线程栈后发现大量时间花在ArrayList的contains方法上元素量是十万级别contains是O(n)所以慢。换成HashSet之后contains降到O(1)接口耗时直接从800毫秒降到30毫秒。这种优化思路就是建立在对集合底层结构复杂度有清晰认知的前提上的。数据结构与集合源码的复习本质上是一次基础和工程的双重修炼。你可能每天都在用ArrayList、HashMap但如果没有理解它们背后的数组、链表、哈希、树这些基础结构一旦遇到性能问题、线程安全问题、排序问题就只能靠蒙和试。而啃完这些源码之后你会慢慢形成一种“看见接口就想到数据结构、看到复杂度就能估算性能”的直觉这种直觉是区分普通增删改查开发者和能独立设计系统的工程师的重要分水岭。希望这篇复习笔记能帮你少走很多弯路也欢迎你在评论区聊聊自己读集合源码时遇到的难点我看到了会尽量回复。