在 Java 中，集合类（Collection classes）是指用来存储、操作数据对象的一系列类。它们位于 java.util 包中，主要分为 List、Set 和 Map 三个类型，每个类型又包含不同的实现类。
1. List 接口及其实现类
List 是一个有序的集合，它允许元素重复，并且元素的插入顺序是被保留的。常用的 List 实现类有：
ArrayList（基于动态数组实现）
底层结构：ArrayList 使用一个 动态数组 来存储元素。访问：通过数组的索引进行快速访问，时间复杂度为 O(1)。插入：如果插入点在数组的末尾，则插入是常数时间 O(1)，但如果在中间插入，则需要移动后续元素，时间复杂度为 O(n)。扩展：当数组容量不足时，ArrayList 会将其容量扩展为原来的 1.5 倍。扩展的过程是 O(n)。删除：删除元素时，需要将其后的所有元素左移，时间复杂度为 O(n)。LinkedList（基于双向链表实现）
底层结构：LinkedList 使用 双向链表 来存储元素，每个节点包含数据和指向前后节点的指针。访问：访问元素需要遍历链表，时间复杂度为 O(n)（从头或尾开始遍历）。插入/删除：插入和删除操作在链表的两端（头或尾）是 O(1)，在中间插入或删除时需要遍历链表，时间复杂度为 O(n)。Vector（基于动态数组实现）
底层结构：Vector 和 ArrayList 类似，也使用动态数组来存储数据。访问/插入：访问和插入的时间复杂度与 ArrayList 相同。线程安全：Vector 是线程安全的，通常通过 同步 来保证线程安全，这会导致一些性能开销。Stack（基于 Vector 实现）
底层结构：Stack 是 Vector 的一个子类，采用 动态数组 存储元素。操作：push() 和 pop() 操作是基于栈的后进先出（LIFO）特性，实际上是通过数组的 add 和 remove 操作来实现的。线程安全：与 Vector 类似，Stack 也是线程安全的。import java.util.*;
public class ListExample {
public static void main(String[] args) {
// 创建一个ArrayList
List
// 添加元素
list.add("Java");
list.add("Python");
list.add("JavaScript");
// 访问元素
System.out.println("List: " + list);
// 访问指定位置的元素
System.out.println("Element at index 1: " + list.get(1));
// 删除元素
list.remove(1);
System.out.println("After removal: " + list);
}
}
2. Set 接口及其实现类
Set 是一个不允许元素重复的集合，它不保证元素的插入顺序。常用的 Set 实现类有：
HashSet（基于哈希表实现）
底层结构：HashSet 使用 哈希表（HashMap） 来存储元素。内部使用一个 HashMap 来存储集合元素，键是元素，值是一个常量对象（如 Boolean.TRUE）。访问：通过元素的哈希值确定其存储位置，查找元素的时间复杂度为 O(1)。插入/删除：插入和删除元素时，通过计算哈希值定位元素的位置，平均时间复杂度为 O(1)，但在哈希冲突严重时，性能会下降到 O(n)。无序性：HashSet 不保证元素的插入顺序。LinkedHashSet（基于哈希表和链表实现）
底层结构：LinkedHashSet 使用 哈希表 和 双向链表 结合的方式实现。哈希表提供快速的查找和插入，链表用于维护元素的插入顺序。访问：查找元素的时间复杂度为 O(1)（与 HashSet 类似），但额外维护了一个链表，用于记录元素插入的顺序。插入/删除：插入和删除元素的时间复杂度为 O(1)，但需要额外维护链表的顺序。TreeSet（基于红黑树实现）
底层结构：TreeSet 使用 红黑树 来存储元素，保证元素的排序。访问：查找、插入和删除操作的时间复杂度为 O(log n)，因为红黑树是自平衡的二叉搜索树。排序：TreeSet 会按照元素的自然顺序（如果元素实现了 Comparable 接口）或提供的 Comparator 进行排序。import java.util.*;
public class SetExample {
public static void main(String[] args) {
// 创建一个HashSet
Set
// 添加元素
set.add("Java");
set.add("Python");
set.add("JavaScript");
set.add("Java"); // 重复元素不会添加
// 打印集合
System.out.println("Set: " + set);
// 使用 LinkedHashSet 来保证插入顺序
Set
linkedSet.add("Java");
linkedSet.add("Python");
linkedSet.add("JavaScript");
System.out.println("LinkedHashSet: " + linkedSet);
}
}
3. Map 接口及其实现类
Map 是一个键值对集合，它允许通过键（key）来映射到值（value）。常用的 Map 实现类有：
HashMap（基于哈希表实现）
底层结构：HashMap 使用 哈希表 来存储键值对。哈希表是一个包含键和值的数组，键通过哈希函数映射到数组的某个位置。查找：通过键的哈希值来快速定位值，平均时间复杂度为 O(1)。冲突处理：当多个键的哈希值相同（发生哈希冲突）时，HashMap 会将冲突的元素链式存储在同一个位置，时间复杂度退化为 O(n)。扩展：当哈希表的负载因子超过某个阈值时，HashMap 会进行扩展，通常扩展为原来的两倍，扩展过程是 O(n)。LinkedHashMap（基于哈希表和链表实现）
底层结构：LinkedHashMap 使用 哈希表 和 双向链表 结合的方式实现。哈希表用于存储键值对，链表用于维护元素的插入顺序。查找：查找操作的时间复杂度为 O(1)，与 HashMap 类似。排序：链表的存在使得 LinkedHashMap 能保持元素插入的顺序或者访问顺序（取决于构造时的参数）。TreeMap（基于红黑树实现）
底层结构：TreeMap 使用 红黑树 来存储键值对，保证键的排序。查找：查找、插入和删除操作的时间复杂度为 O(log n)，因为红黑树是自平衡的二叉搜索树。排序：TreeMap 会按照键的自然顺序（如果键实现了 Comparable 接口）或提供的 Comparator 进行排序。Hashtable（基于哈希表实现）
底层结构：Hashtable 与 HashMap 类似，底层也是一个 哈希表。线程安全：Hashtable 是线程安全的，使用同步（synchronized）来保证线程安全，因此性能较低。由于这一点，Hashtable 在现代 Java 编程中已较少使用，通常建议使用 ConcurrentHashMap。import java.util.*;
public class MapExample {
public static void main(String[] args) {
// 创建一个HashMap
Map
// 添加键值对
map.put("Java", 8);
map.put("Python", 6);
map.put("JavaScript", 7);
// 访问键值对
System.out.println("Map: " + map);
// 根据键访问值
System.out.println("Java's value: " + map.get("Java"));
// 遍历键值对
for (Map.Entry
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
4. Queue 接口及其实现类
Queue 是一个先进先出（FIFO）的集合接口。常用的 Queue 实现类有：
LinkedList（基于双向链表实现）
底层结构：LinkedList 使用 双向链表 来存储元素。它实现了 Queue 接口，可以用作队列。操作：在队列的两端进行插入和删除操作的时间复杂度为 O(1)，这是链表的优势。迭代：访问队列中的元素需要遍历链表，时间复杂度为 O(n)。PriorityQueue（基于堆实现）
底层结构：PriorityQueue 使用 堆（通常是最小堆）来存储元素。操作：插入和删除的时间复杂度为 O(log n)，因为堆在插入和删除操作时需要重新调整堆的结构。排序：PriorityQueue 会根据元素的自然顺序或提供的 Comparator 来确定优先级。ArrayDeque（基于动态数组实现）
底层结构：ArrayDeque 使用 动态数组 来实现双端队列。它提供比 LinkedList 更高效的性能，尤其是在需要频繁访问队列两端时。操作：插入和删除操作在队列的两端都是 O(1)，但是如果数组需要扩展时，扩展过程的时间复杂度为 O(n)。import java.util.*;
public class QueueExample {
public static void main(String[] args) {
Queue
// 添加元素
queue.offer("Java");
queue.offer("Python");
queue.offer("JavaScript");
// 移除元素
System.out.println("Poll: " + queue.poll()); // 移除并返回队列头部元素
System.out.println("Queue after poll: " + queue);
// 查看队列头部元素
System.out.println("Peek: " + queue.peek()); // 查看队列头部元素但不移除
}
}
5. Deque 接口及其实现类
Deque 是双端队列（Double Ended Queue），允许在队列的两端插入和删除元素。常用的 Deque 实现类有：
ArrayDeque（基于动态数组实现）
底层结构：ArrayDeque 使用 动态数组 来存储元素。操作：插入和删除操作的时间复杂度是 O(1)，但如果数组需要扩展，则会有 O(n) 的开销。优点：相较于 LinkedList，ArrayDeque 的性能更高，因为它不需要维护链表的节点指针。LinkedList（基于双向链表实现）
底层结构：LinkedList 使用 双向链表 来存储元素。操作：从两端插入和删除元素的时间复杂度为 O(1)，但在中间插入或删除时，时间复杂度为 O(n)。import java.util.*;
public class DequeExample {
public static void main(String[] args) {
Deque
// 从两端添加元素
deque.addFirst("Java");
deque.addLast("Python");
// 从两端移除元素
System.out.println("Removed from front: " + deque.removeFirst());
System.out.println("Removed from back: " + deque.removeLast());
}
}
6. Stack 类
Stack 是 Vector 的子类，表示后进先出（LIFO）数据结构，常用于实现栈操作。
import java.util.*;
public class StackExample {
public static void main(String[] args) {
Stack
// 压栈
stack.push("Java");
stack.push("Python");
stack.push("JavaScript");
// 弹栈
System.out.println("Popped: " + stack.pop());
System.out.println("Stack after pop: " + stack);
// 查看栈顶元素
System.out.println("Peek: " + stack.peek());
}
}
图源：代码随想录知识星球