一、简介

集合的定义和作用

Java集合是用于存储和操作一组对象的数据结构。它提供了一组接口和类，用于处理不同类型的集合数据，如列表、集、映射等。

Java集合的主要作用是：

1. 存储对象：Java集合可以存储不同类型的对象，并提供了方便的方法来添加、删除和访问集合中的元素。

2. 管理数据：集合提供了多种数据结构，如列表、集、映射等，可以根据不同的需求选择合适的数据结构来管理数据。比如，列表可以按照插入顺序存储数据，集可以保证元素的唯一性，映射可以通过键值对来存储和访问数据等。

3. 提供算法和操作：Java集合提供了一系列算法和操作，如排序、查找、过滤等，可以方便地对集合中的元素进行处理和操作。

4. 提高效率：集合类中的数据结构和算法经过优化，可以提高程序的执行效率。比如，使用HashSet来存储大量数据时，可以通过散列算法快速查找元素，而不需要遍历整个集合。

集合框架的基本概念

Java集合框架是Java编程语言提供的一组类和接口，用于存储、操作和处理数据集合。它提供了各种类型的数据结构，如列表、集合、映射等，以及用于操作和处理这些数据结构的算法和工具。Java集合框架的设计目标是提供高性能、可靠性和可扩展性的数据结构和算法。

Java集合框架的基本概念如下：

1. 接口（Interface）：Java集合框架中定义了许多接口，如List、Set、Map等。接口定义了一组操作集合的方法，是集合框架的核心部分。

2. 类（Class）：Java集合框架提供了实现接口的具体类，如ArrayList、HashSet、HashMap等。这些类实现了接口定义的方法，提供了具体的数据结构和算法。

3. 列表（List）：列表是有序的集合，可以包含重复的元素。Java集合框架提供了多个列表的实现类，如ArrayList、LinkedList等。

4. 集合（Set）：集合是无序的、不重复的元素的集合。Java集合框架提供了多个集合的实现类，如HashSet、TreeSet等。

5. 映射（Map）：映射是一种键值对的集合，每个键对应一个值。Java集合框架提供了多个映射的实现类，如HashMap、TreeMap等。

6. 队列（Queue）：队列是一种先进先出（FIFO）的数据结构。Java集合框架提供了多个队列的实现类，如LinkedList、PriorityQueue等。

7. 迭代器（Iterator）：迭代器用于遍历集合中的元素，提供了统一的访问集合元素的方式。通过迭代器，可以依次访问集合中的每个元素。

8. 泛型（Generics）：Java集合框架使用泛型来增加类型安全性和代码的可读性。通过泛型，可以指定集合中存储的元素类型。

9. 算法（Algorithm）：Java集合框架提供了许多算法和工具类，用于对集合进行排序、搜索、过滤等操作。这些算法和工具类可以方便地操作集合中的元素。

Java集合框架的使用非常广泛，它提供了丰富的数据结构和算法，可以满足各种不同的编程需求。

集合框架的接口和实现类

Java集合框架提供了一些核心接口和相关的实现类，用于存储和操作不同类型的集合数据。

1. Collection 接口：

   • List 接口：有序、可重复的集合，可以通过索引访问元素。常见的实现类有 ArrayList、LinkedList、Vector。
   • Set 接口：无序、不可重复的集合，不允许存储相同元素。常见的实现类有 HashSet、TreeSet、LinkedHashSet。

2. Map 接口：

   • HashMap 类：无序的键值对集合，根据键来存储和访问。常用于快速查找和存储关联数据。
   • TreeMap 类：有序的键值对集合，按照键的自然顺序或特定比较器定义的顺序来存储和访问。
   • LinkedHashMap 类：有序的键值对集合，按照插入顺序或访问顺序来存储和访问。

3. Queue 接口：

   • LinkedList 类：实现了队列的数据结构，支持先进先出（FIFO）的元素访问方式。

4. 栈（Stack）接口：

   • Stack 类：继承自 Vector 类，实现了后进先出（LIFO）的元素访问方式。

5. 接口工具类：

   • Collections 类：提供了一组静态方法，用于对集合对象进行常见操作，如排序、查找、反转等。

除了上述接口和实现类之外，Java集合框架还提供了其他接口和实现类，用于特定的集合需求。例如：

• Deque 接口：双端队列，可以在两端插入和删除元素。
• PriorityQueue 类：优先队列，按照元素的顺序进行访问，优先级高的元素先被访问。
• BitSet 类：位集合，用于存储和操作位信息。

集合框架的继承结构

1. Collection 接口：是所有集合的基本接口，定义了对集合元素的基本操作。它继承自 Iterable 接口，表示支持迭代访问。

2. List 接口：继承自 Collection 接口，表示有序、可重复的集合。List 接口提供了按索引访问和操作集合元素的方法。常见的实现类有 ArrayList、LinkedList、Vector。

3. Set 接口：继承自 Collection 接口，表示无序、不可重复的集合。Set 接口不允许存储相同的元素。常见的实现类有 HashSet、TreeSet、LinkedHashSet。

4. Queue 接口：继承自 Collection 接口，表示一种特殊的集合，用于实现队列（先进先出）的数据结构。Queue 接口提供了添加、删除和检查元素的方法。常见的实现类有 LinkedList、PriorityQueue。

5. Deque 接口：继承自 Queue 接口，表示双端队列，可以在两端插入和删除元素。Deque 接口提供了在队首、队尾进行插入和删除操作的方法。常见的实现类有 LinkedList、ArrayDeque。

6. Map 接口：表示键值对的集合，每个键都是唯一的。Map 接口定义了对键值对进行操作的方法。常见的实现类有 HashMap、TreeMap、LinkedHashMap。

除了上述基本接口之外，还有一些继承于上述接口的子接口和实现类，用于扩展集合框架的功能。

二、List集合

List集合的接口和实现类

List 是 Java 集合框架中的接口之一，它继承自 Collection 接口。List 表示有序、可重复的集合，每个元素都有一个对应的索引，可以通过索引访问和操作元素。

1. List 接口：

   • 方法：List 接口继承自 Collection 接口，除了 Collection 接口的方法外，额外提供了一些特有的方法，如根据索引操作元素、获取子列表等。
   • 实现类：List 接口的主要实现类包括 ArrayList、LinkedList 和 Vector。

2. ArrayList 类：

   • 实现了 List 接口，底层使用数组来存储元素，支持动态扩容。
   • 优点：随机访问元素快速，效率高；适用于频繁的随机访问和遍历操作。
   • 缺点：插入和删除元素的效率相对较低，需要移动大量元素。
   • 线程不安全：ArrayList 不是线程安全的，若需多线程操作，建议使用线程安全的实现类 Vector 或 Collections 工具类的 synchronizedList 方法进行包装。

3. LinkedList 类：

   • 实现了 List 和 Deque 接口，底层使用双向链表来存储元素。
   • 优点：插入和删除元素的效率高，不需要移动大量元素；支持高效的首尾操作。
   • 缺点：随机访问元素效率相对较低。
   • 在需要频繁插入和删除元素的场景中使用 LinkedList 效果更好。

4. Vector 类：

   • 实现了 List 接口，底层也使用数组来存储元素，类似于 ArrayList。
   • 优点：线程安全，可以在多线程环境下使用；支持动态扩容。
   • 缺点：相比 ArrayList，性能稍差。
   • 注意：Vector 是较早的集合实现类，在现代开发中，一般推荐使用 ArrayList 或 LinkedList。

ArrayList和LinkedList的区别和优缺点

ArrayList 和 LinkedList 是 List 接口的两个常见实现类，它们在底层数据结构和性能特点上有所不同。

ArrayList：

• 底层数据结构：ArrayList 使用数组来实现，内部维护一个 Object 类型的数组，默认初始容量为 10。
• 优点：
  • 随机访问元素快速：由于是基于数组实现，通过索引可以直接访问元素，查找和读取效率高。
  • 空间效率高：相对于链表结构，数组具有连续的内存空间，不需要额外的存储空间。
  • 迭代操作效率高：迭代操作和遍历效率高，适用于频繁的随机访问和遍历操作。
• 缺点：
  • 插入和删除元素的效率较低：插入和删除元素需要移动大量元素，特别是在数组中间或开头进行操作时。
  • 动态扩容开销：当元素超过当前容量时，需要进行动态扩容，可能导致性能下降。

LinkedList：

• 底层数据结构：LinkedList 使用双向链表来实现，每个节点包含前后指针以及元素值。
• 优点：
  • 插入和删除元素的效率高：由于是链表结构，插入和删除元素只需调整相邻节点的指针，效率较高。
  • 支持高效的首尾操作：对头部和尾部元素的插入和删除操作效率极高。
• 缺点：
  • 随机访问元素效率相对较低：要查找特定索引的元素需要从头或尾开始遍历链表，时间复杂度为 O(n)。
  • 需要更多存储空间：相对于数组，链表需要额外的指针来维护节点之间的连接关系。

选择 ArrayList 还是 LinkedList 取决于具体的应用场景和操作需求：

• 如果需要频繁进行随机访问、读取和遍历操作，而插入和删除操作较少，可以选择 ArrayList，它具有更高的访问和读取性能。
• 如果需要频繁进行插入和删除操作，尤其是在链表的头部或尾部进行操作，则选择 LinkedList 更加合适，它具有更高的插入和删除性能。
• 如果涉及到多线程环境，建议使用线程安全的 Vector 或利用 Collections 工具类的 synchronizedList 方法包装 ArrayList/LinkedList。

List集合的常用操作和方法

1. 添加元素操作：

   • boolean add(E element): 将指定元素添加到列表的末尾。
   • void add(int index, E element): 在指定索引位置插入指定元素。
   • boolean addAll(Collection<? extends E> c): 将指定集合中的所有元素添加到列表的末尾。
   • boolean addAll(int index, Collection<? extends E> c): 将指定集合中的所有元素插入到指定索引位置。

2. 删除元素操作：

   • boolean remove(Object o): 从列表中删除指定元素的第一个匹配项。
   • E remove(int index): 删除指定索引位置处的元素。
   • boolean removeAll(Collection<?> c): 从列表中删除与指定集合中相同的所有元素。
   • void clear(): 清空列表中的所有元素。

3. 获取元素操作：

   • E get(int index): 返回指定索引位置的元素。
   • int indexOf(Object o): 返回指定元素第一次出现的索引。
   • int lastIndexOf(Object o): 返回指定元素最后一次出现的索引。
   • List<E> subList(int fromIndex, int toIndex): 返回列表中指定范围的子列表。

4. 修改元素操作：

   • E set(int index, E element): 将指定索引位置的元素替换为指定元素。

5. 判断元素是否存在：

   • boolean contains(Object o): 判断列表是否包含指定元素。
   • boolean containsAll(Collection<?> c): 判断列表是否包含指定集合中的所有元素。

6. 判断集合大小和空判断：

   • int size(): 返回列表中的元素个数。
   • boolean isEmpty(): 判断列表是否为空。

7. 遍历操作：

   • 使用 for-each 循环遍历列表中的元素。
   • 使用迭代器（Iterator）遍历列表中的元素。

List集合的遍历方式

1. 使用 for 循环遍历：

   for (int i = 0; i < list.size(); i++) {E element = list.get(i);// 对元素进行操作
   }
   

   通过索引可以逐个访问列表中的元素，并进行相应的操作。

2. 使用增强型 for 循环遍历（foreach 循环）：

   for (E element : list) {// 对元素进行操作
   }
   

   增强型 for 循环可以直接遍历列表中的元素，无需使用索引。

3. 使用迭代器（Iterator）遍历：

   Iterator<E> iterator = list.iterator();
   while (iterator.hasNext()) {E element = iterator.next();// 对元素进行操作
   }
   

   通过调用 iterator() 方法获取迭代器对象，利用 hasNext() 方法判断是否还有下一个元素，通过 next() 方法获取下一个元素进行操作。

4. 使用 Stream API 遍历（Java 8 及以上）：

   list.stream().forEach(element -> {// 对元素进行操作
   });
   

   使用 Stream API 的 stream() 方法将列表转换为流，然后利用 forEach() 方法对流中的每个元素进行操作。

三、Set集合

Set集合的接口和实现类

Set 接口是 Java 集合框架的一部分，它扩展了 Collection 接口。Set 表示一个不允许包含重复元素的集合。

Set 接口的特点主要包括：

1. 不允许重复：Set 中的元素是唯一的，如果尝试向 Set 中添加重复元素，则添加操作会失败。
2. 无序性：Set 中的元素没有固定的顺序。不同的实现类可能以不同的方式存储和迭代元素，因此不能保证元素的存取顺序和插入顺序一致。
3. 允许存储 null 元素：Set 中可以存储一个 null 元素（某些实现类除外）。

常见的 Set 实现类包括：

• HashSet：基于哈希表实现。HashSet 使用 HashMap 存储元素，并使用元素的哈希码进行索引，因此添加、删除和查找操作的时间复杂度为 O(1)。它是最常用的 Set 实现类，但不保证元素的顺序。
• LinkedHashSet：继承自 HashSet，基于哈希表和链表实现。它通过链表维护元素的插入顺序，因此可以有序地遍历元素。性能略低于 HashSet，但仍然比较高效。
• TreeSet：基于红黑树实现。TreeSet 中的元素会按照自然顺序（或者通过 Comparator 接口定义的顺序）进行排序。因此，TreeSet 可以提供一系列有序集合操作。
• EnumSet：专门用于存储枚举类型的 Set 集合。由于枚举类型的取值是有限且固定的，EnumSet 内部使用位向量实现，具有极高的效率。

需要注意的是，Set 接口本身不能直接实例化，必须使用具体的实现类来创建对象。示例代码如下：

Set<String> set = new HashSet<>();  // 创建一个 HashSet 对象

根据需求和特定场景，选择适合的 Set 实现类。HashSet 是最常用的 Set 实现类，适用于大多数情况。如果需要保持插入顺序或按照自然顺序排序，可以选择 LinkedHashSet 或 TreeSet。当需要存储枚举类型的元素时，EnumSet 是最佳选择，因为它是高效的。

HashSet和TreeSet的区别和优缺点

1. 内部实现机制不同：

   • HashSet 使用哈希表（HashMap 实现）存储元素，根据元素的哈希码进行索引。因此，HashSet 具有快速的插入、删除和查找操作，时间复杂度为 O(1)。
   • TreeSet 则是基于红黑树（TreeMap 实现）存储元素，它会按照元素的自然顺序（或者通过 Comparator 接口定义的顺序）进行排序。因此，TreeSet 提供了一些有序集合操作，如范围查找和排序等。

2. 元素顺序：

   • HashSet 中的元素没有特定的顺序，不保证元素的存取顺序和插入顺序一致。因为 HashSet 使用哈希表存储数据，元素在哈希表中的位置是根据元素的哈希码决定的，而不是插入的顺序。
   • TreeSet 中的元素是有序的，根据元素的自然顺序进行排序。或者通过传入的 Comparator 接口来定义排序规则。

3. 性能：

   • HashSet 的插入、删除和查找操作的平均时间复杂度为 O(1)。但是，当哈希表发生冲突时，性能会有所下降，并且在极端情况下，最坏时间复杂度可能达到 O(n)。
   • TreeSet 的插入、删除和查找操作的时间复杂度为 O(log n)，其中 n 是 TreeSet 中元素的数量。由于红黑树的自平衡性质，它可以保持较为稳定的性能。

4. 允许存储 null 元素的情况：

   • HashSet 允许存储一个 null 元素（只能存储一个），因为哈希表中使用特殊的方式处理 null 值。
   • TreeSet 不允许存储 null 元素，因为它需要对元素进行排序，而 null 值无法进行比较。

综上所述，HashSet 适用于需要快速插入、删除和查找的场景，并不关心元素的顺序。而 TreeSet 适用于需要有序集合操作的场景，例如范围查找和排序等，但由于红黑树的特性，其性能相对较低。同时，请注意 HashSet 和 TreeSet 都是线程不安全的，如果在多线程环境下使用，需要通过 Collections 工具类提供的 synchronizedSet 方法进行包装。

Set集合的常用操作和方法

1. 添加元素：

   • boolean add(E element): 将指定元素添加到 Set 中。如果元素已经存在于 Set 中，则添加操作失败并返回 false。
   • 示例代码：

     Set<String> set = new HashSet<>();
     set.add("apple");
     set.add("banana");
     

2. 移除元素：

   • boolean remove(Object o): 从 Set 中移除指定元素。如果元素存在于 Set 中，则移除操作成功并返回 true。
   • 示例代码：

     set.remove("apple");
     

3. 检查元素是否存在：

   • boolean contains(Object o): 判断 Set 中是否包含指定元素。如果元素存在于 Set 中，则返回 true。
   • 示例代码：

     boolean contains = set.contains("banana");
     

4. 获取元素数量：

   • int size(): 返回 Set 中元素的数量。
   • 示例代码：

     int size = set.size();
     

5. 判断是否为空集：

   • boolean isEmpty(): 判断 Set 是否为空集。如果 Set 不包含任何元素，则返回 true。
   • 示例代码：

     boolean isEmpty = set.isEmpty();
     

6. 清空集合：

   • void clear(): 清空 Set 中的所有元素，使其变为空集。
   • 示例代码：

     set.clear();
     

7. 迭代器：

   • Iterator<E> iterator(): 返回一个迭代器，用于遍历 Set 中的元素。
   • 示例代码：

     Iterator<String> iterator = set.iterator();
     while (iterator.hasNext()) {String element = iterator.next();// 处理元素
     }
     

需要注意的是，Set 集合没有提供按索引访问元素的方法，因为在 Set 中元素没有固定的顺序。

此外，Set 接口还继承了 Collection 接口中定义的一些方法，如addAll()、removeAll()、retainAll()、containsAll() 等，用于集合之间的操作。

Set集合的遍历方式

1. 迭代器遍历：
   迭代器是一种用于遍历集合元素的通用方式，在遍历过程中允许修改集合。Set 集合的迭代器通过调用iterator()方法获取，然后使用hasNext()和next()方法遍历元素。

   示例代码：

   Set<String> set = new HashSet<>();
   // 添加元素...Iterator<String> iterator = set.iterator();
   while (iterator.hasNext()) {String element = iterator.next();// 处理元素
   }
   

2. 增强型 for 循环遍历：
   增强型 for 循环是遍历集合元素的简化方式，适用于遍历整个集合的情况。它不需要显式地使用迭代器，只需指定一个变量来接收每个元素。

   示例代码：

   Set<String> set = new HashSet<>();
   // 添加元素...for (String element : set) {// 处理元素
   }
   

3. forEach() 方法遍历（Java 8+）：
   Java 8 引入的 forEach() 方法提供了一种更简洁的遍历方式，可以使用 Lambda 表达式来处理每个元素。

   示例代码：

   Set<String> set = new HashSet<>();
   // 添加元素...set.forEach(element -> {// 处理元素
   });
   

无论使用哪种遍历方式，都可以用于遍历 Set 集合中的所有元素。需要注意的是，在遍历过程中不要修改集合的内容，否则可能导致遍历失败或出现异常。另外，Set 集合中的元素没有固定的顺序，因此无法保证遍历的顺序与添加的顺序相同。

四、Map集合

Map集合的接口和实现类

Map 是 Java 集合框架中用于存储键值对的接口，它提供了一种将键映射到值的方式。在 Map 中，键是唯一的，而值可以重复。

常用的 Map 实现类：

1. HashMap：
   HashMap 是最常用的 Map 实现类，它基于哈希表实现，允许使用 null 作为键和值。HashMap 不保证遍历顺序，性能较高。

2. TreeMap：
   TreeMap 基于红黑树实现，按键的自然顺序或自定义比较器的顺序对键进行排序。TreeMap 不允许使用 null 作为键，但允许使用 null 作为值。

3. LinkedHashMap：
   LinkedHashMap 继承自 HashMap，底层使用哈希表和双向链表实现。它保持了元素插入的顺序，并可以使用访问顺序进行迭代。

4. HashTable：
   HashTable 是早期的 Map 实现类，基于哈希表实现。它不允许使用 null 作为键或值，线程安全但性能较差，通常不推荐使用。

HashMap和TreeMap的区别和优缺点

HashMap：

• 特点：

  • 基于哈希表实现，通过键的哈希值进行快速查找和存储。
  • 不保证遍历顺序，即元素的存储顺序与插入顺序无关。
  • 允许使用 null 作为键和值。
  • 非线程安全。

• 优点：

  • 在大多数情况下，HashMap 的操作时间复杂度为 O(1)，平均性能较高。
  • 适用于不需要关心元素顺序的场景，例如快速查找、存储、删除元素。
  • 内存占用相对较小。

• 缺点：

  • 不保证元素的遍历顺序，所以无法按照插入顺序或者键的顺序进行迭代。
  • HashMap 不是线程安全的，如果需要在多线程环境中使用，需要进行外部同步。

TreeMap：

• 特点：

  • 基于红黑树实现，通过键的自然顺序或自定义比较器进行排序。
  • 按键的有序状态维护元素，支持按键范围查询和遍历。
  • 不允许使用 null 作为键，但允许使用 null 作为值。
  • 非线程安全。

• 优点：

  • TreeMap 保证元素的有序性，可以按照键的自然顺序或者自定义比较器的顺序进行迭代。
  • 适用于需要按照键的顺序进行遍历、范围查询的场景。
  • 提供了一些附加的方法，如 firstKey()、lastKey() 等。

• 缺点：

  • 插入、删除和查找操作的时间复杂度为 O(logN)，性能略低于 HashMap。
  • 内存占用相对较大。

选择使用 HashMap 还是 TreeMap 取决于实际应用场景：

• 如果对于元素的插入、删除和查找操作要求性能较高，并且不关心元素的顺序，可以选择使用 HashMap。
• 如果需要按照键的顺序进行遍历、范围查询等操作，或者需要根据键的自然顺序进行排序，可以选择使用 TreeMap。
• 在多线程环境下，需要考虑线程安全性，可以使用 ConcurrentHashMap 来替代 HashMap 或 ConcurrentSkipListMap 来替代 TreeMap。

Map集合的常用操作和方法

1. 添加和修改元素：

   • V put(K key, V value): 将指定的键值对添加到 Map 中，如果键已存在，则会覆盖原有的值并返回旧值。
   • void putAll(Map<? extends K, ? extends V> map): 将指定 Map 中的所有键值对添加到当前 Map 中。

2. 获取元素：

   • V get(Object key): 返回指定键对应的值，如果键不存在，则返回 null。
   • V getOrDefault(Object key, V defaultValue): 返回指定键对应的值，如果键不存在，则返回默认值。
   • boolean containsKey(Object key): 判断 Map 中是否包含指定的键。
   • boolean containsValue(Object value): 判断 Map 中是否包含指定的值。

3. 移除元素：

   • V remove(Object key): 根据键移除 Map 中的键值对，并返回被移除的值。
   • void clear(): 清空 Map 中的所有键值对。

4. 获取键、值和键值对数量：

   • Set<K> keySet(): 返回 Map 中所有键组成的 Set 集合。
   • Collection<V> values(): 返回 Map 中所有值组成的集合。
   • Set<Map.Entry<K, V>> entrySet(): 返回包含所有键值对的 Set 集合。
   • int size(): 返回 Map 中键值对的数量。
   • boolean isEmpty(): 判断 Map 是否为空。

5. 其他常用方法：

   • boolean equals(Object obj): 判断当前 Map 是否与指定对象相等。
   • int hashCode(): 返回当前 Map 的哈希码值。
   • void replaceAll(BiFunction<? super K, ? super V, ? extends V> function): 使用指定的函数对每个键值对进行替换。
   • void forEach(BiConsumer<? super K, ? super V> action): 对每个键值对执行指定的操作。
   • V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction): 使用指定的函数计算给定键的值，并将结果存储回 Map。
   • boolean replace(K key, V oldValue, V newValue): 替换给定键的值，仅当旧值与指定值相等时才替换。

Map集合的遍历方式

1. 使用 keySet() 遍历键值对：

   Map<K, V> map = ...;
   for (K key : map.keySet()) {V value = map.get(key);// 使用 key 和 value 进行操作
   }
   

   通过 keySet() 方法获取 Map 中所有的键组成的 Set，然后使用增强型 for 循环遍历键，再通过键获取对应的值。

2. 使用 entrySet() 遍历键值对：

   Map<K, V> map = ...;
   for (Map.Entry<K, V> entry : map.entrySet()) {K key = entry.getKey();V value = entry.getValue();// 使用 key 和 value 进行操作
   }
   

   通过 entrySet() 方法获取包含所有键值对的 Set，每个键值对通过 Map.Entry<K, V> 表示，可以依次获取键和值进行操作。

3. 使用 forEach() 方法遍历键值对：

   Map<K, V> map = ...;
   map.forEach((key, value) -> {// 使用 key 和 value 进行操作
   });
   

   在 Java 8 及以上版本中，Map 接口提供了 forEach() 方法，可以直接传入一个 Lambda 表达式，以此遍历每个键值对。

4. 使用迭代器遍历键值对：

   Map<K, V> map = ...;
   Iterator<Map.Entry<K, V>> iterator = map.entrySet().iterator();
   while (iterator.hasNext()) {Map.Entry<K, V> entry = iterator.next();K key = entry.getKey();V value = entry.getValue();// 使用 key 和 value 进行操作
   }
   

   通过 entrySet() 方法获取 Set，并使用 iterator() 获取迭代器进行遍历，然后依次获取每个键值对的键和值。

在遍历 Map 集合时，可以根据具体的需求选择合适的遍历方式。需要注意的是，在遍历过程中，不要修改 Map 集合的结构，否则可能会抛出 ConcurrentModificationException 异常。如有需要修改的情况，可以使用迭代器的 remove() 方法来删除当前遍历的键值对。

五、Queue集合

Queue集合的接口和实现类

Queue 是 Java 集合框架中用于表示队列（先进先出）的接口，提供了在队列两端进行元素操作的方法。

在 Java 中，Queue 接口的常用实现类有：

1. LinkedList：LinkedList 实现了 Queue 接口，并且提供了丰富的队列操作方法。它基于链表结构，可以高效地添加、删除元素，适用于频繁的插入和删除操作。
2. ArrayDeque：ArrayDeque 实现了 Queue 接口，内部使用动态数组实现。它具有高效的添加和删除元素的能力，并且支持双端操作，可以在队列两端进行添加和删除。
3. PriorityQueue: PriorityQueue 是 Java 集合框架中的一个实现了 Queue 接口的优先队列类。它是一个有序的队列，根据元素的优先级进行排序。

这些实现类都是线程不安全的，如果需要在多线程环境中使用队列，可以使用 ConcurrentLinkedQueue 或 ArrayBlockingQueue 等线程安全的实现类。

Queue的常用操作和方法

1. 添加元素：

   • boolean add(E e): 将指定元素添加到队列的尾部，如果队列已满则抛出异常。
   • boolean offer(E e): 将指定元素添加到队列的尾部，如果队列已满则返回 false。

2. 删除元素：

   • E remove(): 移除并返回队列头部的元素，如果队列为空则抛出异常。
   • E poll(): 移除并返回队列头部的元素，如果队列为空则返回 null。

3. 获取头部元素：

   • E element(): 返回队列头部的元素，但不移除，如果队列为空则抛出异常。
   • E peek(): 返回队列头部的元素，但不移除，如果队列为空则返回 null。

4. 判断队列是否为空：

   • boolean isEmpty(): 判断队列是否为空。

5. 获取队列大小：

   • int size(): 返回队列中的元素个数。

Queue 接口继承了 Collection 接口，并且对于添加、删除和获取元素进行了特殊定义，以满足队列的特性。

常用的 Queue 实现类如 LinkedList 和 ArrayDeque 还提供了一些其他的方法：

• boolean contains(Object o): 判断队列是否包含指定元素。
• void clear(): 清空队列中的所有元素。
• Iterator<E> iterator(): 返回队列元素的迭代器，可以用于遍历队列中的元素。

需要注意的是，Queue 接口没有提供直接访问队列中间元素的方法，因为队列的操作应遵循先进先出的原则，只能在队列两端进行操作。

PriorityQueue的特点和用法

特点

1. 优先级排序： PriorityQueue 会根据元素的自然顺序或者通过自定义的比较器(comparator)来确定元素的优先级。默认情况下，元素被认为是可比较的，并且按照升序排序。但你也可以通过构造方法或者使用比较器来指定元素的排序规则。

2. 底层数据结构： PriorityQueue 底层使用数组（完全二叉树形式的数组）实现，这使得 PriorityQueue 在插入和删除元素时具有较好的性能。

3. 元素无重复： PriorityQueue 不允许添加重复的元素。如果试图添加已经存在的元素，不会进行添加操作，而是保持队列不变。

4. 提供队列操作方法： PriorityQueue 实现了 Queue 接口，提供了常用的队列操作方法，包括添加、删除、获取元素等。

5. 不保证迭代顺序： PriorityQueue 不保证在迭代时按照优先级的顺序返回元素。即使插入时是按照优先级排序的，迭代时仍可能返回以不同顺序存储的元素。

6. 快速访问最小元素： PriorityQueue 提供了 peek() 方法用于获取队列中优先级最高的元素，而不会删除它。这使得可以高效地获取队列中的最小元素。

7. 适用于任务调度、事件排序等场景： PriorityQueue 的特性使其特别适用于任务调度、事件排序等场景。通过将任务或事件按照优先级加入到 PriorityQueue 中，并从队列中取出执行，可以实现优先级高的任务或事件先被处理。

• 如果元素没有实现 Comparable 接口，则在创建 PriorityQueue 时需要传入自定义的比较器来指定元素的排序规则。
• 当使用自定义的比较器时，需要保证比较器的逻辑正确，以避免 PriorityQueue 按照错误的顺序进行操作。

用法

1. 创建 PriorityQueue： 可以使用无参构造方法创建一个空的 PriorityQueue，默认情况下元素按照自然顺序排序。也可以使用带有比较器参数的构造方法来创建一个指定排序规则的 PriorityQueue。

   // 创建一个空的 PriorityQueue，默认按照自然顺序排序
   PriorityQueue<Integer> pq1 = new PriorityQueue<>();// 创建一个指定排序规则的 PriorityQueue，按照降序排序
   PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());// 创建一个指定排序规则的 PriorityQueue，使用自定义比较器
   PriorityQueue<Integer> pq3 = new PriorityQueue<>((a, b) -> b - a);
   

2. 添加元素： 使用 add() 或者 offer() 方法向 PriorityQueue 添加元素。

   pq1.add(5);
   pq1.offer(10);
   pq1.add(3);
   

3. 获取队首元素： 使用 peek() 方法获取 PriorityQueue 中优先级最高的元素，而不会删除它。

   Integer highestPriorityElement = pq1.peek();
   

4. 删除队首元素： 使用 poll() 方法删除并返回 PriorityQueue 中优先级最高的元素。

   Integer highestPriorityElement = pq1.poll();
   

5. 检查队列是否为空： 使用 isEmpty() 方法判断 PriorityQueue 是否为空。

   boolean isQueueEmpty = pq1.isEmpty();
   

6. 获取队列大小： 使用 size() 方法获取 PriorityQueue 中元素的个数。

   int queueSize = pq1.size();
   

7. 迭代遍历元素： 由于 PriorityQueue 不保证按照优先级顺序迭代元素，如果需要对元素进行遍历操作，建议使用迭代器或转换为数组进行操作。

   // 使用迭代器遍历元素
   Iterator<Integer> iterator = pq1.iterator();
   while (iterator.hasNext()) {Integer element = iterator.next();// 处理元素
   }// 转换为数组后遍历元素
   Integer[] arr = pq1.toArray(new Integer[0]);
   for (Integer element : arr) {// 处理元素
   }
   

需要注意的是，PriorityQueue 不支持修改操作（例如更新指定位置的元素），因为 PriorityQueue 的设计目标是按照优先级处理元素。如果需要修改操作，可能需要先将元素删除，然后再添加修改后的元素。

六、Collections工具类

Collections类的常用方法

Collections 类是 Java 集合框架提供的一个实用工具类，它包含了大量的静态方法，用于对集合进行操作和处理。

1. 排序操作：

   • sort(List<T> list): 对指定的 List 进行升序排序，要求元素必须实现 Comparable 接口。
   • sort(List<T> list, Comparator<? super T> c): 对指定的 List 进行排序，使用自定义的 Comparator 来定义元素之间的比较规则。
   • reverse(List<?> list): 反转指定 List 中元素的顺序。

2. 查找和替换操作：

   • binarySearch(List<? extends Comparable<? super T>> list, T key): 在指定 List 中使用二分查找算法查找指定的元素，返回元素的索引值。
   • binarySearch(List<? extends T> list, T key, Comparator<? super T> c): 在指定 List 中使用自定义的比较器进行二分查找，返回元素的索引值。
   • replaceAll(List<T> list, T oldVal, T newVal): 将 List 中所有等于 oldVal 的元素替换为 newVal。

3. Synchronized 安全操作：

   • synchronizedList(List<T> list): 返回一个线程安全的 List，所有对该 List 的修改操作都是原子操作。
   • synchronizedSet(Set<T> s): 返回一个线程安全的 Set，所有对该 Set 的修改操作都是原子操作。
   • synchronizedMap(Map<K,V> m): 返回一个线程安全的 Map，所有对该 Map 的修改操作都是原子操作。

4. 不可变集合操作：

   • unmodifiableList(List<? extends T> list): 返回一个不可修改的 List，任何修改操作都会抛出 UnsupportedOperationException 异常。
   • unmodifiableSet(Set<? extends T> s): 返回一个不可修改的 Set。
   • unmodifiableMap(Map<? extends K,? extends V> m): 返回一个不可修改的 Map。

5. 其他常用方法：

   • max(Collection<? extends T> coll): 返回指定 Collection 中的最大元素，要求元素必须实现 Comparable 接口。
   • min(Collection<? extends T> coll): 返回指定 Collection 中的最小元素，要求元素必须实现 Comparable 接口。
   • isEmpty(Collection<?> coll): 判断指定 Collection 是否为空。
   • reverseOrder(): 返回一个比较器，用于实现降序排序。
   • shuffle(List<?> list): 随机打乱指定 List 中元素的顺序。

Collections类的排序方法

Collections 类提供了多种排序方法来对集合进行排序。这些排序方法可以用于对 List、Set 和数组等集合进行排序。

1. sort(List list)：

   • 方法签名：public static <T extends Comparable<? super T>> void sort(List<T> list)
   • 描述：对指定的 List 进行升序排序，要求元素必须实现 Comparable 接口，即具有可比较性。
   • 示例：

     List<Integer> numbers = new ArrayList<>(List.of(5, 2, 8, 1, 9));
     Collections.sort(numbers);
     System.out.println(numbers);  // 输出：[1, 2, 5, 8, 9]
     

2. sort(List list, Comparator<? super T> c)：

   • 方法签名：public static <T> void sort(List<T> list, Comparator<? super T> c)
   • 描述：对指定的 List 进行排序，使用自定义的 Comparator 来定义元素之间的比较规则。
   • 示例：

     List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie", "David"));
     Collections.sort(names, (a, b) -> a.length() - b.length());
     System.out.println(names);  // 输出：[Bob, Alice, David, Charlie]
     

3. reverse(List<?> list)：

   • 方法签名：public static void reverse(List<?> list)
   • 描述：反转指定 List 中元素的顺序。
   • 示例：

     List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4, 5));
     Collections.reverse(numbers);
     System.out.println(numbers);  // 输出：[5, 4, 3, 2, 1]
     

4. shuffle(List<?> list)：

   • 方法签名：public static void shuffle(List<?> list)
   • 描述：随机打乱指定 List 中元素的顺序。
   • 示例：

     List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie", "David"));
     Collections.shuffle(names);
     System.out.println(names);  // 输出类似：[David, Alice, Bob, Charlie]
     

上述方法中的排序操作会直接修改原始集合，所以建议在排序前创建集合的副本，以保留原始数据。此外，这些排序方法的时间复杂度取决于具体的排序算法，一般情况下是 O(n log n)。如果集合较大，可以考虑使用并行排序方法 sort​(List<T> list) 和 sort​(List<T> list, Comparator<? super T> c) 来提高排序速度。

Collections类的查找和替换方法

1. binarySearch(List<? extends Comparable<? super T>> list, T key)：

   • 方法签名：public static <T extends Comparable<? super T>> int binarySearch(List<? extends T> list, T key)
   • 描述：在指定的有序 List 中使用二分查找算法查找指定的元素，并返回元素的索引值。如果元素不存在，返回的是一个负数，表示元素应该插入的位置。
   • 示例：

     List<Integer> numbers = new ArrayList<>(List.of(1, 3, 5, 7, 9));
     int index = Collections.binarySearch(numbers, 5);
     System.out.println(index);  // 输出：2
     

2. binarySearch(List<? extends T> list, T key, Comparator<? super T> c)：

   • 方法签名：public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
   • 描述：在指定的有序 List 中使用自定义的 Comparator 进行二分查找，返回元素的索引值。
   • 示例：

     List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie", "David"));
     int index = Collections.binarySearch(names, "Charlie", (a, b) -> a.length() - b.length());
     System.out.println(index);  // 输出：1
     

3. replaceAll(List list, T oldVal, T newVal)：

   • 方法签名：public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)
   • 描述：将 List 中所有等于 oldVal 的元素替换为 newVal。如果有替换发生，则返回 true，否则返回 false。
   • 示例：

     List<Integer> numbers = new ArrayList<>(List.of(1, 2, 2, 3, 2));
     boolean replaced = Collections.replaceAll(numbers, 2, 7);
     System.out.println(numbers);    // 输出：[1, 7, 7, 3, 7]
     System.out.println(replaced);   // 输出：true
     

这些查找和替换方法可以方便地对集合进行操作。二分查找方法对有序集合特别有用，可以快速定位元素的位置。替换方法可用于将集合中特定元素替换为新的元素。需要注意的是，二分查找方法要求集合必须是有序的，而替换方法会直接修改原始集合。

七、集合的性能分析

集合的时间复杂度分析

集合的时间复杂度分析是评估集合操作的性能指标，它描述了随着集合大小的增加，操作所需的计算资源的增长情况。

1. 添加元素：

   • ArrayList、LinkedList：在末尾添加元素的时间复杂度为 O(1)，但在开头或中间插入元素的时间复杂度为 O(n)。
   • HashSet、LinkedHashSet：添加元素的时间复杂度为 O(1)，不考虑哈希碰撞的情况。
   • TreeSet：添加元素的时间复杂度为 O(log n)，会根据元素的排序进行平衡。
   • HashMap、LinkedHashMap：添加键值对的时间复杂度为 O(1)，不考虑哈希碰撞的情况。

2. 删除元素：

   • ArrayList、LinkedList：删除元素的时间复杂度为 O(n)，因为需要移动其他元素来填补被删除的位置。
   • HashSet、LinkedHashSet：删除元素的时间复杂度为 O(1)，不考虑哈希碰撞的情况。
   • TreeSet：删除元素的时间复杂度为 O(log n)，会根据元素的排序进行平衡。
   • HashMap、LinkedHashMap：删除键值对的时间复杂度为 O(1)，不考虑哈希碰撞的情况。

3. 查找元素：

   • ArrayList、LinkedList：通过索引值查找元素的时间复杂度为 O(1)，但通过值来查找元素的时间复杂度为 O(n)。
   • HashSet、LinkedHashSet：查找元素的时间复杂度为 O(1)，不考虑哈希碰撞的情况。
   • TreeSet：通过值来查找元素的时间复杂度为 O(log n)。
   • HashMap、LinkedHashMap：通过键查找值的时间复杂度为 O(1)，不考虑哈希碰撞的情况。

4. 排序：

   • ArrayList：使用 Collections.sort() 方法进行排序的时间复杂度为 O(n log n)。
   • LinkedList：使用 Collections.sort() 方法进行排序的时间复杂度为 O(n log n)。
   • TreeSet：根据元素的排序进行自动平衡，插入和访问元素的时间复杂度为 O(log n)。
   • TreeMap：根据键的排序进行自动平衡，插入和访问键值对的时间复杂度为 O(log n)。

需要注意的是，上述时间复杂度分析是基于最坏情况下的性能估计，并且忽略了一些特殊情况（如哈希碰撞）。

集合的空间复杂度分析

集合的空间复杂度分析是评估集合所占用的内存空间随着元素数量增加而增长的情况。

1. ArrayList：

   • 空间复杂度取决于元素的数量和底层数组的容量。
   • 当元素数量小于底层数组的容量时，空间复杂度为 O(n)，其中 n 是元素的数量。
   • 当元素数量超过底层数组的容量时，会创建一个新数组来扩容，新数组的长度通常是原数组长度的 1.5 倍，所以空间复杂度为 O(n)。

2. LinkedList：

   • 空间复杂度取决于元素的数量，每个节点需要额外存储指向前后节点的引用。
   • 每个节点需要消耗额外的空间，所以空间复杂度为 O(n)，其中 n 是元素的数量。

3. HashSet、LinkedHashSet：

   • 空间复杂度取决于元素的数量和哈希表的容量。
   • 哈希表的容量是根据元素数量自动调整的，通常为元素数量的两倍或更多。
   • 在没有哈希碰撞的情况下，空间复杂度为 O(n)，其中 n 是元素的数量。

4. TreeSet：

   • 空间复杂度取决于元素的数量。
   • TreeSet 内部使用红黑树来实现，每个节点需要额外存储指向父节点、左子节点和右子节点的引用。
   • 每个节点需要消耗额外的空间，所以空间复杂度为 O(n)，其中 n 是元素的数量。

5. HashMap、LinkedHashMap：

   • 空间复杂度取决于键值对的数量和哈希表的容量。
   • 哈希表的容量是根据键值对数量自动调整的，通常为键值对数量的两倍或更多。
   • 在没有哈希碰撞的情况下，空间复杂度为 O(n)，其中 n 是键值对的数量。

需要注意的是，上述空间复杂度分析是在不考虑集合本身固定开销的情况下进行的。例如，ArrayList 和 LinkedList 都有额外的指针或索引开销，而哈希表和红黑树等数据结构也需要一些空间来存储结构信息。

集合的性能优化方法

1. 选择合适的集合类型： 根据具体需求选择最合适的集合类型，考虑集合的特性、操作频率和数据量等因素。不同的集合类型在不同的操作上有不同的性能特点，例如，ArrayList 适用于频繁的随机访问，而LinkedList 适用于频繁的插入和删除操作。

2. 初始化集合容量： 对于 ArrayList、HashSet、HashMap 等需要扩容的集合，可以在创建集合时指定其初始容量。根据实际需求预估元素数量，并设置一个合理的初始容量，避免频繁的内部数组或哈希表扩容操作，从而提高性能。

3. 使用迭代器遍历集合： 在遍历集合时，尽量使用迭代器而不是通过索引进行遍历。迭代器提供了一种更高效的遍历方式，特别是在 LinkedList 等需要按顺序访问元素的集合中。

4. 注意集合的equals()和hashCode()方法： 当使用自定义对象作为集合元素时，确保正确实现 equals() 和 hashCode() 方法。这样可以在集合的查找、删除等操作中保持哈希表的性能优势，避免哈希碰撞和低效的线性搜索。

5. 使用集合API提供的方法： 集合框架提供了许多高效的操作方法，如addAll()、removeAll()、retainAll() 等。根据具体需求，尽量使用这些方法而不是手动进行迭代操作，可以提高代码的简洁性和性能。

6. 考虑并发安全性： 如果在多线程环境下使用集合，需要考虑并发安全性。可以选择使用线程安全的集合类，如 ConcurrentHashMap、CopyOnWriteArrayList 等，或者通过适当的同步机制来保证线程安全。

7. 避免频繁的集合操作： 频繁的集合操作可能会导致性能下降，尤其是在大规模数据的情况下。如果可能，尽量批量操作或一次性操作集合，减少单个操作的次数，从而提高性能。

8. 避免不必要的装箱和拆箱： 在使用泛型集合时，避免频繁的自动装箱和拆箱操作。可以使用基本数据类型的特殊集合类，如 IntList（针对整型）、LongList（针对长整型）等，或者使用第三方库如 Google Guava 中的原生集合类型。

总的来说，集合的性能优化需要结合具体场景和需求进行。通过选择合适的集合类型、优化操作方法和考虑并发安全等因素，可以提高集合操作的效率和响应速度。如果遇到特定的性能问题，还可以借助性能分析工具进行定位和优化。