关注

JAVA 集合框架进阶：List 与 Set 的深度解析与实战

JAVA 集合框架进阶：List 与 Set 的深度解析与实战

在这里插入图片描述

1.1 本章学习目标与重点

💡 掌握 List 和 Set 接口的核心特性，理解不同实现类的底层原理与适用场景。
💡 熟练运用集合的常用方法，解决数据存储、查找、去重等实际开发问题。
💡 理解集合的线程安全问题，掌握线程安全集合的使用方式。
⚠️ 本章重点是 不同集合的底层数据结构 和 性能对比，这是面试和开发中的核心考点。

1.2 List 接口：有序可重复的集合

1.2.1 List 接口的核心特性

💡 List 是有序集合，元素的存储顺序和插入顺序一致，支持通过索引访问元素。
List 允许存储重复元素，也可以存储 null 值。
List 接口的常用实现类有 ArrayList、LinkedList 和 Vector，它们的底层结构和性能各有差异。

✅ 核心结论：List 适合需要按索引操作、元素有序且允许重复的场景。

1.2.2 ArrayList：基于动态数组的实现

底层原理

💡 ArrayList 的底层是动态扩容的数组，默认初始容量为 10。
当数组容量不足时，会自动扩容为原来的 1.5 倍。
扩容过程需要新建数组并复制原数组元素，频繁扩容会影响性能。

代码实操：ArrayList 的常用操作

① 📝 创建 ArrayList 对象，添加不同类型的元素
② 📝 通过索引获取、修改元素
③ 📝 遍历集合，删除指定元素
④ 📝 判断集合是否包含某个元素

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

public class ArrayListDemo {
    public static void main(String[] args) {
        // 1. 创建 ArrayList 集合
        List<String> list = new ArrayList<>();

        // 2. 添加元素
        list.add("Java");
        list.add("Python");
        list.add("C++");
        list.add("Java"); // 允许重复元素
        list.add(null); // 允许存储null

        // 3. 通过索引获取元素
        String firstElement = list.get(0);
        System.out.println("第一个元素：" + firstElement);

        // 4. 修改元素
        list.set(1, "Go");
        System.out.println("修改后的集合：" + list);

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

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

        // 7. 遍历集合 - 方式3：迭代器
        System.out.println("迭代器遍历：");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            // 迭代器遍历中删除元素，避免并发修改异常
            if (s == null) {
                iterator.remove();
            }
        }
        System.out.println("删除null后的集合：" + list);

        // 8. 判断集合是否包含指定元素
        boolean containsJava = list.contains("Java");
        System.out.println("集合包含Java：" + containsJava);

        // 9. 清空集合
        list.clear();
        System.out.println("清空后的集合是否为空：" + list.isEmpty());
    }
}
性能分析
  • 查询操作：基于索引的查询效率高，时间复杂度为 O(1)。
  • 增删操作：在集合尾部增删元素效率高；在中间增删元素需要移动数组元素，时间复杂度为 O(n)。
    ⚠️ 注意事项：ArrayList 是线程不安全的集合，多线程环境下使用会出现并发修改异常。

1.2.3 LinkedList：基于双向链表的实现

底层原理

💡 LinkedList 的底层是双向链表，每个节点包含前驱节点、后继节点和元素值。
链表结构无需连续的内存空间，增删元素时只需要修改节点的引用关系，不需要扩容。

代码实操：LinkedList 的特有方法

LinkedList 除了继承 List 接口的方法，还提供了操作首尾元素的特有方法，适合作为栈或队列使用。

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        // 1. 添加元素
        linkedList.addFirst("头元素");
        linkedList.addLast("尾元素");
        linkedList.add("中间元素");

        // 2. 获取首尾元素
        String first = linkedList.getFirst();
        String last = linkedList.getLast();
        System.out.println("头元素：" + first + "，尾元素：" + last);

        // 3. 删除首尾元素
        linkedList.removeFirst();
        linkedList.removeLast();
        System.out.println("删除首尾后的集合：" + linkedList);

        // 4. 作为栈使用：先进后出
        linkedList.push("元素1");
        linkedList.push("元素2");
        linkedList.push("元素3");
        System.out.println("栈结构：" + linkedList);
        String popElement = linkedList.pop();
        System.out.println("弹出的元素：" + popElement);
        System.out.println("弹出后的栈：" + linkedList);

        // 5. 作为队列使用：先进先出
        linkedList.offer("队列元素1");
        linkedList.offer("队列元素2");
        System.out.println("队列结构：" + linkedList);
        String pollElement = linkedList.poll();
        System.out.println("出队的元素：" + pollElement);
        System.out.println("出队后的队列：" + linkedList);
    }
}
性能分析
  • 查询操作：查询元素需要遍历链表，时间复杂度为 O(n)。
  • 增删操作：增删元素只需修改节点引用，时间复杂度为 O(1)。
    ⚠️ 注意事项：LinkedList 同样是线程不安全的集合，不适合多线程环境。

1.2.4 Vector：线程安全的动态数组

💡 Vector 的底层和 ArrayList 类似，都是动态数组。
Vector 的方法都加了 synchronized 关键字，是线程安全的集合。
它的扩容机制默认是原来的 2 倍，扩容效率低于 ArrayList。

✅ 核心结论：Vector 性能较低，现代开发中更推荐使用 Collections.synchronizedList() 或 CopyOnWriteArrayList 实现线程安全。

1.2.5 ArrayList 与 LinkedList 性能对比测试

我们通过代码测试两种集合在查询和增删操作中的耗时差异，测试数据为 10 万条元素。

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

public class ListPerformanceTest {
    public static final int SIZE = 100000;

    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // 初始化集合
        for (int i = 0; i < SIZE; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        // 测试查询性能
        long arrayListQueryTime = testQuery(arrayList);
        long linkedListQueryTime = testQuery(linkedList);
        System.out.println("ArrayList查询耗时：" + arrayListQueryTime + "ms");
        System.out.println("LinkedList查询耗时：" + linkedListQueryTime + "ms");

        // 测试中间增删性能
        long arrayListAddRemoveTime = testAddRemove(arrayList);
        long linkedListAddRemoveTime = testAddRemove(linkedList);
        System.out.println("ArrayList中间增删耗时：" + arrayListAddRemoveTime + "ms");
        System.out.println("LinkedList中间增删耗时：" + linkedListAddRemoveTime + "ms");
    }

    // 测试查询性能：随机访问1000次
    private static long testQuery(List<Integer> list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++) {
            int index = (int) (Math.random() * SIZE);
            list.get(index);
        }
        return System.currentTimeMillis() - start;
    }

    // 测试中间增删性能：在中间位置增删1000次
    private static long testAddRemove(List<Integer> list) {
        long start = System.currentTimeMillis();
        int middleIndex = list.size() / 2;
        for (int i = 0; i < 1000; i++) {
            list.add(middleIndex, i);
            list.remove(middleIndex);
        }
        return System.currentTimeMillis() - start;
    }
}

测试结果（仅供参考）

ArrayList查询耗时：1ms
LinkedList查询耗时：15ms
ArrayList中间增删耗时：8ms
LinkedList中间增删耗时：2ms

✅ 核心结论：查询多用 ArrayList，增删多用 LinkedList。

1.3 Set 接口：无序不可重复的集合

1.3.1 Set 接口的核心特性

💡 Set 是无序集合，元素没有索引，存储顺序由底层数据结构决定。
Set 不允许存储重复元素，最多只能存储一个 null 值。
Set 接口的常用实现类有 HashSet、LinkedHashSet 和 TreeSet。

✅ 核心结论：Set 适合需要元素去重、不关注存储顺序的场景。

1.3.2 HashSet：基于哈希表的实现

底层原理

💡 HashSet 的底层是 HashMap，它是通过 HashMap 的 key 来存储元素的，value 是一个固定的 PRESENT 对象。
HashSet 保证元素唯一的原理是：先通过 hashCode() 方法计算哈希值，再通过 equals() 方法比较元素是否相同。
如果两个元素的 hashCode() 值相同且 equals() 方法返回 true，则认为是重复元素，无法添加。

代码实操：HashSet 的常用操作
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class HashSetDemo {
    public static void main(String[] args) {
        Set<String> hashSet = new HashSet<>();

        // 1. 添加元素
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Orange");
        hashSet.add("Apple"); // 重复元素，无法添加
        hashSet.add(null); // 可以存储一个null

        System.out.println("HashSet集合：" + hashSet); // 输出顺序与插入顺序无关

        // 2. 遍历集合
        System.out.println("增强for循环遍历：");
        for (String s : hashSet) {
            System.out.println(s);
        }

        System.out.println("迭代器遍历：");
        Iterator<String> iterator = hashSet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        // 3. 判断元素是否存在
        boolean containsBanana = hashSet.contains("Banana");
        System.out.println("包含Banana：" + containsBanana);

        // 4. 删除元素
        hashSet.remove("Orange");
        System.out.println("删除Orange后的集合：" + hashSet);

        // 5. 清空集合
        hashSet.clear();
        System.out.println("集合是否为空：" + hashSet.isEmpty());
    }
}
性能分析
  • 增删查操作：效率高，时间复杂度为 O(1)。
  • 当哈希冲突严重时，性能会下降到 O(n)。
    ⚠️ 注意事项：
  1. HashSet 是线程不安全的集合。
  2. 存储自定义对象时，必须重写 hashCode() 和 equals() 方法，否则无法保证元素唯一。
自定义对象去重案例

我们定义一个 Student 类，重写 hashCode() 和 equals() 方法，实现基于学号的去重。

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

class Student {
    private String id;
    private String name;

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

    // 重写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 Objects.equals(id, student.id);
    }

    // 重写hashCode方法：根据学号计算哈希值
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Student{id='" + id + "', name='" + name + "'}";
    }
}

public class HashSetCustomObjectDemo {
    public static void main(String[] args) {
        Set<Student> studentSet = new HashSet<>();

        studentSet.add(new Student("001", "张三"));
        studentSet.add(new Student("002", "李四"));
        studentSet.add(new Student("001", "张三")); // 重复元素，无法添加

        for (Student student : studentSet) {
            System.out.println(student);
        }
    }
}

输出结果

Student{id='001', name='张三'}
Student{id='002', name='李四'}

1.3.3 LinkedHashSet：有序的哈希集合

💡 LinkedHashSet 是 HashSet 的子类，底层是 HashMap + 双向链表。
它通过双向链表维护元素的插入顺序，保证遍历顺序和插入顺序一致。
它的元素唯一性原理和 HashSet 相同，性能略低于 HashSet。

代码实操：LinkedHashSet 的有序性
import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        Set<String> linkedHashSet = new LinkedHashSet<>();

        linkedHashSet.add("B");
        linkedHashSet.add("A");
        linkedHashSet.add("C");
        linkedHashSet.add("A"); // 重复元素，无法添加

        // 遍历顺序与插入顺序一致
        System.out.println("LinkedHashSet集合：" + linkedHashSet);
    }
}

输出结果

LinkedHashSet集合：[B, A, C]

✅ 核心结论：需要去重且保留插入顺序时，使用 LinkedHashSet。

1.3.4 TreeSet：基于红黑树的排序集合

底层原理

💡 TreeSet 的底层是 TreeMap，基于红黑树实现。
TreeSet 会自动对元素进行排序，默认是升序排列。
它保证元素唯一的原理是：通过比较元素的大小，相同元素无法添加。

排序方式
  1. 自然排序：元素实现 Comparable 接口，重写 compareTo() 方法。
  2. 定制排序：创建 TreeSet 时传入 Comparator 比较器，自定义排序规则。
代码实操1：自然排序
import java.util.Set;
import java.util.TreeSet;

public class TreeSetNaturalSortDemo {
    public static void main(String[] args) {
        Set<Integer> treeSet = new TreeSet<>();

        treeSet.add(3);
        treeSet.add(1);
        treeSet.add(2);
        treeSet.add(3); // 重复元素，无法添加

        // 自动升序排列
        System.out.println("TreeSet自然排序：" + treeSet);
    }
}

输出结果

TreeSet自然排序：[1, 2, 3]
代码实操2：定制排序

我们对字符串进行降序排列，通过 Comparator 实现定制排序。

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetCustomSortDemo {
    public static void main(String[] args) {
        // 传入比较器，实现字符串降序排列
        Set<String> treeSet = new TreeSet<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.compareTo(o1); // 降序排列
            }
        });

        treeSet.add("Java");
        treeSet.add("Python");
        treeSet.add("Go");

        System.out.println("TreeSet定制排序：" + treeSet);
    }
}

输出结果

TreeSet定制排序：[Python, Java, Go]
性能分析
  • 增删查操作：时间复杂度为 O(log n)，效率低于 HashSet。
    ⚠️ 注意事项：
  1. TreeSet 是线程不安全的集合。
  2. 存储自定义对象时，必须指定排序规则，否则会抛出 ClassCastException。

1.4 集合的线程安全问题与解决方案

1.4.1 线程不安全的表现

当多个线程同时操作一个非线程安全的集合时，会出现 ConcurrentModificationException 并发修改异常。
例如，一个线程遍历集合，另一个线程修改集合，就会触发该异常。

1.4.2 解决方案1：使用 Collections 工具类

java.util.Collections 提供了 synchronizedXxx() 方法，可以将非线程安全的集合包装成线程安全的集合。

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

public class CollectionsSynchronizedDemo {
    public static void main(String[] args) {
        // 将ArrayList包装成线程安全的集合
        List<String> safeList = Collections.synchronizedList(new ArrayList<>());

        safeList.add("线程安全元素1");
        safeList.add("线程安全元素2");

        System.out.println("线程安全集合：" + safeList);
    }
}

1.4.3 解决方案2：使用 JUC 包下的线程安全集合

JUC 包（java.util.concurrent）提供了性能更高的线程安全集合，常用的有：

  • CopyOnWriteArrayList：线程安全的 ArrayList，适合读多写少的场景。
  • CopyOnWriteArraySet：线程安全的 Set，底层是 CopyOnWriteArrayList。
import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteArrayListDemo {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<>();

        cowList.add("元素1");
        cowList.add("元素2");
        cowList.add("元素3");

        // 遍历过程中可以修改集合，不会抛出并发修改异常
        Iterator<String> iterator = cowList.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (s.equals("元素2")) {
                cowList.remove(s);
            }
        }

        System.out.println("修改后的集合：" + cowList);
    }
}

✅ 核心结论：JUC 包下的线程安全集合性能高于 Collections 包装的集合，优先推荐使用。

1.5 实战案例：集合工具类封装

1.5.1 需求分析

💡 封装一个集合工具类 CollectionUtil，提供以下实用功能：

  1. 集合去重：去除 List 中的重复元素，保留插入顺序。
  2. 集合交集：获取两个 List 的共同元素。
  3. 集合差集：获取 List1 中有但 List2 中没有的元素。
  4. 集合排序：对 List 中的自定义对象进行排序。

1.5.2 代码实现

import java.util.*;
import java.util.stream.Collectors;

/**
 * 集合工具类
 */
public class CollectionUtil {

    /**
     * List去重，保留插入顺序
     */
    public static <T> List<T> distinctList(List<T> list) {
        if (list == null || list.isEmpty()) {
            return new ArrayList<>();
        }
        return new LinkedHashSet<>(list).stream().collect(Collectors.toList());
    }

    /**
     * 获取两个List的交集
     */
    public static <T> List<T> intersection(List<T> list1, List<T> list2) {
        if (list1 == null || list1.isEmpty() || list2 == null || list2.isEmpty()) {
            return new ArrayList<>();
        }
        Set<T> set = new HashSet<>(list2);
        return list1.stream().filter(set::contains).collect(Collectors.toList());
    }

    /**
     * 获取两个List的差集（list1 - list2）
     */
    public static <T> List<T> difference(List<T> list1, List<T> list2) {
        if (list1 == null || list1.isEmpty()) {
            return new ArrayList<>();
        }
        if (list2 == null || list2.isEmpty()) {
            return new ArrayList<>(list1);
        }
        Set<T> set = new HashSet<>(list2);
        return list1.stream().filter(t -> !set.contains(t)).collect(Collectors.toList());
    }

    /**
     * 对List中的自定义对象进行排序
     * @param list 待排序集合
     * @param comparator 比较器
     */
    public static <T> void sortList(List<T> list, Comparator<T> comparator) {
        if (list == null || list.isEmpty() || comparator == null) {
            return;
        }
        Collections.sort(list, comparator);
    }

    // 测试方法
    public static void main(String[] args) {
        // 测试去重
        List<Integer> list = Arrays.asList(1, 2, 3, 2, 1, 4);
        List<Integer> distinctList = distinctList(list);
        System.out.println("去重后的集合：" + distinctList);

        // 测试交集
        List<Integer> list1 = Arrays.asList(1, 2, 3, 4);
        List<Integer> list2 = Arrays.asList(3, 4, 5, 6);
        List<Integer> intersection = intersection(list1, list2);
        System.out.println("交集：" + intersection);

        // 测试差集
        List<Integer> difference = difference(list1, list2);
        System.out.println("差集：" + difference);

        // 测试自定义对象排序
        List<Student> studentList = new ArrayList<>();
        studentList.add(new Student("003", "王五", 20));
        studentList.add(new Student("001", "张三", 18));
        studentList.add(new Student("002", "李四", 19));

        // 按年龄升序排序
        sortList(studentList, Comparator.comparingInt(Student::getAge));
        System.out.println("按年龄排序后的学生集合：");
        studentList.forEach(System.out::println);
    }
}

// 学生类
class Student {
    private String id;
    private String name;
    private int age;

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

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Student{id='" + id + "', name='" + name + "', age=" + age + "}";
    }
}

输出结果

去重后的集合：[1, 2, 3, 4]
交集：[3, 4]
差集：[1, 2]
按年龄排序后的学生集合：
Student{id='001', name='张三', age=18}
Student{id='002', name='李四', age=19}
Student{id='003', name='王五', age=20}

1.5.3 案例总结

✅ 这个工具类综合运用了 List 和 Set 的核心知识，解决了开发中常见的集合处理问题。
通过 LinkedHashSet 实现去重并保留顺序，通过 HashSet 提升交集和差集的计算效率，通过 Comparator 实现自定义排序。

1.6 本章总结

  1. List 是有序可重复集合，ArrayList 适合查询，LinkedList 适合增删。
  2. Set 是无序不可重复集合，HashSet 效率最高，LinkedHashSet 保留插入顺序，TreeSet 支持排序。
  3. 存储自定义对象时，HashSet 需要重写 hashCode() 和 equals()，TreeSet 需要指定排序规则。
  4. 多线程环境下，优先使用 JUC 包下的 CopyOnWriteArrayList 和 CopyOnWriteArraySet 保证线程安全。
  5. 集合工具类可以封装常用功能，提升开发效率。

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/xcLeigh/article/details/157511766

评论

赞0

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--