这是我花了几个小时死磕 Java 集合底层源码后的总结。不是背的八股文，是我自己一行行推演出来的理解。以后面试前翻一遍这个就够了。
一、HashMap（面试出现率最高的集合，没有之一）
1.1 整体结构
HashMap 的底层说白了就是一个数组，数组里每个格子叫"桶"。往里面放数据的时候，先算出 key 的 hash 值，然后用这个 hash 值去决定放在哪个桶里。如果两个 key 算出来的桶位置一样（哈希冲突），就在那个桶后面挂一条链表。链表太长了（达到 8 个节点），再升级成红黑树。
所以本质就是：数组 + 链表 + 红黑树。
1.2 hash 怎么算的？为什么要搞个"扰动函数"？
HashMap 不是直接拿 key 的 hashCode 去用的。它多做了一步：把 hashCode 的高 16 位和低 16 位做了一次异或运算（hash ^ (hash >>> 16)）。
为什么要多此一举？因为算桶位置的时候用的是 hash & (n-1)，实际上只有 hash 值的最后几位在起作用，高位的特征全被浪费了。扰动函数就是把高位的信息"混"到低位里去，让散列更均匀，减少冲突。
至于为什么用异或而不是用与（&）或者或（|）？因为异或是唯一一个输出 0 和 1 概率各占 50% 的运算，最大程度保留了随机性。与运算会偏向 0，或运算会偏向 1，都不行。
1.3 为什么容量必须是 2 的 n 次方？
这个是 HashMap 最精妙的设计之一。
算桶位置的公式是 hash & (n-1)。当 n 是 2 的幂次方时，n-1 的二进制全是 1（比如 16-1=15，二进制是 1111）。这样做 & 运算的结果完全取决于 hash 值本身，每个桶都有可能被分配到。
但如果 n 不是 2 的幂，比如 n=10，那 n-1=9，二进制是 1001，中间两位永远是 0。不管你 hash 值是啥，算出来的桶位置中间两位永远是 0，大量桶位置永远用不上，哈希冲突会极其严重。
而且位运算（&）比取模运算（%）快几十倍。所以这个设计既保证了散列均匀，又保证了极致的性能。
如果你 new HashMap<>(10)，底层会通过 tableSizeFor() 方法自动向上取到最近的 2 的幂，也就是 16。它用了一串连续的无符号右移和按位或操作来实现，全程位运算，极快。
1.4 put 的完整流程
这个是面试被问到最多的，我自己推演了一遍源码：
- 先看 table 数组是不是空的。第一次 put 的时候 table 还是 null（懒加载），会先调 resize() 初始化一个默认长度 16 的数组。
- 用
(n-1) & hash算出桶下标。 - 如果那个桶是空的，直接创建新节点放进去，完事。
- 如果桶不为空（哈希冲突了）：
- 先看桶里第一个节点的 key 是不是跟要放的 key 相同（先比 hash，再比 equals）。相同就准备覆盖旧值。
- 如果第一个不是，看这个桶是不是已经变成红黑树了。是的话走红黑树的插入逻辑。
- 如果还是链表，就一个个遍历下去。遍历过程中找到相同的 key 就覆盖；遍历到尾部还没找到，就在尾部追加新节点（JDK 8 是尾插法，JDK 7 是头插法）。
- 插入后检查链表长度有没有到 8。到了的话调 treeifyBin()。
- treeifyBin() 里面还会再判断一次：数组长度有没有到 64。如果数组太短（不到 64），说明冲突是因为容量不够导致的，优先扩容而不是转树。只有链表长度 ≥ 8 且数组长度 ≥ 64，才会真正转红黑树。
- 最后检查 size 有没有超过阈值（容量 × 0.75），超过了就扩容。
为什么先比 hash 再比 equals？因为 hash 是 int 比较，一条 CPU 指令就搞定了。equals 可能要比较好多个字段，很慢。先用便宜的操作排除掉大部分不匹配的，再用昂贵的操作做精确确认。
1.5 get 的流程
get 比 put 简单多了：
- 算 hash，定位桶。
- 检查桶里第一个节点是不是目标（大多数情况一次命中）。
- 不是的话，看是红黑树还是链表，分别用对应的方式遍历查找。
- 找不到就返回 null。
1.6 扩容机制（JDK 8 的平移魔法）
触发扩容的条件：元素个数 > 容量 × 0.75。
扩容时数组容量翻倍（左移 1 位）。重点是数据怎么迁移。
JDK 7 的做法是对每个元素重新算一遍 hash & (newCap-1)，很慢。JDK 8 巧妙地利用了一个数学规律：扩容后 n-1 的掩码只是在高位多了一个 1。所以只需要看每个元素的 hash 值在那个新增的高位上是 0 还是 1。
具体做法是用 hash & oldCap 来判断：
- 结果为 0：留在原来的桶位置。
- 结果不为 0：搬到 原位置 + 旧容量 的新位置。
这样一条链表会被拆成高低两条链表，分别放到新数组的两个位置上。全程不需要重新计算 hash，一次位运算搞定，极致优雅。
而且 JDK 8 扩容拆链表用的是尾插法，保持了原来的顺序。JDK 7 用的头插法会把顺序反过来，多线程下会形成环形链表导致死循环（经典面试题）。
1.7 链表转红黑树的那些细节
为什么阈值是 8？ JDK 源码注释里直接引用了泊松分布的数据。在负载因子 0.75 的情况下，一个桶里挂到 8 个节点的概率是千万分之六，几乎不可能。所以树化只是极端情况的安全兜底。
为什么退化阈值是 6 而不是 8？ 为了防止反复横跳。如果转换和退化都用 8，当链表长度在 7 和 8 之间来回波动时，就会不停地转树、退回链表、转树、退回链表，白白浪费性能。中间留出 6 到 8 的缓冲区。
为什么用红黑树不用 AVL 树？ 红黑树是弱平衡的，插入删除时旋转次数少（最多 3 次），综合读写性能更好。AVL 树严格平衡，查找快一丢丢，但插入删除时旋转次数多。HashMap 的场景是读写都频繁，红黑树更合适。
1.8 负载因子为什么是 0.75？
0.75 是空间利用率和哈希冲突概率之间的最佳平衡点。
太大（比如 1.0）：数组装满才扩容，冲突严重，链表很长，查询变慢。 太小（比如 0.25）：浪费大量空间。 0.75 刚好：75% 使用率，根据泊松分布计算，每个桶的平均元素数约 0.5，链表超过 8 的概率只有千万分之六。
1.9 存 20 个元素扩容几次？
初始容量 16，阈值 12。存到第 13 个时触发扩容，容量变 32，阈值变 24。之后存到 20 都不会再扩容。答案是 1 次。
如果提前知道要存 1000 个元素，应该 new HashMap<>(1334)，底层会向上取到 2048，阈值是 1536，永远不会扩容。
1.10 为什么推荐用 String 做 Key？
三个原因：
- 不可变：hashCode 算一次就缓存起来了，后续调用直接用缓存，不用重新算。
- 天然重写了 equals 和 hashCode：直接能用，不用操心。
- 不会被修改：不存在 hash 值变了但数据还在旧桶里的内存泄漏问题。
如果用可变对象做 Key，put 之后又改了那个对象的属性，它的 hashCode 就变了。再去 get 的时候，根据新 hashCode 去别的桶找，当然找不到。而旧数据还死死卡在原来的桶里，GC 也回收不了（因为 HashMap 的 table 数组还持有它的强引用），这就是经典的内存泄漏。
1.11 HashMap 的线程安全问题
HashMap 绝对不是线程安全的。
JDK 7 的致命问题：多线程并发扩容时，头插法会导致链表形成环，后续 get 操作会陷入死循环，CPU 直接飙到 100%。
JDK 8 改成了尾插法，解决了死循环。但依然有两个致命问题：
- 数据覆盖：两个线程同时往一个空桶里 put，都判断桶是空的，后放的直接把先放的覆盖了。
- size 不准：
size++不是原子操作，两个线程同时加，可能只加了 1。
多线程环境下必须用 ConcurrentHashMap。
1.12 HashMap 的 key 可以为 null 吗？
可以，而且只能有一个 null key。源码里对 null 的处理是直接返回 hash 值 0，所以 null key 永远放在 table[0] 这个桶里。
但是 ConcurrentHashMap 和 Hashtable 的 key 和 value 都不能为 null。
二、ConcurrentHashMap（并发面试必考）
2.1 JDK 7 的分段锁
JDK 7 的思路是把一个大 HashMap 切成 16 个小 HashMap，每个小的叫 Segment。Segment 直接继承了 ReentrantLock，所以它天生就是可重入锁。
写数据的时候只锁对应的那个 Segment，其他 15 个不受影响。最多允许 16 个线程同时写。
问题在于：并发度被固定死了（默认 16），而且每个 Segment 对象本身很重，浪费内存。
2.2 JDK 8 的 CAS + synchronized
JDK 8 把分段锁整个推翻了。数据结构回归为和 HashMap 一样的数组+链表+红黑树。但锁的粒度细化到了每一个桶的头节点。
put 的时候分两种情况：
- 桶是空的：用 CAS 直接塞进去。因为是一步操作，CAS 硬件指令就能保证原子性，全程无锁，极快。
- 桶不为空（有冲突）：用 synchronized 锁住这个桶的头节点，在锁里面安心地遍历链表或红黑树。
如果 CAS 失败了（说明有人抢先把桶占了），不会抛异常，而是进入下一次 for 循环重试。这次发现桶不为空了，就会自动切换到 synchronized 分支。
为什么 JDK 8 又把 synchronized 请回来了？ 因为从 JDK 6 开始，JVM 对 synchronized 做了史诗级优化（偏向锁、轻量级锁、锁升级）。在竞争不激烈时性能和 ReentrantLock 不相上下，而且不用创建锁对象，省内存。
2.3 读操作全程无锁
get 方法不需要加任何锁。这是因为 Node 节点的 val 和 next 都被 volatile 修饰了。
volatile 保证了内存可见性：一个线程改了值，会立刻强制刷新到主内存，其他线程的 CPU 缓存里的旧值自动失效。所以读线程永远能看到最新的数据。
就算某个桶正在被 synchronized 锁住做写操作，读线程依然可以毫无阻塞地读，因为 volatile 保证了可见性，不需要锁来保护。
2.4 size 的极致统计（LongAdder 思想）
如果用一个 AtomicInteger 来统计 size，高并发下所有线程都去 CAS 争抢同一个变量，大量线程 CAS 失败后疯狂自旋，CPU 直接被榨干。
ConcurrentHashMap 学了 LongAdder 的思路：化整为零。
内部有一个 baseCount 和一个 CounterCell 数组。平时没竞争就直接 CAS 加 baseCount。一旦 CAS 失败（有竞争了），线程就用自己的随机 hash 值，分散到 CounterCell 数组的不同格子里去加。
统计 size 的时候，把 baseCount 和所有格子的值加起来就行了。
但这个 size 是弱一致性的。遍历数组求和的过程中没有加锁，其他线程可能还在往里面加数据。所以拿到的值可能不是绝对精准的。在高并发场景下，绝对不能用 map.size() 来做库存拦截或者秒杀判断。
CounterCell 上面还加了个 @sun.misc.Contended 注解，是为了解决 CPU 缓存的伪共享问题。CPU 缓存是按缓存行（64字节）读取的，如果多个 CounterCell 挤在同一个缓存行里，一个被改了整个缓存行都失效，其他格子也得跟着重新从主内存读。这个注解会在对象前后填充空白字节，把不同的 Cell 强行挤到不同的缓存行里。
2.5 为什么不允许 null？
为了避免二义性。在单线程的 HashMap 里，get 返回 null 后可以用 containsKey 去证伪。但在 ConcurrentHashMap 里，你 get 到 null 还没来得及 containsKey，别的线程可能已经把数据改了。你永远无法证明这个 null 到底是"值就是 null"还是"key 不存在"。
2.6 复合操作的陷阱
虽然 ConcurrentHashMap 内部是线程安全的，但 get 之后判断 if null 再 put，这三步合在一起不是原子的。高并发下依然会丢数据。
普通场景可以用 merge 或 putIfAbsent。但如果是热点 Key 的高并发累加（比如统计播放量），用 merge 所有线程都在一个桶的头节点上排队，性能很差。终极方案是用 ConcurrentHashMap<String, LongAdder>，把累加操作下沉到 LongAdder 内部的分散格子里。
三、volatile（JUC 并发编程的灵魂基石）
volatile 有两个超能力和一个致命弱点。
3.1 超能力一：内存可见性
一个线程改了 volatile 变量，JVM 会强制把新值刷到主内存，并且让其他线程 CPU 缓存里的旧值失效。其他线程读的时候，跳过本地缓存直接从主内存拿最新值。
经典案例：一个 while(isRunning) 循环，如果 isRunning 没加 volatile，另一个线程把它改成 false，循环线程可能永远看不到，因为它一直读的是自己 CPU 缓存里的旧值 true，死循环。
3.2 超能力二：禁止指令重排
CPU 为了优化性能会重排指令顺序。volatile 会在变量的读写前后插入内存屏障，禁止跨过屏障的指令重排。
经典案例就是双重检查锁（DCL）单例模式。new Singleton() 在底层分三步：分配内存、初始化对象、赋值引用。CPU 可能重排成分配内存、赋值引用、初始化对象。这样别的线程看到引用不是 null 就直接用了，但对象还没初始化完，直接空指针。加了 volatile 就能强制这三步严格按顺序执行。
3.3 致命弱点：不保证原子性
volatile 只能保证读到最新值，但 count++ 这种操作（读、加、写三步），两个线程可能同时读到同一个值，各自加 1 后写回去，结果只加了 1。
解决办法：用 AtomicInteger（底层是 CAS），或者加 synchronized。
四、ArrayList
4.1 底层结构
就是一个 Object 数组（elementData），外加一个 size 记录实际元素个数。
注意 size 和 capacity 的区别：size 是实际装了多少个，capacity 是数组的物理长度。
4.2 扩容机制
默认初始容量是 10，但用了懒加载。new 的时候底层数组是空的，第一次 add 时才扩容到 10。
每次扩容新容量 = 旧容量 × 1.5（用位运算 oldCapacity + (oldCapacity >> 1) 实现）。
扩容后通过 Arrays.copyOf 创建新数组，底层调的是 System.arraycopy 这个 native 方法，C++ 级别的内存块拷贝，极快。
为什么是 1.5 倍不是 2 倍？ HashMap 必须 2 倍是因为要保证 2 的幂做位运算。ArrayList 没这个限制，1.5 倍更省内存。
边界防御：如果 oldCapacity 是 1，1 + (1>>1) = 1，等于没扩。但源码里有双重保险：算完 1.5 倍后还会跟最低需求值比较，取大的那个。所以不会出问题。
如果提前知道要存多少数据，直接指定初始容量，比如 new ArrayList<>(1000)，避免反复扩容的性能损耗。
4.3 为什么不是线程安全的？
两个致命场景：
- size++ 不是原子操作：两个线程同时读到 size=5，都往下标 5 放数据，后放的覆盖先放的，数据丢失。
- 扩容判断不安全：两个线程同时判断不需要扩容，然后同时 add，数组空间不够，ArrayIndexOutOfBoundsException。
4.4 序列化的骚操作
底层数组 elementData 被 transient 修饰，意思是默认不序列化。但 ArrayList 依然能被序列化，因为它自己写了 writeObject 和 readObject 方法。
为什么要这么做？因为数组的 capacity 通常远大于 size。如果直接序列化整个数组，后面一堆 null 全跟着走了，白白浪费带宽和空间。自定义序列化只写前 size 个有效元素，反序列化时也只创建刚好够用的数组。
五、LinkedList
5.1 底层结构
标准的双向链表，每个 Node 包含 item（数据）、prev（前驱指针）、next（后继指针）。整个 LinkedList 维护了 first 和 last 两个指针。
它还实现了 Deque 接口，所以可以当队列、栈、双端队列用。
5.2 中间插入真的比 ArrayList 快吗？
不一定，大部分情况下并不快。 这是一个经典的认知误区。
LinkedList 修改指针确实是 O(1)，但在调 add(index, e) 的时候，得先调 node(index) 找到那个位置。node 方法虽然做了个小优化（index 在前半段从头找，后半段从尾找），但本质还是逐个节点遍历，O(n)。
所以中间插入两者都是 O(n)。而且 ArrayList 的数组搬运用的是 System.arraycopy（native 方法，整块内存拷贝），实测往往比 LinkedList 的链表遍历还快。
LinkedList 唯一有优势的场景是纯粹的头部或尾部操作（addFirst/addLast/removeFirst/removeLast），因为有 first 和 last 指针可以 O(1) 直达。
六、ArrayList vs LinkedList 的硬件级性能差异
6.1 遍历性能：ArrayList 碾压
理论上遍历都是 O(n)，但实测 ArrayList 比 LinkedList 快 10 倍以上。
原因是CPU 缓存行（Cache Line）和空间局部性（Spatial Locality）。
CPU 每次从主内存读数据是按缓存行（64 字节）整块加载的。ArrayList 底层是连续数组，读第 1 个元素时顺便就把后面十几个元素一起拉进了高速缓存。后续访问直接缓存命中（Cache Hit），纳秒级。
LinkedList 的节点在堆内存中随机分布，物理地址天南地北。每访问一个节点，CPU 缓存里的数据大概率用不上（Cache Miss），只能重新去主内存捞。主内存的延迟是 L1 缓存的 100 倍以上。
而且绝对不能用普通 for 循环遍历 LinkedList！ list.get(i) 每次都从头重新找，O(n²) 复杂度。必须用 Iterator 或 foreach。
6.2 内存占用：LinkedList 浪费严重
在 64 位 JVM（开启指针压缩）下，一个 LinkedList.Node 占 24 字节（对象头 12 + 三个引用 12）。
存 100 万个 Integer：
- ArrayList：数组引用约 4MB。
- LinkedList：Node 对象约 24MB。
光维护数据结构的开销，LinkedList 就是 ArrayList 的 6 倍。如果对内存极度敏感，直接用 int[] 基本类型数组，100 万个 int 只要 4MB。
6.3 队列选型：ArrayDeque 碾压 LinkedList
如果要用队列或栈，别用 LinkedList，用 ArrayDeque。
ArrayDeque 底层是首尾相接的环形数组，头尾操作通过位运算移动指针，绝对 O(1)。不用创建 Node 对象，没有 GC 压力。内存连续，CPU 缓存友好。
ArrayDeque 不能存 null，因为底层用 elements[head] == null 来判断队列是否为空。允许 null 的话就有二义性了。
七、集合遍历的那些坑
7.1 Fail-Fast 机制
ArrayList 内部有个 modCount（修改计数器），每次 add/remove 都会加 1。迭代器创建时会拍一个快照 expectedModCount。
每次调 next() 都会对比这两个值。如果你在 foreach 里直接调 list.remove()，modCount 变了但 expectedModCount 没变，不一致就抛 ConcurrentModificationException。
漏网之鱼：删除倒数第二个元素时可能不报错。因为删除后 size 减 1，恰好等于 cursor，hasNext() 返回 false，循环正常结束，next() 里的校验根本没机会执行。但最后一个元素会被跳过，数据遗漏。
Fail-Fast 不能作为可靠的并发检测手段。modCount 没有 volatile 修饰，多线程下有可见性问题。
7.2 普通 for 循环正序删除的坑
普通 for 循环没有 Fail-Fast，不会抛异常。但正序遍历删除会静默跳过元素。
因为删除一个元素后，后面的元素全部前移。但 i 继续递增，直接跳过了前移过来的那个元素。
解决方案：倒序遍历（从后往前删），或者用 Java 8 的 removeIf。
7.3 安全删除元素的三种正确姿势
iterator.remove()：迭代器自己的 remove 方法会同步更新 expectedModCount。- 倒序 for 循环：后面的元素前移不影响前面还没遍历的元素。
list.removeIf(predicate)：底层做了严格的边界控制，最安全最优雅。
八、SubList 的视图陷阱
subList 不是创建新集合！它返回的内部类持有原 ArrayList 的引用，只是加了 offset 和 size 做可视窗口。
- 改 sub → 原 list 跟着变。
- 改原 list → 再访问 sub 直接报 ConcurrentModificationException（版本校验失败）。
正确做法：如果需要独立副本，套一层 new ArrayList<>(list.subList(2, 5))。
subList 最优雅的用法是范围清除：list.subList(2, 5).clear()。
九、Arrays.asList 的三个致命坑
坑一：不能增删
返回的不是 java.util.ArrayList，而是 Arrays 类的内部类。这个内部类没有重写 add 和 remove，调了直接 UnsupportedOperationException。
坑二：引用传递后门
底层直接 this.a = array 持有了原数组的引用。改原数组，List 跟着变；改 List，原数组也变。
坑三：基础类型泛型灾难
泛型只能是引用类型。传入 int[] arr，整个数组被当成一个 Object 塞进去，得到 List<int[]>，size 永远是 1。
正确做法：
- 对象数组：
new ArrayList<>(Arrays.asList(arr)) - 基础类型数组：
Arrays.stream(arr).boxed().collect(Collectors.toList())
List.of()（JDK 9+）创建的是完全不可变集合，add/set/remove 全部报错，连 null 都不能存。
十、Java 集合 vs Redis 数据结构
它们在逻辑模型上高度一致（List、Set、Map），但底层实现天差地别，因为运行环境不同。
哈希冲突：Java HashMap 用红黑树优化查询；Redis Hash 只有链表没有树（省内存、单线程维护树太复杂）。
扩容机制：Java 一次性全量搬运（多线程环境扛得住瞬间卡顿）；Redis 用渐进式 Rehash 分批搬运（单线程不能卡，每次只搬一个桶）。
有序集合：Java TreeSet 用红黑树；Redis ZSet 用跳表（范围查找更快、实现更简单）。
并发安全：Java 需要 ConcurrentHashMap 用 CAS+锁来保证；Redis 天然安全（单线程执行命令）。
脱离运行环境谈数据结构选型就是耍流氓。底层设计的本质就是空间与时间、并发与单线程的极限取舍。