Java 集合 List 和 Set：面试通关秘籍与生活化实战解析

List 和 Set 作为 Java 集合框架中两个至关重要的接口，在面试中经常被问到。面试官不仅考察你对它们基本概念的理解，更关注你在实际场景中的应用能力。本文将通过超通俗的生活案例，结合深度源码解析，助你彻底掌握 List 和 Set，轻松应对面试。

List：有序可重复，就像排队买奶茶

List 的特点是有序、可重复。你可以把它想象成排队买奶茶的队伍。每个人都有一个明确的位置（索引），队伍中可以有多个点同一款奶茶的人（重复元素）。

ArrayList vs. LinkedList：奶茶店的两种排队方式

ArrayList 和 LinkedList 是 List 接口的两个主要实现类，它们的底层数据结构不同，导致性能差异巨大。

• ArrayList：数组实现，连续存储

  ArrayList 底层基于数组实现，这意味着元素在内存中是连续存储的。就像奶茶店用号码牌来管理排队的人，通过号码牌（索引）可以快速找到对应的人。

  优点：

  • 随机访问效率高： 通过索引直接访问，时间复杂度 O(1)。

  缺点：

  • 插入和删除效率低： 在中间位置插入或删除元素，需要移动后续所有元素，时间复杂度 O(n)。

  • 扩容代价高： 当数组容量不足时，需要创建新的更大的数组，并将原有元素复制过去，时间复杂度 O(n)。

    

  // ArrayList 示例：添加和访问元素
  ArrayList<String> names = new ArrayList<>();
  names.add("张三"); // 添加到末尾
  names.add(0, "李四"); // 在索引 0 处添加
  String name = names.get(0); // 访问索引 0 处的元素
  System.out.println(name); // 输出：李四
  

• LinkedList：链表实现，离散存储

  LinkedList 底层基于链表实现，元素在内存中是离散存储的，每个元素都包含指向下一个元素的指针。就像奶茶店用链子把排队的人串起来，每个人只知道自己后面是谁。

  优点：

  • 插入和删除效率高： 在已知节点位置的情况下，插入和删除元素只需修改指针，时间复杂度 O(1)。

  缺点：

  • 随机访问效率低： 需要从头节点开始遍历，直到找到目标节点，时间复杂度 O(n)。

  // LinkedList 示例：添加和删除元素
  LinkedList<String> names = new LinkedList<>();
  names.add("张三");
  names.addFirst("李四"); // 添加到链表头部
  names.removeLast(); // 移除链表尾部元素
  

如何选择 ArrayList 和 LinkedList？

• 频繁随机访问： 选择 ArrayList。

• 频繁插入和删除： 选择 LinkedList，但要注意定位到需要插入/删除的节点也需要时间复杂度 O(n)。

• 如果数据量较小，或者插入删除操作主要发生在列表的头部或尾部，ArrayList 可能仍然是更好的选择。

• 实际场景：

  

  • ArrayList 适用于存储用户列表、商品列表等，这些场景需要快速访问指定位置的元素。
  • LinkedList 适用于实现队列、栈等数据结构，这些场景需要频繁在头部或尾部进行插入和删除操作。

Set：无序不重复，就像盲盒

Set 的特点是无序、不重复。你可以把它想象成一个盲盒，你往里面放东西，相同的物品只能放一次，而且你不知道下次打开盲盒时物品的顺序。

HashSet vs. TreeSet：两种不同的盲盒

HashSet 和 TreeSet 是 Set 接口的两个主要实现类，它们的底层数据结构不同，导致性能和功能差异巨大。

• HashSet：哈希表实现，无序快速

  HashSet 底层基于哈希表实现，通过计算元素的哈希值来确定其存储位置。就像盲盒里每个格子都有一个编号，物品根据其哈希值放到对应的格子里。

  优点：

  • 查找、添加、删除效率高： 平均时间复杂度 O(1)。

  缺点：

  • 无序： 元素的存储顺序与添加顺序无关。

  • 依赖 hashCode() 和 equals() 方法： 必须正确实现这两个方法，才能保证元素的唯一性。

    

  // HashSet 示例：添加和判断元素
  HashSet<String> uniqueNames = new HashSet<>();
  uniqueNames.add("张三");
  uniqueNames.add("李四");
  boolean containsZhangSan = uniqueNames.contains("张三"); // 检查是否包含
  System.out.println(containsZhangSan); // 输出：true
  

• TreeSet：红黑树实现，有序稳定

  TreeSet 底层基于红黑树实现，元素按照自然顺序或自定义顺序进行排序。就像盲盒里的物品按照大小或者颜色进行排序。

  优点：

  • 有序： 元素按照指定的顺序存储。

  缺点：

  • 查找、添加、删除效率略低于 HashSet： 时间复杂度 O(log n)。

  • 需要实现 Comparable 接口或提供 Comparator： 才能进行排序。

  // TreeSet 示例：添加和迭代元素
  TreeSet<String> sortedNames = new TreeSet<>();
  sortedNames.add("张三");
  sortedNames.add("李四");
  // 迭代器会按照字母顺序输出
  for (String name : sortedNames) {
      System.out.println(name);
  }
  

如何选择 HashSet 和 TreeSet？

• 不需要排序： 选择 HashSet。

• 需要排序： 选择 TreeSet。

  

• 实际场景：

  • HashSet 适用于存储唯一的 ID 集合、用户角色集合等，这些场景不需要排序。
  • TreeSet 适用于存储需要按照特定顺序排列的数据，例如日期、分数等。

实战避坑：equals() 和 hashCode() 的重要性

在使用 HashSet 时，务必重写 equals() 和 hashCode() 方法。这两个方法用于判断对象是否相等。如果只重写了 equals() 方法，而没有重写 hashCode() 方法，会导致相同的对象被存储多次，违反 Set 的唯一性原则。

举例：

假设有一个 Person 类，包含 name 和 age 属性。如果只重写了 equals() 方法，判断 name 和 age 相等就认为两个 Person 对象相等，而没有重写 hashCode() 方法，那么两个 Person 对象的 hashCode() 值可能不同，导致 HashSet 认为它们是不同的对象，从而存储两次。

class Person {
    String name;
    int age;

    // 省略构造函数

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return age == person.age && Objects.equals(name, person.name);
    }

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

最佳实践：

使用 IDE 提供的自动生成 equals() 和 hashCode() 方法的功能，避免手动编写出错。

面试高频问题：

1. List 和 Set 的区别？
2. ArrayList 和 LinkedList 的区别？分别适用于什么场景？
3. HashSet 和 TreeSet 的区别？分别适用于什么场景？
4. HashMap 和 HashSet 的关系？
5. 如何保证 HashSet 中元素的唯一性？equals() 和 hashCode() 方法的作用是什么？
6. List 如何去重？
7. Set 如何排序？

掌握以上知识点，并在面试中结合实际项目经验进行阐述，相信你一定能够脱颖而出！