详解Java容器集合框架

作者：袖梨 2026-06-16

本篇文章涵盖 ArrayList/LinkedList 源码细节、HashMap 完整原理（含红黑树、扩容、扰动函数）、Set 底层实现、迭代器 fail-fast 机制、并发容器简介、Comparable/Comparator 深入、Collections 工具类全解、Properties 详解 以及 实际开发建议。所有代码均可直接运行。

一、容器概览与设计目的

1.1 为什么需要容器（集合框架）

  • 数组的局限：长度固定，只能存储同类型元素，增删操作需要手动移动元素。
  • 动态管理：程序运行时无法预知需要存储多少对象（如数据库查询结果）。
  • 统一操作：Java 集合框架提供统一的接口和算法，降低学习成本。

1.2 容器框架的核心接口

Iterable (根接口，提供 for-each 支持)
│
└── Collection
     ├── List
     ├── Set
     └── Queue
Map (独立分支)
  • Collection：单值存储。
  • Map：键值对存储。

Java容器集合框架详解

二、List 接口详解

2.1 ArrayList 源码核心（JDK 1.8）

2.1.1 底层结构

transient Object[] elementData;   // 存储元素的数组
private int size;                 // 实际元素个数

2.1.2 构造方法

// 无参构造：初始为空数组，第一次 add 时扩容到 10
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 指定初始容量
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

2.1.3 扩容机制

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
  • 每次扩容为原来的 1.5 倍（oldCapacity + oldCapacity / 2）。
  • 使用 Arrays.copyOf 复制原数组，开销较大。
  • 建议：如果能预估元素个数，使用 ArrayList(int initialCapacity) 减少扩容。

2.1.4 add 和 remove 的时间复杂度

操作时间复杂度说明
尾部添加 add(e)均摊 O(1)偶尔扩容 O(n)
指定位置添加 add(i, e)O(n)需要移动元素
尾部删除 remove(size-1)O(1)直接置 null
指定位置删除 remove(i)O(n)移动元素
随机访问 get(i)O(1)数组特性

2.2 LinkedList 源码核心

2.2.1 底层双向链表节点

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

2.2.2 关键字段

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

2.2.3 插入与删除效率

  • 在头部或尾部插入/删除：O(1)（addFirst、addLast、removeFirst、removeLast）。
  • 在指定位置插入/删除：需要先遍历到该位置 O(n)，然后再修改前后指针 O(1)。
  • 随机访问 get(index)：O(n)，需要通过循环或二分折半查找。

2.2.4 LinkedList 作为双端队列

实现了 Deque 接口，可当作栈、队列使用。

Deque<String> stack = new LinkedList<>();
stack.push("A");     // 压栈
String top = stack.pop();   // 弹栈
Deque<String> queue = new LinkedList<>();
queue.offer("A");    // 入队
String head = queue.poll(); // 出队

2.3 Vector 与 Stack（不推荐使用）

  • Vector 与 ArrayList 类似，但方法使用 synchronized 修饰，线程安全，但性能差。
  • Stack 继承 Vector，被 Deque 取代。

三、Set 接口详解

3.1 HashSet 底层 —— 实际上是一个 HashMap

public class HashSet<E> extends AbstractSet<E> implements Set<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;
    }
}
  • HashSet 的元素作为 HashMap 的 Key，Value 是一个固定的占位对象 PRESENT。
  • 因此元素的唯一性完全由 HashMap 的 Key 唯一性保证。

3.2 重写 hashCode 和 equals 的必要性

  • HashSet 判断两个对象是否相等：先比较 hashCode()，若相等再比较 equals()。
  • 若只重写 equals 而不重写 hashCode，则两个逻辑相等的对象可能被放入不同桶中，导致重复。
  • 必须同时重写，且保持一致。

3.3 LinkedHashSet

  • 继承 HashSet，底层使用 LinkedHashMap，维护插入顺序的双向链表。
  • 遍历顺序与插入顺序一致。

3.4 TreeSet

  • 底层是 TreeMap（红黑树），元素可排序。
  • 元素必须实现 Comparable 或在构造时传入 Comparator。
Set<String> treeSet = new TreeSet<>();          // 自然排序
Set<String> treeSet2 = new TreeSet<>(Comparator.reverseOrder()); // 倒序

四、Map 接口详解（重点）

4.1 HashMap 核心原理（JDK 1.8）

4.1.1 数据结构

  • 数组 + 单向链表 + 红黑树。
  • 数组的每个元素称为桶（bucket），每个桶可以是链表或红黑树。

4.1.2 重要常量

常量默认值说明
DEFAULT_INITIAL_CAPACITY16默认初始容量
MAXIMUM_CAPACITY1 << 30最大容量
DEFAULT_LOAD_FACTOR0.75f默认加载因子
TREEIFY_THRESHOLD8链表长度 ≥ 8 且数组长度 ≥ 64 转红黑树
UNTREEIFY_THRESHOLD6树节点 ≤ 6 转回链表
MIN_TREEIFY_CAPACITY64链表树化最小数组长度

4.1.3 put 方法流程

  1. 计算 key 的 hash 值：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)（扰动函数，使高位参与运算，减少碰撞）。
  2. 计算桶索引：(n - 1) & hash（等价于 hash % n，但位运算更快）。
  3. 如果该桶为空，直接创建节点放入。
  4. 如果桶不为空，判断第一个节点是否与当前 key 相等（hash 相等且 equals），是则覆盖。
  5. 否则，如果是树节点，执行红黑树插入。
  6. 否则，遍历链表，若找到相同 key 则覆盖，否则在尾部插入新节点。
  7. 插入后检查链表长度是否 ≥ TREEIFY_THRESHOLD，是则转为红黑树。
  8. 检查 ++size > threshold，是则扩容。

4.1.4 扩容机制

  • 触发条件：size > capacity * loadFactor。
  • 新容量：oldCap << 1（翻倍）。
  • 重哈希：重新计算每个元素的桶位置。由于容量是 2 的幂，元素的新位置要么不变，要么变为 原位置 + oldCap，只需判断原 hash 的第 oldCap 位是否为 1，效率很高。
// 扩容后重新分配元素（简化示意）
if ((e.hash & oldCap) == 0) {
    // 保持原位置
} else {
    // 移动到 oldIndex + oldCap
}

4.1.5 加载因子为什么是 0.75

  • 空间利用率 与 冲突率 的折衷。
  • 过大（如 1.0）：空间利用率高，但链表变长，查询效率低。
  • 过小（如 0.5）：频繁扩容，空间浪费。
  • 0.75 是统计学上的经验值。

4.1.6 红黑树的作用

  • 当链表过长时，查找时间复杂度从 O(n) 降为 O(log n)。
  • 红黑树是一种近似平衡的二叉搜索树，插入删除也保持 O(log n)。

4.2 LinkedHashMap

  • 继承 HashMap，内部维护双向链表记录插入顺序或访问顺序（accessOrder）。
  • 可用于实现 LRU 缓存。
// 构造 accessOrder=true 表示按访问顺序排序
LinkedHashMap<K,V> lru = new LinkedHashMap<K,V>(16, 0.75f, true);

4.3 TreeMap

  • 基于红黑树，Key 可排序。
  • 支持 subMap、headMap、tailMap 等范围视图。

4.4 ConcurrentHashMap（简单介绍）

  • 线程安全的高性能 Map。
  • JDK 1.7 使用分段锁（Segment），JDK 1.8 使用 CAS + synchronized 锁头节点，粒度更细。
  • 读操作基本无锁，写操作只锁定当前桶。

五、迭代器与 fail-fast 机制

5.1 迭代器工作原理

每个集合有一个内部类实现 Iterator 接口，维护以下字段：

  • cursor：下一个返回元素的位置。
  • lastRet：最后一次返回的索引（用于 remove）。
  • expectedModCount：迭代器期望的集合修改次数（初始为 modCount）。

5.2 modCount 与 fail-fast

  • modCount 记录集合结构性修改次数（添加、删除、扩容等）。
  • 每次迭代器操作都会检查 modCount == expectedModCount，若不相等则抛出 ConcurrentModificationException，防止并发修改。

5.3 避免 ConcurrentModificationException

  • 使用迭代器自己的 remove 方法（会同步更新 expectedModCount）。
  • 使用 CopyOnWriteArrayList（写时复制，适合读多写少）。
  • 使用并发集合（ConcurrentHashMap 等）。
// 正确删除
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("B")) {
        it.remove();
    }
}
// Java 8 推荐的删除方式
list.removeIf(s -> s.equals("B"));

5.4 安全失败（fail-safe）机制

  • 并发集合（如 CopyOnWriteArrayList）在迭代时使用的是原集合的快照，不会抛异常，但无法感知迭代过程中的修改。

六、Collections 工具类全解

Java容器集合框架详解

方法描述示例
sort(List)自然排序Collections.sort(list)
sort(List, Comparator)定制排序Collections.sort(list, (a,b)->a-b)
reverse(List)反转顺序Collections.reverse(list)
shuffle(List)随机打乱Collections.shuffle(deck)
swap(List, i, j)交换元素Collections.swap(list,0,1)
rotate(List, distance)循环移动Collections.rotate(list, 2)
fill(List, obj)全部填充Collections.fill(list, null)
copy(dest, src)复制Collections.copy(dest, src)
replaceAll(list, oldVal, newVal)替换Collections.replaceAll(list, 0, -1)
binarySearch(List, key)二分查找Collections.binarySearch(list, 5)
max(Collection), min(Collection)最大最小值Collections.max(set)
frequency(Collection, obj)出现次数Collections.frequency(list, "A")
disjoint(c1, c2)是否无交集Collections.disjoint(set1, set2)
synchronizedXxx(collection)转为线程安全List<String> syncList = Collections.synchronizedList(new ArrayList<>())
unmodifiableXxx(collection)转为不可修改List<String> unmod = Collections.unmodifiableList(list)

七、Comparable 与 Comparator 深入

7.1 Comparable

  • 内置于类，实现 int compareTo(T o)。
  • 返回负数（当前对象小于参数）、0（相等）、正数（大于）。
  • 一旦定义，就是该类的自然排序顺序。
public class Employee implements Comparable<Employee> {
    private int salary;
    @Override
    public int compareTo(Employee o) {
        return Integer.compare(this.salary, o.salary);
    }
}

7.2 Comparator

  • 临时排序策略，实现 int compare(T o1, T o2)。
  • 可用于 TreeSet、TreeMap、Collections.sort 等。
Comparator<Employee> byName = (e1, e2) -> e1.getName().compareTo(e2.getName());
Comparator<Employee> bySalaryDesc = (e1, e2) -> Integer.compare(e2.getSalary(), e1.getSalary());
// 链式排序
Comparator<Employee> chain = Comparator.comparing(Employee::getDept)
                                       .thenComparing(Employee::getSalary);

7.3 区别总结

特性ComparableComparator
位置定义在类内部定义在外部独立
修改类需要修改原类无需修改原类
排序方式只能一种自然顺序可多种自定义顺序
方法compareTo(T o)compare(T o1, T o2)

八、Properties 详解

8.1 加载配置文件

Properties props = new Properties();
// 从类路径加载
try (InputStream in = Thread.currentThread().getContextClassLoader()
        .getResourceAsStream("config.properties")) {
    props.load(in);
}
// 从文件系统加载
try (FileInputStream fis = new FileInputStream("config.properties")) {
    props.load(fis);
}
// 读取属性，提供默认值
String dbUrl = props.getProperty("db.url", "jdbc:mysql://localhost:3306/test");

8.2 存储属性到文件

props.setProperty("app.name", "MyApp");
try (FileOutputStream out = new FileOutputStream("config.properties")) {
    props.store(out, "Application Configuration");
}

8.3 XML 格式属性文件

// 加载 XML
props.loadFromXML(in);
// 存储为 XML
props.storeToXML(out, "Comment");

九、实际开发中的选择建议

场景推荐集合
存储顺序重要，允许重复ArrayList
频繁在中间插入删除LinkedList
去重，不关心顺序HashSet
去重，需要保持插入顺序LinkedHashSet
去重，需要自动排序TreeSet
键值对，快速查找HashMap
键值对，需要保持插入顺序LinkedHashMap
键值对，需要按 Key 排序TreeMap
线程安全的键值对ConcurrentHashMap
读多写少的列表CopyOnWriteArrayList
配置文件Properties

十、常见面试题与陷阱

  • ArrayList 和 LinkedList 的区别
    • 底层结构：数组 vs 双向链表。
    • 随机访问：ArrayList O(1)，LinkedList O(n)。
    • 插入删除：ArrayList 尾部 O(1)，中间 O(n)；LinkedList 两端 O(1)，中间 O(n)。
    • 内存占用：ArrayList 可能有数组闲置空间；LinkedList 每个节点存储额外指针。
  • HashMap 容量为什么是 2 的幂
    • 为了使用 (n-1) & hash 代替 % 运算，提高速度。
    • 扩容时元素位置计算简单。
  • 如何保证 HashMap 线程安全
    • Collections.synchronizedMap(new HashMap<>())
    • ConcurrentHashMap（推荐）
  • HashSet 如何保证元素唯一
    • 利用 HashMap 的 Key 唯一性。
  • TreeSet 中元素如何排序
    • 实现 Comparable 或构造时传入 Comparator。
  • 迭代时删除元素为什么不能用 for-each
    • for-each 底层使用迭代器，但调用集合自身的 remove 会修改 modCount，导致迭代器检查失败抛出异常。

十一、代码演练

示例 1：使用 Comparator 实现多字段排序

class Person {
    String name;
    int age;
    // 构造器、getter、toString 省略
}
List<Person> persons = Arrays.asList(
    new Person("张三", 20),
    new Person("李四", 18),
    new Person("张三", 22)
);
persons.sort(Comparator.comparing(Person::getName)
                       .thenComparingInt(Person::getAge));

示例 2：使用 HashMap 统计单词频率

String text = "hello world hello java";
Map<String, Integer> freq = new HashMap<>();
for (String word : text.split(" ")) {
    freq.merge(word, 1, Integer::sum);
}
System.out.println(freq);  // {hello=2, world=1, java=1}

示例 3：利用 LinkedHashMap 实现 LRU 缓存

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

十二、后续进阶

  • 掌握 ArrayList、LinkedList、HashMap、HashSet 的底层原理是面试和开发的基础。
  • 理解 fail-fast 机制，避免在遍历时修改集合。
  • 正确使用 Comparable 和 Comparator，编写灵活的排序逻辑。
  • 多线程环境优先使用 ConcurrentHashMap 而非同步包装类。
  • 善用 Collections 工具类简化代码。

也可以深入学习 源码分析 和 并发集合，进一步理解 Java 容器的设计精髓。

相关文章

精彩推荐