集合系列

ArrayList源码解析

小细节：以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10

主要逻辑

ArrayList 底层由一个可变长度的数组 (elementData) 支撑；无参构造初始化为空数组，首次添加元素时会分配默认容量 10；每次扩容时，新的容量按照 oldCapacity + (oldCapacity >> 1) 计算（约为 1.5 倍），并通过 Arrays.copyOf（底层使用 System.arraycopy()）将旧数组复制到新数组；在扩容过程中，还会检查溢出并保证满足最小容量；这种扩容策略使得添加操作具有摊销常数时间复杂度。

初始容量与构造函数

无参构造

调用 new ArrayList<>() 时，内部的 elementData 被赋值为常量空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，此时容量为 0。
当第一次执行 add(E e) 时，通过 ensureCapacityInternal(1) 检测到当前容量不足，进而将容量提升至默认 DEFAULT_CAPACITY = 10，再执行后续操作。

有参构造

若使用 new ArrayList<>(initialCapacity) ，则直接在构造方法中按 initialCapacity 大小分配底层数组，跳过首次默认容量分配逻辑。
这样可以避免未预知扩容带来的多次数组复制。

扩容触发时机

每次向 ArrayList 添加元素时，都会调用 ensureExplicitCapacity(size + 1) 判断当前 size+1（我要放当前元素所需要的容量）是否超出 elementData.length（数组长度）；若超出则触发扩容。**
ensureCapacityInternal 会根据传入的最小容量（minCapacity，一般为 size+1）与当前容量（oldCapacity）关系，决定是否进行扩容；只有在 minCapacity - oldCapacity > 0 时才扩容，避免不必要的数组复制。

扩容算法

容量增长公式

Java 8（及以后）中，扩容时新容量通过以下公式计算：

java

int newCapacity = oldCapacity + (oldCapacity >> 1);

即在原容量基础上增加 ∼50%。

在更早的 Java 6 实现中，采用的是 (oldCapacity * 3)/2 + 1 的方式，效果与前者类似。

溢出与最小容量保证

若计算出的 newCapacity （要扩展的容量）小于 minCapacity （当前最小需要的容量），则扩容后的容量直接取 minCapacity；
如原数组为空且使用无参构造，则最终容量至少为 DEFAULT_CAPACITY = 10 ，以避免零容量数组引发频繁扩容；
当 newCapacity 大于 MAX_ARRAY_SIZE 即超过最大容量阈值时会进入 hugeCapacity 函数中，如果 minCapacity 大于 MAX_ARRAY_SIZE 会直接取整数最大值 Integer.MAX_VALUE ，否则取 MAX_ARRAY_SIZE**
如 minCapacity 超过 Integer.MAX_VALUE ，会抛出 OutOfMemoryError 以防止溢出。以上逻辑保障了容量既不过度浪费，也能满足当前需要。

扩容流程

计算最小需求：minCapacity = size + 1。
检查是否空数组：若底层为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则将 minCapacity 与 DEFAULT_CAPACITY（10）比较，取较大者作为新的最小容量。
调用 grow(minCapacity)：
- 获取 oldCapacity = elementData.length。
- 计算 newCapacity = oldCapacity + (oldCapacity >> 1)。
- 如 newCapacity < minCapacity，则 newCapacity = minCapacity。
- 如 newCapacity 超过最大容量阈值，则调整为 hugeCapacity(minCapacity)。
数组复制：通过 Arrays.copyOf(elementData, newCapacity) 创建新数组并替换原引用，实现元素迁移。

整个过程会在 add() 方法中内联，以减少方法调用开销，并通过 modCount++ 维护结构修改次数，支持快速失败的迭代器。

性能及优化建议

摊销常数时间：由于每次扩容大约增长 1.5 倍，使得在多次 add() 操作下，扩容次数为 O(log n)，拷贝成本摊销至每次添加，使得单次添加的平均复杂度为 O(1)。
预分配容量：若能预知大致元素数量，建议使用 new ArrayList<>(expectedSize) 或调用 ensureCapacity(expectedSize)，可显著减少或避免扩容所带来的数组复制开销。
内存与性能权衡：容量增长率（1.5×）兼顾了性能（低频次复制）与内存利用（不过度浪费）间的权衡，是常见的动态数组设计策略。

HashMap源码解析

本质上，HashMap 通过一个长度为 2 的次幂的数组 table 维护所有条目，解决哈希冲突采用“数组 + 链表”或“数组 + 红黑树”混合结构。当链表长度超过阈值（TREEIFY_THRESHOLD = 8）且表容量不小于 MIN_TREEIFY_CAPACITY = 64 时，会将该链表转化为红黑树，以确保最坏情况下的查询性能由 O(n) 降至 O(log n)；反之，在扩容时若红黑树节点数低于 UNTREEIFY_THRESHOLD = 6，则会“退化”回链表结构。HashMap 的默认初始容量为 16，默认加载因子为 0.75，**每次扩容都会将容量翻倍**，并更新阈值 threshold = capacity * loadFactor，以保证空间与时间开销的平衡。以上设计使得 HashMap 在大多数应用场景中既能保持常数级别的平均时间复杂度，又能在极端冲突情况下依然提供可接受的性能保证。

底层数据结构

数组与链表 / 红黑树

HashMap 的主体是一个 Node<K,V>[] table 数组，每个 Node 包含 key、value、hash 以及指向下一个节点的 next 引用，用于链表结构的实现在 JDK 1.8 之前，所有冲突均以链表形式存储；从 JDK 1.8 开始，当某个桶（数组索引）处的链表长度达到 8 且表容量至少为 64 时，该链表会被转换为红黑树节点（TreeNode），查询效率从 O(n) 提升到 O(log n)

哈希计算与索引定位

hash 函数

插入或查找时，HashMap 会先对 key 的原生 hashCode() 值进行扰动（高位与低位异或），以减少低位比特不均匀带来的冲突：

java

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

此操作将低 16 位的信息扩散到高 16 位，然后通过 index = (n - 1) & hash 定位到数组下标，其中 n 为当前表的长度（始终为 2 的幂）

`put` 操作流程

初始化：如果 table == null 或长度为 0，则调用 resize() 初始化为默认容量（16）
定位桶：计算 key 的扰动哈希并映射到数组下标 i；
空位直接插入：若 table[i] 为空，直接创建新节点；否则进入冲突处理；
冲突处理：

- 若首节点与待插入 key 相同（hash 和 equals 均匹配），直接覆盖旧值；
- 若当前首节点为红黑树节点，调用 putTreeVal() 在树中插入；
- 否则遍历链表，若遍历中发现已有匹配节点则覆盖并退出；若遍历完毕还没有匹配节点则添加到最后面，添加完毕后，判断链表长度 + 1 ≥ 8 且数组长度 ≥ 64，则调用 treeifyBin() 将链表树化；否则，就是只是对数组扩容

检查并触发扩容：插入后若总节点数超过 threshold，调用 resize() 扩容（容量翻倍，重新分配、迁移所有节点）

`get` 操作流程

空表或空桶：若 table == null 或对应桶 table[i] 为空，直接返回 null；
定位节点：若首节点匹配，立即返回；否则：

- 若该桶为红黑树节点，调用 getTreeNode() 在树中查找；
- 否则遍历链表，依次比较 hash 与 equals，直到找到或链表末尾返回 null

扩容（`resize()`）

触发时机：首次初始化和每次插入后节点数超过阈值时；
核心逻辑：新容量 = 旧容量 × 2；新阈值 = 新容量 × 加载因子；分配新数组后，遍历旧表中所有节点并根据新哈希高位对它们进行“低位不变 / 高位索引偏移”双路分配，以减少全部重新哈希的开销（“高位”拆分优化）
红黑树退化：在迁移过程中，若某棵树节点数低于 UNTREEIFY_THRESHOLD = 6，则再将树转换为链表节点，以减少树结构的过度维护成本

树化与退化阈值

TREEIFY_THRESHOLD = 8（链表 → 红黑树）
UNTREEIFY_THRESHOLD = 6（红黑树 → 链表）
MIN_TREEIFY_CAPACITY = 64（触发树化的最小表容量）这些常量保证了树化仅在真正有必要时发生，同时在扩容后又可避免树化带来的额外平衡维护开销

性能与特性

平均时间复杂度：插入、查询、删除均为 O(1)；在极端冲突（链表）情况下最坏 O(n)，但树化后最坏 O(log n)
空间开销：维护链表与红黑树节点会带来不同内存开销；红黑树节点需额外维护父、左右子指针与颜色标志。
线程安全：非线程安全，多线程写入可能导致死循环或数据丢失；推荐使用 ConcurrentHashMap 或外部加锁来替代

ConcurrentHashMap解析

以下是对 Java 8 及以后版本 ConcurrentHashMap 源码的深入解析，涵盖其底层数据结构、并发控制机制、核心操作流程、扩容与迁移、树化/退化策略，以及性能特性。总体来说，ConcurrentHashMap 在 JDK 8 中摒弃了原有的 Segment 分段锁，采用了「数组 + 链表/红黑树 + CAS + synchronized」的设计，使得检索无锁、更新高并发，且在扩容时支持多线程协作，以此在确保线程安全的同时，最大化地提升性能和可伸缩性。

底层数据结构

ConcurrentHashMap 维护一个类型为 Node<K,V>[] table 的主数组，数组长度始终为 2 的幂次方，每个桶（bin）最初存储 Node 节点（单链表）或 TreeBin（红黑树）

Node：包含 final int hash; final K key; volatile V val; volatile Node<K,V> next;，用于链表结构的实现
TreeBin：当单链表长度 ≥ 8 且数组容量 ≥ 64 时，链表会转换为红黑树节点（TreeNode），以将单桶最坏查找从 O(n) 降至 O(log n)

并发控制机制

CAS 与 Unsafe

ConcurrentHashMap 使用 sun.misc.Unsafe 提供的 CAS 原语（casTabAt、U.compareAndSwapObject 等）来在无锁情况下完成桶头的插入（桶中无数据时）与更新，从而实现高效的并发写

当 CAS 插入失败（即已存在元素，或链表/树操作），会对该桶首节点 **f** 加 **synchronized(f)** 锁以串行化后续对链表或树结构的修改，保证冲突处理的正确性而不会全表加锁

核心操作流程

初始化

构造 ConcurrentHashMap 实例时，table 并不立即分配；首个插入或显式调用 put 时，才通过 CAS 确保单线程完成初始化（容量默认为 16）

`get`

直接读取 table（不加锁）；
计算扰动哈希 h = spread(key.hashCode()) 并定位桶索引 i = (n – 1) & h；
若 tab[i] == null，返回 null；若首节点匹配则返回值；否则依次遍历链表或在 TreeBin 中调用 find 进行对数级查找

`put`

计算哈希并尝试在对应桶通过 CAS 插入新 Node 作为头节点；
若 CAS 失败且 tab[i] 已存在：

- 对首节点 f 加锁，检查键是否已存在，存在则覆盖；
- 否则将新节点追加到链表尾部，若链表长度达 8 且表容量 ≥ 64，则调用 treeifyBin 将桶转为红黑树；

更新计数器 size，如超过阈值 threshold = capacity * loadFactor，触发扩容

`remove` 与 `compute`

remove 同样通过 CAS 快速尝试删除头节点，失败则锁定对应桶进行遍历删除；
computeIfAbsent 等高级方法在锁定桶头后进行 remappingFunction 调用，并在必要时插入新节点，递归调用时会触发 OpenJDK 中对递归的防护机制（过于严格时可参考 JDK-8294891 报告）

扩容与迁移

扩容由 transfer 方法完成，支持多线程协作：

单线程初始化 nextTable（容量翻倍）并设置 transferIndex；
多线程迁移：各线程通过 CAS 递减 transferIndex 分配任务块，遇到 forwarding 标记则跳过，遍历旧 Node 并按高位拆分到新表的 i 或 i + oldCap 位置；
迁移完成后，nextTable 替代 table，更新 sizeCtl 为新容量 × 0.75

树化与退化

树化阈值：链表长度 ≥ 8 且表容量 ≥ 64 时由 treeifyBin 转为红黑树；
退化阈值：在迁移过程中，若树节点数 < 6，则调用 untreeify 将 TreeBin 转回链表，以减少平衡维护开销

性能与特性

并发级别：检索无锁（完全并发），更新高预期并发性（局部 synchronized + CAS）
时间复杂度：平均 O(1)，最坏 O(log n)（树化后）；
内存开销：红黑树节点需额外维护父/左右指针与颜色标志；
线程安全：内部确保了多线程访问安全，无死锁风险，但不支持全表锁定；全表级别的操作需外部同步或使用其他并发集合。

CAS 和Synchronized的使用时机

1. CAS（Compare-And-Swap）使用场景 🔄

适用于无冲突或低冲突操作，确保乐观并发性。

表初始化：
- 使用 CAS 保证 table 初始化只由一个线程成功（initTable() 方法）。
- casTabAt(tab, i, null, newNode) 用于无锁创建桶。
节点插入（无冲突时）：
- 当目标桶 tab[i] 为空，直接使用 CAS 插入新节点，无需加锁。
计数器更新：
- 使用 CAS 递增 baseCount 计数器（统计元素个数）。
- 如果 CAS 失败，才会退化到 fullAddCount()，分散计数压力。

典型源码片段：

java

if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) {
    break; // 成功插入
}

2. synchronized 使用场景 🔒

适用于存在冲突或复杂结构变更的操作，确保悲观锁定。

桶内链表/树操作：
- 如果 CAS 插入失败（表示桶非空），需要遍历链表或红黑树；
- 此时，对桶头节点 synchronized (f) 加锁，串行化冲突修改。
链表转红黑树（treeify）：
- 当桶中链表长度 ≥ 8，需要加锁完成链表到红黑树的结构变换。
红黑树操作：
- TreeBin 内部操作，比如插入、删除、旋转、平衡时，用 synchronized 确保树结构正确。
复杂删除和 compute 方法：
- 如 remove()、computeIfAbsent()、compute()，涉及读取 + 修改；
- 这些方法会对桶头 synchronized 来串行化整个修改逻辑。

典型源码片段：

java

synchronized (f) {
    Node<K,V>[] tab2;
    // 遍历链表/树进行插入或更新
}

✅ 总结记忆口诀：

场景	用法
无冲突，简单插入	CAS
冲突、遍历、结构变更	synchronized
链表 → 红黑树转化	synchronized
红黑树插入/删除	synchronized
size 计数更新	CAS + 分段计数

🚩设计哲学：

优先使用 CAS（乐观并发） → 快速失败重试，效率高；
结构性修改退化为 synchronized → 保证链表/树一致性，不追求无锁，但控制在桶级别，避免全表锁。

LinkedHashMap源码解析

LinkedHashMap 是 Java 集合框架中在保留 HashMap 高效存取性能的基础上，通过额外维护一条双向链表来保证元素的迭代顺序（插入顺序或访问顺序）的 Map 实现。其核心思路是在每个桶（bucket）节点上都增加 before 和 after 指针，串联成一个环形双向链表，并由 head、tail 引用维护链表首尾。当执行 put、get（若开启访问顺序）、remove 等操作时，除了调用 HashMap 的基本操作，还会对链表做相应调整，以保证有序迭代。以下从源码结构、主要方法、链表维护、扩容与迭代等方面做深入剖析。

1. 源码结构概览

1.1 继承关系与节点设计

LinkedHashMap<K,V> 直接继承自 HashMap<K,V>，复用其拉链表/红黑树冲突解决机制，同时为每个节点增加双向链表功能
内部静态类 LinkedHashMap.Entry<K,V> extends HashMap.Node<K,V>，在父类 Node 的基础上新增两个指针：

java

Entry<K,V> before; // 前驱
Entry<K,V> after;  // 后继

使得所有节点在 hash 桶结构之外，还串联成一条双向链表

1.2 关键字段

transient Entry<K,V> head：链表的“最旧”节点（首节点）。
transient Entry<K,V> tail：链表的“最新”节点（尾节点）。
final boolean accessOrder：决定迭代顺序：
- false：保持插入顺序
- true：保持访问顺序（每次 get/put 或 putIfAbsent 会将节点移到链表尾部）

2. 插入操作（put）源码分析

2.1 调用 HashMap 的 putNode

LinkedHashMap 的 put(K key, V value) 方法最终会调用 HashMap 的 putVal，它在完成哈希桶插入或更新后，返回插入或更新的 Node。

2.2 链表尾部插入

在 HashMap.putVal 执行完毕后，LinkedHashMap 会重写 afterNodeInsertion(boolean evict)：

plain

java


复制编辑
void afterNodeInsertion(boolean evict) {
    // 新节点 always 添加到 tail 之后
    Entry<K,V> p = (Entry<K,V>) e;
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
    if (evict && removeEldestEntry(head))
        removeNode(head.hash, head.key, null, false, true);
}

其中 evict 用于支持根据策略（如 LRU）剔除最旧节点。该逻辑在 removeEldestEntry 返回 true 时触发

3. 访问操作（get）及访问顺序维护

3.1 默认不改变链表结构

若 accessOrder == false，get 操作仅返回值，不调整链表。

3.2 访问顺序下的节点后移

若 accessOrder == true，在 HashMap.getNode 调用后，LinkedHashMap 重写了 afterNodeAccess(Node<K,V> e)：

java

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p = (Entry<K,V>) e;
        // 断链
        unlink(p);
        // 重新接到尾部
        p.before = last;
        p.after = null;
        last.after = p;
        tail = p;
    }
}

其中 unlink(p) 会调整 before.after、after.before 等指针，确保链表完整性

4. 删除操作与链表维护

4.1 普通删除

remove(Object key) 会在 HashMap 中删除节点，随后调用 afterNodeRemoval(Node<K,V> e)：

java

void afterNodeRemoval(Node<K,V> e) {
    Entry<K,V> p = (Entry<K,V>) e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

这样可在 O(1) 时间内从双向链表中摘除任意节点

4.2 批量清空

clear() 调用 HashMap.clear() 清桶后，同时将 head = tail = null，断开所有链表引用。

5. 扩容（resize）与迭代顺序

HashMap 的扩容只会重新分配并重链桶内链表/树结构，不会改变 LinkedHashMap 维护的双向链表；即原有的 before/after 关系保持不变
因此，无论何时遍历 LinkedHashMap，都能根据链表次序输出所有键值对。

6. 小结

结构：在 HashMap 的每个节点基础上，通过 Entry.before/Entry.after 串成环形双向链表，并用 head、tail 跟踪首尾
顺序维护：

- 插入顺序（默认）：新节点追加到尾部。
- 访问顺序（accessOrder=true）：每次访问将对应节点移动到尾部。

性能：

- 与 HashMap 相比，插入、删除及访问（若维护顺序）多了 O(1) 的链表操作开销。
- 保留了哈希表的 O(1) 平均存取性能，并在需要有序迭代时表现优异。

通过以上分析，可以清晰地理解 LinkedHashMap 如何在 HashMap 基础上，以最小改动代价引入双向链表，进而同时满足快速存取和有序迭代两大需求。

集合系列 ​

ArrayList源码解析 ​

初始容量与构造函数 ​

无参构造 ​

有参构造 ​

扩容触发时机 ​

扩容算法 ​

容量增长公式 ​

溢出与最小容量保证 ​

扩容流程 ​

性能及优化建议 ​

HashMap源码解析 ​

底层数据结构 ​

数组与链表 / 红黑树 ​

哈希计算与索引定位 ​

hash 函数 ​

put 操作流程 ​

get 操作流程 ​

扩容（resize()） ​

树化与退化阈值 ​

性能与特性 ​

ConcurrentHashMap解析 ​

底层数据结构 ​

并发控制机制 ​

CAS 与 Unsafe ​

核心操作流程 ​

初始化 ​

get ​

put ​

remove 与 compute ​

扩容与迁移 ​

树化与退化 ​

性能与特性 ​

CAS 和Synchronized的使用时机 ​

1. CAS（Compare-And-Swap）使用场景 🔄 ​

适用于无冲突或低冲突操作，确保乐观并发性。 ​

典型源码片段： ​

2. synchronized 使用场景 🔒 ​

适用于存在冲突或复杂结构变更的操作，确保悲观锁定。 ​

典型源码片段： ​

✅ 总结记忆口诀： ​

🚩设计哲学： ​

LinkedHashMap源码解析 ​

1. 源码结构概览 ​

1.1 继承关系与节点设计 ​

1.2 关键字段 ​

2. 插入操作（put）源码分析 ​

2.1 调用 HashMap 的 putNode ​

2.2 链表尾部插入 ​

3. 访问操作（get）及访问顺序维护 ​

3.1 默认不改变链表结构 ​

3.2 访问顺序下的节点后移 ​

4. 删除操作与链表维护 ​

4.1 普通删除 ​

4.2 批量清空 ​

5. 扩容（resize）与迭代顺序 ​

6. 小结 ​

集合系列

ArrayList源码解析

初始容量与构造函数

无参构造

有参构造

扩容触发时机

扩容算法

容量增长公式

溢出与最小容量保证

扩容流程

性能及优化建议

HashMap源码解析

底层数据结构

数组与链表 / 红黑树

哈希计算与索引定位

hash 函数

`put` 操作流程

`get` 操作流程

扩容（`resize()`）

树化与退化阈值

性能与特性

ConcurrentHashMap解析

底层数据结构

并发控制机制

CAS 与 Unsafe

核心操作流程

初始化

`get`

`put`

`remove` 与 `compute`

扩容与迁移

树化与退化

性能与特性

CAS 和Synchronized的使用时机

1. CAS（Compare-And-Swap）使用场景 🔄

适用于无冲突或低冲突操作，确保乐观并发性。

典型源码片段：

2. synchronized 使用场景 🔒

适用于存在冲突或复杂结构变更的操作，确保悲观锁定。

典型源码片段：

✅ 总结记忆口诀：

🚩设计哲学：

LinkedHashMap源码解析

1. 源码结构概览

1.1 继承关系与节点设计

1.2 关键字段

2. 插入操作（put）源码分析

2.1 调用 HashMap 的 putNode

2.2 链表尾部插入

3. 访问操作（get）及访问顺序维护

3.1 默认不改变链表结构

3.2 访问顺序下的节点后移

4. 删除操作与链表维护

4.1 普通删除

4.2 批量清空

5. 扩容（resize）与迭代顺序

6. 小结