Java集合框架全解析：从基础到实战应用

# Java集合框架全解析：从基础到实战应用 ## 1. Java集合框架概述 Java集合框架提供了接口、实现类、算法和基础设施代码，旨在让对象集合的操作变得安全、可靠且简单。 ### 1.1 集合框架的目的 假设Java集合框架不存在，每个需要管理对象集合的Java程序员都得创建像`DynamicArray`这样的自定义类。这些自定义类会有不同的接口方法、性能存疑，且由于缺乏严格测试，可靠性不佳。不同开发者提供的API可能开源或作为商业产品，性能和特性各异，程序员需学习多个API，且不同API间的互操作性无法保证，编程工作会变得混乱。 而Java集合框架通过提供全面的集合管理API解决了这些问题。开发者只需学习一个API，其集合操作代码就能在各部署平台上运行。通过实现所需的集合接口并遵循简单规则，还能构建自定义类。而且，集合框架经过了整个Java开发者社区的严格测试，能让开发者编写更可靠的代码。 ### 1.2 框架组织 Java集合框架主要分为四个领域： 1. 一组核心集合接口 2. 一组通用实现类 3. 用于集合操作的现成算法 4. 便于集合操作的基础设施代码 要充分利用集合框架，需了解以下内容： 1. 每个核心接口的基本特性和支持的方法 2. 通用实现类及其根本差异 3. 如何使用提供的算法操作集合 4. 对象在集合中的排序方式 5. 如何使用迭代器操作集合 ### 1.3 核心集合接口 Java 1.4.2平台的核心集合接口层次结构包含六个核心接口，分为两个不同的继承层次结构：一个以`Collection`接口为根，另一个以`Map`接口为根。`Map`本身不是`Collection`，但`Map`接口声明了将`Map`的不同视图作为`Collection`对象返回的方法，转换后的`Map`元素可相应操作。 核心集合接口的一般特性如下表所示： | 接口 | 特性 | | --- | --- | | Collection | 所有集合的基础接口，提供统一的集合对象操作方式。部分方法可选，通用集合实现类可能实现也可能不实现。集合元素可通过迭代器访问和操作。 | | List | 元素按顺序排列的集合，元素可插入到列表任意位置，通常允许重复元素。可通过`ListIterator`访问和操作元素，`ListIterator`能前后遍历列表。 | | Set | 不包含重复元素的集合。 | | SortedSet | 迭代器按元素自然顺序遍历的`Set`。插入操作可能较慢，但检索时间可预测。 | | Map | 存储和检索元素（值）的对象，元素位置由键决定。不能包含重复值，一个键只能映射一个值。虽不是`Collection`，但提供返回包含`Map`元素的`Collection`对象的方法。 | | SortedMap | 元素按自然顺序存储的`Map`。插入操作可能较慢，但检索时间可预测。 | ### 1.4 通用实现类 Java集合框架提供了一组通用实现类，可直接在程序中使用。这些类实现了核心集合接口，包括列表、集合、排序集合、映射和排序映射。 每个实现类通常有两种或更多变体，基于数组、链表或树等基础数据结构。为选择合适的集合类，需了解这些基础数据结构的一般性能特性。 #### 1.4.1 数组性能特性 数组是连续的同质元素集合，可用于基本类型或对象引用。数组的性能问题主要涉及在非末尾位置插入新元素、访问元素和搜索特定值。在非末尾位置插入元素时，需将后续元素右移，可能导致性能下降。若触发数组增长机制，性能影响更大。不过，元素检索速度较快，因为数组元素地址计算方式高效。 #### 1.4.2 链表性能特性 链表的元素在内存中独立存在，通过引用相互连接。与数组不同，链表节点是复杂的数据结构，包含指向前一个节点、后一个节点和对象负载的引用。链表元素插入速度快，无需元素移动，但查找元素需遍历链表，会带来性能开销。 #### 1.4.3 哈希表性能特性 哈希表是元素可指向一系列节点的数组，结构上是数组和单向链表的结合。哈希表通过哈希函数将元素分配到数组位置，可减少内存浪费。但可能出现哈希冲突，即不同键映射到相同数组索引，此时通过链表解决冲突。哈希表初始内存开销低，元素插入相对较快，但冲突过多时，链表遍历会影响性能。 #### 1.4.4 红黑树性能特性 名称中包含“tree”的集合实现了`SortedSet`或`SortedMap`接口，插入元素时自动排序，基于红黑树实现。红黑树是一种自平衡的二叉搜索树，节点有额外的颜色属性。插入元素后会进行自平衡操作，确保所有叶节点到根节点的黑色节点数量相同。红黑树的主要优点是节点搜索性能好，但插入大量节点时会有性能开销。 #### 1.4.5 实现类与基础数据结构的映射 通用实现类的名称由基础数据结构名称（如`Array`、`Linked`、`Hash`或`Tree`）和实现的接口名称（如`List`、`Set`或`Map`）组合而成。例如，`HashSet`的基础数据结构是哈希表，`TreeSet`基于红黑树实现。 ### 1.5 算法 Java集合框架提供了一组现成的算法，以`Collections`类的静态方法实现。该类提供了排序、搜索集合以及查找最大和最小元素值的方法。`Arrays`类也提供了排序、搜索和操作数组的静态方法，`Collection`接口的`toArray()`方法可将集合元素转换为数组，以便使用`Arrays`类的方法操作。 ### 1.6 基础设施 Java集合框架提供了几个类和接口，用于帮助操作集合元素（`Iterator`和`ListIterator`）、创建集合感知类（`Comparable`和`Comparator`）以及捕获特定集合异常（`UnsupportedOperationException`和`ConcurrentModificationException`），这些被称为基础设施。 ## 2. Java 1.4.2风格的集合 Java 1.4.2及之前的集合框架允许管理对象集合而无需指定对象类型。若要调用对象特有的方法，需将检索到的对象强制转换为所需类型。以下是几个示例程序，展示了Java 5之前的集合框架编程风格。 ### 2.1 从列表创建集合 以下是`SetTestApp`程序示例： ```java import java.util.*; public class SetTestApp { public static void main(String[] args) { List list = new LinkedList(); for (int i = 0; i < 100; i++) { list.add(new Integer(i % 10)); } System.out.print("List Contents: "); for (Iterator i = list.iterator(); i.hasNext();) { System.out.print(i.next().toString()); } System.out.println(); Set set = new TreeSet(list); System.out.print("Set Contents: "); for (Iterator i = set.iterator(); i.hasNext();) { System.out.print(i.next().toString()); } System.out.println(); } } ``` 该程序创建了一个包含重复元素的`LinkedList`，然后使用该列表的元素创建了一个`TreeSet`。由于`Set`不允许重复元素，`TreeSet`只包含列表中的唯一元素。 ### 2.2 重温PeopleManager示例 此示例将`PeopleManager`类中的数组替换为`LinkedList`，并为`Person`类添加了`toString()`方法。 `Person.java`代码如下： ```java import java.util.*; public class Person { private String first_name = null; private String middle_name = null; private String last_name = null; private Calendar birthday = null; private String gender = null; public static final String MALE = "Male"; public static final String FEMALE = "Female"; public Person(String f_name, String m_name, String l_name, int dob_year, int dob_month, int dob_day, String gender) { first_name = f_name; middle_name = m_name; last_name = l_name; this.gender = gender; birthday = Calen ```