Java 核心复习：集合框架与并发编程

List

// ArrayList：数组实现
List<String> arrayList = new ArrayList<>();
arrayList.add("A");           // 尾部插入 O(1) 均摊
arrayList.add(0, "B");        // 指定位置插入 O(n)——需要移动元素
arrayList.get(0);              // 随机访问 O(1)
arrayList.remove(0);           // 删除头部 O(n)——后面元素前移

// LinkedList：双向链表实现
List<String> linkedList = new LinkedList<>();
linkedList.add("A");           // 尾部插入 O(1)
linkedList.add(0, "B");        // 指定位置插入 O(n)——需要遍历到位置
linkedList.get(0);              // 随机访问 O(n)——从头部遍历
linkedList.remove(0);           // 删除头部 O(1)

何时用哪个？

• ArrayList：随机访问多、尾部增删多
• LinkedList：头部频繁增删、实现栈/队列

注意：JDK 中 LinkedList 基本不会比 ArrayList 快。因为 ArrayList 内存连续，CPU 缓存友好。LinkedList 每个节点是独立对象，内存不连续，缓存不友好。非极端场景无脑 ArrayList。

HashMap

JDK 8+ 的 HashMap 结构：数组 + 链表 + 红黑树

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);   // 计算 hashCode → 定位桶 → 插入
map.get("A");       // 计算 hashCode → 定位桶 → 查找
map.put("A", 2);   // 同 key 覆盖旧值

重要的实现细节

1. 容量是 2 的幂次方：默认 16，扩容翻倍为 32、64、128……

   • 原因：(n - 1) & hash 替代 hash % n，位运算比取模快得多
   • 只有 n 是 2 的幂时才能这样优化

2. put 流程：

   hash(key) → 计算桶位置 → 该位置为空则直接插入
                         → 不为空则遍历链表/红黑树
                           → key 已存在则覆盖 value
                           → key 不存在则插入尾部
   

3. 红黑树化：当链表长度 > 8 且数组长度 >= 64 时，链表转红黑树。查找从 O(n) 降到 O(log n)

4. put 的语义：key 已存在时，新 value 替换旧 value，返回旧 value。不是"相同的 key 返回相同的 value"

并发编程

synchronized

// 实例方法锁：锁的是 this
public synchronized void method() { ... }

// 静态方法锁：锁的是 Class 对象
public static synchronized void staticMethod() { ... }

// 代码块锁：锁指定对象
public void method() {
    synchronized (this) { ... }
}

synchronized 在 JDK 6+ 有锁升级过程：

无锁 → 偏向锁（单线程） → 轻量级锁（少量竞争） → 重量级锁（大量竞争）

偏向锁在只有一个线程访问时几乎无开销。竞争加剧时逐步升级为重量级锁。

ReentrantLock

ReentrantLock lock = new ReentrantLock();
lock.lock();
try {
    // 临界区
} finally {
    lock.unlock();  // 必须在 finally 中释放
}

相比 synchronized 的优势：

特性	synchronized	ReentrantLock
自动释放	是	否（必须 finally）
尝试获取	不支持	tryLock()
可中断	不支持	lockInterruptibly()
公平锁	不支持	构造参数 true
条件变量	wait/notify	Condition

ThreadPoolExecutor 漏斗模型

ThreadPoolExecutor executor = new ThreadPoolExecutor(
    2,        // corePoolSize：核心线程数
    4,        // maximumPoolSize：最大线程数
    60,       // keepAliveTime：空闲线程存活时间
    TimeUnit.SECONDS,
    new LinkedBlockingQueue<>(100),  // 工作队列
    new ThreadPoolExecutor.AbortPolicy()  // 拒绝策略
);

执行流程：

提交任务 →
  核心线程 < corePoolSize → 创建核心线程执行
  核心线程满了 → 放入工作队列排队
  队列满了 → 创建新线程（不超过 maximumPoolSize）
  线程数达最大 + 队列满 → 执行拒绝策略

四种拒绝策略：

1. AbortPolicy（默认）：抛 RejectedExecutionException
2. CallerRunsPolicy：提交任务的线程自己执行
3. DiscardPolicy：静默丢弃
4. DiscardOldestPolicy：丢弃队列中最旧的任务

总结

集合框架和并发编程是 Java 开发的重中之重。理解 ArrayList/HashMap 的底层实现、synchronized/ReentrantLock 的使用场景、线程池的工作流程，基本就覆盖了日常开发中 80% 的场景。