简述：

Java 集合框架以 Collection（单列集合） 和 Map（双列集合） 为核心，底层依托「数组、链表、红黑树」三大基础结构，通过组合优化实现不同性能特性。

一、单列集合（Collection 接口）

Collection 包含 List（有序可重复、支持索引）和 Set（无序不可重复、无索引）两大子接口，底层结构直接决定其核心能力。

（一）List 接口实现类（有序、可重复、支持索引）

1. ArrayList（最常用）

1. 底层结构：基于动态数组（Object[]）实现，JDK 8 中默认初始容量为 10。
2. 核心机制：当元素数量超过数组容量时触发扩容，扩容公式为「新容量 = 旧容量 + 旧容量右移 1 位」（即 1.5 倍扩容）；扩容时需创建新数组，将原数据拷贝至新数组，属于耗时操作；通过数组下标 array[index] 直接访问元素，无需遍历。
3. 核心特性：查询效率极高（时间复杂度 O (1)），插入 / 删除元素需移动目标位置后的所有元素（时间复杂度 O (n)），非线程安全，支持随机访问和索引操作。
4. 适用场景：查询操作远多于插入、删除操作的场景，例如数据展示列表、高频读取的配置缓存等。

2. LinkedList

1. 底层结构：基于双向链表实现（JDK 8 取消循环链表设计），每个节点（Node）包含前驱指针（prev）、元素本身（item）、后继指针（next）。
2. 核心机制：无数组下标，访问指定索引元素时需从链表头或尾遍历定位（遍历方向取决于索引位置）；插入 / 删除元素时，仅需修改目标节点的 prev 和 next 指针，无需移动其他元素；额外实现 Deque 接口，支持头尾快速操作（如 addFirst、removeLast 等）。
3. 核心特性：插入 / 删除效率高（定位节点后时间复杂度 O (1)，未定位时需遍历 O (n)），查询效率低（时间复杂度 O (n)），非线程安全，内存开销略高于 ArrayList。
4. 适用场景：频繁插入、删除元素的场景，例如队列、栈的实现，或需要频繁在首尾操作数据的场景。

3. Vector（几乎淘汰）

1. 底层结构：与 ArrayList 一致，基于动态数组实现，默认初始容量为 10。
2. 核心机制：线程安全通过「全局 synchronized 锁」实现，所有方法均加锁；扩容规则为 2 倍扩容（新容量 = 旧容量 × 2），空间利用率低于 ArrayList；其他存储、访问逻辑与 ArrayList 完全一致。
3. 核心特性：查询快、增删慢（同 ArrayList），线程安全但效率极低（全局锁导致并发阻塞），空间利用率低。
4. 适用场景：仅适用于老旧系统兼容，新开发场景优先使用 CopyOnWriteArrayList 替代。

4. CopyOnWriteArrayList（线程安全）

1. 底层结构：基于「不可变数组 + 写时复制（COW）」机制，底层维护一个 volatile 修饰的数组（保证多线程可见性）。
2. 核心机制：读操作无需加锁，直接访问原数组（时间复杂度 O (1)），无并发阻塞；写操作（添加、删除、修改）时，先复制原数组生成副本，在副本上完成修改，再将原数组引用指向副本（全程加锁），复制数组耗时（时间复杂度 O (n)）；读操作可能读取到旧数据（弱一致性）。
3. 核心特性：线程安全，读操作效率极高，写操作效率低（复制数组开销），弱一致性，支持索引访问。
4. 适用场景：「读多写少」的并发场景，例如高频查询的配置列表、日志记录集合等。

5. List实现类底层(表格)

List 实现类	底层核心结构	核心特性（有序 / 线程安全 / 核心效率）
ArrayList（常用）	动态数组（Object []）	有序可重复、非线程安全、查询 O (1)、增删 O (n)
LinkedList	双向链表（prev+item+next）	有序可重复、非线程安全、查询 O (n)、增删 O (1)（定位后）
Vector（淘汰）	动态数组（加全局 synchronized 锁）	有序可重复、线程安全（低效）、查询 O (1)、增删 O (n)
CopyOnWriteArrayList	不可变数组 + 写时复制（COW）	有序可重复、线程安全、读 O (1)、写 O (n)（读多写少）

（二）Set 接口实现类（无序、不可重复、无索引）

Set 核心是保证元素唯一性，底层依赖哈希表或红黑树，无序性指存储顺序与插入顺序不一致（LinkedHashSet 除外）。

1. HashSet（最常用）

1. 底层结构：依赖 HashMap 实现，内部持有一个 HashMap 实例，元素存储在 HashMap 的 key 中，value 固定为静态空对象（PRESENT）。
2. 核心机制：元素唯一性通过「哈希值（hashCode()）+ equals()」判断；哈希桶底层为「数组 + 链表 / 红黑树」，元素散列存储，无固定顺序。
3. 核心特性：无序、不可重复，查询 / 插入 / 删除平均时间复杂度 O (1)，非线程安全，允许存储一个 null 元素。
4. 适用场景：无需保留顺序的去重场景，例如存储用户 ID 集合、标签集合等。

2. LinkedHashSet

1. 底层结构：依赖 LinkedHashMap 实现，内部持有 LinkedHashMap 实例，复用其「哈希表 + 双向链表」结构。
2. 核心机制：元素唯一性判断逻辑与 HashSet 一致（hashCode() + equals()）；通过双向链表记录插入顺序，保证有序性；哈希计算、扩容机制与 HashMap 完全一致。
3. 核心特性：有序（插入顺序）、不可重复，查询 / 插入 / 删除效率略低于 HashSet，非线程安全，允许存储一个 null 元素。
4. 适用场景：需要保留插入顺序的去重场景，例如记录用户操作日志的唯一标识、按顺序存储去重后的请求参数等。

3. TreeSet

1. 底层结构：依赖 TreeMap 实现，内部持有 TreeMap 实例，底层核心为红黑树（平衡二叉搜索树）。
2. 核心机制：元素有序性通过「自然顺序」或「自定义比较器（Comparator）」实现；元素唯一性通过比较结果判断（比较结果为 0 则视为重复）；红黑树中序遍历可直接得到有序结果。
3. 核心特性：有序（排序后顺序）、不可重复，查询 / 插入 / 删除时间复杂度 O (log n)，非线程安全，不允许存储 null 元素。
4. 适用场景：需要按指定规则排序的去重场景，例如按数值大小排序的 ID 集合、按字符串字典序排序的名称集合等。

4. CopyOnWriteArraySet（线程安全）

1. 底层结构：依赖 CopyOnWriteArrayList 实现，内部持有 CopyOnWriteArrayList 实例，复用其「写时复制」机制。
2. 核心机制：元素唯一性通过 CopyOnWriteArrayList 的 addIfAbsent() 方法实现（先遍历判断是否存在，再复制添加）；读操作无锁，写操作加锁复制数组。
3. 核心特性：线程安全、有序（插入顺序）、不可重复，读操作效率高（O (1)），写操作效率低（O (n)），弱一致性。
4. 适用场景：「读多写少」的并发去重场景，例如并发环境下的配置标签去重、高频查询的唯一标识集合等。

5. Set实现类底层(表格)

Set 实现类	底层核心结构	核心特性（有序 / 线程安全 / 核心效率）
HashSet（常用）	HashMap（key 集合）	无序不可重复、非线程安全、增删查 O (1)
LinkedHashSet	LinkedHashMap（哈希表 + 双向链表）	有序（插入顺序）、不可重复、非线程安全、增删查 O (1)（略低）
TreeSet	TreeMap（红黑树）	有序（排序后）、不可重复、非线程安全、增删查 O (log n)
CopyOnWriteArraySet	CopyOnWriteArrayList	有序（插入顺序）、不可重复、线程安全、读 O (1)、写 O (n)

二、双列集合（Map 接口）

Map 存储键值对（key-value），key 不可重复（底层逻辑与 Set 一致），value 可重复，核心实现类围绕「哈希表」和「红黑树」设计。

1. HashMap（最常用）

1. 底层结构：JDK 8 中为「数组（哈希桶）+ 链表 + 红黑树」组合结构，默认初始容量 16（2 的幂）。
2. 核心机制：负载因子默认 0.75，扩容阈值 = 容量 × 负载因子；key 索引通过「扰动函数 + 位运算」计算；链表长度 ≥8 且容量 ≥64 时转红黑树，≤6 时转回链表；key 唯一性通过 hashCode() + equals() 判断，允许 key 和 value 为 null（key 仅 1 个）。
3. 核心特性：无序，key 唯一、value 可重复，查询 / 插入 / 删除平均时间复杂度 O (1)，非线程安全。
4. 适用场景：无需顺序的键值对存储场景，例如缓存用户信息、存储配置参数等。

2. LinkedHashMap

1. 底层结构：基于 HashMap 扩展，增加「双向链表」记录键值对顺序（数组 + 链表 / 红黑树 + 双向链表）。
2. 核心机制：支持两种有序模式 —— 默认「插入顺序」，指定 accessOrder = true 为「访问顺序」（最近访问后置）；复用 HashMap 的哈希、扩容、去重逻辑。
3. 核心特性：有序（插入 / 访问顺序），key 唯一、value 可重复，效率略低于 HashMap，非线程安全，允许 key 和 value 为 null。
4. 适用场景：需要保留键值对顺序的场景，例如实现 LRU 缓存（访问顺序模式）、记录请求参数顺序等。

3. TreeMap

1. 底层结构：基于红黑树（平衡二叉搜索树）实现，无哈希桶数组。
2. 核心机制：key 有序性通过「自然顺序」或「自定义比较器」实现；key 唯一性通过比较结果判断（结果为 0 则重复）；增删查需维持红黑树平衡，时间复杂度 O (log n)；不允许 key 为 null，value 可为 null。
3. 核心特性：有序（排序后顺序），key 唯一、value 可重复，非线程安全，性能稳定无哈希冲突退化问题。
4. 适用场景：需要按 key 排序的键值对存储场景，例如按时间戳排序的日志记录、按用户等级排序的用户信息等。

4. Hashtable（几乎淘汰）

1. 底层结构：基于「数组（哈希桶）+ 链表」实现，无红黑树优化，默认初始容量 11（非 2 的幂）。
2. 核心机制：线程安全通过「全局 synchronized 锁」实现，并发效率极低；扩容公式为「新容量 = 旧容量 × 2 + 1」；不允许 key 和 value 为 null；仅通过链表解决哈希冲突。
3. 核心特性：无序，key 唯一、value 可重复，线程安全但低效，空间利用率低。
4. 适用场景：仅适用于老旧系统兼容，新开发场景优先使用 ConcurrentHashMap 替代。

5. ConcurrentHashMap（线程安全、高并发）

1. 底层结构：JDK 8 为「数组 + 链表 / 红黑树 + synchronized 锁 + CAS」，取消 JDK 7 的分段锁。
2. 核心机制：线程安全通过「哈希桶头节点细粒度锁 + CAS」实现；支持并发扩容（多线程协同迁移数据）；复用 HashMap 的哈希、红黑树转换逻辑；不允许 key 和 value 为 null。
3. 核心特性：线程安全、高并发，查询 / 插入 / 删除效率接近 HashMap，无全局锁开销。
4. 适用场景：高并发读写的键值对存储场景，例如分布式系统的本地缓存、高并发接口的参数缓存等。

6. Map实现类底层(表格)

Map 实现类	底层核心结构	核心特性（有序 / 线程安全 / 核心效率）
HashMap（常用）	数组 + 链表 + 红黑树（JDK8）	无序、key 唯一、非线程安全、增删查 O (1)
LinkedHashMap	数组 + 链表 / 红黑树 + 双向链表	有序（插入 / 访问）、key 唯一、非线程安全、增删查 O (1)（略低）
TreeMap	红黑树（平衡二叉搜索树）	有序（排序后）、key 唯一、非线程安全、增删查 O (log n)
Hashtable（淘汰）	数组 + 链表（加全局 synchronized 锁）	无序、key 唯一、线程安全（低效）、增删查 O (1)
ConcurrentHashMap	数组 + 链表 / 红黑树 + 细粒度锁 + CAS（JDK8）	无序、key 唯一、线程安全（高并发）、增删查接近 O (1)

三、核心结论

1. 底层结构决定性能上限：

   • 数组（ArrayList、HashMap）：支持随机访问（O (1)），适合查询密集型场景；
   • 链表（LinkedList）：插入 / 删除仅改指针（O (1)），适合修改密集型场景；
   • 红黑树（TreeSet、TreeMap）：平衡排序（O (log n)），适合有序场景，性能稳定。

2. 线程安全选型原则：

   • 读多写少：CopyOnWriteArrayList、CopyOnWriteArraySet（写时复制，读无锁）；
   • 高并发读写：ConcurrentHashMap（细粒度锁 + CAS，兼顾安全与效率）；
   • 避免使用：Vector、Hashtable（全局锁低效，已被现代实现替代）。

3. 有序性实现方式：

   • 插入顺序：LinkedHashMap、LinkedHashSet（双向链表记录）；
   • 排序顺序：TreeSet、TreeMap（红黑树 + 比较器）；
   • 访问顺序：LinkedHashMap（指定 accessOrder = true）。

4. 去重逻辑匹配规则：

   • 哈希类集合（HashSet、HashMap）：需同时重写 hashCode() 和 equals()；
   • 排序类集合（TreeSet、TreeMap）：需实现 Comparable 或传入 Comparator。