Java 集合与系统设计中的扩缩容机制全解析

从 ArrayList 的 1.5 倍扩容到 Redis 的渐进式 Rehash，从线程池的弹性伸缩到 LRU/LFU 的淘汰策略——扩缩容是计算机科学中最普遍的设计模式之一。本文将系统性地梳理 Java 集合框架和分布式系统中的扩缩容机制，揭示它们背后共同的设计哲学。

---

引言：扩缩容的本质

时间-空间权衡

扩缩容的核心是时间与空间的权衡：

• 预分配过多空间：浪费内存，但减少扩容次数
• 预分配过少空间：节省内存，但频繁扩容导致性能下降

均摊分析（Amortized Analysis）

动态数组（如 ArrayList）的扩容看似昂贵（需要复制所有元素），但通过均摊分析可以证明，每次插入操作的均摊时间复杂度仍然是 O(1)。

假设初始容量为 1，每次扩容翻倍。插入 n 个元素时，扩容发生在第 1, 2, 4, 8, …, n 次插入时，总复制次数为：

1 + 2 + 4 + 8 + ... + n = 2n - 1

均摊到 n 次插入，每次插入的均摊成本 = (n + 2n - 1) / n ≈ 3 = O(1)。

---

Part 1: ArrayList——动态数组的经典实现

内部结构

public class ArrayList<E> {
    transient Object[] elementData;  // 底层数组
    private int size;                // 实际元素数量
}

扩容机制

初始容量：10（使用默认构造函数时，首次 add 时分配）
扩容因子：1.5 倍（oldCapacity + (oldCapacity >> 1)）
扩容触发：size == elementData.length 时

扩容流程：

1. 计算新容量：newCapacity = oldCapacity + (oldCapacity >> 1)
   如果新容量仍不够，使用所需的最小容量
   如果新容量超过 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8），使用 Integer.MAX_VALUE
   调用 Arrays.copyOf() 创建新数组并复制元素

为什么是 1.5 倍而不是 2 倍

扩容因子	优势	劣势
2 倍	扩容次数少	内存浪费大（最多浪费 50%）
1.5 倍	内存利用率更高	扩容次数稍多
黄金比例 φ ≈ 1.618	理论最优（旧空间可被复用）	实现复杂

1.5 倍的另一个优势：oldCapacity >> 1 是位运算，比乘法更快。

缩容：ArrayList 不会自动缩容

ArrayList 不会自动缩容。即使删除了大量元素，底层数组的大小不变。需要手动调用 trimToSize()：

ArrayList<Integer> list = new ArrayList<>(1000000);
// 添加 100 万个元素...
list.clear();  // size = 0，但底层数组仍然是 100 万大小
list.trimToSize();  // 手动缩容，底层数组缩小到 0

10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → 244 → 366 → 549 → 823 → 1234
}

---

## Part 2: HashMap——哈希表的扩容与树化

### 内部结构（Java 8+）

HashMap 内部结构：
┌─────────────────────────────────────┐
│ Node<K,V>[] table (桶数组) │
├─────┬─────┬─────┬─────┬─────┬──────┤
│ 0 │ 1 │ 2 │ 3 │ … │ n-1 │
└──┬──┴─────┴──┬──┴─────┴─────┴──────┘
│ │
▼ ▼
Node Node → Node → Node (链表，长度 < 8)
│
▼
TreeNode → … (红黑树，长度 >= 8)

### 关键参数

| 参数 | 默认值 | 含义 |
|------|--------|------|
| **初始容量** | 16 | 桶数组的初始大小（必须是 2 的幂） |
| **负载因子** | 0.75 | 触发扩容的阈值 = 容量 × 负载因子 |
| **树化阈值** | 8 | 链表长度达到 8 时转为红黑树 |
| **反树化阈值** | 6 | 红黑树节点数降到 6 时退化为链表 |
| **最小树化容量** | 64 | 桶数组容量小于 64 时，优先扩容而非树化 |

### 扩容流程（resize）

1. 新容量 = 旧容量 × 2
2. 新阈值 = 新容量 × 负载因子
3. 创建新的桶数组
4. **重新分配**所有节点到新桶

**重新分配的巧妙优化**：由于容量总是 2 的幂，扩容后每个节点要么留在原位置，要么移动到 `原位置 + 旧容量` 的位置。判断依据：`hash & oldCapacity` 是否为 0。

扩容前（容量 16）：
hash = 0b…1010 0101
index = hash & 0b1111 = 0b0101 = 5

扩容后（容量 32）：
index = hash & 0b11111 = 0b00101 = 5（不变）
或
index = hash & 0b11111 = 0b10101 = 21 = 5 + 16（移动）

### 为什么容量必须是 2 的幂

1. **取模优化**：`hash % capacity` 等价于 `hash & (capacity - 1)`，位运算比取模快
2. **扩容优化**：节点要么不动，要么移动固定距离（旧容量），无需重新计算哈希
3. **均匀分布**：配合扰动函数，减少哈希冲突

### 扰动函数

```java
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

将 hashCode 的高 16 位与低 16 位异或，使得高位信息也参与桶的选择，减少冲突。

树化与反树化

为什么树化阈值是 8？

在理想的哈希分布下，桶中元素数量服从泊松分布。当负载因子为 0.75 时，一个桶中有 8 个元素的概率约为 0.00000006（千万分之一）。所以树化是极端情况下的保护措施。

为什么反树化阈值是 6 而不是 8？

如果树化和反树化使用相同的阈值，当元素数量在阈值附近波动时，会频繁地在链表和红黑树之间转换。设置一个间隔（8 和 6）可以避免这种情况。此外，红黑树的查询复杂度虽然为 O(log n)，但在节点数量较少时（如 6 个节点），其查询性能与链表的 O(n) 差异不明显，而链表的结构更简单，内存占用更低。因此，当节点数减少到 6 时，退化为链表是合理的选择。

ConcurrentHashMap 的扩容

ConcurrentHashMap（Java 8+）使用分段迁移来实现并发扩容：

1. 当某个线程触发扩容时，创建一个两倍大小的新数组
2. 将旧数组分成多个段（stride），每段默认 16 个桶
3. 多个线程可以并发迁移不同的段
4. 迁移完成前，读操作可以同时访问新旧数组
5. 写操作如果遇到正在迁移的桶，会帮助迁移

sizeCtl 字段的含义

JDK 8 中的 sizeCtl 是一个控制并发扩容状态的关键字段：

• 负值：表示正在进行扩容或初始化
• -1：表示正在初始化
• -(1 + 扩容线程数)：表示正在扩容，数值的绝对值减 1 为参与扩容的线程数
• 0：默认值，表示尚未初始化
• 正数：表示下一次扩容的阈值（类似 HashMap 的 threshold）

通过 CAS 操作修改 sizeCtl，ConcurrentHashMap 能够协调多个线程安全地参与扩容过程，无需使用重量级锁。

---

Part 3: StringBuilder——字符缓冲区的扩容

扩容策略

初始容量：16（默认）或 str.length() + 16（从字符串构造）
扩容因子：2 倍 + 2（(oldCapacity << 1) + 2）

为什么是 2 倍 + 2

• 2 倍：保证均摊 O(1) 的追加操作
• +2：处理初始容量为 0 的边界情况（0 × 2 = 0，永远无法扩容）

Java 9+ 的 Compact Strings 影响

Java 9 引入 Compact Strings 后，StringBuilder 内部也从 char[] 变为 byte[]：

• 纯 Latin-1 字符：每字符 1 字节
• 包含非 Latin-1 字符：每字符 2 字节
• 当追加非 Latin-1 字符到 Latin-1 的 StringBuilder 时，需要膨胀（inflate）：将所有 1 字节字符转换为 2 字节

最佳实践

// ✅ 预估容量
StringBuilder sb = new StringBuilder(estimatedLength);

// ✅ 大量字符串拼接用 StringBuilder
String result = new StringBuilder()
    .append("Hello")
    .append(" ")
    .append("World")
    .toString();

// ❌ 循环中用 + 拼接（每次创建新的 StringBuilder）
String result = "";
for (String s : list) {
    result += s;  // 每次循环都创建新的 StringBuilder
}

---

Part 4: 线程池——弹性伸缩的工作者

ThreadPoolExecutor 的核心参数

new ThreadPoolExecutor(
    corePoolSize,      // 核心线程数（常驻）
    maximumPoolSize,   // 最大线程数（峰值）
    keepAliveTime,     // 非核心线程的空闲存活时间
    timeUnit,          // 时间单位
    workQueue,         // 任务队列
    threadFactory,     // 线程工厂
    rejectedHandler    // 拒绝策略
);

扩容流程

新任务到达
    │
    ▼
当前线程数 < corePoolSize？
    ├── 是 → 创建核心线程执行任务
    │
    ▼
任务队列未满？
    ├── 是 → 任务入队等待
    │
    ▼
当前线程数 < maximumPoolSize？
    ├── 是 → 创建非核心线程执行任务
    │
    ▼
执行拒绝策略

缩容机制

非核心线程在空闲 keepAliveTime 后会被回收。如果设置了 allowCoreThreadTimeOut(true)，核心线程也会被回收。

四种拒绝策略

策略	行为	适用场景
AbortPolicy	抛出 RejectedExecutionException	默认策略，快速失败
CallerRunsPolicy	由提交任务的线程执行	降级处理，自动限流
DiscardPolicy	静默丢弃任务	可丢弃的任务
DiscardOldestPolicy	丢弃队列中最老的任务	优先处理新任务

CallerRunsPolicy 的隐含风险

虽然 CallerRunsPolicy 能够提供降级处理，但它存在隐含风险：当线程池饱和时，提交任务的线程会被阻塞去执行任务。如果提交任务的线程是主线程或关键业务线程，这种阻塞可能导致整个系统响应变慢，甚至引发级联故障。在微服务架构中，如果上游服务使用 CallerRunsPolicy，可能导致调用线程池耗尽，进而影响下游服务的调用。

常见线程池配置

类型	corePoolSize	maxPoolSize	队列	适用场景
FixedThreadPool	n	n	LinkedBlockingQueue（无界）	CPU 密集型
CachedThreadPool	0	Integer.MAX_VALUE	SynchronousQueue	短生命周期任务
SingleThreadExecutor	1	1	LinkedBlockingQueue（无界）	顺序执行
ScheduledThreadPool	n	Integer.MAX_VALUE	DelayedWorkQueue	定时任务

生产环境建议：不要使用 Executors 工厂方法，而是手动创建 ThreadPoolExecutor，明确指定所有参数，特别是使用有界队列。

动态调整线程池

ThreadPoolExecutor executor = new ThreadPoolExecutor(10, 20, 60, TimeUnit.SECONDS,
    new LinkedBlockingQueue<>(1000));

// 运行时动态调整
executor.setCorePoolSize(20);      // 扩大核心线程数
executor.setMaximumPoolSize(40);   // 扩大最大线程数
executor.setKeepAliveTime(30, TimeUnit.SECONDS);  // 缩短空闲时间

---

Part 5: Redis 的渐进式 Rehash

为什么需要渐进式 Rehash

Redis 是单线程模型。如果像 Java HashMap 那样一次性迁移所有数据，会导致长时间阻塞，影响服务可用性。

双哈希表结构

typedef struct dict {
    dictht ht[2];       // 两个哈希表
    long rehashidx;     // rehash 进度，-1 表示未在 rehash
    // ...
} dict;

渐进式 Rehash 流程

1. 触发条件：负载因子 > 1（无 BGSAVE）或 > 5（有 BGSAVE）
2. 分配新表：ht[1] 的大小为 ht[0] 的 2 倍
3. 渐进迁移：每次对字典的增删改查操作时，顺带迁移一个桶
4. 双表查询：rehash 期间，先查 ht[0]，再查 ht[1]
5. 新增写入 ht[1]：保证 ht[0] 只减不增
6. 完成：ht[0] 为空时，交换 ht[0] 和 ht[1]，释放旧表

定时辅助迁移

除了操作时顺带迁移，Redis 还在**定时任务（serverCron）**中进行辅助迁移：每次迁移最多 100 个桶，耗时不超过 1ms。

缩容

当负载因子 < 0.1 时，Redis 会触发缩容。缩容也使用渐进式 Rehash，新表大小为第一个大于等于已用节点数的 2 的幂。

---

Part 6: LRU 与 LFU——淘汰即缩容

LRU（Least Recently Used）

核心思想：淘汰最久未被访问的数据。

Java 实现：LinkedHashMap

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);  // accessOrder = true
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

LinkedHashMap 维护了一个双向链表，accessOrder=true 时每次访问都会将节点移到链表尾部，头部就是最久未访问的节点。

手动实现 LRU：

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> map;
    private final Node<K, V> head;  // 哨兵头节点
    private final Node<K, V> tail;  // 哨兵尾节点

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToTail(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToTail(node);
        } else {
            if (map.size() >= capacity) {
                Node<K, V> evicted = head.next;
                removeNode(evicted);
                map.remove(evicted.key);
            }
            Node<K, V> newNode = new Node<>(key, value);
            addToTail(newNode);
            map.put(key, newNode);
        }
    }

    private void moveToTail(Node<K, V> node) {
        removeNode(node);
        addToTail(node);
    }

    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToTail(Node<K, V> node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }
}

LFU（Least Frequently Used）

核心思想：淘汰访问频率最低的数据。频率相同时，淘汰最久未访问的。

实现要点：

public class LFUCache<K, V> {
    private final int capacity;
    private int minFrequency;
    private final Map<K, Node<K, V>> keyToNode;
    private final Map<Integer, LinkedHashSet<K>> frequencyToKeys;

    private static class Node<K, V> {
        K key;
        V value;
        int frequency;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.frequency = 1;
        }
    }

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFrequency = 0;
        this.keyToNode = new HashMap<>();
        this.frequencyToKeys = new HashMap<>();
    }

    public V get(K key) {
        Node<K, V> node = keyToNode.get(key);
        if (node == null) return null;
        incrementFrequency(node);
        return node.value;
    }

    public void put(K key, V value) {
        if (capacity <= 0) return;

        Node<K, V> node = keyToNode.get(key);
        if (node != null) {
            node.value = value;
            incrementFrequency(node);
        } else {
            if (keyToNode.size() >= capacity) {
                evictLeastFrequent();
            }
            Node<K, V> newNode = new Node<>(key, value);
            keyToNode.put(key, newNode);
            frequencyToKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
            minFrequency = 1;
        }
    }

    private void incrementFrequency(Node<K, V> node) {
        int oldFreq = node.frequency;
        LinkedHashSet<K> oldSet = frequencyToKeys.get(oldFreq);
        oldSet.remove(node.key);
        if (oldSet.isEmpty()) {
            frequencyToKeys.remove(oldFreq);
            if (minFrequency == oldFreq) {
                minFrequency++;
            }
        }
        node.frequency++;
        frequencyToKeys.computeIfAbsent(node.frequency, k -> new LinkedHashSet<>()).add(node.key);
    }

    private void evictLeastFrequent() {
        LinkedHashSet<K> minFreqKeys = frequencyToKeys.get(minFrequency);
        K evictedKey = minFreqKeys.iterator().next();
        minFreqKeys.remove(evictedKey);
        if (minFreqKeys.isEmpty()) {
            frequencyToKeys.remove(minFrequency);
        }
        keyToNode.remove(evictedKey);
    }
}

Redis 的近似 LRU 和 LFU

Redis 不使用精确的 LRU/LFU（需要额外的数据结构），而是使用近似算法：

近似 LRU：

• 每个 key 记录最后一次访问时间（24 位，精度约 1 秒）
• 淘汰时随机采样 N 个 key（默认 5 个），淘汰其中最久未访问的
• 采样数越大，越接近精确 LRU

近似 LFU（Redis 4.0+）：

• 每个 key 用 8 位存储对数化的访问频率（Morris Counter）
• 频率随时间衰减（避免历史热点永远不被淘汰）
• 淘汰时随机采样，淘汰频率最低的

Redis 7.0 的 listpack 改进

Redis 7.0 引入了 listpack 来替代 ziplist，作为列表和哈希表的底层压缩结构。listpack 的主要改进包括：

• 无连锁更新问题：ziplist 在插入或删除元素时可能引发连锁更新，导致最坏 O(n²) 的时间复杂度。listpack 通过重新设计内存布局，消除了连锁更新的风险，保证了最坏 O(n) 的时间复杂度。
• 更紧凑的内存编码：listpack 优化了整数和字符串的编码方式，进一步减少了内存占用。
• 更好的边界检查：listpack 在访问元素时会进行更严格的边界检查，提高了内存安全性。

这些改进使得 listpack 在保持内存紧凑的同时，提供了更稳定的性能表现，特别是在频繁插入和删除的场景下。

---

Part 7: 数据结构的衍生关系

以下 mermaid 图展示了常见数据结构之间的演化关系：

graph TD
    Array[数组 Array] --> ArrayList[ArrayList<br/>动态数组]
    Array --> HashMap[HashMap<br/>哈希表]
    Array --> Deque[ArrayDeque<br/>循环数组]

    LinkedList_Node[链表节点] --> LinkedList[LinkedList<br/>双向链表]
    LinkedList_Node --> LRU[LRU Cache<br/>哈希+双向链表]

    HashMap --> LinkedHashMap[LinkedHashMap<br/>有序哈希表]
    HashMap --> ConcurrentHashMap[ConcurrentHashMap<br/>分段锁/CAS]
    HashMap --> HashSet[HashSet<br/>集合]

    Tree[二叉树] --> BST[二叉搜索树]
    BST --> AVL[AVL 树]
    BST --> RedBlack[红黑树]
    RedBlack --> TreeMap[TreeMap]
    RedBlack --> HashMap_TreeBin[HashMap 树化桶]

    BST --> BTree[B-Tree]
    BTree --> BPlusTree[B+ Tree<br/>数据库索引]

    Heap[堆] --> PriorityQueue[PriorityQueue<br/>优先队列]
    Heap --> TopK[TopK 问题]

    SkipList[跳表] --> ConcurrentSkipListMap[ConcurrentSkipListMap]
    SkipList --> Redis_ZSet[Redis ZSet]

---

Part 8: 扩缩容的通用设计模式

模式一：倍增策略

系统	扩容因子	触发条件
ArrayList	1.5x	size == capacity
HashMap	2x	size > capacity × 0.75
StringBuilder	2x + 2	length > capacity
Redis dict	2x	load_factor > 1 或 5
Go slice	2x（小于 256）/ 1.25x（大于 256）	append 超出容量

模式二：渐进式迁移

当数据量大到无法一次性迁移时，采用渐进式策略：

系统	策略
Redis Rehash	每次操作迁移一个桶 + 定时辅助
ConcurrentHashMap	多线程并发迁移不同段
Elasticsearch Reindex	后台异步迁移，双索引并行

模式三：水位线触发

系统	高水位（扩容）	低水位（缩容）
HashMap	负载因子 > 0.75	不缩容
Redis	负载因子 > 1/5	负载因子 < 0.1
线程池	队列满 + 线程数 < max	空闲超时
K8s HPA	CPU > 80%	CPU < 30%

模式四：淘汰策略

当空间不足时，选择性地丢弃数据：

策略	适用场景	代表
LRU	时间局部性强	Memcached、操作系统页面置换
LFU	频率分布不均	Redis 4.0+、CDN
FIFO	简单场景	消息队列 TTL
Random	无明显访问模式	Redis random 策略
TTL	有过期时间的数据	Redis volatile-ttl

---

总结

数据结构/系统	初始容量	扩容因子	缩容	特殊机制
ArrayList	10	1.5x	手动 trimToSize	—
HashMap	16	2x	不缩容	链表→红黑树
StringBuilder	16	2x + 2	不缩容	Compact Strings
ThreadPoolExecutor	core	到 max	空闲超时回收	拒绝策略
Redis dict	4	2x	渐进式	渐进式 Rehash
LRU/LFU Cache	固定	不扩容	淘汰最旧/最少	近似算法

核心设计原则：

1. 预分配：已知大小时预分配，避免多次扩容
2. 均摊 O(1)：倍增策略保证均摊常数时间
3. 渐进式：大数据量时分批迁移，避免阻塞
4. 水位线：设置合理的扩缩容阈值，避免抖动

参考资料

• Java ArrayList 源码
• Java HashMap 源码
• Redis 源码 - dict.c
• ThreadPoolExecutor 官方文档