List；Set；Map集合

一、List集合

1. 概念和特点

• 定义：List是一个有序的集合，它允许存储重复的元素。可以通过索引来访问、插入和删除元素。

• 示例代码：

  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(0));//通过索引访问元素
      }
  }
  

2. 主要实现类

• ArrayList：

  • 数据结构：它基于数组实现。当创建ArrayList时，会有一个初始容量（默认为10），随着元素的增加，如果容量不足，会自动扩容。

  • 性能特点：随机访问（通过索引访问元素）速度快，时间复杂度为$O(1)$。但是在插入和删除元素时（特别是在中间位置），可能需要移动大量元素，插入和删除操作的时间复杂度为$O(n)$。

  • 应用场景：适用于频繁读取元素，而插入和删除操作相对较少的场景。例如，存储用户信息列表，主要操作是根据索引获取用户信息。

• LinkedList：

  • 数据结构：它是基于双向链表实现的。每个节点包含元素、指向前一个节点的引用和指向后一个节点的引用。

  • 性能特点：插入和删除操作速度快，在链表头部或尾部插入/删除元素的时间复杂度为$O(1)$。但是随机访问元素的速度较慢，时间复杂度为$O(n)$。

  • 应用场景：适用于需要频繁进行插入和删除操作的场景。比如，实现一个队列或栈的数据结构。

3. 常用方法

• 添加元素：

  • add(E element)：将指定元素添加到列表的末尾。

  • add(int index, E element)：将指定元素插入到指定索引位置。

• 删除元素：

  • remove(int index)：删除指定索引位置的元素。

  • remove(Object element)：删除指定元素，如果列表中有多个相同元素，只删除第一个匹配的元素。

• 访问元素：

  • get(int index)：返回指定索引位置的元素。

• 其他方法：

  • size()：返回列表中元素的数量。

  • contains(Object element)：判断列表是否包含指定元素。

二、Set集合

1. 概念和特点

• 定义：Set是一个不允许存储重复元素的集合。它主要用于存储无序的、唯一的元素。

• 示例代码：

  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. 主要实现类

• HashSet：

  • 数据结构：它是基于哈希表实现的。通过计算元素的哈希值来确定元素在集合中的存储位置。

  • 性能特点：添加、删除和查找元素的时间复杂度接近$O(1)$，性能较好。但是在哈希冲突比较严重的情况下，性能可能会下降。

  • 应用场景：适用于需要快速判断元素是否存在，对元素的顺序没有要求的场景。例如，在用户权限管理中，判断用户是否具有某种权限。

• TreeSet：

  • 数据结构：它是基于红黑树实现的。元素在集合中是按照自然顺序或者指定的比较器顺序进行排序的。

  • 性能特点：添加、删除和查找元素的时间复杂度为$O(logn)$。因为需要维护元素的顺序，所以插入和删除操作相对较慢。

  • 应用场景：适用于需要对元素进行排序，并且不允许重复元素的场景。比如，存储学生成绩排名，需要按照成绩高低排序。

3. 常用方法

• 添加元素：add(E element)：将指定元素添加到集合中，如果元素已存在，则添加失败。
• 删除元素：remove(Object element)：从集合中删除指定元素。
• 判断元素是否存在：contains(Object element)：判断集合中是否包含指定元素。
• 其他方法：size()：返回集合中元素的数量。

三、Map集合

1. 概念和特点

• 定义：Map是一种用于存储键 - 值对（key - value）的集合。每个键在Map中是唯一的，通过键可以快速获取对应的值。

• 示例代码：

  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);
          System.out.println(map.get("apple"));
      }
  }
  

2. 主要实现类

• HashMap：

  • 数据结构：它是基于哈希表实现的。通过对键进行哈希计算来确定键 - 值对在集合中的存储位置。

  • 性能特点：添加、删除和查找操作的时间复杂度接近$O(1)$。但是在哈希冲突严重时，性能会受到影响。

  • 应用场景：适用于需要快速查找、插入和删除键 - 值对的场景。例如，存储用户ID和用户信息的映射关系，方便通过用户ID快速获取用户信息。

• TreeMap：

  • 数据结构：它是基于红黑树实现的。键在集合中是按照自然顺序或者指定的比较器顺序进行排序的。

  • 性能特点：添加、删除和查找操作的时间复杂度为$O(logn)$。因为需要维护键的顺序，所以性能相对较慢。

  • 应用场景：适用于需要对键进行排序，并且按照排序后的顺序遍历键 - 值对的场景。比如，存储单词和单词出现次数的映射关系，按照字母顺序输出单词和次数。

3. 常用方法

• 添加/更新元素：put(K key, V value)：将指定的键 - 值对添加到Map中，如果键已存在，则更新对应的值。

• 获取元素：get(K key)：返回指定键对应的的值，如果键不存在，则返回null。

• 删除元素：remove(K key)：删除指定键对应的键 - 值对。

• 其他方法：

  • size()：返回Map中键 - 值对的数量。

  • containsKey(K key)：判断Map中是否包含指定的键。

  • containsValue(V value)：判断Map中是否包含指定的值。

  ---

  凡是过去，皆为序章；凡是未来，皆有可期。