第16章 集合框架：List 与 Set

第16章 集合框架：List 与 Set

数组长度固定，无法满足动态需求。集合（Collection）是 Java 提供的"可动态增长"的容器。本节重点学习 List 与 Set 两大接口及常用实现。

一、集合框架概览

先看数组的痛点——长度一旦确定就改不了：String[] arr = new String[3]只能放 3 个元素，第 4 个直接ArrayIndexOutOfBoundsException。集合就是为了解决"长度动态变化"而生的：想加就加、想删就删，不用管容量。整个集合框架分两大阵营：

Collection（单列集合） ├── List 有序、可重复 │ ├── ArrayList 底层数组，查询快增删慢 │ ├── LinkedList 底层链表，增删快查询慢 │ └── Vector 线程安全（老式，已少用） ├── Set 无序（部分有序）、不可重复 │ ├── HashSet 底层 HashMap，无序 │ ├── LinkedHashSet 底层 LinkedHashMap，按插入顺序 │ └── TreeSet 底层红黑树，自动排序 └── Queue 队列（先进先出） Map（双列集合，键值对）→ 下一节讲

最常用的三个实现：ArrayList、HashSet、HashMap，记住"List 有序可重复、Set 无序不可重复"。

二、List 接口

List 是有序集合，元素可重复，可以通过下标访问。它有两个关键特性：元素按插入顺序排列、每个元素有下标——这决定了它"像数组一样好查"。

ArrayList（最常用）

底层是可变数组，查询快、增删慢（中间插入要移动元素）：

importjava.util.ArrayList;importjava.util.List;List<String>list=newArrayList<>();list.add("Java");// 追加元素list.add("Python");list.add("Go");list.add(1,"C++");// 在指定下标插入System.out.println(list);// [Java, C++, Python, Go]System.out.println(list.size());// 4System.out.println(list.get(0));// Java：按下标取System.out.println(list.contains("Go"));// truelist.remove(0);// 按下标删除list.remove("Go");// 按内容删除

为什么"查询快、增删慢"？数组在内存里是连续空间，按下标直接定位（O(1)）；而中间插入/删除要整体"挪位置"（O(n)）。查找还有indexOf(x)/lastIndexOf(x)（第一次/最后一次出现的位置），找不到返回 -1。

LinkedList

底层是双向链表，增删快、查询慢：

LinkedList<String>linkedList=newLinkedList<>();linkedList.addFirst("头");// 头部添加linkedList.addLast("尾");// 尾部添加linkedList.removeFirst();// 删除头部

LinkedList 实现了 Deque 接口，常用作栈或队列：

// 当栈用（后进先出）Deque<String>stack=newLinkedList<>();stack.push("A");stack.push("B");System.out.println(stack.pop());// BSystem.out.println(stack.peek());// A：只看栈顶// 当队列用（先进先出）Queue<String>queue=newLinkedList<>();queue.offer("1号");queue.offer("2号");System.out.println(queue.poll());// 1号

选择建议

• 大多数场景（遍历、按下标查）→ArrayList
• 频繁在头部/中间增删 → LinkedList

实际开发里 90% 场景用 ArrayList 就够，LinkedList 更多用在队列、栈。

三、遍历 List 的四种方式

// JDK 11 和 17 里可以直接用 List.of 快速创建不可变列表// （JDK 8 没有这个写法，要用 Arrays.asList 或手动 add）List<String>list=List.of("Java","Python","Go");// 方式一：普通 for（需要下标）for(inti=0;i<list.size();i++){System.out.println(list.get(i));}// 方式二：增强 for（最常用）for(Stringlang:list){System.out.println(lang);}// 方式三：Iterator 迭代器Iterator<String>it=list.iterator();while(it.hasNext()){System.out.println(it.next());}// 方式四：Lambda（JDK 8+，简洁）list.forEach(lang->System.out.println(lang));

增强 for 遍历时不能同时修改集合（会抛 ConcurrentModificationException），要删除元素用 Iterator 的remove()或 for 倒序删除。

四、Set 接口

Set 是不可重复的集合，不能按下标访问。Set 的"去重"能力靠的是哈希，先看最常用的 HashSet。

HashSet（最常用）

底层是 HashMap，无序（不保证迭代顺序），去重核心：

Set<String>set=newHashSet<>();set.add("apple");set.add("banana");set.add("apple");// 重复元素：添加失败，不报错System.out.println(set);// [banana, apple]（顺序不固定）System.out.println(set.size());// 2：去重成功

为什么"无序"？元素存到哪个位置由hashCode()算出的哈希桶决定，跟插入顺序无关，别依赖迭代顺序。

去重的原理

HashSet 判断元素是否重复：先看hashCode()，hashCode 相同再看equals()。

因此：自定义类的对象放进 HashSet，必须同时重写hashCode()和equals()，否则两个内容相同的对象会被当成不同元素。

classStudent{Stringname;intage;Student(Stringname,intage){this.name=name;this.age=age;}@Overridepublicbooleanequals(Objecto){if(this==o)returntrue;if(!(oinstanceofStudent))returnfalse;Students=(Student)o;returnage==s.age&&name.equals(s.name);}@OverridepublicinthashCode(){returnObjects.hash(name,age);// IDEA 可自动生成}}

Set<Student>students=newHashSet<>();students.add(newStudent("张三",18));students.add(newStudent("张三",18));// 重写后被认为是重复，去重成功System.out.println(students.size());// 1

如果不重写会怎样？用 Object 默认的 hashCode/equals（比较内存地址），两个new出来的对象地址不同，被当成两个元素（见易错点 3 的演示）。

LinkedHashSet 与 TreeSet

// LinkedHashSet：按插入顺序，可去重且有序Set<String>lhs=newLinkedHashSet<>();lhs.add("c");lhs.add("a");lhs.add("b");System.out.println(lhs);// [c, a, b]：保持插入顺序// TreeSet：自动排序（元素必须可比较）Set<Integer>ts=newTreeSet<>();ts.add(5);ts.add(1);ts.add(3);System.out.println(ts);// [1, 3, 5]：升序

TreeSet 要求元素实现Comparable接口，或构造时传入比较器：

// 自定义比较器：按年龄升序Set<Student>byAge=newTreeSet<>((s1,s2)->Integer.compare(s1.age,s2.age));byAge.add(newStudent("张三",20));byAge.add(newStudent("李四",18));for(Students:byAge){System.out.println(s.name+": "+s.age);// 李四: 18 / 张三: 20}

三个 Set 怎么选？只要去重用 HashSet，去重又保序用 LinkedHashSet，自动排序用 TreeSet。

五、集合元素去重实战

保留 List 中的不重复元素：

List<String>list=Arrays.asList("a","b","a","c","b");Set<String>unique=newHashSet<>(list);// 利用 Set 去重System.out.println(unique);// [a, b, c]

六、集合工具类 Collections

Collections 是操作集合的静态工具类，排序、反转、打乱、查找全都有：

List<Integer>nums=newArrayList<>(Arrays.asList(3,1,4,1,5));Collections.sort(nums);// 排序Collections.reverse(nums);// 反转Collections.shuffle(nums);// 随机打乱Collections.max(nums);// 最大值Collections.min(nums);// 最小值Collections.frequency(nums,1);// 统计出现次数

七、扩展知识

1. ArrayList 的扩容机制

ArrayList 底层的数组是"装不满"的——它有容量（capacity）和实际大小（size）。当 size 达到容量上限时会自动扩容：新容量约为旧容量的1.5 倍（JDK 8/11/17 都是oldCapacity + (oldCapacity >> 1)），用Arrays.copyOf把旧数组整体拷贝到新数组。默认初始容量是10，前 10 个元素不扩容，第 11 个才触发。

经验：频繁 add 大量数据时，用new ArrayList<>(预估容量)能显著减少扩容拷贝的开销。

2. LinkedList vs ArrayList 终极对比

结论：LinkedList 遍历要用迭代器/增强 for，别用 get(i)——get(i) 每次都从头遍历，整体 O(n²)。

3. HashSet 底层就是 HashMap

打开 HashSet 源码会发现它内部维护了一个 HashMap：add 的元素作为key存入，value 统一用占位对象PRESENT。元素唯一性 = key 唯一性，复用 HashMap 的去重逻辑。

set.add(x)的返回值就是"这次有没有真正加进去"：

Set<String>set=newHashSet<>();System.out.println(set.add("a"));// true：加进去了System.out.println(set.add("a"));// false：已存在，加失败

4. 迭代器与 fail-fast 机制

集合内部维护修改计数器modCount，每次 add/remove 都会 +1。迭代器创建时记录当时的 modCount，迭代中一旦发现计数变了，立即抛ConcurrentModificationException——这就是 fail-fast（快速失败）：

List<String>list=newArrayList<>();list.add("a");list.add("b");list.add("c");// ❌ 错误示范：迭代中调用 list.addfor(Strings:list){list.add("x");// 抛 ConcurrentModificationException}

正确的删除姿势见易错点 1：用迭代器自己的remove()（it.remove()会同步维护 modCount，所以安全）。

八、易错点

1. 遍历时删除元素 → 抛异常

// ❌ 增强 for 中删除：抛 ConcurrentModificationExceptionList<String>list=newArrayList<>();list.add("a");list.add("b");list.add("c");for(Strings:list){if(s.equals("b"))list.remove(s);}// ✅ 用迭代器的 remove()List<String>list2=newArrayList<>();list2.add("a");list2.add("b");list2.add("c");Iterator<String>it=list2.iterator();while(it.hasNext()){if(it.next().equals("b"))it.remove();}System.out.println(list2);// [a, c]// ✅ 或者 for 循环倒序删除（见易错点 5）

2. List.of 创建的列表不能增删

// 需 JDK 11/17 才能运行（JDK 8 没有 List.of）List<String>fixed=List.of("a","b","c");// ❌ fixed.add("d"); // 抛 UnsupportedOperationException// ❌ fixed.remove("a"); // 同样抛异常// ✅ 想要可变列表，先拷贝一份List<String>mutable=newArrayList<>(List.of("a","b","c"));mutable.add("d");System.out.println(mutable);// [a, b, c, d]

顺带：JDK 8 里常用的Arrays.asList也是定长的——不能 add/remove（抛 UnsupportedOperationException），但可以 set 修改已有元素。

3. HashSet 存自定义对象没重写 hashCode/equals

// ❌ 没重写：两个"张三"被当成不同元素，都存进去了classStudentNoHash{Stringname;StudentNoHash(Stringname){this.name=name;}}Set<StudentNoHash>s1=newHashSet<>();s1.add(newStudentNoHash("张三"));s1.add(newStudentNoHash("张三"));System.out.println(s1.size());// 2：去重失败！// ✅ 重写 hashCode + equals 之后（见上文的 Student 类）Set<Student>s2=newHashSet<>();s2.add(newStudent("张三",18));s2.add(newStudent("张三",18));System.out.println(s2.size());// 1：去重成功

4. 用下标访问 LinkedList，性能惨不忍睹

// ❌ LinkedList.get(i) 每次都要从头遍历，整体 O(n²)for(inti=0;i<linkedList.size();i++){System.out.println(linkedList.get(i));}// ✅ 迭代器 / 增强 for：O(n)for(Strings:linkedList){System.out.println(s);}

5. 正序删除会漏删（下标前移）

List<String>list=newArrayList<>(Arrays.asList("a","b","b","c"));// ❌ 正序删除"b"：删掉第一个 b 后元素前移，第二个 b 被跳过for(inti=0;i<list.size();i++){if(list.get(i).equals("b"))list.remove(i);}System.out.println(list);// [a, b, c]：漏删了一个 b！// ✅ 倒序删除：不涉及下标前移问题for(inti=list.size()-1;i>=0;i--){if(list.get(i).equals("b"))list.remove(i);}System.out.println(list);// [a, c]

九、小结

• List 有序可重复（ArrayList 查询快 / LinkedList 增删快）
• Set 不可重复（HashSet 无序 / LinkedHashSet 保序 / TreeSet 排序）
• 自定义类进 HashSet 必须重写 hashCode + equals
• 遍历集合别在增强 for 中修改集合，删除用 Iterator.remove() 或倒序 for
• ArrayList 自动扩容（默认容量 10，1.5 倍增长），大数据量提前指定容量
• LinkedList 遍历要用迭代器，别用 get(i)；JDK 11/17 的 List.of 不可变、不能增删

下一节学习集合框架：Map。

下一篇：第17章 集合框架：Map（待发布）