【Java】集合详解及常见方法
前言
Java 提供了一套强大的集合框架（Java Collections Framework），包含了不同类型的数据结构，能够有效地存储、访问和操作数据。集合框架提供了多种常用接口、类和方法，帮助开发者管理和操作数据。Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。
Collection集合框架图
1.List
List 接口的实现类，如 ArrayList 和 LinkedList，提供了按索引访问元素的能力，并允许元素重复。
1.1 ArrayList
ArrayList 是一个基于动态数组实现的 List，它允许按索引访问元素，并且支持快速随机访问。每次元素添加时，ArrayList 会自动调整数组的大小，以便容纳更多的元素。
1.1.1 特点
随机访问快：由于 ArrayList 是基于数组实现的，它能够快速地通过索引访问元素。随机访问的时间复杂度为 O(1)。动态数组扩展：当数组满了时，ArrayList 会自动扩展数组的容量。扩展通常是原容量的 1.5 倍。插入和删除效率低：在 ArrayList 中，元素的插入和删除操作比较慢，尤其是在中间位置插入或删除时。因为需要移动数组中的其他元素，这些操作的时间复杂度是 O(n)，其中 n 是集合的大小。内存使用：由于 ArrayList 使用数组存储元素，当数组容量增长时，可能会浪费内存（即内存会预留一些空间以应对未来的扩容）。
1.1.2 适用场景
适合需要频繁随机访问元素的场景（例如查找、遍历）。适合插入和删除操作较少的场景，或者仅在末尾进行添加。
1.1.3 代码示例
import java.util.*;
public class ArrayListExample {
public static void main(String[] args) {
// 创建一个 ArrayList
List
// 添加元素
list.add("Apple");
list.add("Banana");
list.add("Cherry");
// 获取元素
System.out.println("Element at index 1: " + list.get(1)); // Banana
// 删除元素
list.remove("Banana");
// 遍历
for (String fruit : list) {
System.out.println(fruit);
}
}
}
1.1.4 ArrayList 常用方法
add(E e)：将元素添加到末尾。add(int index, E element)：在指定位置插入元素。get(int index)：获取指定位置的元素。remove(Object o)：删除指定元素。remove(int index)：删除指定位置的元素。size()：获取集合的大小。contains(Object o)：判断集合中是否包含指定元素。
1.1.5 ArrayList 的扩容机制
ArrayList 是基于动态数组实现的。当元素数量超过当前数组的容量时，ArrayList 会进行扩容。
扩容原理：
初始容量：ArrayList 在初始化时，如果没有显式指定容量，则默认为 10。如果指定了容量，则 ArrayList 会按照指定的容量初始化数组。
扩容方式：每当 ArrayList 满了，它会将当前数组的容量增加为原容量的 1.5 倍。例如，如果当前数组容量为 10，那么扩容后的新容量将是 15（10 * 1.5）。这种方式可以减少频繁的扩容次数，从而提高性能。
实现机制：当 ArrayList 扩容时，实际上会创建一个新的更大的数组，将原数组中的元素复制到新的数组中，然后丢弃旧的数组。
扩容时的时间复杂度：
扩容操作：扩容时的时间复杂度为 O(n)，因为需要将数组中的所有元素复制到新的数组中，其中 n 是当前数组的容量。单次插入操作：在没有发生扩容时，插入操作是 O(1)，即常数时间。只有当扩容时，插入操作的时间复杂度才会增加。
1.2 LinkedList
1.2.1 特点
插入和删除效率高：LinkedList 在中间插入和删除元素时非常高效。插入和删除元素的时间复杂度为 O(1)，不需要移动其他元素，只需修改指针即可。访问元素慢：由于 LinkedList 是基于链表结构的，它不支持通过索引进行随机访问。访问元素时需要从头（或尾）开始遍历链表，直到找到目标元素。访问元素的时间复杂度是 O(n)，其中 n 是元素数量。内存使用：每个元素不仅要存储数据本身，还要存储两个指针（指向前后节点的指针），因此相较于 ArrayList，LinkedList 占用更多内存。支持双向操作：LinkedList 是双向链表，支持从头部和尾部进行插入和删除操作，效率相同。
1.2.2 适用场景
适合需要频繁插入和删除元素的场景，尤其是在中间位置进行操作时。不适合频繁访问元素的场景，因为访问时间较长。
1.2.3 代码示例
import java.util.*;
public class LinkedListExample {
public static void main(String[] args) {
// 创建一个 LinkedList
List
// 添加元素
list.add("Apple");
list.add("Banana");
list.add("Cherry");
// 获取元素
System.out.println("Element at index 1: " + list.get(1)); // Banana
// 删除元素
list.remove("Banana");
// 遍历
for (String fruit : list) {
System.out.println(fruit);
}
}
}
1.2.4 LinkedList 常用方法
add(E e)：将元素添加到末尾。add(int index, E element)：在指定位置插入元素。get(int index)：获取指定位置的元素。remove(Object o)：删除指定元素。remove(int index)：删除指定位置的元素。size()：获取集合的大小。contains(Object o)：判断集合中是否包含指定元素。addFirst(E e)：将元素添加到链表的开头。addLast(E e)：将元素添加到链表的末尾。removeFirst()：移除并返回链表的第一个元素。removeLast()：移除并返回链表的最后一个元素。
1.2.5 LinkedList 扩容机制
LinkedList 的底层实现是基于双向链表的，因此它与 ArrayList 不同，不存在传统意义上的扩容问题。链表结构本身是由节点（Node）组成的，每个节点包含数据和指向前后节点的引用。
扩容原理：
无固定容量：LinkedList 没有像 ArrayList 那样的固定容量。它的大小由链表中节点的数量决定，元素的添加和删除不需要预先定义容量。每次添加元素时，LinkedList 会创建一个新的节点，并将该节点与前后节点连接起来。
无需扩容：由于链表的节点是动态分配内存的，因此 LinkedList 不需要像 ArrayList 那样进行扩容操作。它的内存分配是按需进行的，不会一次性为未来的容量需求分配过多内存。
插入/删除操作：插入和删除操作是通过修改指针来完成的，不需要移动其他元素。因此，LinkedList 在插入和删除时相对 ArrayList 更为高效，尤其是在链表的开头和中间部分。
扩容时的时间复杂度：
添加元素：每次插入元素时，时间复杂度是 O(1)（在尾部添加），或者 O(n)（在中间插入时，仍然需要遍历链表）。链表没有固定容量，只有在遍历链表时会遇到时间复杂度为 O(n) 的情况。内存管理：由于节点是动态分配的，每个节点需要额外的内存来存储指向前后节点的引用，所以 LinkedList 相比 ArrayList 的内存占用会更高。
ArrayList 与 LinkedList 对比
特性ArrayListLinkedList底层数据结构动态数组双向链表随机访问性能O(1)O(n)插入/删除性能在末尾 O(1)，在中间 O(n)在任意位置 O(1)内存消耗仅存储元素存储元素及前后节点的指针适用场景需要频繁随机访问且插入删除较少的场景需要频繁插入和删除元素的场景扩容机制初始容量10，扩容为原容量的 1.5 倍无需扩容2.Set
Set 是一个接口，属于 java.util 包的一部分，表示一个集合，它不会包含重复的元素。Set 接口继承自 Collection 接口，因此具有 Collection 接口的所有基本操作，如添加、删除、查询等。
2.1 特点
不允许重复元素：Set 中的元素是唯一的，如果试图添加重复的元素，集合会忽略该元素。没有索引：Set 不像 List 那样有索引，无法通过索引访问集合中的元素。集合中的元素没有固定顺序，具体顺序取决于实现类。适用于需要确保唯一性的场景：如存储不重复的元素，快速去重等。
2.2 适用场景
Set 适用于那些不关心元素顺序且要求元素唯一的场景。常见的应用包括：
去重：当需要一个不包含重复元素的集合时，使用 Set 比使用 List 更合适。快速查找：由于哈希表的高效性，Set 可以在常数时间内进行元素查找。数学运算：可以使用 Set 来实现集合的并、交、差等数学运算。
2.3 常见的 Set 实现类
2.3.1 HashSet
基于哈希表（HashMap）实现，是最常用的 Set 实现类。不保证元素的顺序，元素的顺序是随机的，取决于哈希算法和元素的哈希值。允许 null 元素（最多一个 null）。查询、插入和删除 操作的时间复杂度为 O(1)，即常数时间复杂度。
import java.util.HashSet;
public class HashSetExample {
public static void main(String[] args) {
HashSet
set.add("apple");
set.add("banana");
set.add("apple"); // 重复元素，会被忽略
set.add(null); // 允许 null 元素
System.out.println(set); // 输出： [apple, banana, null]
}
}
2.3.2 LinkedHashSet
继承自 HashSet，同时维护了元素的插入顺序。即元素是按插入顺序存储的。查询、插入、删除操作的时间复杂度依然是 O(1)，但由于额外的链表维护开销，LinkedHashSet 会稍微比 HashSet 稍慢一些。允许 null 元素。
import java.util.LinkedHashSet;
public class LinkedHashSetExample {
public static void main(String[] args) {
LinkedHashSet
set.add("apple");
set.add("banana");
set.add("apple"); // 重复元素，会被忽略
set.add(null); // 允许 null 元素
System.out.println(set); // 输出： [apple, banana, null]
}
}
2.3.3 TreeSet
基于红黑树实现，元素是有序的，默认按照元素的自然顺序排序（Comparable），或者使用提供的 Comparator 进行排序。不允许 null 元素，因为 null 无法与其他元素进行比较。查询、插入、删除操作的时间复杂度为 O(log n)，相比于 HashSet 和 LinkedHashSet，TreeSet 在性能上稍逊。
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
TreeSet
set.add("apple");
set.add("banana");
set.add("apple"); // 重复元素，会被忽略
System.out.println(set); // 输出： [apple, banana]
}
}
2.4 Set 的常用方法
add(E e)：将元素 e 添加到集合中。如果集合中已存在该元素，则返回 false，否则返回 true。remove(Object o)：从集合中移除指定的元素 o，如果集合包含该元素，返回 true，否则返回 false。clear()：移除集合中的所有元素。contains(Object o)：检查集合是否包含指定的元素 o。isEmpty()：检查集合是否为空。size()：返回集合中元素的数量。iterator()：返回一个 Iterator 对象，可以用于遍历集合。addAll(Collection c)：将一个集合中的所有元素添加到当前集合中。removeAll(Collection c)：从当前集合中删除包含在指定集合中的所有元素。retainAll(Collection c)：保留当前集合和指定集合中相同的元素。containsAll(Collection c)：检查当前集合是否包含指定集合中的所有元素。
下面是 HashSet、LinkedHashSet 和 TreeSet 这三者的比较表格：
特性HashSetLinkedHashSetTreeSet实现基于哈希表（HashMap）继承自 HashSet，基于哈希表并维护元素插入顺序基于红黑树实现，有序集合元素顺序无序按插入顺序有序按自然顺序或自定义 Comparator 排序允许重复元素不允许重复元素不允许重复元素不允许重复元素是否允许 null 元素允许，最多只能有一个 null 元素允许，最多只能有一个 null 元素不允许 null 元素性能（插入、删除、查询）O(1) 平均时间复杂度，最坏情况下 O(n)O(1) 平均时间复杂度，最坏情况下 O(n)O(log n) 时间复杂度插入顺序无插入顺序保持插入顺序无插入顺序，按照排序顺序用途适用于需要去重且不关心顺序的场景适用于需要去重且关心插入顺序的场景适用于需要有序且去重的场景（自然顺序或自定义排序）线程安全性不是线程安全的不是线程安全的不是线程安全的内部结构使用哈希表实现，元素通过哈希值存储使用哈希表实现，保持插入顺序的双向链表使用红黑树实现，元素按顺序存储典型使用场景去重、不关心顺序的集合操作去重、需要保持插入顺序的集合操作去重、需要排序或比较的集合操作
3.Map
Map 是一个用于存储键值对（key-value）的集合接口。特点是每个元素都由一对键和值组成，且每个键只能映射到一个值。Map 不属于 Collection 接口层次结构，而是单独存在的，因为它并不代表一个单一的集合，而是一个映射关系。常见的实现类有 HashMap、LinkedHashMap、TreeMap 等。
3.1 HashMap
3.1.1 特点
HashMap 使用哈希表实现，存储键值对时根据键的哈希值确定存储位置。
键和值都可以是 null，但最多只能有一个 null 键。
迭代顺序是无序的，即不保证按照插入顺序遍历元素。
线程安全性：HashMap 不是线程安全的。在多线程环境下，如果多个线程同时对同一个 HashMap 进行读写操作，可能会导致数据不一致或者程序抛出异常。
HashMap 的性能较高，因为它不需要考虑线程同步，因此它的读写操作非常高效。大多数情况下，它的插入、删除和查找操作的时间复杂度是 O(1)，但在极端情况下（比如哈希冲突较多）可能退化为 O(n)。
3.1.2 使用场景
适用于单线程环境，或者外部同步保证线程安全的场景。
3.1.3 代码示例
Map
map.put("one", 1);
map.put("two", 2);
System.out.println(map.get("one")); // 输出: 1
3.1.4 HashMap常用方法
put(K key, V value)：将指定的键值对插入到 HashMap 中，如果键已存在，则替换旧的值。get(Object key)：根据指定的键获取对应的值。如果键不存在，返回 null。containsKey(Object key)：检查 HashMap 中是否包含指定的键。containsValue(Object value)：检查 HashMap 中是否包含指定的值。remove(Object key)：删除指定键的键值对。size()：获取 HashMap 中键值对的数量。clear()：清空 HashMap 中的所有元素。keySet()：获取 HashMap 中所有键的集合。values()：获取 HashMap 中所有值的集合。entrySet()：获取 HashMap 中所有键值对的集合，返回 Set
3.2 ConcurrentHashMap
ConcurrentHashMap 是线程安全的 HashMap 实现，适用于多线程环境。它使用分段锁（或更细粒度的锁机制）来保证并发访问时的线程安全，避免了全局锁的性能瓶颈。
3.2.1 特点
不允许 null 键和 null 值，任何尝试插入 null 键或 null 值都会抛出 NullPointerException。提供了并发的 putIfAbsent、replace 等方法，能更好地处理并发场景。支持高效的并发操作，避免了使用全局锁导致的性能瓶颈。迭代顺序是不保证的，通常也不保证与插入顺序一致。ConcurrentHashMap 是线程安全的，它在多线程环境下特别有效。与 Hashtable 不同，它使用了更细粒度的锁机制，确保多个线程可以并发地操作集合中的不同部分，而不需要对整个数据结构加锁相比于 Hashtable，ConcurrentHashMap 在多线程环境下具有更好的性能，因为它支持更细粒度的锁定，而 Hashtable 需要对整个数据结构加锁。
3.2.2 使用场景
适用于多线程并发操作的场景，特别是在高并发的应用中，如多线程处理任务、缓存等。
3.2.3 代码示例
Map
map.put("one", 1);
map.put("two", 2);
System.out.println(map.get("one")); // 输出: 1
3.2.4 ConcurrentHashMap常用方法
put(K key, V value)：插入键值对，如果键已存在，则替换旧值。线程安全。get(Object key)：根据键获取值。线程安全。putIfAbsent(K key, V value)：如果指定的键不存在，才插入该键值对。线程安全。remove(Object key)：删除指定键的键值对。线程安全。replace(K key, V oldValue, V newValue)：如果键对应的值为 oldValue，则替换为 newValue。线程安全。replace(K key, V value)：替换指定键的值。线程安全。size()：获取 ConcurrentHashMap 中键值对的数量。线程安全。forEach(BiConsumer action)：遍历每个键值对并执行指定的操作。线程安全。clear()：清空 ConcurrentHashMap 中的所有元素。线程安全。computeIfAbsent(K key, Function mappingFunction)：如果指定的键不存在，则通过 mappingFunction 计算值并插入。
3.3 Hashtable
Hashtable 是早期 Java 中的线程安全的哈希表实现，使用同步锁来保证线程安全。不过，由于性能较差（因为每个操作都要加锁），现代 Java 中更推荐使用 ConcurrentHashMap。
3.3.1 特点
采用哈希表实现，存储键值对时使用键的哈希值来定位。键和值都不能为 null，任何尝试插入 null 键或 null 值都会抛出 NullPointerException。Hashtable 是较老的类，早期 Java 版本中就存在，但后来随着 ConcurrentHashMap 的出现，它的使用逐渐减少。迭代顺序也是无序的，且同样不保证按插入顺序遍历元素。Hashtable 是线程安全的，所有的操作都由单一的全局锁控制，这意味着每次只能有一个线程访问 Hashtable 中的元素，这种做法会大大降低性能，尤其在多线程环境中。因为 Hashtable 的所有方法都进行了同步（synchronized），每次操作都会获得全局锁，这在多线程高并发时会导致性能瓶颈。
3.3.2 使用场景
适用于单线程环境或者需要保证线程安全且操作量较小的场景，但一般来说，Hashtable 已经较少使用，更多情况下推荐使用 ConcurrentHashMap。
3.3.3 代码示例
Map
map.put("one", 1);
map.put("two", 2);
System.out.println(map.get("one")); // 输出: 1
3.3.4 Hashtable常用方法
put(K key, V value)：插入键值对，如果键已存在，则替换旧值。线程安全。get(Object key)：根据键获取值。线程安全。containsKey(Object key)：检查 Hashtable 中是否包含指定的键。线程安全。remove(Object key)：删除指定键的键值对。线程安全。size()：获取 Hashtable 中键值对的数量。线程安全。clear()：清空 Hashtable 中的所有元素。线程安全。keySet()：获取 Hashtable 中所有键的集合。线程安全。elements()：获取 Hashtable 中所有值的枚举。线程安全。forEach(BiConsumer action)：遍历每个键值对并执行指定的操作（Java 8 及之后版本支持）。
三者总结对比
特性HashMapConcurrentHashMapHashtable线程安全否是（分段锁机制）是（全表锁机制）null 键和 null 值支持支持不支持 null 键和 null 值不支持 null 键和 null 值性能高（单线程环境）中等（线程安全但开销较大）较低（全表锁机制，性能瓶颈）使用场景单线程或外部同步控制的多线程多线程环境多线程环境，但较少推荐使用遍历方式）keySet(), values(), entrySet()forEach(), keySet(), values()keys(), elements()3.4 Map扩容机制
3.4.1 扩容触发条件
HashMap 会在以下两种情况下进行扩容：
负载因子（load factor）：HashMap 的初始容量是16，默认负载因子是 0.75，即当 HashMap 中的元素数量达到当前数组容量的 75% 时，就会触发扩容。元素数量：如果 HashMap 中的元素数量超过了当前容量与负载因子的乘积，扩容会自动触发。
例如，HashMap 的初始容量是 16，负载因子是 0.75，那么当存储的元素数量达到 16 * 0.75 = 12 时，就会触发扩容操作。
3.4.2 扩容过程
当触发扩容时，HashMap 会进行以下步骤：
数组大小翻倍：HashMap 的容量会扩大到原来容量的两倍。这是为了降低哈希冲突的概率，使得每个桶的元素数量保持相对较小。重新哈希：所有原来哈希表中的元素（键值对）会被重新计算哈希值，并根据新的容量重新分配到新的桶中。由于数组大小发生了变化，元素的位置可能会发生变化。
3.4.3 扩容后影响
性能：扩容过程中，HashMap 必须遍历原数组并将所有的元素重新哈希到新的数组中，这个过程是相对昂贵的，因此应该尽量避免频繁扩容。如果频繁扩容，可能会导致性能下降。扩容的次数：扩容是指数级的，每次都会将容量翻倍，因此在合适的时机进行扩容能够保持哈希表的性能。