Java 集合框架

Java 集合框架

在 Java 2 之前，像 Vector、Stack 和 Hashtable 这样的类被用来管理对象组。然而，它们缺乏一致的设计，并且不容易互操作。

Java 集合框架 (Java Collections Framework, JCF)，在 Java 1.2 中引入，为表示和操作集合（对象组）提供了一个统一的架构。其主要目标包括：

• 高性能： 为常见数据结构提供高效的实现。
• 互操作性： 允许不同集合类型无缝地协同工作。
• 可扩展性： 易于扩展或改编现有集合或实现新集合。
• 减少编程工作量： 提供标准数据结构和算法，节省开发人员时间。

该框架建立在以下基础上：

• 接口 (Interfaces)： 定义了不同类型集合的抽象数据类型 (ADT)，如 List、Set、Map。它们指定了契约（方法），但不详细说明实现。代码通常应该面向接口编写（例如，List<String> list = new ArrayList<>();）。
• 实现类 (Implementations / Classes)： 提供了实现集合接口的具体数据结构的具体类（例如，ArrayList、LinkedList、HashSet、HashMap）。
• 算法 (Algorithms)： 执行对集合进行多态操作的工具方法（通常是静态方法，主要在 Collections 类中），如排序、搜索、洗牌等。

映射 (Maps)（Map 接口及其实现类如 HashMap） 也是该框架的一部分。虽然它们不严格属于 Collection（它们存储键值对，而不是单个元素），但它们是紧密集成的。

核心 Collection 接口

主要接口形成了一个层次结构：

接口 (Interface)	描述 (Description)
Collection<E>	大多数集合的根接口（不包括 Map）。表示一组对象（元素）。定义了基本方法，如 add()、remove()、size()、iterator()、contains()。
List<E>	继承自 Collection。表示一个有序的元素序列。允许重复元素并支持按位置访问（通过索引）。常见实现类：ArrayList、LinkedList。
Set<E>	继承自 Collection。表示一个不包含重复元素的集合（集）。通常不保证元素的顺序（LinkedHashSet 和 SortedSet 除外）。常见实现类：HashSet、LinkedHashSet、TreeSet。
SortedSet<E>	继承自 Set。表示一个 Set，其元素按排序顺序维护（自然顺序或通过 Comparator）。由 TreeSet 实现。
NavigableSet<E>	继承自 SortedSet。增加了导航方法（例如，查找最近匹配项）和按降序迭代的能力。由 TreeSet 实现。
Queue<E>	继承自 Collection。表示一个通常用于在处理之前保存元素的集合（例如，FIFO - 先进先出）。实现类：LinkedList、PriorityQueue、ArrayDeque。
Deque<E>	继承自 Queue。表示一个双端队列，支持在两端插入和删除元素。实现类：ArrayDeque、LinkedList。

核心 Map 接口

接口 (Interface)	描述 (Description)
Map<K, V>	表示从唯一键 (K) 到值 (V) 的映射。每个键最多映射到一个值。不属于 Collection 层次结构。常见实现类：HashMap、LinkedHashMap、TreeMap。
SortedMap<K, V>	继承自 Map。表示一个 Map，其条目按键的升序维护（自然顺序或通过 Comparator）。由 TreeMap 实现。
NavigableMap<K, V>	继承自 SortedMap。增加了键的导航方法（例如，查找最近匹配项）。由 TreeMap 实现。
Map.Entry<K, V>	Map 的一个内部接口。表示 Map 中的单个键值对。

常见实现类

Java 提供了几种标准实现类：

类 (Class)	实现的接口 (Interface(s) Implemented)	描述与用例 (Description & Use Case)
ArrayList<E>	List<E>	可调整大小的数组实现。快速随机访问（通过索引），中间插入/删除相对较慢。优秀的通用列表。
LinkedList<E>	List<E>，Deque<E>	双向链表实现。在两端和中间（如果迭代器已定位）快速插入/删除，随机访问较慢。适合频繁插入/删除，可用作队列/栈。
HashSet<E>	Set<E>	使用哈希表。提供快速的添加、删除、包含操作（平均 O(1)）。不保证顺序。当需要唯一性且顺序不重要时使用。
LinkedHashSet<E>	Set<E>	哈希表 + 链表实现。类似 HashSet，但维护元素的插入顺序。由于需要维护链表，比 HashSet 稍慢。
TreeSet<E>	NavigableSet<E>，SortedSet<E>	使用树结构（红黑树）。按排序顺序存储元素（自然顺序或通过 Comparator）。添加/删除/包含操作比 HashSet 慢（O(log n)），但提供有序遍历。
HashMap<K, V>	Map<K, V>	基于哈希表的实现。快速的 put、get、containsKey 操作（平均 O(1)）。不保证顺序。标准的通用 Map 实现。
LinkedHashMap<K, V>	Map<K, V>	哈希表 + 链表实现。类似 HashMap，但维护条目的插入顺序或访问顺序。适用于缓存（LRU）。
TreeMap<K, V>	NavigableMap<K, V>，SortedMap<K, V>	使用树结构（红黑树）。按键排序存储条目（自然顺序或通过 Comparator）。put/get/containsKey 操作比 HashMap 慢（O(log n)），但提供按键的有序迭代。
ArrayDeque<E>	Deque<E>	Deque 的可调整大小数组实现。在两端高效添加/删除。是栈和队列的良好选择。

遗留类 (新代码中通常应避免使用):

• Vector<E>: ArrayList 的同步版本。由于同步开销而较慢。如果需要同步，优先使用 ArrayList 并进行外部同步，或使用并发集合。
• Stack<E>: 继承自 Vector。后进先出 (LIFO) 栈实现。对于栈操作，优先使用 ArrayDeque。
• Hashtable<K, V>: HashMap 的同步版本。不允许 null 键或值。优先使用 HashMap 或 ConcurrentHashMap。
• Dictionary<K, V>: Map 的抽象前身。已过时。
• Properties: Hashtable 的子类。仍然常用于配置文件（键值对是字符串）。

遍历集合

常见的遍历方式：

• 增强型 for 循环 (Foreach)： 最简单且通常首选的方式。适用于实现 Iterable 的任何类（包括所有 Collection）。
• 迭代器 (Iterator)： 提供 hasNext()、next() 和 remove() 方法。当您需要在迭代期间删除元素时需要使用。
• Streams API (Java 8+)： 提供了一种函数式方法，使用 forEach()、map()、filter()、collect() 等方法。对于处理元素序列非常强大。

使用迭代器的示例：

List<String> names = new ArrayList<>(Arrays.asList("Alice", "Bob", "Charlie"));
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    String name = iterator.next();
    System.out.println(name);
    if (name.equals("Bob")) {
        iterator.remove(); // 在迭代期间安全地删除元素
    }
}
System.out.println("After removal: " + names); // 输出: [Alice, Charlie]

Collections 工具类

java.util.Collections 类提供了用于操作或返回集合的静态工具方法。例如：

• sort(List<T> list) / sort(List<T> list, Comparator<? super T> c): 对列表进行排序。
• binarySearch(List<? extends Comparable<? super T>> list, T key): 搜索已排序列表。
• reverse(List<?> list): 反转列表中元素的顺序。
• shuffle(List<?> list): 随机置换列表中的元素。
• max(Collection<? extends T> coll) / min(...): 根据自然顺序查找最大/最小元素。
• frequency(Collection<?> c, Object o): 计算元素出现的次数。
• synchronizedList(List<T> list) / synchronizedSet(...) / synchronizedMap(...): 返回线程安全的包装器（但通常不如并发集合高效）。
• unmodifiableList(List<? extends T> list) / unmodifiableSet(...) / unmodifiableMap(...): 返回集合的不可修改视图。

Comparator 接口

当您需要自定义排序逻辑，或者想要排序未实现 Comparable 的类对象，或者不期望使用自然顺序时使用。Comparator 接口定义了 int compare(T o1, T o2) 方法。

使用 Java 8+，Comparator 通常可以使用 lambda 表达式或方法引用简洁地实现。

List<String> words = Arrays.asList("apple", "banana", "kiwi", "orange");
// 使用 lambda 表达式按长度排序
words.sort((s1, s2) -> Integer.compare(s1.length(), s2.length()));
// 或使用 Comparator.comparingInt 方法引用
// words.sort(Comparator.comparingInt(String::length));
System.out.println(words); // 输出: [kiwi, apple, orange, banana]

用于集合处理的 Streams API

Java 8 引入了 Streams API（java.util.stream），提供了一种强大的函数式风格来处理元素序列，包括集合。

示例：过滤和收集

List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "Anna");

// 获取以 'A' 开头并转换为大写的名字列表
List<String> aNamesUpper = names.stream() // 从列表中获取一个流
                                .filter(name -> name.startsWith("A")) // 保留以 A 开头的名字
                                .map(String::toUpperCase) // 将剩余的名字转换为大写
                                .collect(Collectors.toList()); // 将结果收集到一个新的 List 中

System.out.println(aNamesUpper); // 输出: [ALICE, ANNA]

总结

Java 集合框架对于任何 Java 开发人员来说都是至关重要的。它提供了一套强大的接口、实现和算法，用于高效且有效地管理对象组。优先面向接口编程，根据性能需求（访问速度、插入/删除速度、内存使用、顺序）选择实现类，并利用 Streams API 处理复杂的任务。