Java集合源码与数据结构：从ArrayList到HashMap的底层原理-平芜编程栈

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接口下另一个经典实现，它的底层是双向链表。源码里有个私有静态内部类Node：

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> 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)方法：

Node<E> node(int index) { if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> 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复杂。先看几个核心字段：

Node<K,V>[] table：哈希桶数组，真正存储数据的地方，每个桶可以放一个节点，也可以通过链表或树放多个节点。
int size：表示当前存储的键值对数量。
int threshold：扩容阈值，当size超过threshold时触发扩容。threshold = 负载因子 * 当前容量。
final float loadFactor：负载因子，默认0.75。
int modCount：结构性修改次数，服务于fail-fast机制。

节点结构在JDK 8里长这样：

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,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!

当k=8时，这个概率约为千万分之六。也就是说，在随机哈希函数理想的前提下，一个桶里出现8个节点的概率微乎其微。一旦真的出现链表长度达到8，往往是hash函数出了问题或者key的hashCode分布极度不均匀，这种情况下单纯加长链表已经无法保证查询性能，于是选择引入红黑树来做兜底。

另外要区分threshold和loadFactor的关系。threshold是resize的触发点，它等于capacity * loadFactor。比如默认容量16，负载因子0.75，threshold = 12，也就是HashMap里元素超过12个就会触发扩容。如果你自定义初始容量时传了一个不是2的幂的数，HashMap的构造函数会调用tableSizeFor方法，将它调整为大于等于该数的最小2的幂次方。源码里tableSizeFor用的是连续无符号右移和或运算，最后加1，这也是一个位运算的经典题目。

5. HashMap源码精读下篇：树化、扩容与并发问题

5.1 链表转红黑树的条件：为什么TREEIFY_THRESHOLD取8，UNTREEIFY_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长度小于64，HashMap会优先执行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永不为null，get时遍历链表就会陷入死循环。

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来存元素，元素作为key，value是同一个占位对象PRESENT，这是组合复用思路的体现。

7. HashSet、LinkedHashMap与PriorityQueue：值得一提的其他集合背后数据结构

7.1 HashSet内部持有HashMap，那HashMap的value是什么

很多人以为HashSet自己实现了去重逻辑，源码翻出来会惊讶，HashSet内部居然直接持有一个HashMap：

private transient HashMap<E,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 Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; }

这条双向链表有两种维护模式：插入顺序模式和访问顺序模式。构造时传入accessOrder参数，默认false表示按插入顺序遍历，true表示按访问顺序遍历。每次调用get或put访问某个已有key时，LinkedHashMap会通过afterNodeAccess方法把这个节点移到链表尾部。于是，链表头部的节点就是最久未访问的，链表尾部的就是最近访问的。这正是LRU缓存淘汰策略的语义。

好处是，我们可以基于LinkedHashMap快速实现一个最精简的LRU缓存。只需要覆写removeEldestEntry方法，设定一个缓存容量上限，当链表节点数超过上限时返回true，LinkedHashMap在每次put后会自动把最老的节点删除。源码里removeEldestEntry默认返回false，也就是不淘汰；覆写后要求size() > maxSize时淘汰头节点。

class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int maxSize; public LRUCache(int maxSize) { super(maxSize, 0.75f, true); this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry<K, 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 - 8
HashMap底层结构	哈希表结构	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为何线程不安全	并发覆盖、modCount	JDK 7头插法扩容会形成环形链表；JDK 8改为尾插，还会出现数据覆盖和size计数不准，应使用ConcurrentHashMap
HashSet如何保证去重	组合复用	内部是HashMap，元素作为key，value统一是PRESENT占位对象，重复判断依赖equals和hashCode
TreeMap底层原理	红黑树	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，但如果没有理解它们背后的数组、链表、哈希、树这些基础结构，一旦遇到性能问题、线程安全问题、排序问题，就只能靠蒙和试。而啃完这些源码之后，你会慢慢形成一种“看见接口就想到数据结构、看到复杂度就能估算性能”的直觉，这种直觉，是区分普通增删改查开发者和能独立设计系统的工程师的重要分水岭。希望这篇复习笔记能帮你少走很多弯路，也欢迎你在评论区聊聊自己读集合源码时遇到的难点，我看到了会尽量回复。

Java集合源码与数据结构：从ArrayList到HashMap的底层原理