Java集合与类加载图解 从"背八股"到"看懂画面"

前端转Java面试备战 · SVG结构图+流程图 · 一图胜千言

1 Java集合框架全景图

Iterable<E> Collection<E> Map<K,V> List Set Queue ArrayList LinkedList Vector⚠️ SortedSet NavigableSet HashSet LinkedHashSet TreeSet Deque PriorityQueue ArrayDeque HashMap LinkedHashMap TreeMap Hashtable⚠️ SortedMap / NavigableMap 图例说明 List — 有序、可重复 Set — 无序、不可重复 Queue — 队列、FIFO/优先级 Map — 键值对映射（不属于Collection） ⚠️ 遗留类，不推荐使用 实线=接口继承 虚线=接口→实现类
记忆口诀

List排队可重复，Set去重不排序，Queue先进先出队，Map键值成双对。

2 HashMap全链路（面试超高频🔥）

🅿️ 停车场类比

HashMap = 停车场：每个车位有编号（桶位index），同一车位的多辆车排成一列（链表），车太多了升级VIP区（红黑树）。

找车过程：拿车牌号算hash → 取模得到车位号 → 到车位找车。车位空就直接停，不空就排到后面。

2.1 HashMap内部结构

HashMap 内部结构：table[] 数组 + 链表/红黑树 table[] [0] [1] [2] [3] [4] [5] [6] [7] [8] [9-15] K2→V2 K9→V9 K17→V17 → null K5→V5 K21→V21 → null K8 K24 K40 K56 K72 key → index 计算过程 1. hash = key.hashCode() 2. hash ^= (hash >>> 16) // 扰动 3. index = hash & (n-1) // n=数组长度 等价于 hash % n（但位运算更快） 树化条件（链表→红黑树） ① 链表长度 > 8 ② 数组长度 ≥ 64 两个条件同时满足才树化 空桶（null） 链表 红黑树（长度>8） 黑节点 / 红节点

2.2 put操作流程

HashMap.put(key, value) 流程 put(key, value) hash = hash(key) index = hash & (n-1) tab[i] == null? 是 直接插入 ✅ 否 key相同? (equals) 是 覆盖value ✏️ 否 遍历链表/红黑树追加 ++size > threshold? 是→resize() 扩容2倍 🔄 链表长度>8且n≥64? →树化🌳
HashMap.java — putVal核心源码
📁 java.util
HashMap.java
Node.java
TreeNode.java
// JDK 8 HashMap.putVal 精简版 final V putVal(int hash, K key, V value, boolean onlyIfAbsent) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 懒初始化 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = new Node<>(hash, key, value, null); // 空桶→直接插入 else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || key.equals(k))) e = p; // key相同→覆盖 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 红黑树插入 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = new Node<>(hash, key, value, null); // 尾插法追加 if (binCount >= 8 - 1) treeifyBin(tab, hash); // 树化判断 break; } if (e.hash == hash && key.equals(e.key)) break; p = e; } } if (e != null) { e.value = value; return oldValue; } // 覆盖旧值 } if (++size > threshold) resize(); // 检查扩容 return null; }

2.3 resize扩容过程

resize扩容：容量 16 → 32，元素重新分配 旧 table[] (n=16) [0] [2] K2 [4] [5] K5 [8] [10] K10 ... ⇒ 新 table[] (n=32) [0] [2] K2 [4] [5] K5 [8] [10] K10 ... [18] K18 [21] K21 ... 扩容重新分配规则（JDK8 尾插法） 核心判断：e.hash & oldCap == 0 → 原位置不变（K2: hash=2, 2&16=0 → 留在[2]） != 0 → 原位置+oldCap（K18: hash=18, 18&16≠0 → [2+16]=[18]）

面试核心问题

为什么HashMap线程不安全？

JDK7 头插法 + 并发resize → 死循环：多线程同时扩容时，头插法导致链表形成环形引用，get操作陷入死循环。

JDK8 尾插法解决了死循环，但仍有数据覆盖问题：两个线程同时put，如果都判断tab[i]==null，后一个会覆盖前一个的写入。

为什么用红黑树不用AVL树？

AVL树要求严格平衡（左右子树高度差≤1），插入/删除时需要更多旋转操作。红黑树是弱平衡（最长路径不超过最短路径2倍），插入/删除时旋转次数更少。

HashMap的put/get/delete操作频繁，红黑树在写性能上更优，而查询性能差距可忽略（O(log n) vs O(log n)）。

负载因子为什么是0.75？

是时间和空间的折中：

• 太小(如0.5)：频繁扩容，空间浪费大

• 太大(如1.0)：hash冲突严重，链表过长，查询退化为O(n)

• 0.75在统计学上使得hash冲突概率在泊松分布下可控（每个桶平均0.5个元素时冲突率低）

3 ConcurrentHashMap进化史

🏢 多层停车场类比

JDK7 = 每层有独立门锁(Segment)：停车场分16层，每层一把锁，不同层可同时进出，但同一层只能排队。

JDK8 = 每个车位有独立锁(CAS+synchronized)：每个车位独立控制，不同车位完全并行，并发度 = 车位总数。

3.1 JDK7 Segment分段锁结构

JDK7 ConcurrentHashMap：Segment分段锁 Segment[] (默认16个) Segment 0 🔒 ReentrantLock HashEntry[] [0] K→V [1] [2] [3] K→V [4]...[n] Segment 1 🔒 ReentrantLock HashEntry[] [0] [1] K→V [2] K→V [3] [4]...[n] … Segment 15 🔒 ReentrantLock HashEntry[] [0] K→V [1] [2] [3] K→V [4]...[n] JDK7 核心特点 • 并发度 = Segment数量（默认16），最多16个线程同时写 • 每个Segment是一把ReentrantLock + 一个小的HashMap • 定位过程：hash → 定位Segment → 再hash → 定位HashEntry • 缺点：Segment数量初始化后不可变，并发度固定 • 缺点：查询需要两次hash，效率偏低 • 缺点：Segment内扩容时阻塞整个Segment

3.2 JDK8 CAS+synchronized结构

JDK8 ConcurrentHashMap：CAS + synchronized 锁桶头 Node[] table tab[i] == null CAS插入 ✅ 无锁操作 tab[i] != null 🔒 synchronized(头节点) 只锁这一个桶 树化桶 🔒🌳 synchronized(树根) TreeBin红黑树 数组全景示意： [0]∅ [1]∅ [2]🔒 [3]∅ [4]∅ [5]🔒 [6]∅ [7]🌳 ... JDK8 核心改进 • 去掉Segment，直接用Node[] + CAS + synchronized • 空桶：CAS无锁插入（compareAndSwapInt） • 非空桶：synchronized锁桶头节点（JDK8对synchronized做了大量优化） • 并发度 = 数组长度，理论上是JDK7的数倍 • 支持红黑树（链表>8且数组≥64时树化） • 查询只需一次hash定位，效率提升 • 扩容时支持多线程协助迁移（transfer），不阻塞读 （ForwardingNode标记正在迁移的桶，读请求转发到新表）

3.3 JDK8 put流程图

ConcurrentHashMap.put() 流程 (JDK8) put(key, value) hash = spread(key.hashCode()) 确保table已初始化 tab[i]==null? 是 CAS插入 ✅ 失败→自旋重试 否 正在扩容? (f.hash==MOVED) 是 协助迁移数据 否 synchronized(f) 🔒 遍历链表/红黑树 key相同→覆盖 | 不相同→追加 binCount≥8 → treeifyBin

JDK7 vs JDK8 对比

对比维度JDK7 SegmentJDK8 CAS+sync
锁粒度Segment级别（段锁）桶头节点级别（行锁）
并发度固定=Segment数(默认16)=数组长度(动态扩容)
查询效率两次hash定位一次hash定位
内存开销Segment+HashEntry双层Node[]单层，更紧凑
红黑树不支持支持(链表>8树化)
扩容Segment内阻塞多线程协助迁移
读操作volatile读volatile读+ForwardingNode

4 ArrayList vs LinkedList 内存布局

🎬 电影院 vs 🎫 排队买票

ArrayList = 电影院座位：连续编号，找第10排O(1)超快，但中间加座要整排往后挪O(n)。

LinkedList = 排队买票：不连续站位，找人要从头遍历O(n)，但插队只需改前后人的手指方向O(1)。

4.1 ArrayList内存布局

ArrayList：连续内存数组 elementData[] "A" [0] "B" [1] "C" [2] "D" [3] "E" [4] null [5] null [6] null [7] elementData = new Object[10] size = 5 | 容量 = 10 | 连续内存 | 随机访问O(1) 扩容策略：每次扩容1.5倍 (oldCapacity + oldCapacity >> 1)，Arrays.copyOf()整体复制 get(4) → 直接计算地址: baseAddr + 4 * elementSize

4.2 LinkedList内存布局

LinkedList：双向链表 Node{item, prev, next} prev null "A" next first prev "B" next prev "C" next last 每个Node = { E item, Node<E> prev, Node<E> next } 不连续内存 | 双向链表 | 随机访问O(n) | 头尾操作O(1) 额外内存: 每个Node 2个指针(16B) get(2) → 从first开始，沿着next走2步 → O(n)

4.3 插入/删除操作对比

ArrayList 删除中间元素 LinkedList 删除中间元素 删除前： A B❌ C D E 删除后： A C⬆ D⬆ E⬆ null C/D/E全部前移1位 O(n) 删除前： A B❌ C D 删除后： A C D ✅ A.next = C, C.prev = A O(1) 时间复杂度对比 操作 ArrayList LinkedList get(i) 随机访问 O(1) ⚡ O(n) 🐌 add(e) 尾部追加 O(1)* 均摊 O(1) add(i, e) 中间插入 O(n) O(n)* 定位+O(1)插入 remove(i) 删除 O(n) O(n)* 定位+O(1)删除 遍历 iterator O(n) 缓存友好 O(n) 缓存不友好
面试易错点

LinkedList的add(i, e)并不是O(1)！需要先遍历到第i个位置O(n)，然后才是O(1)的指针操作。所以中间插入/删除，LinkedList并不比ArrayList快。

实际开发中，ArrayList在绝大多数场景下优于LinkedList（CPU缓存行友好、内存连续）。

5 类加载机制与双亲委派

📝 找领导签字类比

双亲委派 = 找领导签字：你收到一份文件，自己不能批→先找直属上级(App)，上级不能批→找部门经理(Ext)，经理不能批→找老板(Bootstrap)。老板批不了才一层层退回让你自己处理。

好处：核心类(如java.lang.Object)永远由Bootstrap加载，防止你自己写一个假的Object覆盖它。

5.1 双亲委派模型流程

双亲委派模型：自底向上委派，自顶向下加载 Custom ClassLoader 自定义类加载器（用户开发的） App ClassLoader 加载 classpath 下的类（应用类） Ext ClassLoader 加载 ext 目录下的类（扩展类） Bootstrap ClassLoader 加载 rt.jar / 核心类库（C++实现） 委派方向 ⬆ 加载方向 ⬇ ① 委派：收到加载请求 → 先交给parent加载 → parent找不到 → 再自己加载 ② 加载：Bootstrap先尝试 → 找到就加载 → 找不到 → Ext尝试 → App尝试 → Custom尝试 ③ 都找不到 → ClassNotFoundException

5.2 类加载5个阶段

类加载5个阶段 加载 读class文件→二进制流 验证 格式/元数据/字节码验证 准备 静态变量赋零值 解析 符号引用→直接引用 初始化 clinit()执行赋值 准备阶段： static int a = 10 → 准备阶段a=0，初始化阶段a=10 初始化触发： new对象 / 反射调用 / 访问静态字段 / main()所在类

5.3 打破双亲委派场景

打破双亲委派的三大场景 1. SPI机制 如 JDBC DriverManager Bootstrap CL加载Driver接口 ↓ 但实现在classpath ↓ Bootstrap无法向下加载! → 用线程上下文CL（App CL）加载实现 2. Tomcat类加载器 每个WebApp独立CL WebApp1用Spring4 WebApp2用Spring5 同类名不同版本→必须隔离 → 每个App用独立ClassLoader 3. OSGi热部署 模块化动态加载 每个Bundle一个CL 可动态卸载/替换模块 网状依赖→不再是树形委派 → 按需加载，打破树形结构 打破双亲委派的核心思路 1. 自定义ClassLoader：重写loadClass()，不委派给parent，直接自己findClass() 2. 线程上下文类加载器：SPI中Bootstrap用Thread.getContextClassLoader()获取App CL 3. OSGi网状结构：每个模块有独立CL，根据Import-Package按需委托，不再是树形 JDK本身也打破了双亲委派：rt.jar中的DriverManager通过SPI机制加载classpath中的驱动实现
自定义ClassLoader示例
📁 classloader
MyClassLoader.java
public class MyClassLoader extends ClassLoader { private String classPath; public MyClassLoader(String classPath) { this.classPath = classPath; } // 重写findClass，不重写loadClass → 仍遵循双亲委派 @Override protected Class<?> findClass(String name) throws ClassNotFoundException { byte[] data = loadClassData(name); return defineClass(name, data, 0, data.length); } // 重写loadClass → 打破双亲委派（自己先加载） @Override protected Class<?> loadClass(String name, boolean resolve) { Class<?> c = findLoadedClass(name); if (c == null) { try { c = findClass(name); } // 先自己找 catch (ClassNotFoundException e) { c = super.loadClass(name, resolve); // 找不到再委派 } } if (resolve) resolveClass(c); return c; } }

6 大汇总

6.1 集合选型决策树

Java集合选型决策树 键值对？ 是 需排序？ 是 TreeMap 否 需插入序？ 否 HashMap 是 LinkedHashMap 线程安全？ ConcurrentHashMap 否 允许重复？ 是 → List 频繁随机访问？ 是 ArrayList ✅ 否 LinkedList 否 → Set 队列？ 需排序？ 是 TreeSet 否 需插入序？ 是 LinkedHashSet 否 HashSet ✅ 双端？ 否 PriorityQueue 是 ArrayDeque 需要线程安全？ Map → ConcurrentHashMap（不要用Hashtable!） List → Collections.synchronizedList() 或 CopyOnWriteArrayList（读多写少） Set → ConcurrentSkipListSet 或 Collections.synchronizedSet() Queue → ConcurrentLinkedQueue / BlockingQueue（生产者-消费者模式）

6.2 类比总结表

知识点生活类比核心记忆
HashMap🅿️ 停车场：车位=桶位，同车位排链表，多车升级VIP区(红黑树)hash&n-1定位 / 链表>8且n≥64树化 / 扩容2倍
ConcurrentHashMap🏢 多层停车场：JDK7每层一把锁，JDK8每个车位独立锁JDK8: 空桶CAS / 非空synchronized锁桶头
ArrayList🎬 电影院座位：连续编号，找座快，加座要挪人O(1)随机访问 / 1.5倍扩容 / CPU缓存友好
LinkedList🎫 排队买票：不连续，找人慢，插队快O(n)定位+O(1)操作 / 额外2指针内存
双亲委派📝 找领导签字：自己批不了→找上级→找上上级自底向上委派 / 自顶向下加载 / 保核心类安全
打破双亲委派🔑 越级审批：特殊情况上级授权你直接办SPI上下文CL / Tomcat隔离 / OSGi网状

6.3 面试速答6题

Q1: HashMap的底层数据结构是什么？

JDK8：数组 + 链表 + 红黑树。数组是主体（默认16），每个槽位可以挂链表（hash冲突时），链表长度超过8且数组长度≥64时转红黑树。红黑树查找O(log n)优于链表O(n)。

Q2: HashMap为什么线程不安全？

JDK7：并发resize + 头插法 → 链表成环 → 死循环。JDK8改尾插法解决了成环，但并发put仍有数据覆盖问题：两个线程同时判断tab[i]==null，都去写入，后者覆盖前者。

Q3: ConcurrentHashMap JDK7和JDK8的区别？

JDK7用Segment分段锁（默认16段，ReentrantLock），锁粒度粗，并发度固定。JDK8去掉Segment，改用CAS+synchronized锁桶头，并发度=数组长度，支持红黑树，扩容时多线程可协助迁移。

Q4: ArrayList和LinkedList的区别？实际用哪个？

ArrayList基于数组，随机访问O(1)，尾部增O(1)均摊，中间增删O(n)。LinkedList基于双向链表，随机访问O(n)，头尾操作O(1)，中间操作需要O(n)定位+O(1)指针操作。实际95%场景用ArrayList，CPU缓存行友好、内存紧凑。

Q5: 什么是双亲委派？为什么需要？

类加载时先委派给父加载器，父加载器加载不了再自己加载。保证核心类（如java.lang.Object）只被Bootstrap CL加载一次，防止用户自定义同名类覆盖核心类，保证Java类型安全。

Q6: 什么场景打破双亲委派？

① SPI机制：Bootstrap CL加载接口，通过线程上下文CL(通常是App CL)加载classpath中的实现类。② Tomcat：每个WebApp用独立CL实现类隔离（不同应用可用不同版本库）。③ OSGi：网状依赖关系，按需委托，支持热部署。

6.4 实战建议

ProTip 1: 集合初始化指定容量

ArrayList、HashMap等在知道大致容量时，初始化就指定大小。避免频繁扩容的Arrays.copyOf开销。如 new ArrayList<>(1000)、new HashMap<>(1024)。

ProTip 2: 优先使用ConcurrentHashMap而非Collections.synchronizedXxx

synchronizedMap/List是对整个对象加锁，并发度极低。ConcurrentHashMap锁粒度细到桶级别，CopyOnWriteArrayList适合读多写少场景。选对并发集合比加锁重要得多。

ProTip 3: HashMap的key必须重写hashCode和equals

如果key是自定义对象，必须同时重写hashCode()和equals()。hashCode决定桶位，equals决定是否覆盖。只重写equals不重写hashCode，两个"相等"的对象可能进不同桶，导致重复key。String和Integer已正确实现，可直接用。

核心三原则速记

集合与类加载三原则：① ArrayList 查快 LinkedList 增删快，HashMap 随机访问 O(1) → ② ConcurrentHashMap 分段锁/CAS 比 synchronized Map 快 → ③ 双亲委派保证核心类不被篡改，SPI 打破双亲委派