一、起源:数组的局限

数组是 Java 中最基础的容器,也是集合框架出现前唯一的批量数据载体。它的局限直接决定了集合框架的形态。

1. 定长

数组在创建时必须确定长度,且长度不可变。

int[] arr = new int[10];        // 长度确定为 10
arr[10] = 1;                    // 运行期抛 ArrayIndexOutOfBoundsException

要在运行期容纳更多数据,只能手工再声明一个更大的数组,把旧数据 System.arraycopy 过去。这段"扩容 + 复制 + 替换引用"的逻辑与业务无关,却被每一处需要动态数据的地方重复实现。

定长带来的第二个问题是空槽位语义缺失:int[10] 的长度是 10,但未必装满了 10 个有效元素,数组本身无法区分"没有元素"和"元素值为 0"。使用者必须额外维护一个 size 变量。

2. 类型不安全

集合框架之前的通用容器是 Object[] 与 Vector——用 Object 通吃所有类型。

// 用 Object 数组做"通用容器"
Object[] bucket = new Object[10];
bucket[0] = "hello";
bucket[1] = 42;

String s = (String) bucket[1];  // 编译通过,运行期抛 ClassCastException

类型错误被推迟到运行期才暴露,且只能在强转那一行报错,与真正写错数据的位置可能相距很远。数组本身是类型安全的(String[] 里塞不进 Integer),但一旦退化为 Object[],这层保护就消失了。

关于类型系统本身的分层与取舍,见 数据类型系统;泛型如何在不破坏二进制兼容的前提下补回类型安全,见 泛型。

3. 缺少通用算法

排序、查找、去重、求交集,这些操作对所有容器都一样,但数组只能靠 Arrays 工具类对数组做,且每个容器都要单独写一遍。更关键的是缺少统一的遍历方式——遍历数组用下标,遍历链表用指针,遍历哈希表用桶,调用方无法写出一段"通吃所有容器"的代码。

4. 集合框架要解决的三件事

Java 集合框架(JCF,Java Collections Framework,JDK 1.2 引入)针对上述局限给出三组答案。

目标 手段 结果
统一抽象 定义 Collection、List、Set、Queue、Map 等接口 调用方面向接口编程,与具体实现解耦
可复用算法 Collections、Arrays 工具类 + 基于接口实现的默认方法 排序、查找、洗牌等只写一次
性能可控的实现 数组、链表、哈希表、红黑树、跳表等多套实现并存 按访问模式选择,代价可预期

集合框架的设计原则是"接口定义契约,抽象类提供骨架,具体类给出实现"。理解这条线索,就理解了整个框架的组织方式。

本笔记聚焦上述三件事在 JDK 中的落地方式,即各集合的实现原理与代价。增删改查的具体方法签名与 API 用法不在此重复,见 Java 完整手册 第四章集合框架。


二、原理

1. 体系结构

1.1 两大分支

集合框架在顶层分叉为两条互不相交的血脉:Collection 与 Map。

Iterable
└── Collection
    ├── List      有序、可重复、有下标
    ├── Set       不重复
    ├── Queue     队列语义(FIFO / 优先级)
    └── Deque     双端队列(Queue 的子接口)

Map               键值映射
├── SortedMap     按键有序
│   └── NavigableMap  支持范围与邻近查询
└── ConcurrentMap 并发安全契约

List、Set、Queue 都继承 Collection;Map 不继承 Collection。

1.2 Map 为什么不属于 Collection

Collection 的契约围绕"一组元素"展开:add(E)、contains(Object)、iterator(),元素的身份就是它自己。

Map 的契约围绕"键到值的映射"展开:put(K, V)、get(Object key)、containsKey(Object),元素是成对的,键与值承担不同角色。两者放不到同一个方法签名体系里:

  • Collection.add 接收一个元素;Map 没有对应的单参数"添加"语义(需要键和值两个参数)
  • Collection.contains 判断"是否包含这个元素";Map 需要区分 containsKey 与 containsValue,语义不同
  • Collection.iterator() 返回单个元素;Map 迭代要返回 Map.Entry<K,V>

强行把 Map 塞进 Collection 只能让 Map.Entry 冒充 Collection 的元素,接口会立刻出现大量无法统一的默认实现。因此 JDK 的选择是:Map 独立成根接口,通过视图方法与 Collection 建立联系。

1.3 视图方法:两条血脉的连接点

Map 通过三个视图方法把自己"投影"成 Collection:

方法 返回类型 语义
keySet() Set<K> 键的集合视图
values() Collection<V> 值的集合视图
entrySet() Set<Map.Entry<K,V>> 键值对的集合视图

这三者都是视图而非拷贝:对视图的删除会作用到原 Map 上。视图是 Map 接入 Collections 工具类(排序、查找、批量操作)的通道。视图的语义与陷阱见本节第 6 小节。

1.4 抽象骨架与模板方法

每个核心接口都配有一个 AbstractXxx 骨架实现:

接口 骨架类 需要子类实现的最小集合
Collection AbstractCollection iterator()、size()
List AbstractList get(int)、size()
SequentialList AbstractSequentialList listIterator(int)
Set AbstractSet iterator()、size()
Map AbstractMap entrySet()
Queue AbstractQueue offer()、poll()、peek()、iterator()、size()

以 AbstractCollection 为例,只要实现 iterator() 与 size(),就自动获得 contains、toArray、remove(Object)、addAll、containsAll、retainAll、toString 等一批方法。这是模板方法模式的应用:骨架类固定算法步骤,把差异点下沉为抽象方法。

代价是默认实现未必高效。AbstractCollection.contains 是遍历式 O(n) 查找,而 HashSet 会覆盖为 O(1) 的哈希查找。判断一个实现类有没有覆盖某个方法,是评估其性能的前提。

AbstractMap 的 hashCode、equals 也是模板方法的典型:Map 的相等语义定义为"键值对集合相等",与实现无关,因此放在骨架类里统一实现。

骨架类的存在使自定义集合的门槛降到两个方法。JDK 中大量内部类(如 HashMap 的 keySet() 返回的 KeySet、ArrayList 的 SubList)都继承了对应骨架类。

2. List 实现

2.1 ArrayList 的数组结构

ArrayList 的核心字段只有三个:

public class ArrayList<E> extends AbstractList<E> {
    transient Object[] elementData;   // 实际存放元素的数组
    private int size;                 // 有效元素个数(与 elementData.length 不同)
    private static final int DEFAULT_CAPACITY = 10;
}

关键点在于 size 与 elementData.length 是两个独立概念:前者是逻辑长度(size() 的返回值),后者是容量。这个分离正是对数组"空槽位语义缺失"的补偿。

构造方法的差异直接影响首次扩容:

构造方式 初始 elementData 第一次 add 时的行为
new ArrayList<>() 共享的空数组常量 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 扩容到 10
new ArrayList<>(0) 共享的空数组常量 EMPTY_ELEMENTDATA 扩容到 1(按需增长)
new ArrayList<>(n) 直接分配长度 n 的数组 不扩容(直到超过 n)

无参构造并不立即分配 10 个槽位,而是等第一次 add 时再分配。这个延迟分配策略是为了让大量空集合不占用数组内存(JDK 6 及以前无参构造会在构造时就分配 10 个引用)。

2.2 扩容倍数与扩容代价

add 在容量不足时调用 grow:

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity,   // 最小增长量
                oldCapacity >> 1);           // 优先增长量:旧容量的一半
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

因此扩容倍数是 1.5 倍(oldCapacity + oldCapacity / 2)。若 1.5 倍仍不满足需求(如一次 addAll 塞入大量元素),则直接扩到需要的容量。容量上限受数组最大长度约束,接近 Integer.MAX_VALUE - 8 时进入特殊处理分支。

扩容的代价有两层:

  1. 时间代价:Arrays.copyOf 内部是 System.arraycopy,把旧数组的全部引用复制到新数组,单次为 O(n)。add 到 n 个元素,累计复制量约为最终元素数的常数倍(1.5 倍增长下约为 2n 量级的引用复制)。因此尾部追加是均摊 O(1),而不是严格 O(1)。
  2. 空间代价(峰值):扩容瞬间,旧数组(容量 c)与新数组(容量 1.5c)同时存在,这段时间内该集合的数组占用达到 2.5c。对几百 MB 量级的 ArrayList,这个峰值足以让堆进入紧张状态,甚至触发 Full GC 或 OOM。

这是"预设容量"最重要的理由:不是省下几次 arraycopy,而是削掉 2.5 倍的内存峰值。

2.3 随机访问与中间插入

操作 复杂度 原因
get(i) / set(i, e) O(1) 数组下标直接寻址
add(e)(尾部) 均摊 O(1) 可能触发 1.5 倍扩容
add(0, e) / add(i, e) O(n) 需要把 i 之后的元素整体后移
remove(i) / remove(Object) O(n) 需要把 i 之后的元素整体前移;remove(Object) 还要先线性查找

数组的连续布局带来两个优势:下标寻址是常数时间;元素在内存中相邻,符合 CPU 缓存局部性,顺序遍历极快。代价是中间位置的插入删除必须搬移数据,且搬移量随元素数量线性增长。

2.4 LinkedList 的双向链表结构

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E> {
    transient int size;
    transient Node<E> first;   // 头节点
    transient Node<E> last;    // 尾节点

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }
}

LinkedList 同时实现 List 与 Deque,因此既能当列表用,也能当队列/栈用。

节点结构的代价在于每个元素都需要一个独立的 Node 对象。在 64 位 JVM 开启压缩指针时,一个 Node 的内存布局大致为:对象头 12 字节 + item 引用 4 字节 + next 引用 4 字节 + prev 引用 4 字节 = 24 字节,按 8 字节对齐后仍是 24 字节。而 ArrayList 中一个元素只占数组里 4 字节的引用位。

也就是说,同样 100 万个元素,LinkedList 仅节点结构就要多消耗约 24 MB,是 ArrayList 引用数组(约 4 MB)的数倍。若关闭压缩指针,引用宽度翻倍,差距进一步扩大。

2.5 LinkedList 访问与插入的真实代价

课本上常说"链表插入删除 O(1)",这个结论成立的前提是已经持有待操作节点的引用。List 接口的 API 只给下标,因此必须先定位:

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) x = x.next;   // 从头部走
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) x = x.prev;  // 从尾部走
        return x;
    }
}

node(index) 会判断下标在前半段还是后半段,从较近的一端遍历,平均走 n/4 步,复杂度仍是 O(n)。所以:

操作 复杂度 说明
get(i) O(n) 需要 node(i)
add(i, e) O(n) 定位 O(n) + 链接 O(1)
remove(i) O(n) 定位 O(n) + 断链 O(1)
addFirst / addLast O(1) 直接操作 first / last
removeFirst / removeLast O(1) 同上
iterator() 顺序遍历 O(n) 沿指针走,每个元素 O(1)

要注意 O(n) 前面的常数:链表的"n 步"是指针追逐,每跳一次都要访问一个可能位于堆中任意位置的 Node 对象,几乎每次都是缓存未命中。数组的"n 步"是连续内存的顺序扫描,一次缓存行能覆盖多个元素。因此在元素数量相同的情况下,链表的线性操作实际耗时远高于数组的线性操作,常数差距可达一个数量级。

实践结论:LinkedList 的合理用途是两端操作频繁的队列/栈(作为 Deque),或迭代器顺序遍历中间大量删除。把它当成"插入快"的通用列表使用,在随机访问场景会显著劣化。

2.6 Vector 与 CopyOnWriteArrayList 的定位

Vector 是 JDK 1.0 遗留类,所有公开方法都带 synchronized,扩容倍数为 2 倍(或构造时指定的 capacityIncrement)。其问题在于锁的粒度是整张表,且每次单元素操作都要获取监视器,在高并发下退化为串行执行。新代码不应再使用 Vector 与它的子类 Stack,需要栈语义时用 ArrayDeque。

CopyOnWriteArrayList 是 JDK 5 引入的并发集合,策略是写时复制:

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();                // 读 volatile 数组
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);         // 全量复制
        es[len] = e;
        setArray(es);                            // volatile 写,一次性发布
        return true;
    }
}

public E get(int index) {
    return elementAt(getArray(), index);         // 完全无锁
}

它的特性由此推出:

  • 读操作完全无锁,读性能与 ArrayList 相当
  • 写操作全量复制整个数组,单次写为 O(n),且内存峰值同样达到 2 倍数组
  • 迭代器基于创建时的快照,迭代过程中不会抛 ConcurrentModificationException(fail-safe),但也看不到迭代开始后的写入
  • 适用于读多写极少的场景(如监听器列表、配置白名单),写入频繁时复制成本无法接受

其底层依赖的 volatile 数组发布语义,以及写时复制与内存可见性的关系,见 Java 并发编程 第四章;其他并发集合(ConcurrentHashMap、ConcurrentSkipListMap、阻塞队列)的对比见第三部分第 1 小节与第 4 小节,细节见 Java 并发编程。

3. HashMap

HashMap 是集合框架中实现最复杂的类。它在 JDK 8 中采用数组 + 链表 + 红黑树的组合结构。

3.1 散列函数与扰动

定位一个键的桶下标分两步。

第一步,把 hashCode() 的返回值做扰动:

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

第二步,用位与代替取模计算下标:

int index = (table.length - 1) & hash;

扰动的作用:table.length 是 2 的幂,length - 1 的低位全是 1,高位全是 0。若直接用原始 hashCode 做与运算,只有低位参与,高位信息被丢弃。当一批键的 hashCode 高位不同而低位相同(例如同一区间的小整数、String 的短字符串)时,冲突会集中爆发。把高 16 位异或到低 16 位,让高位信息参与下标计算,显著降低这类规律性冲突。

null 键被特殊处理为 hash = 0,因此始终落在 table[0],这也是 HashMap 允许一个 null 键的原因。

3.2 容量为何取 2 的幂

容量取 2 的幂有三个直接好处:

  1. 位运算替代取模。hash % n 需要整除指令,而 hash & (n - 1) 在 n 为 2 的幂时与取模等价,且是单条位运算指令。这是性能路径上的关键优化。
  2. 扩容拆分可以只判断一个位。扩容后容量翻倍,length - 1 多出一个高位 1。元素的新下标只能有两种结果:留在原下标,或移动到"原下标 + 旧容量"。判断依据就是 hash & oldCapacity。详见 3.5。
  3. 元素分布更适合位运算下的散列。若容量含奇数因子(如 15),length - 1 的二进制中会出现 0 位,这些位对应的桶永远无法被访问,元素分布必然出现空洞。

即使构造时传入非 2 的幂(如 new HashMap<>(17)),HashMap 也会用 tableSizeFor 把它向上取整到最近的 2 的幂(17 → 32)。

3.3 负载因子与扩容机制

参数 默认值 含义
DEFAULT_INITIAL_CAPACITY 16 首次分配 table 的容量
DEFAULT_LOAD_FACTOR 0.75 元素数 / 容量 的阈值
threshold 容量 × 负载因子 触发扩容的元素数量

扩容逻辑:元素数量超过 threshold 时,容量翻倍,threshold 随之翻倍。

负载因子取 0.75 是在空间利用率与冲突概率之间取折中:

  • 负载因子越大,空桶越少、空间利用率越高,但平均链表越长、查找越慢
  • 负载因子越小,冲突越少、查找越快,但空桶更多、内存浪费越大

JDK 源码注释给出了理论依据:在理想散列(hashCode 均匀分布)下,一个桶中元素个数服从泊松分布。负载因子 0.75 时,单个桶中出现 8 个元素的概率约为 6×10⁻⁸,这为"链表长度达到 8 才树化"的阈值提供了依据——正常情况下链表根本长不到 8,树化只是防御退化哈希的兜底。

3.4 链表与红黑树的转换阈值

常量 值 作用
TREEIFY_THRESHOLD 8 链表节点数达到该值时尝试树化
UNTREEIFY_THRESHOLD 6 红黑树节点数降到该值时退化回链表
MIN_TREEIFY_CAPACITY 64 允许树化的最小 table 容量

树化的完整条件:某桶的链表节点数达到 8,且 table 容量不小于 64。

若容量小于 64,treeifyBin 不做树化,而是执行一次扩容。原因是容量小时冲突的根因往往是表太短,扩容摊开元素比在短表上维持红黑树更划算。

退化条件是节点数降到 6,而不是与树化阈值相同的 8。留出 6 与 8 的差值是为了避免在边界反复转换:若两个阈值相同,一个桶稳定在 8 个节点并不断增删,就会在"链表 → 树 → 链表 → 树"之间抖动,每次转换都要重建结构。

树化的收益是把最坏情况下的桶内查找从 O(m)(m 为链表长度)降到 O(log m)。在哈希被恶意构造(哈希碰撞攻击)或大量键低位相同时,这个兜底决定了单次 get 是毫秒级还是微秒级。

3.5 扩容与 rehash 拆分

JDK 7 与 JDK 8 的扩容实现差异极大,且这个差异直接影响并发行为。

JDK 8 的拆分式扩容。因为新容量是旧容量的 2 倍,且下标用位与计算,元素的新下标只有两种可能:

旧容量 oldCap = 16,oldCap - 1 = 0000 1111
新容量 newCap = 32,newCap - 1 = 0001 1111
                              ↑ 多出的这一位决定去向

hash & oldCap == 0  →  新下标 = 旧下标
hash & oldCap != 0  →  新下标 = 旧下标 + oldCap

因此 resize 遍历每条旧链时,用 hash & oldCap 把节点分成两条子链:低位链(loHead/loTail)留在原下标,高位链(hiHead/hiTail)挂到 j + oldCap。整个过程不需要重新计算 hashCode(),只需一次位判断。

JDK 7 的头插法问题。JDK 7 使用头插法(新节点插在链表头部),扩容时链表顺序被反转。并发扩容下,两个线程同时搬运同一条链,可能让链表中出现指向自身的节点,形成环形链表,后续任何一次 get 命中该桶都会陷入死循环,CPU 占满且无法恢复。

JDK 8 改为尾插法(loTail.next = e),搬运过程中保持相对顺序,消除了成环条件。但 HashMap 依然是线程不安全的:并发 put 仍可能丢数据(两个线程同时写入同一空桶,后写覆盖先写)、size 计数错误、扩容期间读到 null。JDK 8 只消除了死循环这一最恶性后果,不代表可以并发使用。

扩容的总代价:容量从 16 增长到 n,需要 log₂(n/16) 次扩容,每次重新分配数组并搬运全部元素,累计工作量 O(n)。这是"大 Map 必须预设容量"的直接原因。

3.6 哈希冲突与键设计契约

Object 定义了两个必须成对遵守的方法:

public boolean equals(Object obj)   // 默认实现是 this == obj
public int hashCode()               // 默认实现通常由对象地址推导

契约内容:

  1. equals 相等 ⇒ hashCode 必须相等。这是强制的,违反它会让哈希容器彻底失效。
  2. hashCode 相等 ⇏ equals 相等。冲突是允许的,容器会用 equals 在同一桶内做二次比较。
  3. 对象参与 equals / hashCode 的状态在作为键期间不得变化。

HashMap 的查找过程是"先定位桶,再在桶内用 equals 逐个比较",两个方法的职责分工由此清晰:

情形 后果
equals 相等但 hashCode 不同 两个键落到不同桶,put 后 get 取不到,HashSet 去重失效,出现逻辑重复元素
hashCode 相等但 equals 不同 落在同一桶,冲突可接受,但大规模冲突会让桶退化为链表甚至红黑树,查找从 O(1) 劣化到 O(log n) / O(n)
恒返回常量 hashCode 所有元素挤入一个桶,HashMap 退化为链表,性能与 LinkedList 等同

3.7 可变对象作键的风险

若键对象在放入容器后被修改,且修改涉及参与 hashCode 计算的字段,就会出现"失联":

List<String> key = new ArrayList<>(List.of("a"));
Map<List<String>, String> map = new HashMap<>();
map.put(key, "value");

key.add("b");                                   // 修改了参与 hashCode 的字段
map.get(key);                                   // null:已经换了桶
map.remove(key);                                // 也删不掉,元素残留在旧桶

原因是在 put 时按下标 j 入桶,修改后 hashCode 变化,再次查找时算出的下标已不是 j。这个元素既取不出也删不掉,只能等到整体 clear 或重建 Map。

因此作键的对象应满足不可变(或至少在作键期间不修改参与哈希的状态)。Java 中天然满足的候选:

  • String、包装类(Integer、Long 等)、枚举、BigDecimal(但注意其 equals 对精度的要求)
  • record(字段按值参与 equals / hashCode,且不可变)
  • java.time 系列(LocalDate、Instant 等)

4. LinkedHashMap

4.1 双向链表维护顺序

LinkedHashMap 继承 HashMap,并复用其全部散列逻辑,只额外维护一条贯穿所有条目的双向链表:

public class LinkedHashMap<K,V> extends HashMap<K,V> {
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;    // 在原有 hash/key/value/next 之上增加两个指针
    }
    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;
    final boolean accessOrder;
}

HashMap 在关键节点预留了三个空实现的钩子方法:

void afterNodeAccess(Node<K,V> p)     { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p)     { }

LinkedHashMap 覆盖这三个钩子,在读取、插入、删除时同步维护 before/after 链。这是第 1 小节介绍的模板方法模式的又一次应用:父类定义流程,子类插入差异。

4.2 插入顺序与访问顺序

构造参数 accessOrder 决定链表的排序依据:

// 插入顺序(默认):链表顺序 = 元素首次插入的顺序
new LinkedHashMap<K, V>();

// 访问顺序:每次 get / put 命中的节点被移动到链表尾部
new LinkedHashMap<K, V>(16, 0.75f, true);
模式 链表顺序 典型用途
插入顺序(accessOrder = false) 按插入时间 需要可预期的迭代顺序(配置项、字段映射)
访问顺序(accessOrder = true) 按最近访问时间,头部最旧、尾部最新 LRU 缓存

访问顺序模式下,get 会修改链表结构(并递增 modCount),因此在迭代过程中调用 get 同样可能触发并发修改异常。这一点与普通 HashMap 的直觉不同。

4.3 removeEldestEntry 与 LRU

afterNodeInsertion 在插入后调用 removeEldestEntry,默认返回 false(不删除):

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

重写该方法即可得到容量受限的 LRU 缓存:

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

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

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;           // 超出上限时淘汰链表头部(最久未访问)
    }
}

淘汰发生在链表头部,即最久未被 get 或 put 命中的条目,这正是 LRU(Least Recently Used)的定义。容量上限由 maxSize 保证,因此该 Map 的条目数不会无限增长——这是它与普通 HashMap 做缓存时最关键的区别。

需要说明的边界:

  • 该实现非线程安全,并发场景需要外部加锁,或使用专门的缓存库(Caffeine、Guava Cache)以获得分段并发、过期策略与统计能力
  • 淘汰策略只有 LRU,没有 TTL、LFU 等
  • 迭代期间调用 get 会改变链表结构,需注意 4.2 提到的 modCount 问题

5. TreeMap 与 Set 系列

5.1 红黑树与有序性

TreeMap 的底层是红黑树——一种自平衡二叉搜索树,满足五条性质:

  1. 每个节点是红色或黑色
  2. 根节点是黑色
  3. 每个叶子节点(NIL)是黑色
  4. 红色节点的两个子节点都是黑色(不存在连续的红节点)
  5. 从任一节点到其所有叶子的路径包含相同数量的黑节点

性质 4 与性质 5 共同保证最长路径不超过最短路径的两倍,因此树高始终为 O(log n)。插入和删除通过旋转(左旋/右旋)与重新着色恢复平衡。

操作 复杂度 说明
get / put / remove O(log n) 树高保证
firstKey / lastKey O(log n) 沿最左/最右路径
ceilingKey / floorKey O(log n) 邻居查询
headMap / tailMap / subMap O(log n) 返回范围视图
顺序遍历 O(n) 中序遍历即有序序列

相比 HashMap 的 O(1),TreeMap 牺牲了常数级的查找速度,换来有序性与范围查询能力。当需求包含"按键排序输出"、"取某个区间内的键"、"找最接近的键"时,HashMap 无法替代。

5.2 比较器与自然序

TreeMap 不依赖 hashCode,而依赖比较:

// 自然序:键必须实现 Comparable
Map<String, Integer> natural = new TreeMap<>();

// 自定义序:传入 Comparator
Map<String, Integer> custom = new TreeMap<>(Comparator.reverseOrder());
Map<String, Integer> byLength = new TreeMap<>(Comparator.comparingInt(String::length));

两个必须注意的语义差异:

  1. 比较结果为 0 即视为同一个键。TreeMap 用 compare 的结果判断键的相等性,不使用 equals。若 Comparator 与 equals 不一致(例如按字符串长度比较),两个 equals 返回 false 的键会互相覆盖。
  2. 键必须可比较。既未实现 Comparable、构造时也未传入 Comparator 时,第一次 put 抛出 ClassCastException。

违反一致性契约还会破坏 Map 接口的 equals 语义(Map.equals 基于 entrySet 的相等性,而 TreeMap 的 keySet() 又依赖比较结果),这是 SortedMap 文档中明确警示的边界。

5.3 Set 系列对 Map 的依赖

Set 的三个常用实现都不是独立的数据结构,而是对同名 Map 的薄封装。

HashSet:内部持有一个 HashMap,元素充当键,值统一填充一个静态哨兵对象。

public class HashSet<E> extends AbstractSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();   // 全局共享的占位值

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;    // 返回 null 表示此前不存在
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

值使用全局共享的同一个 PRESENT 对象,不随元素数量增长而增加内存。因此 HashSet 的单元素开销与 HashMap 完全一致(多出的只是一个引用,而该引用位在 HashMap.Node 中本就存在)。

由此可推出 HashSet 的全部性能特征与陷阱:

  • 增删查 O(1),与 HashMap 相同
  • 去重依赖元素的 equals / hashCode,契约被破坏则去重失效
  • 迭代顺序与 HashMap 一样不可预测
  • 底层 HashMap 会扩容,元素多时应预设容量

LinkedHashSet:HashSet 提供了一个包级构造方法 HashSet(int initialCapacity, float loadFactor, boolean dummy),内部改用 LinkedHashMap 作为承载容器。LinkedHashSet 构造时传入 true 触发该分支,从而获得保持插入顺序的迭代能力,代价是每个元素多两个链表指针。

TreeSet:内部持有 NavigableMap(实际是 TreeMap),同样以元素为键、PRESENT 为值。

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E> {
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();
}

因此 TreeSet 的有序性、比较器语义、键必须可比较的要求,全部继承自 TreeMap。

Set 实现 底层容器 迭代顺序 单元素额外开销
HashSet HashMap 不可预测 哈希槽位 + 链表/树指针
LinkedHashSet LinkedHashMap 插入顺序 上述 + 两个链表指针
TreeSet TreeMap 排序顺序 红黑树节点(含颜色、左右子、父指针)

6. 迭代器与视图

6.1 迭代器接口

Collection 继承 Iterable,Iterable.iterator() 返回 Iterator:

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() { throw new UnsupportedOperationException(); }
    default void forEachRemaining(Consumer<? super E> action) { ... }
}

List 额外提供 ListIterator,支持双向遍历、set(替换当前元素)与 add(在当前元素前插入)。这是链表类实现高效遍历的基础——AbstractSequentialList 的 get(i) 就是通过 listIterator(i) 实现的。

迭代器是有状态的游标:它持有当前位置,并与容器结构绑定。这决定了它的生命周期语义。

6.2 fail-fast 机制的原理

ArrayList、HashMap 等类维护一个 modCount 字段,记录结构性修改的次数。结构性修改指改变元素数量或内部结构的操作(add、remove、clear、扩容搬运),而 set(i, e) 这类只替换元素值的操作不算。

迭代器在创建时记录当时的 modCount 作为 expectedModCount,每次操作都校验:

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

于是出现以下典型现象:

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    if ("b".equals(s)) {
        list.remove(s);     // 结构性修改 → modCount++
    }                    // 下一次迭代器 next()/hasNext() 校验失败
}                        // 抛 ConcurrentModificationException

需要澄清三点:

  1. ConcurrentModificationException 的名字具有误导性。它在单线程的遍历中删除元素同样会抛出。"并发修改"指的是"迭代期间修改",与多线程无关。
  2. fail-fast 是尽力而为的检测机制,不是并发安全保证。它只比较计数字段,不保证一定能检出:若在两次校验之间发生了偶数次成对的结构性修改(理论上),或修改发生后迭代器刚好结束循环,异常就不会出现。因此不能依赖它来发现并发 bug。
  3. modCount 不是 volatile。多线程场景下它本身也存在可见性问题,异常能否抛出同样不确定。

6.3 fail-safe 的取舍

与之相对的是 fail-safe(弱一致)迭代器,代表实现是 CopyOnWriteArrayList 与 ConcurrentHashMap。

特性 fail-fast fail-safe
代表实现 ArrayList、HashMap、TreeMap CopyOnWriteArrayList、ConcurrentHashMap
检测机制 比较 modCount 不检测
迭代期间修改 抛 ConcurrentModificationException 不抛
数据视图 强一致(要么完整,要么中止) 快照或弱一致(可能读到旧值,可能看不到新值)
代价 不支持迭代期间修改 快照复制开销,或"看不到最新数据"的语义

ConcurrentHashMap 的迭代器基于弱一致性:不保证反映迭代开始之后的修改,也不保证所有元素都被遍历到。好处是并发吞吐高、不需要加锁即可迭代。

取舍原则:单线程场景用 fail-fast 实现以获得确定的语义与最低开销;并发场景用并发容器并接受弱一致性;需要"迭代期间修改且立刻生效"时,应先收集待修改项,在遍历结束后统一执行。

6.4 遍历中删除的正确做法

做法 是否可行 说明
for 增强循环中 list.remove(o) 不可行 抛 ConcurrentModificationException
显式 Iterator + it.remove() 可行 Itr.remove 会同步更新 expectedModCount,是最经典的做法
list.removeIf(predicate) 可行 JDK 8+,内部使用迭代器实现,语义清晰
Collection.removeAll(sub) 可行 批量删除,内部依赖 contains,注意复杂度
倒序索引 for (int i = size - 1; i >= 0; i--) 可行 只适用于 List,删除后前面的下标不受影响
Stream.filter(...).collect(...) 可行 生成新集合,原集合不变

Iterator.remove() 的语义是"删除 next() 最近返回的那个元素",因此必须先调用 next() 再调用 remove(),否则抛 IllegalStateException。

6.5 视图的语义与陷阱

subList 是视图,不是拷贝:

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
List<Integer> sub = list.subList(1, 3);   // [2, 3]
sub.set(0, 99);                            // 原 list 变为 [1, 99, 3, 4, 5]
list.add(6);                               // 结构性修改
sub.get(0);                                // ConcurrentModificationException

ArrayList.subList 返回内部类 SubList,它持有原列表引用与偏移量。由此产生三个陷阱:

  1. 对子列表的修改直接作用于原列表
  2. 原列表发生结构性修改后,再操作子列表抛 ConcurrentModificationException(SubList 同样校验 modCount)
  3. SubList 持有原列表引用,长期保存会导致原列表无法回收,是内存泄漏的常见来源

需要独立副本时应显式拷贝:new ArrayList<>(list.subList(1, 3))。

keySet / values / entrySet 也是视图:

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);

Set<String> keys = map.keySet();
keys.remove("a");          // 直接删除 map 中的条目
map.put("b", 2);
keys.size();               // 1,视图始终反映 map 的最新状态

keys.add("c");             // UnsupportedOperationException:视图不支持添加

视图上的删除会反映到原 Map,但视图不允许添加(因为添加缺少值)。

Map.Entry.setValue 是迭代中唯一允许的修改:entrySet() 迭代时调用 entry.setValue(v) 会写回 Map,且不改变 modCount,因此不会抛异常。

其他易混淆的"看起来像集合"的对象:

创建方式 类型 可变性
Arrays.asList(array) Arrays.ArrayList 固定大小视图,set 可写回原数组,add / remove 抛 UnsupportedOperationException
List.of(...)(Java 9+) 真正不可变 任何修改抛 UnsupportedOperationException,且不接受 null
Collections.unmodifiableList(list) 只读视图 自身不可改,但原列表的变化会透出
Collections.singletonList(x) 不可变单元素 不可修改
list.subList(a, b) 视图 可修改,作用于原列表

区分"不可变"与"只读视图"很重要:unmodifiableList 只是拒绝写操作,原列表仍可能被其他持有者修改,不构成真正的不可变保障。

7. 遍历与性能

7.1 三种遍历方式的差异

// 方式一:索引 for
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

// 方式二:增强 for(编译为迭代器)
for (String s : list) {
    process(s);
}

// 方式三:Stream
list.stream().forEach(this::process);
方式 对 ArrayList 对 LinkedList 备注
索引 for 最快,无迭代器对象、无 modCount 校验 极慢,每次 get(i) 都从头部或尾部线性定位,整体 O(n²) 只应作用于支持随机访问的 List
增强 for 与索引 for 接近,多一个迭代器对象 快,沿 next 指针前进,整体 O(n) 通用选择
Stream.forEach 略慢,因管道对象与 Lambda 调用开销 同左 有转换/聚合逻辑时才体现价值

关于 LinkedList 的性能陷阱值得单独强调:索引 for 在 LinkedList 上的复杂度是 O(n²)。100 万元素的列表会产生约 5×10¹¹ 次指针跳转,表现为进程 CPU 占满、接口长时间无响应。这是"看起来无害的循环写法"造成的典型事故。

ArrayList 的迭代器分配通常不会成为瓶颈:逃逸分析在多数情况下能把它标量化消除(相关机制见 类加载机制与执行引擎)。

7.2 集合初始容量对扩容次数的影响

扩容的代价由"次数"和"每次搬运量"共同决定。预设容量能把两者都降为零。

// ArrayList:已知最终元素数 n
List<String> list = new ArrayList<>(n);

// 若不确定但知道量级,给一个上界估计
List<String> list2 = new ArrayList<>(1024);

估算方式:

  • ArrayList:容量即为元素数组长度,直接按预期元素数设置即可
  • HashMap / HashSet:容量必须满足 元素数 ≤ 容量 × 负载因子,因此需要的容量是 元素数 / 0.75,并向上取整到 2 的幂
// 预期 1000 个元素:1000 / 0.75 ≈ 1334 → 向上取整到 2 的幂 = 2048
Map<String, Integer> map = new HashMap<>(2048);

若容量计算不准,HashMap 的 putAll 与带 Map 参数的构造方法有内部优化(一次性扩到足够容量),批量导入时优先使用:

Map<String, Integer> map = new HashMap<>(sourceMap);   // 内部按 sourceMap 规模计算容量

反过来,过大的初始容量同样是浪费:HashMap 的 table 数组按容量一次性分配引用槽位,容量 1 万的空 Map 也要占用约 40 KB 的数组。

7.3 集合选型的复杂度总表

实现 get add(尾部/默认) 中间插入 contains 迭代顺序
ArrayList O(1) 均摊 O(1) O(n) O(n) 插入顺序
LinkedList O(n) O(1) O(n) 定位 + O(1) 链接 O(n) 插入顺序
ArrayDeque — O(1) — O(n) 队列顺序
HashSet — O(1) — O(1) 不可预测
LinkedHashSet — O(1) — O(1) 插入顺序
TreeSet — O(log n) — O(log n) 排序顺序
HashMap O(1) O(1) — O(1) 不可预测
LinkedHashMap O(1) O(1) — O(1) 插入/访问顺序
TreeMap O(log n) O(log n) — O(log n) 排序顺序
PriorityQueue — O(log n) — O(n) 堆序(非完全有序)

表中的 O(1) 均为均摊复杂度,且是哈希分布良好的前提下的期望值。

8. 哈希与相等的契约

8.1 equals 与 hashCode 不一致的后果

契约的强制方向只有一个:equals 为真则 hashCode 必须相同。违反它的症状是"元素取不出、删不掉、去重失败"。

// 只重写 equals,不重写 hashCode 的错误实现
class BadKey {
    private final String id;

    BadKey(String id) { this.id = id; }

    @Override
    public boolean equals(Object o) {
        return o instanceof BadKey && id.equals(((BadKey) o).id);
    }
    // 缺少 hashCode 重写 → 使用 Object 的身份哈希
}

Map<BadKey, String> map = new HashMap<>();
map.put(new BadKey("A"), "v1");
map.get(new BadKey("A"));    // null:两个对象身份哈希不同,落在不同桶
map.size();                  // 1;再 put 同 id 的对象会得到 size = 2

反方向的"hashCode 相同但 equals 不同"是允许的,代价只是冲突。但在大规模数据下恶意构造的冲突会让性能雪崩,因此哈希容器用红黑树兜底(见 3.4)。

8.2 正确实现的双字段写法

public final class OrderKey {
    private final String tenantId;
    private final long orderId;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;                       // 同一引用,快速路径
        if (!(o instanceof OrderKey other)) return false; // 类型检查(Java 16+ 模式匹配)
        return orderId == other.orderId
                && Objects.equals(tenantId, other.tenantId);
    }

    @Override
    public int hashCode() {
        return Objects.hash(tenantId, orderId);
    }
}

要点:

  • equals 必须自反、对称、传递、一致(多次调用结果相同),且 x.equals(null) 恒为 false
  • 字段比较用 Objects.equals(容忍 null),基本类型用 ==(double / float 用 Double.compare)
  • Objects.hash(...) 会做装箱并分配一个 Object[],在极端热点路径上可以手工展开为 31 * h1 + h2 形式以省掉这两个分配
  • 优先使用 record,编译器自动生成一致的 equals / hashCode / toString

8.3 字符串与包装类的实现要点

String.hashCode 采用多项式滚动哈希:

public int hashCode() {
    int h = hash;                    // 缓存字段,只计算一次
    if (h == 0 && !hashIsZero) {
        for (byte v : value) {
            h = 31 * h + (v & 0xff);
        }
        hash = h;
    }
    return h;
}

选 31 的原因:31 是奇素数(乘奇数不会让溢出信息丢失,且能减少冲突),且 31 * h 可以被 JIT 优化为 (h << 5) - h。

String 的不可变性保证了 hashCode 在对象生命周期内恒定,因此 String 是可靠的 HashMap 键,也是 Java 中最常见的键类型。

包装类的 hashCode 各有实现:

类型 hashCode 说明
Integer value 本身 直接返回内部 int
Long (int)(value ^ (value >>> 32)) 高低 32 位异或
Double 基于 IEEE 754 位模式 通过 doubleToLongBits 后取 Long 的哈希
Boolean 1231 / 1237 两个常量

包装类的 equals 按值比较,与 hashCode 一致,因此可以作为键。需要区分的两个相邻问题:

  • == 比较的陷阱:Integer 缓存了 −128~127 的值(Integer.valueOf 走缓存),此范围内 == 为 true,范围外为 false。这只影响 ==,不影响 HashMap(HashMap 用 equals 比较键)。自动装箱的机制与缓存范围见 数据类型系统
  • 数组不可作为键:数组的 equals / hashCode 继承自 Object,是身份语义。两个内容相同的数组不相等,用 int[] 作键的结果是每个数组都是独立键。需要按内容作键时应包装为 String、List<Integer> 或自定义的不可变包装类型

三、实现

1. 选型决策表

按访问模式与并发需求给出推荐实现。增删改查的 API 用法见 Java 完整手册 第四章。

按访问模式选择

访问模式 推荐实现 理由与排除项
随机访问为主,尾部追加 ArrayList 下标寻址 O(1),缓存局部性好,迭代快;排除 LinkedList(get(i) 为 O(n))
两端频繁增删(队列/栈) ArrayDeque 环形数组,无节点开销,比 LinkedList 更快;需要 List 语义时才用 LinkedList
频繁在任意位置插入删除,且用迭代器顺序遍历 LinkedList 迭代器遍历中删除是 O(1);注意不要用 get(i) 随机访问
需要去重 HashSet O(1) 的 add / contains;要求元素正确实现 equals / hashCode
去重且需要固定迭代顺序 LinkedHashSet 插入顺序稳定,便于测试与展示;每个元素多两个指针
去重且需要排序或范围查询 TreeSet 红黑树有序,支持 first / ceiling / subSet;键必须可比较
键值映射,无须顺序 HashMap 期望 O(1) 查找;必须预设容量以抑制扩容
键值映射且需要顺序 LinkedHashMap 插入顺序可预期;accessOrder = true 时天然支持 LRU
键值映射且需要排序/范围查询 TreeMap headMap / tailMap / ceilingKey 等导航能力
按优先级出队 PriorityQueue 二叉堆,offer / poll 为 O(log n);注意它并非完全有序
只读的常量集合 List.of / Map.of(Java 9+) 真正不可变,可安全共享;不接受 null

按并发需求选择

并发需求 推荐实现 代价
读多写极少 CopyOnWriteArrayList / CopyOnWriteArraySet 单次写全量复制 O(n),内存峰值 2 倍
高并发键值映射 ConcurrentHashMap 无全表锁,但复合操作仍需用原子方法
高并发有序映射 ConcurrentSkipListMap 跳表实现,O(log n),比红黑树实现更易并发化
生产者-消费者队列 ArrayBlockingQueue / LinkedBlockingQueue 有界队列提供背压;无界队列有 OOM 风险
需要全表锁的兼容场景 Collections.synchronizedXxx 整表串行,且迭代仍需手工加锁
单线程或已外部加锁 普通非并发实现 性能最优

并发容器的实现细节(ConcurrentHashMap 的桶级锁与扩容协助、CopyOnWriteArrayList 的 volatile 发布)见 Java 并发编程。

2. 常见陷阱与修复

陷阱一:遍历中直接修改集合

// 错误:抛 ConcurrentModificationException
for (String s : list) {
    if (needRemove(s)) list.remove(s);
}

修复:使用 removeIf(推荐)或显式迭代器。

list.removeIf(this::needRemove);

// 或
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (needRemove(it.next())) it.remove();
}

若必须使用 Java 8 之前的写法,注意 Map 的删除要走 entrySet().iterator()。

陷阱二:扩容导致的内存峰值

现象:给已有几十万元素的 ArrayList 追加数据时,出现堆内存迅速上涨甚至 OOM。原因是旧数组与新数组同时存在,峰值达到 2.5 倍。

修复:

  • 能估算规模时预设容量:new ArrayList<>(expectedSize)
  • 无法估算时使用 ensureCapacity 在批量追加前一次性扩到足够容量,把多次扩容合并为一次
  • 超大集合考虑分片处理,或改用流式处理避免整体驻留

陷阱三:大 Map 未预设容量

现象:循环 put 十万条数据,耗时明显高于预期,GC 日志显示多次 Young GC。

原因:HashMap 从 16 开始,经 17 次扩容到达 262144 的容量,每次扩容都要重新分配数组并搬运全部元素,累计搬运量约为元素总数的两倍。

修复:new HashMap<>(expectedSize / 0.75 + 1),或直接使用 putAll / 带 Map 参数的构造方法。JDK 19+ 提供 HashMap.newHashMap(numMappings) 静态工厂,自动完成上述估算。

陷阱四:可变对象作键后失联

现象:map.get(key) 返回 null,map.remove(key) 无效,map.size() 与预期不符。

原因:键的 hashCode 在入桶后被改变,导致按新哈希找不到旧桶。

修复:用不可变对象作键;若必须使用可变对象,把参与 hashCode 的字段在作键期间冻结在不可变的包装类型里(如把 List 转成 String 或用 record 包装)。

陷阱五:LinkedList 的随机访问

现象:对 LinkedList 使用索引遍历,CPU 占满、响应超时。

原因:get(i) 每次线性定位,整体退化到 O(n²)。

修复:改用增强 for / 迭代器;若必须按下标访问,换成 ArrayList。

陷阱六:把 Arrays.asList 或 subList 当独立集合使用

List<String> l1 = Arrays.asList("a", "b");
l1.add("c");     // UnsupportedOperationException(固定大小视图)

List<String> l2 = list.subList(0, 5);
list.add("x");
l2.get(0);       // ConcurrentModificationException(原列表已结构变化)

修复:需要独立集合时显式拷贝 new ArrayList<>(...)。

陷阱七:依赖 HashMap 的迭代顺序

现象:本地测试遍历顺序稳定,上线后顺序变化;基于顺序写下的逻辑偶发失败。

原因:HashMap 的迭代顺序由容量、哈希值与插入历史共同决定,扩容会改变顺序,且不同 JDK 版本实现不同。

修复:需要稳定顺序时使用 LinkedHashMap 或 TreeMap;测试断言不要依赖 HashMap 的顺序。

陷阱八:用 == 比较集合元素

Set<Integer> set = new HashSet<>();
set.add(1000);
set.contains(1000);     // true,contains 内部用 equals
Integer a = 1000, b = 1000;
System.out.println(a == b);   // false,超出 Integer 缓存范围

contains 与 equals 不受缓存影响,但 == 会。修改变量声明类型为 int 或统一使用 equals。

3. 内存占用估算

3.1 单元素开销差异

在 64 位 JVM 开启压缩指针(堆小于约 32 GB 时默认开启)的条件下,引用宽度为 4 字节,对象头为 12 字节,数组对象额外有 4 字节长度字段,对象总大小按 8 字节对齐。

对象头构成、字段重排与指针压缩的机制,以及大对象(含 G1 的 Humongous 对象)的判定与晋升路径,见 JVM 内存结构与垃圾回收。

实现 单元素结构开销 100 万元素的容器结构占用
ArrayList 数组中的 1 个引用 = 4 字节 数组头 16 + 4 × 100 万 ≈ 4 MB
LinkedList 1 个 Node 对象 = 12(头)+ 4(item)+ 4(next)+ 4(prev)= 24 字节 ≈ 24 MB
HashMap 1 个 Node = 12(头)+ 4(hash)+ 4(key)+ 4(value)+ 4(next)= 28 → 对齐 32 字节;table 槽位 4 字节 节点 ≈ 32 MB + table ≈ 5 MB(容量 2²¹)
HashMap(树化节点) TreeNode ≈ 48 字节 仅在冲突严重的桶中出现
TreeMap 1 个 Entry ≈ 12 + 4(key)+ 4(value)+ 4(left)+ 4(right)+ 4(parent)+ 1(color)≈ 45 → 对齐 48 字节 ≈ 48 MB
ArrayDeque 环形数组 1 个引用 = 4 字节 ≈ 4 MB

表中数值仅统计容器结构本身,不包含键、值对象自身的内存。实际的键值对象往往才是占用主体:一个含 5 个 String 字段的实体对象通常超过 100 字节。

几个可直接用于判断的结论:

  • LinkedList 与 TreeMap 的每元素结构开销是 ArrayList 的 6 至 12 倍
  • HashMap 因负载因子 0.75,table 中有约 1/3 的槽位是空的,这部分空间按容量计算而非按元素数计算
  • 元素数量巨大且键是简单类型时,装箱本身的开销可能超过容器结构开销(每个 Integer 对象 16 字节,而 int 只有 4 字节)

3.2 主机内存视角

JVM 堆并不是"直接持有物理内存",而是通过 mmap 向内核申请的一块虚拟地址区域;只有被实际访问过的页才会驻留物理内存并计入 RSS。这带来两个要点:

  1. 容器结构的膨胀最终体现为 RSS 增长。100 万个 LinkedList 节点会在堆上散落 100 万个 24 字节的对象,这些对象真实触碰了物理页,RSS 随之上升。在 cgroup 内存限制下(容器编排平台的 limits.memory),RSS 上涨触顶会触发 OOM Killer 直接杀掉进程,表现为"没有堆溢出日志的进程消失"。
  2. 稀疏的大数组会按页真实占用内存。ArrayList 一次性分配 100 万容量的数组时,即使只填了 10 个元素,这 4 MB 的数组也会因写入而触碰页,实际占用物理内存。因此"预设过大容量"并不是零成本的优化。

虚拟内存、页、缺页中断、页缓存与 cgroup 的关系见 内存管理。

3.3 大批量数据的取舍

场景 取舍建议
数十万以内的对象集合 优先 ArrayList / HashMap,可读性优先,不做微观优化
百万级以上的简单数值集合 考虑用数组或 int[] 替代 List<Integer>,消除装箱与容器结构开销
需要去重的超大规模字符串集合 HashSet 是必须的,但应预设容量并评估键对象本身的内存
只需要顺序遍历的处理流程 用流式处理(逐条读出、处理、丢弃),避免整体驻留
需要长期驻留的缓存 不要用裸 HashMap,改用带容量上限与淘汰策略的缓存组件,并在容量上做显式限制

4. 与并发的配合

4.1 集合的线程安全性

实现 线程安全 说明
ArrayList / LinkedList 否 并发 add 可能丢数据、size 计数错误、读到中间态
HashMap 否 JDK 8 已消除扩容死循环,但仍会丢数据与读到 null
TreeMap / LinkedHashMap 否 结构维护无同步
Vector / Hashtable 是(全表锁) 方法级 synchronized,并发下串行化,已不推荐
Collections.synchronizedXxx 是(全表锁) 单方法原子,迭代时仍需手工同步
ConcurrentHashMap 是 CAS + 桶级锁 + 扩容协助,读操作基本无锁
CopyOnWriteArrayList 是 写加锁 + 全量复制,读无锁
ConcurrentSkipListMap / Set 是 跳表,无锁算法
阻塞队列系列 是 内置 put / take 的阻塞语义

关键区分:并发容器保证单个方法的原子性,不保证复合操作的原子性。

// 错误:get-then-put 之间存在竞态
if (!map.containsKey(key)) {
    map.put(key, compute(key));     // 两个线程可能都进来,重复计算并覆盖
}

// 正确:使用原子的复合方法(内部对同一个桶加锁)
map.computeIfAbsent(key, this::compute);
map.merge(key, 1, Integer::sum);
map.putIfAbsent(key, value);

Collections.synchronizedMap 的迭代必须手工加锁,因为迭代是多次方法调用的组合:

Map<String, Integer> map = Collections.synchronizedMap(new HashMap<>());
synchronized (map) {                     // 必须显式同步,否则抛 CME
    for (Map.Entry<String, Integer> e : map.entrySet()) {
        // ...
    }
}

4.2 弱一致迭代的语义

ConcurrentHashMap 的迭代器不抛 ConcurrentModificationException,但也不保证"看到全部最新数据"。它按桶逐个扫描,扫描过程中发生的修改可能被看到也可能不被看到。这被称为弱一致性。

对多数统计类、监控类场景,弱一致完全够用。若业务要求"迭代期间的修改必须精确可见",则并发容器也给不了这个保证,需要业务层加锁或改用快照语义。

集合与并发的关系涉及 volatile 发布、CAS、AQS、happen-before 规则等底层机制,详见 Java 并发编程。CopyOnWriteArrayList 的 volatile 数组实现、ConcurrentHashMap 的分段与桶级锁演进,是理解"无锁读 + 有限锁写"设计思路的入口。

5. 排查手段

5.1 从内存快照定位集合膨胀

按由轻到重的顺序使用以下手段:

# 1. 类直方图:按实例数与占用粗略排序,快速判断哪个集合类异常(会触发一次 Full GC)
jcmd <pid> GC.class_histogram

# 2. 堆转储:导出完整快照供离线分析
jcmd <pid> GC.heap_dump /tmp/heap.hprof

# 3. 查看堆与 GC 概况
jcmd <pid> GC.heap_info

高危:jcmd GC.heap_dump 与 jmap -dump 会暂停应用(Stop-The-World),转储期间进程响应停滞;快照文件大小可达堆的 1 倍以上,可能占满磁盘。影响范围:该 JVM 的所有在线请求。回滚方式:无法回滚已产生的停顿,只能在低峰期执行并预先确认磁盘剩余空间;若需避免停顿,改用 -XX:+HeapDumpOnOutOfMemoryError 在 OOM 时自动落盘,或使用支持并发导出的商业工具。

离线分析(Eclipse MAT、JProfiler、VisualVM)时的定位路径:

  1. 打开 支配树(Dominator Tree),按 Retained Size 降序排列
  2. 查找 java.util.HashMap$Node[]、java.lang.Object[]、java.util.HashMap$Node、java.util.LinkedHashMap$Entry 等数组与节点类
  3. 从大对象向下追溯引用链(Path to GC Roots,排除弱引用),找到持有者字段,定位业务代码位置
  4. 对比两次快照的增量(MAT 的 Compare Basket),锁定持续增长的集合

堆转储的获取方式与触发时机、保留大小与支配树的口径、到 GC Roots 引用链的判读方法,见 JVM 内存结构与垃圾回收 的堆转储分析一节。

判断标准:

  • 某个 Node[] 数组的 Retained Size 占比异常高 → 该 Map 元素过多
  • 同一个集合类的实例数很多(而非单个实例很大)→ 存在按请求/按租户维度累积的结构
  • Entry 数量远超预期 → 可能因 equals / hashCode 契约被破坏导致重复键堆积

5.2 代码级定位大集合的来源

排查方向 具体做法
静态缓存 检索 static 修饰的 Map / List 字段,检查是否有容量上限与淘汰策略
无界累积 检索 new HashMap<>() 后放入长生命周期容器的位置;检索 add 在循环中无上限的场景
全量查询 检索 selectList / findAll / list() 类调用,确认是否有分页或 limit
分组聚合 检索 Collectors.groupingBy / Collectors.toMap,评估分组键的基数(高基数分组会产生大量小集合)
监听器列表 检索 addListener / register 调用,确认是否有对应的注销路径
线程局部变量 检索 ThreadLocal 持有集合的场景,线程池复用线程时该集合不会被释放
迭代器未释放 检索长期持有的 subList 结果与 Iterator 引用

5.3 集合相关故障的快速判断表

现象 可能原因 验证方式
抛 ConcurrentModificationException 遍历中修改集合;subList 在原列表变化后被使用 检查循环体与 subList 生命周期
get 返回 null 但 containsKey 曾为 true 键对象被修改,或 hashCode 不稳定 打印键的 hashCode 前后对比
Set 中出现"重复"元素 equals / hashCode 未同时重写或实现不一致 单测断言两个疑似重复元素的 equals 与 hashCode
堆内存持续上涨不回落 静态 Map 无上限;ThreadLocal 持有集合;监听器只注册不注销 类直方图 + 支配树
单次查询耗时与数据量平方相关 LinkedList 索引遍历;List.contains 嵌套循环 检查嵌套遍历与容器类型
UnsupportedOperationException 使用了 Arrays.asList、List.of、unmodifiableXxx 或 keySet().add 检查集合的创建方式
排序结果与 equals 不一致 Comparator 与 equals 不一致(TreeMap / TreeSet) 检查比较器实现

四、总结

集合框架的本质是对数组局限的系统性补偿:用接口解决统一抽象,用骨架类与工具类解决算法复用,用多套实现解决性能可控。

实现层面的核心事实可以归纳为几条主线:

  • List 的两极。ArrayList 用连续数组换随机访问,代价是中间插入的搬移与 1.5 倍扩容时的 2.5 倍内存峰值;LinkedList 用节点指针换两端操作,代价是每元素约 24 字节的结构开销与极差的缓存局部性。"链表插入快"只在已持有节点引用时成立,通过下标操作依然是 O(n)。
  • HashMap 的三层结构。数组提供 O(1) 的桶定位,链表处理冲突,红黑树在链表达到 8 且容量不小于 64 时兜底。2 的幂容量让取模变为位与、让扩容拆分只需判断一个位;0.75 的负载因子在空间与冲突之间取折中。JDK 8 的尾插法消除了 JDK 7 的扩容成环问题,但没有让 HashMap 变得线程安全。
  • 顺序是额外的结构。LinkedHashMap 在 HashMap 之上加一条双向链表,靠父类预留的三个钩子维护;removeEldestEntry 把这个结构变成 LRU。TreeMap 用红黑树换来有序性与范围查询,代价是比较操作与 O(log n) 的常数,且"比较结果为 0 即为同一个键"这条语义与 equals 并不等价。
  • Set 依附于 Map。HashSet、LinkedHashSet、TreeSet 分别是 HashMap、LinkedHashMap、TreeMap 的薄封装,元素作键、PRESENT 作值。Set 的选择等价于"选择哪种 Map"。
  • 迭代器是契约的执行者。modCount 校验带来的 ConcurrentModificationException 是"迭代期间修改"的信号,与线程无关,且只是尽力而为的检测。视图(subList、keySet、entrySet、unmodifiableXxx)不是拷贝,语义混淆是空指针与异常的常见来源。
  • 哈希契约只有一条强制方向。equals 相等则 hashCode 必须相等,反之不要求。违反它的代价是元素取不出、删不掉、去重失效;键对象在作键期间不可修改。

工程层面的结论同样收敛:

  • 容量预设是性价比最高的优化。它同时削掉扩容的时间开销与瞬时内存峰值,ArrayList 按元素数设置,HashMap 按 元素数 / 0.75 向上取整到 2 的幂。
  • 内存占用要按结构估算而非按元素数估算。LinkedList 与 TreeMap 的每元素结构开销是 ArrayList 的 6 至 12 倍,且堆内存最终要通过页的形式体现为主机 RSS,在容器内存限制下会直接表现为进程被杀。
  • 并发场景不要试图给普通集合加锁了事。Collections.synchronizedXxx 的迭代仍需手工同步;应改用 ConcurrentHashMap、CopyOnWriteArrayList 等并发容器,并注意复合操作必须走 computeIfAbsent / merge 这类原子方法。
  • 排查从两个方向入手。自顶向下用堆转储与支配树定位膨胀的集合实例;自底向上检索静态缓存、全量查询、无上限累积等代码模式定位来源。

集合框架的每一处设计都是明确取舍的结果:时间与空间、有序性与常数开销、迭代安全和并发吞吐。掌握这些取舍的边界,比记住 API 列表更能决定代码在数据量增长后的表现。