一、起源:数组的局限
数组是 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 时进入特殊处理分支。
扩容的代价有两层:
- 时间代价:
Arrays.copyOf内部是System.arraycopy,把旧数组的全部引用复制到新数组,单次为 O(n)。add到 n 个元素,累计复制量约为最终元素数的常数倍(1.5 倍增长下约为 2n 量级的引用复制)。因此尾部追加是均摊 O(1),而不是严格 O(1)。 - 空间代价(峰值):扩容瞬间,旧数组(容量 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 的幂有三个直接好处:
- 位运算替代取模。
hash % n需要整除指令,而hash & (n - 1)在 n 为 2 的幂时与取模等价,且是单条位运算指令。这是性能路径上的关键优化。 - 扩容拆分可以只判断一个位。扩容后容量翻倍,
length - 1多出一个高位 1。元素的新下标只能有两种结果:留在原下标,或移动到"原下标 + 旧容量"。判断依据就是hash & oldCapacity。详见 3.5。 - 元素分布更适合位运算下的散列。若容量含奇数因子(如 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() // 默认实现通常由对象地址推导
契约内容:
equals相等 ⇒hashCode必须相等。这是强制的,违反它会让哈希容器彻底失效。hashCode相等 ⇏equals相等。冲突是允许的,容器会用equals在同一桶内做二次比较。- 对象参与
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 的底层是红黑树——一种自平衡二叉搜索树,满足五条性质:
- 每个节点是红色或黑色
- 根节点是黑色
- 每个叶子节点(NIL)是黑色
- 红色节点的两个子节点都是黑色(不存在连续的红节点)
- 从任一节点到其所有叶子的路径包含相同数量的黑节点
性质 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));
两个必须注意的语义差异:
- 比较结果为 0 即视为同一个键。
TreeMap用compare的结果判断键的相等性,不使用equals。若Comparator与equals不一致(例如按字符串长度比较),两个equals返回false的键会互相覆盖。 - 键必须可比较。既未实现
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
需要澄清三点:
ConcurrentModificationException的名字具有误导性。它在单线程的遍历中删除元素同样会抛出。"并发修改"指的是"迭代期间修改",与多线程无关。- fail-fast 是尽力而为的检测机制,不是并发安全保证。它只比较计数字段,不保证一定能检出:若在两次校验之间发生了偶数次成对的结构性修改(理论上),或修改发生后迭代器刚好结束循环,异常就不会出现。因此不能依赖它来发现并发 bug。
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,它持有原列表引用与偏移量。由此产生三个陷阱:
- 对子列表的修改直接作用于原列表
- 原列表发生结构性修改后,再操作子列表抛
ConcurrentModificationException(SubList同样校验modCount) 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。这带来两个要点:
- 容器结构的膨胀最终体现为 RSS 增长。100 万个
LinkedList节点会在堆上散落 100 万个 24 字节的对象,这些对象真实触碰了物理页,RSS 随之上升。在 cgroup 内存限制下(容器编排平台的limits.memory),RSS 上涨触顶会触发 OOM Killer 直接杀掉进程,表现为"没有堆溢出日志的进程消失"。 - 稀疏的大数组会按页真实占用内存。
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)时的定位路径:
- 打开 支配树(Dominator Tree),按 Retained Size 降序排列
- 查找
java.util.HashMap$Node[]、java.lang.Object[]、java.util.HashMap$Node、java.util.LinkedHashMap$Entry等数组与节点类 - 从大对象向下追溯引用链(Path to GC Roots,排除弱引用),找到持有者字段,定位业务代码位置
- 对比两次快照的增量(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 列表更能决定代码在数据量增长后的表现。