返回学习记录

Learning archive

Java 集合模块学习记录

系统梳理 Java 集合框架的核心接口、常用实现、底层原理、遍历陷阱与选型建议。

2026年10月30日
  • Java
  • 集合框架
  • 学习笔记

Java 集合模块学习记录#

本文档记录 Java 集合框架(Collections Framework)的核心知识点、底层原理与常用示例代码。 适合作为学习笔记、复习资料与面试准备。


一、集合框架总览#

Java 集合框架提供了一套用于存储和操作一组对象的工具类,位于 java.util 包中。

1.1 整体结构#

Collection(接口)
├── List(有序、可重复、有索引)
│   ├── ArrayList
│   ├── LinkedList
│   └── Vector(线程安全)
├── Set(无序、不可重复)
│   ├── HashSet
│   ├── LinkedHashSet(有序)
│   └── TreeSet(可排序)
└── Queue(队列)
    ├── LinkedList
    ├── PriorityQueue
    └── Deque → ArrayDeque

Map(接口,键值对,不属于 Collection)
├── HashMap
├── LinkedHashMap(有序)
├── TreeMap(可排序)
├── Hashtable(线程安全,已过时)
└── ConcurrentHashMap(线程安全,推荐)

1.2 两大核心接口#

接口特点常用实现
Collection存储单个元素的集合List / Set / Queue
Map存储键值对(key-value)HashMap / TreeMap

重点: Map 不属于 Collection 体系,它是独立的顶层接口。


二、List 体系#

List 的特点:有序、可重复、支持索引访问。

2.1 ArrayList#

底层结构: 动态数组(Object[] elementData)

特点:

  • 随机访问快(get O(1))
  • 尾部插入快,中间/头部插入删除慢(需移动元素)
  • 线程不安全

扩容机制:

  • 默认初始容量 10(首次添加元素时才分配)
  • 扩容为原来的 1.5 倍:newCapacity = oldCapacity + (oldCapacity >> 1)

常用方法示例:

import java.util.ArrayList;
import java.util.List;

public class ArrayListDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("Java");        // 添加元素
        list.add("Python");
        list.add(1, "C++");      // 指定索引插入

        System.out.println(list);            // [Java, C++, Python]
        System.out.println(list.get(0));     // Java
        System.out.println(list.size());     // 3
        System.out.println(list.contains("Java")); // true

        list.set(0, "Go");       // 修改元素
        list.remove("Python");   // 按值删除
        list.remove(0);          // 按索引删除

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

2.2 LinkedList#

底层结构: 双向链表(Node { prev, item, next })

特点:

  • 随机访问慢(get O(n),需遍历)
  • 头尾插入删除快(O(1))
  • 实现了 Deque,可作为队列/双端队列使用
  • 线程不安全

示例:

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("A");
        list.add("B");
        list.addFirst("Start");   // 头部添加
        list.addLast("End");      // 尾部添加

        System.out.println(list);          // [Start, A, B, End]
        System.out.println(list.getFirst()); // Start
        System.out.println(list.getLast());  // End

        list.removeFirst();
        list.removeLast();
        System.out.println(list);          // [A, B]
    }
}

2.3 ArrayList vs LinkedList#

对比项ArrayListLinkedList
底层结构动态数组双向链表
随机访问O(1) 快O(n) 慢
头尾插入删除慢(需移动)O(1) 快
中间插入删除慢慢(需先找到位置)
内存占用较少(连续内存)较多(每个节点存前后指针)
适用场景查询多频繁增删

2.4 Vector#

  • 底层也是数组,线程安全(方法加 synchronized)
  • 扩容为原来 2 倍
  • 效率低,已被 Collections.synchronizedList() 或 CopyOnWriteArrayList 替代

三、Set 体系#

Set 的特点:不可重复(元素唯一)。

3.1 HashSet#

底层结构: 基于 HashMap,元素作为 key 存储(value 是固定的 PRESENT 对象)。

特点:

  • 无序(不保证插入顺序)
  • 元素唯一
  • 允许一个 null 元素
  • 依赖元素的 hashCode() 和 equals() 保证唯一性

去重原理: 添加元素时,先计算 hashCode 定位桶,再比较 equals,两者都相同才视为重复。

示例:

import java.util.HashSet;
import java.util.Set;

public class HashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("Java");
        set.add("Python");
        set.add("Java");        // 重复,添加失败,返回 false

        System.out.println(set);         // [Java, Python]
        System.out.println(set.size());  // 2
        System.out.println(set.contains("Java")); // true

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

自定义对象去重示例:

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Student {
    private int id;
    private String name;

    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    // 必须重写 hashCode 和 equals 才能正确去重
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return id == student.id && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    public static void main(String[] args) {
        Set<Student> set = new HashSet<>();
        set.add(new Student(1, "张三"));
        set.add(new Student(1, "张三")); // hashCode 和 equals 相同,视为重复
        System.out.println(set.size());  // 1
    }
}

3.2 LinkedHashSet#

  • 继承 HashSet,底层使用 LinkedHashMap
  • 保留插入顺序(维护了一条双向链表)
  • 元素唯一,性能略低于 HashSet
import java.util.LinkedHashSet;
import java.util.Set;

Set<String> set = new LinkedHashSet<>();
set.add("B");
set.add("A");
set.add("C");
System.out.println(set); // [B, A, C] —— 保持插入顺序

3.3 TreeSet#

底层结构: 基于 TreeMap(红黑树)。

特点:

  • 自动排序(自然顺序或自定义 Comparator)
  • 元素唯一
  • 不允许 null(会抛 NullPointerException)
  • 增删查时间复杂度 O(log n)
import java.util.Set;
import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(5);
        set.add(1);
        set.add(3);
        System.out.println(set); // [1, 3, 5] —— 自动升序

        // 自定义 Comparator:降序
        Set<Integer> desc = new TreeSet<>((a, b) -> b - a);
        desc.add(5);
        desc.add(1);
        desc.add(3);
        System.out.println(desc); // [5, 3, 1]
    }
}

3.4 三种 Set 对比#

对比项HashSetLinkedHashSetTreeSet
底层结构HashMapLinkedHashMapTreeMap(红黑树)
顺序无序插入顺序排序顺序
性能最快略慢较慢(O(log n))
null 元素允许 1 个允许 1 个不允许

四、Map 体系#

Map 存储 键值对,key 唯一,value 可重复。

4.1 HashMap(重点)#

底层结构(JDK 8+): 数组 + 链表 + 红黑树

核心机制:

  • 通过 key 的 hashCode() 扰动计算得到 hash 值
  • 通过 (n - 1) & hash 计算数组下标(n 为数组长度,容量为 2 的幂)
  • 哈希冲突时挂在链表上,链表长度 > 8 且数组容量 ≥ 64 时转为红黑树
  • 默认容量 16,负载因子 0.75,扩容为原来的 2 倍
  • 允许一个 null key 和多个 null value
  • 线程不安全

put 流程简化:

  1. 计算 key 的 hash
  2. 定位数组下标,桶为空则直接放入
  3. 桶不为空:遍历链表/红黑树,key 相同则覆盖 value,否则追加到链表尾部
  4. 判断是否需要树化、是否需要扩容

常用方法示例:

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("Java", 95);      // 添加/覆盖
        map.put("Python", 88);
        map.put("C++", 90);

        System.out.println(map.get("Java"));       // 95
        System.out.println(map.containsKey("Go"));  // false
        System.out.println(map.size());             // 3

        map.put("Java", 100);      // 覆盖旧值
        System.out.println(map.get("Java"));        // 100

        map.remove("C++");         // 删除

        // 遍历方式一:entrySet(推荐,效率高)
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }

        // 遍历方式二:keySet
        for (String key : map.keySet()) {
            System.out.println(key + " -> " + map.get(key));
        }

        // 遍历方式三:forEach(Java 8+)
        map.forEach((k, v) -> System.out.println(k + " " + v));
    }
}

常用实用方法:

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);

map.getOrDefault("b", 0);                 // 不存在时返回默认值 0
map.putIfAbsent("a", 100);                // 已存在则不覆盖
map.computeIfAbsent("c", k -> 10);        // 不存在才计算并放入
map.merge("a", 1, Integer::sum);          // 合并值,a 变为 2

4.2 LinkedHashMap#

  • 继承 HashMap,在节点上增加了 before/after 指针维护双向链表
  • 保留插入顺序(或访问顺序)
  • 可实现 LRU 缓存(构造参数 accessOrder = true)
import java.util.LinkedHashMap;
import java.util.Map;

// LRU 缓存示例:控制容量为 3
public class LRUCacheDemo {
    public static void main(String[] args) {
        Map<Integer, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
                return size() > 3; // 超过 3 个就淘汰最久未访问的
            }
        };
        lru.put(1, "A");
        lru.put(2, "B");
        lru.put(3, "C");
        lru.get(1);        // 访问 1,1 变为最近使用
        lru.put(4, "D");   // 容量超限,淘汰最久未访问的 2
        System.out.println(lru); // {3=C, 1=A, 4=D}
    }
}

4.3 TreeMap#

  • 基于 红黑树,key 自动排序
  • key 不能为 null
  • 增删查 O(log n)
  • 可实现范围查找(headMap、tailMap、subMap)
import java.util.Map;
import java.util.TreeMap;

Map<Integer, String> map = new TreeMap<>();
map.put(30, "C");
map.put(10, "A");
map.put(20, "B");
System.out.println(map);                 // {10=A, 20=B, 30=C}
System.out.println(map.firstKey());      // 10
System.out.println(map.headMap(25));     // {10=A, 20=B}

4.4 Hashtable 与 ConcurrentHashMap#

对比项HashMapHashtableConcurrentHashMap
线程安全否是(全表锁)是(分段/CAS + synchronized)
性能最高低高
null 键值允许不允许不允许
推荐度单线程首选已过时多线程首选
import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("count", 1);
map.computeIfAbsent("a", k -> 0);
map.merge("count", 1, Integer::sum); // 线程安全的累加

五、迭代器与遍历#

5.1 Iterator#

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class IteratorDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String s = it.next();
            if ("B".equals(s)) {
                it.remove(); // 推荐用迭代器的 remove 删除元素
            }
        }
        System.out.println(list); // [A, C]
    }
}

5.2 重要陷阱:ConcurrentModificationException#

错误写法: 用增强 for 循环遍历时直接调用集合的 remove()

// ❌ 错误:会抛 ConcurrentModificationException
for (String s : list) {
    if ("B".equals(s)) {
        list.remove(s);
    }
}

原因: 增强 for 底层是迭代器,集合的 remove() 会修改 modCount,而迭代器检查时发现 modCount != expectedModCount,抛出异常。

正确写法:

// ✅ 方式一:使用 Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if ("B".equals(it.next())) {
        it.remove();
    }
}

// ✅ 方式二:Java 8+ 的 removeIf
list.removeIf("B"::equals);

六、Collections 工具类#

Collections 是操作集合的工具类(注意与 Collection 接口区分)。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Collections.addAll(list, 3, 1, 2);   // 批量添加
        Collections.sort(list);              // 排序:[1, 2, 3]
        Collections.reverse(list);           // 反转:[3, 2, 1]
        Collections.shuffle(list);           // 随机打乱
        System.out.println(Collections.max(list)); // 最大值
        System.out.println(Collections.min(list)); // 最小值

        // 线程安全包装
        List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());

        // 不可变集合
        List<Integer> immutable = Collections.unmodifiableList(list);
    }
}

七、泛型在集合中的应用#

泛型让集合在编译期就能检查类型安全,避免强制类型转换。

import java.util.ArrayList;
import java.util.List;

// 泛型集合:只能存 String
List<String> names = new ArrayList<>();
names.add("张三");
// names.add(123); // ❌ 编译报错,类型不安全

// 通配符
// List<?>            任意类型
// List<? extends T>  上界,只能读
// List<? super T>    下界,只能写
public static void printAll(List<? extends Number> list) {
    for (Number n : list) {
        System.out.println(n);
    }
}

八、集合选择建议#

需求推荐集合理由
大量随机访问ArrayListget 为 O(1)
频繁头尾增删LinkedList链表 O(1)
元素去重、无需顺序HashSet去重最快
去重且保持插入顺序LinkedHashSet有顺序
去重且自动排序TreeSet红黑树排序
键值对、单线程HashMap性能最好
键值对、保持顺序LinkedHashMap插入顺序
键值对、按 key 排序TreeMap红黑树排序
键值对、多线程ConcurrentHashMap线程安全且高效
队列/栈ArrayDeque比 Stack/LinkedList 更优

九、常见面试题 & 易错点#

9.1 为什么 HashMap 的容量是 2 的幂?#

  • 因为计算下标使用 (n - 1) & hash,当 n 为 2 的幂时,n - 1 的二进制全是 1,能让 hash 的低位全部参与运算,减少哈希冲突,使分布更均匀。

9.2 HashMap 为什么线程不安全?#

  • 多线程同时 put 可能造成数据覆盖(JDK 8 前还有死循环问题)。
  • 多线程场景应使用 ConcurrentHashMap。

9.3 重写 equals 为什么必须重写 hashCode?#

  • 约定:equals 相等的两个对象,hashCode 必须相同。
  • 若只重写 equals,对象放入 HashSet 或作为 HashMap 的 key 时,可能因 hash 不同而无法正确去重/查找。

9.4 数组和集合的区别?#

对比项数组集合
长度固定可变
存储类型基本类型 + 引用类型只能存对象(引用类型)
功能简单丰富(增删改查、排序等)

9.5 List 去重有哪几种方式?#

import java.util.*;

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 2, 3, 3, 3));

// 方式一:利用 Set 去重
Set<Integer> set = new LinkedHashSet<>(list);
List<Integer> result1 = new ArrayList<>(set);

// 方式二:Stream 去重
List<Integer> result2 = list.stream().distinct().collect(java.util.stream.Collectors.toList());

// 方式三:contains 判断(效率低)
List<Integer> result3 = new ArrayList<>();
for (Integer i : list) {
    if (!result3.contains(i)) {
        result3.add(i);
    }
}

9.6 ArrayList 遍历删除的正确姿势?#

见 5.2 节,推荐使用 Iterator.remove() 或 removeIf()。


十、知识总结#

  1. 集合分类: Collection(List / Set / Queue)与 Map 两大体系。
  2. List 有序可重复: ArrayList 查快、LinkedList 增删快。
  3. Set 不可重复: HashSet 无序、LinkedHashSet 有序、TreeSet 排序。
  4. Map 键值对: HashMap 是核心,JDK 8 后为"数组+链表+红黑树"。
  5. 线程安全: 优先 ConcurrentHashMap,而非 Hashtable。
  6. 遍历删除: 使用 Iterator.remove() 或 removeIf(),避免 ConcurrentModificationException。
  7. 选择原则: 根据"是否去重、是否需要顺序、读写场景、是否线程安全"综合选择。

学习建议:多用 Debug 查看 ArrayList 扩容和 HashMap 桶结构,结合源码理解原理,效果更佳。

页内目录10 章