在 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) {// 创建一个ArrayListList<String> list = new ArrayList<>();// 添加元素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) {// 创建一个HashSetSet<String> set = new HashSet<>();// 添加元素set.add("Java");set.add("Python");set.add("JavaScript");set.add("Java"); // 重复元素不会添加// 打印集合System.out.println("Set: " + set);// 使用 LinkedHashSet 来保证插入顺序Set<String> linkedSet = new LinkedHashSet<>();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) {// 创建一个HashMapMap<String, Integer> map = new HashMap<>();// 添加键值对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<String, Integer> entry : map.entrySet()) {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<String> queue = new LinkedList<>();// 添加元素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<String> deque = new ArrayDeque<>();// 从两端添加元素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<String> stack = new 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());}
}
