数据结构java从入门到实战

Java数据结构源码拆解：从入门到精通避坑指南 官方文档太长，翻到第三页就头晕？想搞懂 数据结构java 底层逻辑，却总被 ArrayList 的扩容机制绕晕？别慌。 很多开发者卡在 入门到精通 的瓶颈期，就是因为只背 API，没看源码。今天不整虚的，直接扒开 JDK 源码，带你把最核心的数据结构看透。 01 入口定位：为什么是 ArrayList？ 在 Java 集合框架中，List 接口有两个主要实现：ArrayList 和 LinkedList。 选谁？看场景。读多写少：选 ArrayList，数组连续存储，CPU 缓存命中率高。 频繁增删：选 LinkedList，双向链表，节点插入删除 O(1)。但 90% 的业务场景，ArrayList 是默认首选。它的底层是一个对象数组 Object[]。 很多人有个误区：认为 ArrayList 每次添加元素都要新建数组。错！它有个扩容机制。初始容量：10（JDK 8+ 默认，JDK 7 是 0，第一次 add 才扩容到 10）。 扩容策略：每次扩容为原来的 1.5 倍。这个 1.5 倍 不是随便定的。它是在“内存浪费”和“拷贝开销”之间找平衡。扩 2 倍：内存浪费多，GC 压力大。 扩 1.2 倍：拷贝次数多，CPU 开销大。1.5 倍是经验值。JDK 源码里写死了 oldCapacity + (oldCapacity 1)，也就是 oldCapacity * 1.5。 记住这个点，面试常被问。 02 核心片段：源码逐行拆解 来看 JDK 1.8 中 ArrayList 的 add 方法核心逻辑。 public boolean add(E e) {ensureCapacityInternal(size + 1); // 1. 确保容量足够elementData[size++] = e; // 2. 元素放入数组末尾return true; }private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(minCapacity); }private void ensureExplicitCapacity(int minCapacity) {modCount++; // 3. 修改计数器，用于并发检查// 如果当前容量小于所需最小容量，触发扩容if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureCapacityInternal(minCapacity); }private void ensureCapacityInternal(int minCapacity) {synchronized (this) {// 防止并发扩容if (minCapacity - elementData.length 0)grow(minCapacity);} }private void grow(int minCapacity) {int oldCapacity = elementData.length;// 4. 计算新容量：oldCapacity + (oldCapacity 1)int newCapacity = oldCapacity + (oldCapacity 1);if (newCapacity - minCapacity 0)newCapacity = minCapacity; // 5. 如果新容量仍不够，直接用最小容量if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity = hugeCapacity(minCapacity); // 6. 超过最大数组限制// 7. 复制数组：System.arraycopy 是底层 C 代码，比 for 循环快elementData = Arrays.copyOf(elementData, newCapacity); }逐行注释重点：ensureCapacityInternal(size + 1)：每次 add 前，检查容量是否够下一个元素。 modCount++：这是 fail-fast 机制的核心。如果在迭代过程中，其他线程修改了列表，modCount 变了，迭代器会抛出 ConcurrentModificationException。 oldCapacity 1：右移一位，等价于除以 2。这是位运算优化，比除法快。 Arrays.copyOf：底层调用 System.arraycopy，是 JVM 层面的内存拷贝，效率远高于 Java 层的 for 循环逐个赋值。关键设计：懒加载：JDK 8 中，new ArrayList() 不会立刻分配数组，而是指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA（空数组）。第一次 add 时才真正分配 10 个空间。节省内存。 同步块：grow 方法里有 synchronized。注意，这不是线程安全！synchronized 只保护 grow 方法本身，但 add 方法整体不是同步的。并发调用 add，还是可能数据错乱。03 设计思想：为什么这么写？ 1. 空间换时间 数组连续存储，支持 O(1) 随机访问。get(i) 直接 elementData[i]，不需要遍历。这是 ArrayList 的核心优势。 2. 扩容的平衡术 1.5 倍扩容，是工程折中。如果每次加 1 个：new int[n+1]，拷贝 n 个元素，总拷贝次数 O(n²)，太慢。 如果每次翻倍：内存浪费最多 50%，GC 压力大。 1.5 倍：拷贝总次数 O(n)，内存浪费可控。3. fail-fast 机制 modCount 是并发安全的“报警器”。单线程迭代中 remove 元素，modCount 不变，迭代器不报错。 并发场景下，modCount 变了，迭代器发现不一致，立刻抛异常。 目的：快速失败，避免数据不一致导致的隐蔽 Bug。对比 LinkedList： LinkedList 底层是双向链表。add(i, e)：找到第 i 个节点，插入新节点，修改前后指针。O(1)（假设已定位）。 get(i)：从头或尾遍历到第 i 个。O(n)。结论：需要随机访问：ArrayList。 需要频繁中间插入/删除：LinkedList。 但实际业务中，LinkedList 很少用。因为：节点分散在堆内存，CPU 缓存命中率低。 每个节点多两个指针（prev, next），内存开销大。 ArrayList 的扩容开销，在多数场景下可接受。04 手写简化版：从 0 到 1 实现 理解源码后，自己写一个 MyArrayList，巩固理解。 import java.util.Arrays;public class MyArrayListE {private Object[] elementData;private int size;private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {};public MyArrayList() {elementData = EMPTY_ELEMENTDATA;}public MyArrayList(int initialCapacity) {if (initialCapacity 0)throw new IllegalArgumentException(Illegal Capacity: + initialCapacity);this.elementData = new Object[initialCapacity];}public boolean add(E e) {ensureCapacity(size + 1);elementData[size++] = e;return true;}public E get(int index) {rangeCheck(index);return (E) elementData[index];}public E remove(int index) {rangeCheck(index);E oldValue = (E) elementData[index];int numMoved = size - index - 1;if (numMoved 0)// 数组元素前移，覆盖被删除元素System.arraycopy(elementData, index + 1, elementData, index, numMoved);elementData[--size] = null; // 帮助 GCreturn oldValue;}private void ensureCapacity(int minCapacity) {if (minCapacity - elementData.length 0)grow(minCapacity);}private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity 1);if (newCapacity - minCapacity 0)newCapacity = minCapacity;elementData = Arrays.copyOf(elementData, newCapacity);}private void rangeCheck(int index) {if (index = size)throw new IndexOutOfBoundsException(Index: + index + , Size: + size);}public int size() {return size;} }关键点：elementData[--size] = null：删除元素后，将末尾位置置空。否则，被删除的对象仍被数组引用，GC 无法回收，导致内存泄漏。 System.arraycopy：比 for 循环快，底层是 native 方法。 rangeCheck：索引越界检查，必须做。测试： public static void main(String[] args) {MyArrayListString list = new MyArrayList();list.add(A);list.add(B);list.add(C);System.out.println(list.get(1)); // 输出 Blist.remove(0);System.out.println(list.get(0)); // 输出 BSystem.out.println(list.size()); // 输出 2 }05 应用场景：避坑与实战 坑 1：初始容量估算 如果你知道大概要存 1000 个元素，不要 new ArrayList()。 // 错误：默认 10，扩容 10-15-22-33-49-73-109-163-244-366-549-823-1234 ListString list = new ArrayList(); for (int i = 0; i 1000; i++) {list.add(item + i); }// 正确：直接指定容量，避免多次扩容 ListString list = new ArrayList(1000);原因：每次扩容都要 System.arraycopy，拷贝 1000 个对象，开销巨大。 坑 2：并发修改 // 错误：多线程同时 add ListString list = new ArrayList(); new Thread(() - {for (int i = 0; i 1000; i++) {list.add(A + i);} }).start(); new Thread(() - {for (int i = 0; i 1000; i++) {list.add(B + i);} }).start();结果：size 可能小于 2000，数据丢失。 解决：用 CopyOnWriteArrayList（读多写少，快照隔离）。 用 Collections.synchronizedList(new ArrayList())（全同步，性能差）。 用 ConcurrentLinkedQueue（无锁，线程安全，但不支持随机访问）。坑 3：迭代器删除 // 错误：for-each 中 remove ListString list = new ArrayList(Arrays.asList(A, B, C)); for (String s : list) {if (B.equals(s)) {list.remove(s); // 抛出 ConcurrentModificationException} }// 正确：用迭代器 IteratorString it = list.iterator(); while (it.hasNext()) {if (B.equals(it.next())) {it.remove();} }原因：for-each 底层用迭代器，list.remove 直接改 modCount，迭代器发现不一致，抛异常。 实战建议：JDK 8+：优先用 ArrayList，初始容量设大点。 高并发：CopyOnWriteArrayList（读多）或 ConcurrentLinkedQueue（队列场景）。 需要排序：TreeSet / TreeMap（红黑树，O(log n) 查找）。 需要去重：HashSet / TreeSet。性能对比（JMH 基准测试，大致参考）： | 操作 | ArrayList | LinkedList | | :--- | :--- | :--- | | get(i) | 1ns | 10ns (遍历) | | add(i) | 100ns (移动元素) | 10ns (指针操作) | | remove(i) | 100ns | 10ns | | 内存占用 | 低 | 高 (指针开销) | 数据支撑： 在 10 万元素级别，ArrayList 的 get 操作比 LinkedList 快 10 倍以上。因为 CPU 缓存行（64 字节）能容纳多个数组元素，而链表节点分散，缓存命中率低。 RFC 规范参考： 虽然 Java 集合框架没有 RFC 规范，但其设计思想与 RFC 2818（HTTP 安全扩展）中的“最小权限原则”类似——ArrayList 不提供线程安全，避免不必要的同步开销。并发安全交给用户选择（Collections.synchronizedList 或 CopyOnWriteArrayList）。 总结：ArrayList 是默认选择，理解 1.5 倍扩容。 初始容量估算，避免多次扩容。 并发场景，别裸用 ArrayList。 迭代删除，用迭代器。你更常用哪种写法？评论区交流。 是 ArrayList 一把梭，还是会根据场景选 LinkedList？或者你有更优雅的并发集合用法？留言区见。