第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;ListStringlistnewArrayList();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底层是双向链表增删快、查询慢LinkedListStringlinkedListnewLinkedList();linkedList.addFirst(头);// 头部添加linkedList.addLast(尾);// 尾部添加linkedList.removeFirst();// 删除头部LinkedList 实现了 Deque 接口常用作栈或队列// 当栈用后进先出DequeStringstacknewLinkedList();stack.push(A);stack.push(B);System.out.println(stack.pop());// BSystem.out.println(stack.peek());// A只看栈顶// 当队列用先进先出QueueStringqueuenewLinkedList();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 或手动 addListStringlistList.of(Java,Python,Go);// 方式一普通 for需要下标for(inti0;ilist.size();i){System.out.println(list.get(i));}// 方式二增强 for最常用for(Stringlang:list){System.out.println(lang);}// 方式三Iterator 迭代器IteratorStringitlist.iterator();while(it.hasNext()){System.out.println(it.next());}// 方式四LambdaJDK 8简洁list.forEach(lang-System.out.println(lang));增强 for 遍历时不能同时修改集合会抛 ConcurrentModificationException要删除元素用 Iterator 的remove()或 for 倒序删除。四、Set 接口Set 是不可重复的集合不能按下标访问。Set 的去重能力靠的是哈希先看最常用的 HashSet。HashSet最常用底层是 HashMap无序不保证迭代顺序去重核心SetStringsetnewHashSet();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.namename;this.ageage;}Overridepublicbooleanequals(Objecto){if(thiso)returntrue;if(!(oinstanceofStudent))returnfalse;Students(Student)o;returnages.agename.equals(s.name);}OverridepublicinthashCode(){returnObjects.hash(name,age);// IDEA 可自动生成}}SetStudentstudentsnewHashSet();students.add(newStudent(张三,18));students.add(newStudent(张三,18));// 重写后被认为是重复去重成功System.out.println(students.size());// 1如果不重写会怎样用 Object 默认的 hashCode/equals比较内存地址两个new出来的对象地址不同被当成两个元素见易错点 3 的演示。LinkedHashSet 与 TreeSet// LinkedHashSet按插入顺序可去重且有序SetStringlhsnewLinkedHashSet();lhs.add(c);lhs.add(a);lhs.add(b);System.out.println(lhs);// [c, a, b]保持插入顺序// TreeSet自动排序元素必须可比较SetIntegertsnewTreeSet();ts.add(5);ts.add(1);ts.add(3);System.out.println(ts);// [1, 3, 5]升序TreeSet 要求元素实现Comparable接口或构造时传入比较器// 自定义比较器按年龄升序SetStudentbyAgenewTreeSet((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 中的不重复元素ListStringlistArrays.asList(a,b,a,c,b);SetStringuniquenewHashSet(list);// 利用 Set 去重System.out.println(unique);// [a, b, c]六、集合工具类 CollectionsCollections 是操作集合的静态工具类排序、反转、打乱、查找全都有ListIntegernumsnewArrayList(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 终极对比维度ArrayListLinkedList底层结构连续数组双向链表按下标查询 get(i)O(1)直接定位O(n)要挨个找头部插入/删除O(n)整体挪动O(1)改指针中间插入/删除O(n)挪动后半段O(n)先找到位置额外内存少每个节点多存前后指针典型场景遍历、随机访问频繁头尾增删、队列/栈结论LinkedList 遍历要用迭代器/增强 for别用 get(i)——get(i) 每次都从头遍历整体 O(n²)。3. HashSet 底层就是 HashMap打开 HashSet 源码会发现它内部维护了一个 HashMapadd 的元素作为key存入value 统一用占位对象PRESENT。元素唯一性 key 唯一性复用 HashMap 的去重逻辑。set.add(x)的返回值就是这次有没有真正加进去SetStringsetnewHashSet();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快速失败ListStringlistnewArrayList();list.add(a);list.add(b);list.add(c);// ❌ 错误示范迭代中调用 list.addfor(Strings:list){list.add(x);// 抛 ConcurrentModificationException}正确的删除姿势见易错点 1用迭代器自己的remove()it.remove()会同步维护 modCount所以安全。八、易错点1. 遍历时删除元素 → 抛异常// ❌ 增强 for 中删除抛 ConcurrentModificationExceptionListStringlistnewArrayList();list.add(a);list.add(b);list.add(c);for(Strings:list){if(s.equals(b))list.remove(s);}// ✅ 用迭代器的 remove()ListStringlist2newArrayList();list2.add(a);list2.add(b);list2.add(c);IteratorStringitlist2.iterator();while(it.hasNext()){if(it.next().equals(b))it.remove();}System.out.println(list2);// [a, c]// ✅ 或者 for 循环倒序删除见易错点 52. List.of 创建的列表不能增删// 需 JDK 11/17 才能运行JDK 8 没有 List.ofListStringfixedList.of(a,b,c);// ❌ fixed.add(d); // 抛 UnsupportedOperationException// ❌ fixed.remove(a); // 同样抛异常// ✅ 想要可变列表先拷贝一份ListStringmutablenewArrayList(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.namename;}}SetStudentNoHashs1newHashSet();s1.add(newStudentNoHash(张三));s1.add(newStudentNoHash(张三));System.out.println(s1.size());// 2去重失败// ✅ 重写 hashCode equals 之后见上文的 Student 类SetStudents2newHashSet();s2.add(newStudent(张三,18));s2.add(newStudent(张三,18));System.out.println(s2.size());// 1去重成功4. 用下标访问 LinkedList性能惨不忍睹// ❌ LinkedList.get(i) 每次都要从头遍历整体 O(n²)for(inti0;ilinkedList.size();i){System.out.println(linkedList.get(i));}// ✅ 迭代器 / 增强 forO(n)for(Strings:linkedList){System.out.println(s);}5. 正序删除会漏删下标前移ListStringlistnewArrayList(Arrays.asList(a,b,b,c));// ❌ 正序删除b删掉第一个 b 后元素前移第二个 b 被跳过for(inti0;ilist.size();i){if(list.get(i).equals(b))list.remove(i);}System.out.println(list);// [a, b, c]漏删了一个 b// ✅ 倒序删除不涉及下标前移问题for(intilist.size()-1;i0;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() 或倒序 forArrayList 自动扩容默认容量 101.5 倍增长大数据量提前指定容量LinkedList 遍历要用迭代器别用 get(i)JDK 11/17 的 List.of 不可变、不能增删下一节学习集合框架Map。下一篇第17章 集合框架Map待发布