Java中的集合（1）——List、Map和Set

        Java标准库自带的java.util包提供了集合类：Collection，它是除Map外所有其他集合类的根接口。Java的java.util包中提供了以下三种类型的集合：

• List：一种有序列表的集合，例如，按索引排列的Student的List；

• Set：一种保证没有重复元素的集合，例如，所有无重复名称的Student的Set；

• Map：一种通过键值（key-value）查找的映射表集合，例如，根据Student的name查找对应Student的Map。

1. List

  List 是 Java 中 java.util 包下的一个接口，它继承自 Collection 接口，表示一种有序且可以包含重复元素的集合。List 提供了丰富的方法来访问、操作和遍历集合中的元素。

1.1 List 的特点

1. 有序性：List 保持元素的插入顺序，即元素会按照它们被添加到集合中的顺序存储。
2. 允许重复元素：List 允许包含相同的元素，即重复值是允许的。
3. 索引访问：List 提供了按索引（位置）访问元素的能力，允许通过数字索引直接获取、设置、删除和插入元素。

1.1 常见的 List 实现类

1. ArrayList

   • 特点：基于动态数组实现，支持快速随机访问，查询性能好（时间复杂度为 O(1)），但插入和删除元素的效率相对较低（特别是从中间位置插入或删除）。
   • 应用场景：适合在需要频繁读取数据的场景，比如读取数据库查询结果列表、存储临时数据等。
   • 注意：当元素较多时，频繁插入或删除会导致性能下降。

2. LinkedList

   • 特点：基于双向链表实现，适合频繁插入和删除操作（时间复杂度为 O(1)），但随机访问性能较差（时间复杂度为 O(n)）。
   • 应用场景：适合在需要频繁添加或删除元素的场景，比如实现队列或栈的功能。

3. Vector

   • 特点：类似于 ArrayList，但 Vector 是线程安全的，因为它的所有方法都是同步的。不过它的性能相对较低，因为同步的开销较大。
   • 应用场景：适合在多线程环境下使用，但现代应用中更推荐使用 Collections.synchronizedList() 或并发包中的 CopyOnWriteArrayList。

4. CopyOnWriteArrayList

   • 特点：线程安全的 List，写操作会创建副本，读操作不需要加锁，因此适合读多写少的场景。
   • 应用场景：适合多线程环境下的读操作非常频繁、写操作较少的场景，比如缓存。

1.3 List 常用方法

• 添加元素：

  list.add("element"); // 添加元素到末尾 list.add(1, "element"); // 在指定位置添加元素

• 获取元素：

  String element = list.get(0); // 获取指定索引的元素

• 更新元素：

  list.set(1, "newElement"); // 替换指定索引的元素

• 删除元素：

  list.remove(0); // 删除指定索引的元素 list.remove("element"); // 删除指定值的元素

• 查询大小：

  int size = list.size(); // 返回列表中的元素数量

• 遍历列表：

  for (String element : list) { System.out.println(element); }

1.4 List 的应用场景

• 动态数组：当数组大小在程序执行期间会变化时，ArrayList 是一个很好的选择。
• 需要按顺序处理数据：List 保持插入顺序，适合需要按顺序处理数据的场景。
• 允许重复数据：如果允许存储重复的对象（如购物车中的商品），可以使用 List。

2. Map

   Map 是 Java 中的一个重要接口，它位于 java.util 包下，表示一种键值对（key-value）的数据结构。Map 不属于 Collection 接口的子接口，但与集合框架紧密相关。它主要用于根据键（key）来查找、存储和操作对应的值（value）。在 Map 中，每个键都是唯一的，但值可以重复。

2.1 Map 的特点

1. 键唯一：每个键在 Map 中是唯一的，不能重复。添加新的键值对时，如果键已存在，新的值会替换掉旧的值。
2. 通过键查找值：Map 提供了通过键快速查找对应值的功能。
3. 无序或有序：不同的 Map 实现类对键值对的顺序有不同的处理方式。HashMap 无序，TreeMap 是有序的。

2.2 常见的 Map 实现类

1. HashMap

   • 特点：基于哈希表实现，允许 null 键和 null 值。它提供了快速的查找、插入和删除操作，适合大多数场景。
   • 无序：HashMap 不保证键值对的顺序，即插入的顺序和取出的顺序可能不同。
   • 应用场景：适合需要快速查找键值对的场景，如存储缓存数据、用户 ID 和其信息等。

2. LinkedHashMap

   • 特点：继承自 HashMap，但保留了插入顺序或访问顺序。它内部维护了一个双向链表，来记录元素的插入顺序。
   • 有序：当你需要遍历 Map 时希望元素按插入顺序（或访问顺序）返回，可以使用 LinkedHashMap。
   • 应用场景：适合需要维护键值对插入顺序的场景，如实现 LRU（最近最少使用）缓存。

3. TreeMap

   • 特点：基于红黑树实现，键值对会按照键的自然顺序（或自定义的比较器顺序）排序。
   • 有序：按键的顺序存储数据，适合需要排序的场景。
   • 应用场景：适合需要按键排序的场景，如按字母顺序排列的词典、按键进行范围查询等。

4. Hashtable

   • 特点：一种古老的线程安全实现，所有方法都是同步的，不允许 null 键或 null 值。
   • 线程安全：由于同步机制，其性能相对较低，现在更推荐使用 ConcurrentHashMap 来替代。
   • 应用场景：适合多线程环境，但不推荐在现代 Java 编程中使用，除非需要特定的线程安全需求。

5. ConcurrentHashMap

   • 特点：线程安全的 HashMap 实现，适合多线程环境。它的性能比 Hashtable 高，因为它使用了更精细的锁机制（锁分段）。
   • 应用场景：适合在并发环境下频繁读写数据的场景，如多线程的缓存或共享资源存储。

2.3 Map 常用方法

• 插入键值对：

  map.put("key", "value"); // 插入或更新键值对

• 获取值：

  String value = map.get("key"); // 根据键获取对应的值

• 删除键值对：

  map.remove("key"); // 根据键删除对应的键值对

• 判断是否包含键或值：

  map.containsKey("key"); // 判断 Map 是否包含指定的键 map.containsValue("value"); // 判断 Map 是否包含指定的值

• 遍历 Map：
  • 使用 keySet() 遍历键：

    for (String key : map.keySet()) { System.out.println(key + ": " + map.get(key)); }

  • 使用 entrySet() 遍历键值对：

    for (Map.Entry<String, String> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); }

2.4 Map 的应用场景

• 快速查找数据：例如，在电话簿中查找电话号码，通过唯一的姓名（键）找到对应的电话号码（值）。
• 数据关联关系：存储键值对之间的映射关系，如用户 ID 和用户信息、商品编号和商品详情。
• 实现缓存机制：LinkedHashMap 可以用于实现基于访问顺序的 LRU 缓存。

2.5 线程安全问题

        通的 HashMap 并不是线程安全的，因此在多线程环境中，可能会导致数据不一致的问题。可以使用 Collections.synchronizedMap() 方法将 HashMap 变为线程安全的，或者使用更高效的 ConcurrentHashMap。

2.6 小结

• HashMap：无序，适合快速查找，允许 null 键和值。
• LinkedHashMap：有序，按插入顺序或访问顺序存储元素。
• TreeMap：有序，按键的自然顺序或自定义顺序排序。
• ConcurrentHashMap：线程安全，适合多线程环境。

3. Set

   Set 是 Java 中 java.util 包中的一个接口，继承自 Collection，用于存储不允许重复的元素。与 List 不同，Set 不保证元素的顺序，除非使用特定的实现类。Set 常用于去重、集合运算等场景。

3.1 Set 的特点

1. 无重复元素：Set 不允许存储重复的元素。添加重复元素时，添加操作会被忽略。
2. 无固定顺序：Set 的实现类可能不会保持元素的插入顺序（如 HashSet），但某些实现类会有序（如 LinkedHashSet 和 TreeSet）。
3. 效率高：Set 通常比 List 更高效，特别是在查找和去重方面。

3.2 常见的 Set 实现类

1. HashSet

   • 特点：基于哈希表实现，存储元素时无序，允许 null 元素。HashSet 提供快速的增删查操作，通常比 List 更快。
   • 无序：HashSet 不保证元素的存储顺序，插入顺序与遍历顺序可能不同。
   • 应用场景：适用于需要快速去重和高效查询的场景，比如存储唯一的用户 ID、唯一的商品代码等。

2. LinkedHashSet

   • 特点：继承自 HashSet，但在内部使用链表来维护元素的插入顺序，因此元素的遍历顺序与插入顺序相同。
   • 有序：与 HashSet 不同，LinkedHashSet 保留了元素的插入顺序。
   • 应用场景：当你需要去重并保留元素的插入顺序时，比如按顺序存储唯一的登录记录。

3. TreeSet

   • 特点：基于红黑树实现，元素按自然顺序（或自定义比较器顺序）排序。由于排序机制，TreeSet 不允许 null 元素。
   • 有序：TreeSet 自动对元素进行排序，支持按顺序遍历元素。
   • 应用场景：需要对元素进行排序时，如按字母顺序排序的唯一用户名集合，或者需要对数据进行范围查询的场景。

3.3 Set 常用方法

• 添加元素：

  set.add("element"); // 添加元素，若元素已存在，操作会被忽略

• 删除元素：

  set.remove("element"); // 删除指定的元素

• 检查是否包含某元素：

  set.contains("element"); // 检查 Set 中是否包含指定的元素

• 获取大小：

  int size = set.size(); // 获取 Set 中元素的数量

• 遍历 Set：

  for (String element : set) { System.out.println(element); }

3.4 Set 的应用场景

1. 去重：Set 不允许重复元素，因此常用于需要自动去重的场景。比如，在集合中保存一组用户 ID，并确保每个用户只能添加一次。
2. 快速查找：Set 可以提供高效的查找操作，特别是 HashSet，可以在 O(1) 时间内判断一个元素是否存在。
3. 集合操作：Set 接口常用于实现数学集合的操作，如交集、并集和差集等。
   • 交集：两个集合中的公共元素。

     set1.retainAll(set2);

   • 并集：两个集合的所有元素。

     set1.addAll(set2);

   • 差集：属于第一个集合但不属于第二个集合的元素。

     set1.removeAll(set2);

3.5 线程安全问题

        HashSet 和其他常见的 Set 实现类都不是线程安全的。在多线程环境下，可能会出现并发修改异常。可以通过 Collections.synchronizedSet() 方法将 Set 包装为线程安全的版本，或者使用并发包中的 ConcurrentSkipListSet 来处理多线程场景。

3.6 Set 与 List 的区别

• 是否允许重复元素：Set 不允许重复元素，而 List 允许。
• 有序性：List 保证元素的插入顺序，而 Set 的实现类（如 HashSet）通常不保证顺序。LinkedHashSet 保证插入顺序，TreeSet 保证排序顺序。
• 访问方式：List 可以通过索引随机访问元素，而 Set 没有索引，需要通过遍历来访问。

3.7 小结

• HashSet：无序，不允许重复，适合快速查找和去重。
• LinkedHashSet：有序，不允许重复，适合需要保留插入顺序的场景。
• TreeSet：有序（按自然顺序或自定义顺序），不允许重复，适合需要排序的场景。