在 Java 中，List、Set 和 Map 是集合框架中非常重要的接口，它们各自有着不同的特点和用途。以下是对它们的详细介绍：

1. List 接口

特点

  • 有序性：List 中的元素是按照插入顺序排列的，每个元素都有一个对应的索引，通过索引可以精确地访问和操作元素。
  • 可重复性：允许存储重复的元素，即同一个元素可以在 List 中出现多次。

常用实现类

  • ArrayList：基于动态数组实现，它支持随机访问，通过索引可以快速访问元素，时间复杂度为 $O(1)$。但是在插入和删除元素时，尤其是在数组中间或开头进行操作，可能需要移动大量元素，时间复杂度为 $O(n)$。
  • LinkedList：基于双向链表实现，在插入和删除元素时效率较高，时间复杂度为 $O(1)$，但随机访问的效率较低，时间复杂度为 $O(n)$。

示例代码

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

public class ListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");
        list.add("banana");
        list.add("apple"); // 允许重复元素
        System.out.println(list.get(1)); // 输出: banana
    }
}

2. Set 接口

特点

  • 无序性：Set 中的元素没有特定的顺序，不能通过索引来访问元素。
  • 不可重复性：不允许存储重复的元素，如果尝试添加重复的元素，添加操作将不会生效。

常用实现类

  • HashSet：基于哈希表实现，不保证元素的顺序。它通过元素的 hashCode() 和 equals() 方法来判断元素是否重复，添加、删除和查找元素的时间复杂度为 $O(1)$。
  • TreeSet：基于红黑树实现，元素会按照自然顺序或指定的比较器进行排序。添加、删除和查找元素的时间复杂度为 $O(log n)$。

示例代码

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

public class SetExample {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("apple");
        set.add("banana");
        set.add("apple"); // 重复元素，添加失败
        System.out.println(set.size()); // 输出: 2
    }
}

3. Map 接口

特点

  • 键值对存储：Map 存储的是键值对（key-value），每个键（key）是唯一的，通过键可以快速查找对应的值（value）。
  • 键不可重复：键（key）不允许重复，如果尝试使用已存在的键来存储新的值，会覆盖原有的值。

常用实现类

  • HashMap：基于哈希表实现，不保证键值对的顺序。它通过键的 hashCode() 和 equals() 方法来判断键是否重复，添加、删除和查找键值对的时间复杂度为 $O(1)$。
  • TreeMap：基于红黑树实现，键会按照自然顺序或指定的比较器进行排序。添加、删除和查找键值对的时间复杂度为 $O(log n)$。

示例代码

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

public class MapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("apple", 3); // 键重复，覆盖原有值
        System.out.println(map.get("apple")); // 输出: 3
    }
}

区别总结

  • 存储方式：List 存储单个元素，Set 也存储单个元素但不允许重复，Map 存储键值对。
  • 顺序性：List 是有序的，Set 通常是无序的（TreeSet 除外），Map 通常也是无序的（TreeMap 除外）。
  • 重复性：List 允许元素重复，Set 和 Map 的键不允许重复。
  • 访问方式：List 可以通过索引访问元素，Set 没有索引，只能通过迭代器或增强 for 循环访问元素，Map 通过键来访问对应的值。