ArrayList

// JDK 8 ArrayList 构造方法
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 空数组 {}
}
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} (共享的空数组实例)
// 区别于 EMPTY_ELEMENTDATA（明确传入容量 0 时的空数组）

// ArrayList.add(E e) 源码流程（JDK 8）
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // ① 确保容量足够
    elementData[size++] = e;           // ② 放入元素
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(
        calculateCapacity(elementData, minCapacity)
    );
}

// 如果是默认空数组，取 max(10, minCapacity)
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity); // DEFAULT_CAPACITY = 10
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  // 结构性修改计数（fail-fast 机制）
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);  // 真正扩容
}

// 核心扩容方法
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // ★ 1.5 倍扩容：oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;  // 1.5 倍仍不够，直接用所需容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);  // 超大容量处理
    elementData = Arrays.copyOf(elementData, newCapacity);  // 数组拷贝
}

import java.util.*;

// 场景：飞翔科技技术部小崔实现员工列表的基础 CRUD
public class EmployeeArrayList {
    public static void main(String[] args) {
        ArrayList<String> employees = new ArrayList<>();

        // 1. 添加员工（尾部添加，均摊 O(1)）
        employees.add("大翔（CEO）");
        employees.add("白歌（架构师）");
        employees.add("小崔（后端开发）");
        employees.add("孔蓝（测试工程师）");
        System.out.println("初始员工列表: " + employees);

        // 2. 指定位置插入（O(n)，需要移动后续元素）
        employees.add(1, "韩信（技术总监 - 新入职）");
        System.out.println("插入韩信后: " + employees);

        // 3. 随机访问（O(1)）
        System.out.println("第 3 位员工: " + employees.get(2));

        // 4. 替换元素（O(1)）
        employees.set(3, "小崔（高级后端开发 - 升职）");
        System.out.println("升职后: " + employees);

        // 5. 按索引删除（O(n)）
        employees.remove(1);  // 删除韩信
        System.out.println("删除韩信后: " + employees);

        // 6. 按对象删除（O(n)，先线性查找再移动）
        employees.remove("孔蓝（测试工程师）");
        System.out.println("删除孔蓝后: " + employees);

        // 7. 遍历方式对比
        System.out.println("\n=== 遍历方式对比 ===");
        // 方式一：for-i（ArrayList 最佳，利用 O(1) 随机访问）
        long start = System.nanoTime();
        for (int i = 0; i < employees.size(); i++) {
            employees.get(i);
        }
        System.out.println("for-i 耗时: " + (System.nanoTime() - start) + "ns");

        // 方式二：增强 for
        start = System.nanoTime();
        for (String emp : employees) {
            // 不操作，仅遍历
        }
        System.out.println("增强 for 耗时: " + (System.nanoTime() - start) + "ns");

        // 方式三：forEach Lambda（Java 8）
        System.out.println("\n--- forEach 打印 ---");
        employees.forEach(emp -> System.out.println("  " + emp));
    }
}

import java.util.*;

public class ArrayListExpansionDemo {
    public static void main(String[] args) {
        // === 对比：不预分配 vs 预分配容量 ===

        // 方案一：不预分配（多次扩容）
        long start = System.currentTimeMillis();
        ArrayList<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            list1.add(i);
        }
        long time1 = System.currentTimeMillis() - start;
        System.out.println("不预分配容量: " + time1 + "ms");

        // 方案二：预分配容量（零扩容）
        start = System.currentTimeMillis();
        ArrayList<Integer> list2 = new ArrayList<>(100000);
        for (int i = 0; i < 100000; i++) {
            list2.add(i);
        }
        long time2 = System.currentTimeMillis() - start;
        System.out.println("预分配容量  : " + time2 + "ms");
        System.out.println("性能提升: " + String.format("%.1f", (double)(time1 - time2) / time1 * 100) + "%");

        // === 扩容轨迹追踪 ===
        ArrayList<Integer> trace = new ArrayList<>();
        int lastCapacity = getCapacity(trace);
        System.out.println("\n=== 扩容轨迹 ===");
        System.out.println("初始容量: " + lastCapacity);
        for (int i = 0; i < 100; i++) {
            trace.add(i);
            int currentCapacity = getCapacity(trace);
            if (currentCapacity != lastCapacity) {
                System.out.println("第 " + (i + 1) + " 次 add 触发扩容: " 
                    + lastCapacity + " → " + currentCapacity);
                lastCapacity = currentCapacity;
            }
        }
    }

    // 通过反射获取 ArrayList 内部数组长度
    private static int getCapacity(ArrayList<?> list) {
        try {
            java.lang.reflect.Field field = ArrayList.class.getDeclaredField("elementData");
            field.setAccessible(true);
            return ((Object[]) field.get(list)).length;
        } catch (Exception e) {
            return -1;
        }
    }
}

// ❌ 错误：使用 for-i 遍历 ArrayList 并删除元素
ArrayList<String> employees = new ArrayList<>(Arrays.asList(
    "大翔", "白歌", "小崔（离职）", "孔蓝", "韩信（离职）"
));

for (int i = 0; i < employees.size(); i++) {
    if (employees.get(i).contains("离职")) {
        employees.remove(i);  // 删除后，后续元素前移，但 i 继续++
    }
}
System.out.println("清理后: " + employees);
// 实际输出: [大翔, 白歌, 孔蓝, 韩信（离职）]  ← 韩信被漏掉了！

// ✅ 方案一：倒序遍历
for (int i = employees.size() - 1; i >= 0; i--) {
    if (employees.get(i).contains("离职")) {
        employees.remove(i);
    }
}

// ✅ 方案二：使用 Iterator
Iterator<String> it = employees.iterator();
while (it.hasNext()) {
    if (it.next().contains("离职")) {
        it.remove();
    }
}

// ✅ 方案三：Java 8 removeIf（最简洁）
employees.removeIf(emp -> emp.contains("离职"));

// ❌ 错误：多线程同时 add，导致数据丢失甚至 ArrayIndexOutOfBoundsException
ArrayList<Integer> list = new ArrayList<>();

// 10 个线程各添加 1000 个元素
for (int t = 0; t < 10; t++) {
    new Thread(() -> {
        for (int i = 0; i < 1000; i++) {
            list.add(i);  // 非原子操作：elementData[size++] = e
        }
    }).start();
}

Thread.sleep(2000);
System.out.println("期望: 10000, 实际: " + list.size());  // 很可能 < 10000

// ✅ 方案一：使用 Collections.synchronizedList 包装
List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());

// ✅ 方案二：使用 CopyOnWriteArrayList（读多写少场景）
List<Integer> cowList = new CopyOnWriteArrayList<>();

// ✅ 方案三：使用 Vector（遗留方案，不推荐）
Vector<Integer> vec = new Vector<>();