Java集合全套原理（List+Map底层、扩容机制、线程安全集合对比）

本文一次性讲透 ArrayList、LinkedList、HashMap、LinkedHashMap、HashTable、ConcurrentHashMap 底层结构、核心原理、扩容机制、线程安全、优缺点、场景对比，是Java面试必考核心全集，逻辑闭环、无废话、可直接背诵。

一、集合整体分类

• List（有序可重复）：ArrayList、LinkedList、Vector
• Map（键值对、key唯一）：HashMap、LinkedHashMap、HashTable、ConcurrentHashMap

二、List 系列底层原理 & 扩容机制

1. ArrayList（非线程安全）

底层结构

Object[] 动态数组，基于连续内存存储，支持随机访问。

初始化机制（JDK1.8）

• new ArrayList()：默认是空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，懒加载，不占用内存
• 第一次 add 才初始化容量为 默认容量10
• new ArrayList(100)：直接初始化指定容量数组

扩容原理（核心）

• 扩容时机：元素个数 size >= 数组容量，触发扩容
• 扩容比例：原容量 << 1.5倍（原容量 + 原容量/2）
• 扩容流程：新建更大数组 → Arrays.copyOf 拷贝全部元素 → 替换数组引用
• 最大容量：Integer.MAX_VALUE - 8

优缺点

• 优点：查询快（随机访问O(1)）
• 缺点：增删末尾快、中间增删慢（需要移动元素）、扩容有拷贝开销、非线程安全

2. LinkedList（非线程安全）

底层结构

双向链表（JDK1.6之前是双向循环链表，1.7+取消循环）

每个节点：prev 前驱指针 + next 后继指针 + data数据

核心特性

• 无数组、无扩容，按需创建节点
• 首尾增删极快 O(1)
• 随机查询慢 O(n)，必须从头遍历

优缺点

• 优点：任意位置增删效率高，无内存浪费
• 缺点：查询遍历慢，不支持随机访问

3. Vector（古老、线程安全）

• 底层也是 Object 数组
• 默认扩容2倍（比ArrayList更浪费内存）
• 所有方法加 synchronized，锁粒度极大，性能极差
• 基本废弃，生产不用

4. ArrayList vs LinkedList 终极对比

• 查询多、改多、少增删 → ArrayList
• 频繁中间/首尾增删 → LinkedList

三、Map 系列底层原理 & 扩容机制（重点）

1. HashMap 底层原理（JDK1.8）

底层结构

数组 + 链表 + 红黑树 三合一结构

• 数组：哈希桶，存放链表/树根节点
• 链表：解决哈希冲突，链地址法
• 红黑树：链表过长优化查询效率

核心阈值（必考）

• 默认初始容量：16
• 负载因子：0.75
• 扩容阈值：容量 * 0.75（16*0.75=12）
• 树化阈值：链表长度 >= 8 且 数组容量 >= 64 → 转红黑树
• 退化阈值：树节点数量 <= 6 → 退化为链表

扩容原理

• 扩容时机：元素数量 >= 扩容阈值
• 扩容倍数：固定 2倍扩容（保证容量永远是2的幂次）
• 重哈希优化：JDK1.8 无需重新计算hash值，通过 hash & 新容量高位 判断节点迁移位置，要么原下标、要么原下标+旧容量
• 大大减少扩容开销

HashMap 为什么容量必须是2的幂次？

为了用 hash & (len-1) 代替取模运算，效率更高，同时保证哈希分布均匀。

HashMap 为什么线程不安全？

• 多线程put导致数据覆盖
• JDK1.7 多线程扩容会出现 循环链表、死循环CPU100%
• JDK1.8 修复死循环，但仍存在数据覆盖、丢失数据问题

2. LinkedHashMap

• 继承 HashMap，底层结构一致
• 额外维护一条 双向链表，保证插入有序/访问有序
• 可实现 LRU 缓存淘汰（重写removeEldestEntry方法）

3. HashTable（废弃）

• 线程安全，所有方法加 synchronized
• 初始容量11，扩容 2倍+1
• 不允许null键、null值
• 效率极低，完全被 ConcurrentHashMap 替代

四、线程安全集合 完整对比（面试核心）

1. 非线程安全集合（常用）

• ArrayList、LinkedList
• HashMap、LinkedHashMap

2. 线程安全集合分类

（1）Vector / HashTable（低效、废弃）

全局方法锁，锁粒度太大，并发性能极差

（2）Collections.synchronized 包装集合

通过同步代码块加锁，全局锁，所有线程竞争同一把锁，并发弱，适合低并发场景

（3）JUC高性能线程安全集合（生产推荐）

• CopyOnWriteArrayList：ArrayList 线程安全版
• ConcurrentHashMap：HashMap 线程安全版
• CopyOnWriteArraySet：Set 线程安全版

3. CopyOnWriteArrayList 原理

核心机制：写时复制

• 读不加锁：读原数组，并发极高
• 写加锁（ReentrantLock）：写入时复制新数组，修改新数组，最后替换引用
• 弱一致性：迭代器遍历的是旧数组快照，不保证实时最新数据

适用场景

读多写少（配置、白名单、常量列表），写多场景会频繁数组拷贝，性能爆炸

4. ConcurrentHashMap 原理（JDK1.8）

核心优化：CAS + synchronized 细粒度锁

• 不再分段锁，锁定 单个桶的头节点，锁粒度极小
• 无冲突 CAS 写入
• 冲突后加 synchronized 锁桶
• 支持高并发读写，吞吐量极高

特性

• key/value 均不允许null
• 扩容、树化、退化逻辑与HashMap基本一致
• 多线程协助扩容，进一步提升并发性能

五、高频面试对比总结（必背）

1. ArrayList vs LinkedList

• ArrayList：数组、查询快、中间增删慢、1.5倍扩容、有内存开销
• LinkedList：双向链表、无扩容、增删快、查询慢

2. HashMap vs HashTable vs ConcurrentHashMap

• HashMap：非线程安全、2的幂次容量、1.8数组链表红黑树、允许null
• HashTable：全局sync、初始11、扩容2倍+1、不允许null、废弃
• ConcurrentHashMap：CAS+桶锁、高并发、不允许null、生产首选

3. 线程安全集合选型口诀

• 读多写少 List → CopyOnWriteArrayList
• 读写并发 Map → ConcurrentHashMap
• 绝对禁止：Vector、HashTable

六、扩容机制终极汇总

• ArrayList：1.5倍扩容
• Vector：2倍扩容
• HashMap/ConcurrentHashMap：2倍扩容、保持2的幂次
• HashTable：2倍+1扩容
• LinkedList：无扩容机制