集合，是每个Java程序员的必修课。无论你是刚入行的新手，还是工作多年的老鸟，集合框架都是每天都要打交道的工具。但是你真的了解它们吗？ArrayList 和 LinkedList 的区别，你能说出几条？HashMap 的扩容机制，你能讲清楚吗？ConcurrentHashMap 为什么线程安全？这篇文章，我会从最基础的用法开始，逐步深入到源码原理，带你彻底搞懂Java集合框架。

一、什么是集合框架

在讲具体实现之前，我们先理解一下：为什么需要集合？

假设你要存储一组学生的姓名。用数组可以这样写：

java

String[] students = new String[10];
students[0] = "张三";

但数组有个明显的限制：长度固定。如果你不确定会有多少个学生，数组就不太合适了。

集合就是用来解决这个问题的。它是Java提供的一套动态存储对象的容器，可以根据需要自动扩容，还提供了丰富的操作接口。

整个集合框架分为两大体系：

  • Collection：存储单个元素的集合

  • Map：存储键值对的集合

下面我们分别讲解。

二、Collection 体系详解

Collection是所有单元素集合的根接口，它有三个主要的子接口：List、Set、Queue。

2.1 List：有序可重复的序列

List的特点是：元素有顺序、可以重复、可以通过索引访问。

2.1.1 ArrayList

底层实现：数组

ArrayList就是Java对动态数组的实现。当你创建一个ArrayList时，它内部会创建一个数组来存储元素。

java

// 创建一个ArrayList
List<String> list = new ArrayList<>();

// 添加元素
list.add("苹果");    // 追加到末尾
list.add(0, "香蕉"); // 在指定位置插入

// 获取元素
String fruit = list.get(0);

// 修改元素
list.set(1, "橘子");

// 删除元素
list.remove(0);      // 按索引删除
list.remove("苹果");  // 按元素删除

// 获取大小
int size = list.size();

// 判断是否包含
boolean hasApple = list.contains("苹果");

// 遍历方式1：普通for循环
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 遍历方式2：增强for循环
for (String s : list) {
    System.out.println(s);
}

// 遍历方式3：forEach + Lambda（Java 8）
list.forEach(s -> System.out.println(s));

核心特点：

  • 随机访问速度极快，通过索引get(i)和set(i, e)的时间复杂度是O(1)

  • 在末尾添加元素add(e)很快，平均时间复杂度O(1)

  • 在中间插入或删除元素较慢，因为需要移动后续元素，时间复杂度O(n)

扩容机制：

当数组容量不够时，ArrayList会自动扩容。默认初始容量是10，每次扩容为原来的1.5倍。

java

// 你可以指定初始容量，避免频繁扩容
List<String> list = new ArrayList<>(100);

使用场景：

  • 频繁通过索引访问元素

  • 主要在末尾添加元素

  • 不需要线程安全

一个常见误区：很多人认为ArrayList只适合数据量小的场景。实际上，ArrayList的查询性能非常优秀，即使在百万级数据下，随机访问也是毫秒级响应。

2.1.2 LinkedList

底层实现：双向链表

LinkedList内部是由一个个节点连接而成的链表。每个节点包含三个部分：前一个节点的引用、当前节点的值、后一个节点的引用。

java

LinkedList<String> list = new LinkedList<>();

// 添加元素（ArrayList也有的方法）
list.add("苹果");      // 追加到末尾
list.add(0, "香蕉");   // 插入到指定位置

// LinkedList特有的方法
list.addFirst("草莓"); // 在头部添加
list.addLast("西瓜");  // 在尾部添加

// 获取元素
String first = list.getFirst();
String last = list.getLast();

// 删除元素
list.removeFirst();
list.removeLast();

核心特点：

  • 在头部和尾部添加、删除元素非常快，时间复杂度O(1)

  • 在中间位置插入或删除，需要先遍历找到该位置，时间复杂度O(n)

  • 随机访问较慢，需要从头或尾遍历，时间复杂度O(n)

实现Queue和Deque接口：

LinkedList同时实现了Queue和Deque接口，可以作为队列或双端队列使用。

java

// 作为队列使用（FIFO）
Queue<String> queue = new LinkedList<>();
queue.offer("任务1");  // 入队
queue.offer("任务2");
String task = queue.poll();  // 出队

// 作为栈使用（LIFO）
Deque<String> stack = new LinkedList<>();
stack.push("方法1");   // 压栈
stack.push("方法2");
String method = stack.pop();  // 弹栈

使用场景：

  • 需要频繁在头部和尾部操作

  • 实现队列或栈结构

  • 元素数量变化频繁，但不需要随机访问

2.1.3 ArrayList vs LinkedList 深度对比
维度 ArrayList LinkedList
底层数据结构 数组 双向链表
内存占用 连续内存，可能浪费少量空间（预留容量） 分散内存，每个节点多存储两个指针
尾部添加 O(1) 均摊 O(1)
头部添加 O(n) O(1)
中间插入 O(n) O(n)（遍历成本高，但插入本身O(1)）
随机访问get/set O(1) O(n)
按值删除 O(n)（先找再删） O(n)（先找再删）

实际测试结论：

  • 对于百万级数据，ArrayList的遍历速度约是LinkedList的3-5倍

  • 在头部频繁插入时，LinkedList有明显优势

  • 大部分业务场景下，ArrayList表现更好，因为现代CPU对连续内存的缓存命中率更高

选型建议：

  • 默认选择ArrayList

  • 只有当你确定需要频繁在头部操作，或需要实现队列时，才考虑LinkedList

2.1.4 Vector（了解即可）

Vector是Java早期的动态数组实现，和ArrayList非常相似，但它是线程安全的。

java

Vector<String> vector = new Vector<>();
vector.add("元素");

与ArrayList的区别：

  • Vector的方法都加了synchronized，线程安全但性能较差

  • Vector扩容时默认翻倍，ArrayList是1.5倍

在实际开发中，基本不再使用Vector。如果需要线程安全的List，可以使用：

java

List<String> list = Collections.synchronizedList(new ArrayList<>());

或者使用CopyOnWriteArrayList（适用于读多写少的场景）。

2.2 Set：元素不可重复的集合

Set的特点是：元素不重复。它就像数学中的集合，可以执行并集、交集等操作。

2.2.1 HashSet

底层实现：HashMap

HashSet是最常用的Set实现。你可能很好奇：Set是单元素集合，为什么底层是Map？答案是：HashSet把元素作为Map的Key，Value用一个固定的占位对象填充。

java

Set<String> set = new HashSet<>();

// 添加元素
set.add("苹果");
set.add("香蕉");
set.add("苹果");  // 返回false，添加失败，因为已存在

// 删除元素
set.remove("苹果");

// 判断是否包含
boolean hasBanana = set.contains("香蕉");

// 获取大小
int size = set.size();

// 遍历
for (String s : set) {
    System.out.println(s);
}

核心特点：

  • 元素无序（不保证遍历顺序和插入顺序一致）

  • 元素不重复

  • 允许一个null值

  • 添加、删除、查找的时间复杂度都是O(1)（假设哈希函数良好）

如何保证元素不重复：

当你调用add(e)时，HashSet会调用HashMap的put(e, PRESENT)方法。HashMap判断两个key是否相等的规则是：

  1. 先比较两个key的hashCode是否相等

  2. 如果hashCode相等，再比较equals是否相等

因此，存入HashSet的元素必须正确重写hashCode和equals方法。

使用场景：

  • 需要去重，不关心顺序

  • 快速查找某个元素是否存在

2.2.2 LinkedHashSet

底层实现：LinkedHashMap

LinkedHashSet是HashSet的子类，它在HashSet的基础上维护了一个双向链表，用来记录元素的插入顺序。

java

Set<String> set = new LinkedHashSet<>();

set.add("香蕉");
set.add("苹果");
set.add("橘子");

System.out.println(set);  // 输出：[香蕉, 苹果, 橘子]（保持插入顺序）

核心特点：

  • 维护插入顺序（或访问顺序，需配置）

  • 性能略低于HashSet

  • 其他特性和HashSet一样

使用场景：

  • 需要去重，同时需要保持元素的插入顺序

2.2.3 TreeSet

底层实现：TreeMap（红黑树）

TreeSet是有序的Set实现。元素会按照自然顺序，或者你指定的Comparator进行排序。

java

// 自然顺序（数字从小到大，字母从A到Z）
Set<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(1);
numbers.add(3);
System.out.println(numbers);  // 输出：[1, 3, 5]

// 自定义排序（倒序）
Set<String> names = new TreeSet<>((a, b) -> b.compareTo(a));
names.add("张三");
names.add("李四");
names.add("王五");
System.out.println(names);  // 输出：[王五, 李四, 张三]

TreeSet提供了一些额外的方法：

java

TreeSet<Integer> set = new TreeSet<>();
set.add(1);
set.add(3);
set.add(5);
set.add(7);
set.add(9);

// 获取第一个和最后一个
int first = set.first();   // 1
int last = set.last();     // 9

// 获取大于等于给定值的最小元素
int ceiling = set.ceiling(4);   // 5

// 获取小于等于给定值的最大元素
int floor = set.floor(4);       // 3

// 获取严格大于给定值的最小元素
int higher = set.higher(5);     // 7

// 获取严格小于给定值的最大元素
int lower = set.lower(5);       // 3

// 获取子集
Set<Integer> subSet = set.subSet(3, 8);  // [3, 5, 7]

核心特点：

  • 元素自动排序

  • 元素不可重复

  • 不能包含null（除非Comparator允许）

  • 添加、删除、查找的时间复杂度都是O(log n)

使用场景：

  • 需要元素自动排序

  • 需要进行范围查找（如查询某个区间的数据）

  • 需要获取最大/最小值

2.3 Queue：队列

Queue是Java中的队列接口，遵循FIFO（先进先出）原则。

2.3.1 ArrayDeque

ArrayDeque是双端队列（Deque）的实现，底层使用循环数组。

java

// 作为队列使用
Queue<String> queue = new ArrayDeque<>();
queue.offer("第一个人");
queue.offer("第二个人");
queue.offer("第三个人");

String first = queue.poll();  // 第一个人
String peek = queue.peek();   // 第二个人（查看不移除）

// 作为双端队列使用
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("头部元素");
deque.addLast("尾部元素");
String head = deque.removeFirst();
String tail = deque.removeLast();

核心特点：

  • 比LinkedList更节省内存（不需要存储节点指针）

  • 不允许存储null

  • 作为队列使用时，性能优于LinkedList

  • 不支持并发访问

使用场景：

  • 实现队列（FIFO）

  • 实现栈（LIFO）—— 推荐用ArrayDeque替代Stack类

2.3.2 PriorityQueue

PriorityQueue是优先级队列，元素按照优先级出队，而不是按照插入顺序。

java

// 最小堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.offer(8);

System.out.println(minHeap.poll());  // 1（最小值）
System.out.println(minHeap.poll());  // 3
System.out.println(minHeap.poll());  // 5

// 最大堆（自定义比较器）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);

System.out.println(maxHeap.poll());  // 5（最大值）

核心特点：

  • 底层是二叉堆（默认最小堆）

  • 时间复杂度：入队O(log n)、出队O(log n)、查看队首O(1)

  • 不保证元素顺序，只保证队首是最大或最小

  • 不允许null

  • 不是线程安全的

使用场景：

  • 任务调度（优先级高的先执行）

  • 求Top K元素

  • 数据流中的中位数问题

三、Map 体系详解

Map存储的是键值对（Key-Value），通过Key可以快速找到对应的Value。Key必须唯一，Value可以重复。

3.1 HashMap

HashMap是最常用的Map实现，也是面试的重点。

java

Map<String, Integer> map = new HashMap<>();

// 添加或修改
map.put("苹果", 5);    // 苹果对应5
map.put("香蕉", 3);
map.put("苹果", 10);   // 覆盖，苹果变成10

// 获取
Integer count = map.get("苹果");     // 10
Integer defaultValue = map.getOrDefault("橘子", 0);  // 0

// 检查是否存在
boolean hasApple = map.containsKey("苹果");   // true
boolean hasValue = map.containsValue(10);     // true

// 删除
map.remove("香蕉");

// 遍历方式1：遍历Entry（推荐）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + " = " + value);
}

// 遍历方式2：遍历Key
for (String key : map.keySet()) {
    Integer value = map.get(key);
}

// 遍历方式3：遍历Value
for (Integer value : map.values()) {
    System.out.println(value);
}

// 遍历方式4：forEach + Lambda（Java 8）
map.forEach((key, value) -> System.out.println(key + " = " + value));
核心原理

底层数据结构：

Java 8之后，HashMap的底层是：数组 + 链表 + 红黑树

  • 默认初始容量：16

  • 默认负载因子：0.75

  • 当链表长度达到8且数组长度达到64时，链表转换为红黑树

  • 当红黑树节点数降为6时，退化为链表

put方法的执行流程：

  1. 计算key的hash值

  2. 根据hash值计算数组索引位置

  3. 如果该位置为空，直接放入

  4. 如果该位置不为空，判断是链表还是红黑树，分别处理

  5. 如果key已存在，覆盖旧值

  6. 如果key不存在，插入新节点

  7. 如果size超过阈值，进行扩容

为什么负载因子是0.75：

这是时间和空间的平衡。负载因子越大，空间利用率越高，但哈希冲突概率增加，查询效率降低。0.75是经过大量测试得出的最优值。

为什么容量必须为2的幂：

因为计算索引时用的是(n - 1) & hash，当n为2的幂时，n-1的低位全是1，这样hash值的高位也能参与运算，减少哈希冲突。

扩容机制

当元素个数超过容量 * 负载因子时，HashMap会扩容为原来的2倍。

扩容时，旧数组中的元素需要重新计算索引位置。Java 8对此做了优化：重新计算后，元素要么留在原位置，要么移动到原位置 + 原容量的位置，不需要重新计算hash。

使用场景：

  • 绝大多数需要键值对的场景

  • 不需要线程安全

  • 不关心元素顺序

3.2 LinkedHashMap

LinkedHashMap继承自HashMap，它在HashMap的基础上维护了一个双向链表，用来记录键值对的顺序。

java

// 保持插入顺序
Map<String, Integer> map = new LinkedHashMap<>();
map.put("香蕉", 3);
map.put("苹果", 5);
map.put("橘子", 2);

System.out.println(map.keySet());  // 输出：[香蕉, 苹果, 橘子]

两种顺序模式：

  1. 插入顺序（默认）：按照元素插入的顺序遍历

  2. 访问顺序：按照元素被访问的顺序遍历，最近访问的放到最后

java

// 使用访问顺序模式
Map<String, Integer> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put("A", 1);
lruMap.put("B", 2);
lruMap.put("C", 3);

lruMap.get("A");  // 访问A，A被移到最后

System.out.println(lruMap.keySet());  // 输出：[B, C, A]

实现LRU缓存：

利用LinkedHashMap的访问顺序模式，可以轻松实现LRU（最近最少使用）缓存：

java

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// 使用
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("key1", "value1");
cache.put("key2", "value2");
cache.put("key3", "value3");
cache.put("key4", "value4");  // key1被移除

使用场景：

  • 需要保持元素的插入顺序

  • 实现LRU缓存

3.3 TreeMap

TreeMap是基于红黑树实现的有序Map。键会自动排序（自然顺序或自定义顺序）。

java

// 自然顺序
Map<String, Integer> map = new TreeMap<>();
map.put("张三", 25);
map.put("李四", 30);
map.put("王五", 28);

System.out.println(map.keySet());  // [张三, 李四, 王五]（按拼音排序）

// 自定义顺序（按照年龄降序排序键）
TreeMap<Integer, String> ageMap = new TreeMap<>((a, b) -> b - a);

TreeMap提供了丰富的方法：

java

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "a");
map.put(3, "c");
map.put(5, "e");
map.put(7, "g");
map.put(9, "i");

// 获取第一个和最后一个
Map.Entry<Integer, String> first = map.firstEntry();   // 1=a
Map.Entry<Integer, String> last = map.lastEntry();     // 9=i

// 获取小于等于给定key的最大key
Map.Entry<Integer, String> floor = map.floorEntry(4);   // 3=c

// 获取大于等于给定key的最小key
Map.Entry<Integer, String> ceiling = map.ceilingEntry(4); // 5=e

// 获取子Map（前闭后开）
SortedMap<Integer, String> subMap = map.subMap(3, 8);  // {3=c,5=e,7=g}

为什么使用红黑树：

红黑树是一种自平衡二叉查找树，能够保证：

  • 查找、插入、删除的时间复杂度都是O(log n)

  • 能够保持元素的有序性

使用场景：

  • 需要键自动排序

  • 需要进行范围查找（如查询某个区间的数据）

  • 需要获取最大键、最小键

3.4 ConcurrentHashMap

ConcurrentHashMap是线程安全的HashMap实现。

核心特点：

  • 读操作无锁，写操作只锁当前桶

  • 支持高并发读写

  • 不允许null的key和value

与Hashtable的区别：

  • Hashtable是直接在方法上加synchronized，锁整个表，并发性能差

  • ConcurrentHashMap使用更精细的锁机制，并发性能好

java

// 创建ConcurrentHashMap
Map<String, Integer> map = new ConcurrentHashMap<>();

// 线程安全的各种操作
map.put("key", 1);
map.get("key");
map.remove("key");

// 原子操作
map.putIfAbsent("key", 100);  // 如果key不存在才放入

// 并发安全的遍历
map.forEach((key, value) -> System.out.println(key + "=" + value));

使用场景：

  • 多线程环境下需要使用Map

  • 性能要求较高的场景

四、Collections工具类

Collections是Java提供的集合工具类，提供了很多实用的静态方法。

java

// 排序（List必须是可排序的，元素实现了Comparable）
Collections.sort(list);

// 自定义排序
Collections.sort(list, (a, b) -> b.compareTo(a));

// 反转
Collections.reverse(list);

// 随机打乱
Collections.shuffle(list);

// 二分查找（必须先排序）
int index = Collections.binarySearch(list, "查找的元素");

// 最值
Integer max = Collections.max(list);
Integer min = Collections.min(list);

// 线程安全包装
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>());

// 不可变集合
List<String> immutableList = Collections.unmodifiableList(list);
Set<String> immutableSet = Collections.unmodifiableSet(set);
Map<String, String> immutableMap = Collections.unmodifiableMap(map);

// Java 9+ 简化的不可变集合
List<String> list = List.of("a", "b", "c");
Set<String> set = Set.of("a", "b", "c");
Map<String, String> map = Map.of("k1", "v1", "k2", "v2");

// 空集合
List<String> emptyList = Collections.emptyList();
Set<String> emptySet = Collections.emptySet();
Map<String, String> emptyMap = Collections.emptyMap();

// 频率和替换
int frequency = Collections.frequency(list, "a");
Collections.replaceAll(list, "旧值", "新值");

五、选型速查表

需求场景 推荐集合 理由
存储列表，频繁随机访问 ArrayList O(1)的随机访问，内存连续
存储列表，频繁头尾操作 LinkedList/ArrayDeque 头尾操作O(1)
实现队列 ArrayDeque 性能好，内存省
实现栈 ArrayDeque 比Stack好
元素去重，不关顺序 HashSet O(1)的查找性能
元素去重，需保持顺序 LinkedHashSet 保持插入顺序
元素去重，需排序 TreeSet 自动排序
键值对，不关顺序 HashMap 通用性能最好
键值对，需保持插入顺序 LinkedHashMap 保持插入顺序
键值对，需排序 TreeMap 自动排序
键值对，多线程环境 ConcurrentHashMap 高并发安全
优先级任务 PriorityQueue 按优先级处理
LRU缓存 LinkedHashMap 内置访问顺序模式

六、常见面试题速答

Q1：ArrayList和LinkedList的区别？

底层：数组 vs 双向链表；随机访问：O(1) vs O(n)；头尾操作：O(n) vs O(1)；内存：连续 vs 分散。

Q2：HashSet如何保证元素不重复？

底层是HashMap，元素作为key存入，value是固定对象。HashMap通过hashCode和equals判断key是否重复。

Q3：HashMap的扩容机制是什么？

当size > 容量 * 0.75时，容量翻倍，重新计算每个元素的位置。Java 8优化后，元素要么在原位置，要么在原位置+原容量。

Q4：ConcurrentHashMap为什么线程安全？

JDK 1.8中，使用CAS + synchronized，只锁住当前桶的头节点，读操作无锁，并发性能好。

Q5：TreeMap和HashMap的区别？

TreeMap有序（红黑树），HashMap无序；TreeMap时间复杂度O(log n)，HashMap O(1)；TreeMap支持范围查询，不支持null key（除非特殊处理）。

Q6：LinkedHashMap如何实现LRU？

构造函数中设置accessOrder=true，开启访问顺序模式，重写removeEldestEntry方法，当size超过限制时移除最老元素。

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

为了用按位与运算替代取模运算，提高性能，同时让哈希值的高位也能参与索引计算，减少冲突。

Q8：fail-fast和fail-safe的区别？

fail-fast：检测到并发修改立即抛异常（如HashMap迭代时）；fail-safe：在副本上操作，不抛异常（如ConcurrentHashMap）。

七、写在最后

集合框架是Java编程的基础，也是面试的重点。掌握好它们，不仅能写出更高效的代码，也能在面试中更有底气。

如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、转发。

# python # windows # 开发语言
Logo
亚马逊云科技技术品牌专区

更多推荐

Kiro Editor 开发实战：使用 Cargo 构建、测试与性能优化指南

欢迎来到这篇终极指南，我们将深入探索如何使用Rust构建高性能的终端文本编辑器Kiro Editor。无论你是Rust新手还是经验丰富的开发者，这篇完整教程将带你了解如何利用Cargo工具链进行高效的开发、测试和性能优化，打造一款快速、轻量且功能强大的UTF-8文本编辑器。## 什么是Kiro Editor？Kiro Editor是一款使用Rust编写的极简终端文本编辑器，它最初是著名编辑

avatar 亚马逊云科技技术品牌专区

近期零基础学量化，先按基础差异拆学习顺序

读者应明白，拆解学习顺序时要先看自己的基础缺口，再决定哪一段需要放慢。不同流程阶段都有不同检查任务，学习路线要能反映这些差异。

avatar 亚马逊云科技技术品牌专区

2026年量化工具选择，要跟着能力基础走

读者应理解，选择工具前要先判断自己的能力基础和当前任务。工具应该帮助自己补上当前最关键的缺口，而不是替代学习顺序本身。

avatar 亚马逊云科技技术品牌专区