Java集合框架：数据结构与使用指南

### Java集合框架：数据结构与使用指南 #### 1. 集合基础方法 在Java编程中，集合是非常重要的数据结构。集合提供了一些基础方法，如下所示： - `clear()`：移除集合中的所有元素。 - `retainAll(Collection other)`：移除集合中所有与`other`集合中元素不相等的元素。如果集合因此调用而发生改变，则返回`true`。 - `toArray()`：返回集合中对象的数组。 迭代器（`Iterator`）也是集合操作中的重要部分，它有以下方法： - `hasNext()`：如果还有下一个元素可访问，则返回`true`。 - `next()`：返回下一个要访问的对象。如果已经到达集合末尾，则抛出`NoSuchElementException`异常。 - `remove()`：移除并返回最后访问的对象。此方法必须紧跟元素访问之后调用。如果自上次元素访问以来集合已被修改，则抛出`IllegalStateException`异常。 #### 2. 链表（Linked Lists） 数组和`ArrayList`在移除或插入中间元素时效率较低，因为需要移动大量元素。而链表则解决了这个问题。在Java中，链表实际上是双向链表，每个节点不仅存储指向下一个节点的引用，还存储指向前一个节点的引用。 以下是一个简单的链表操作示例： ```java LinkedList staff = new LinkedList(); staff.add("Angela"); staff.add("Bob"); staff.add("Carl"); Iterator iter = staff.iterator(); for (int i = 0; i < 3; i++) System.out.println(iter.next()); iter.remove(); // remove last visited element ``` 链表是有序集合，`LinkedList.add`方法默认将对象添加到列表末尾。如果需要在列表中间添加元素，则需要使用`ListIterator`。`ListIterator`是`Iterator`的子接口，包含`add`方法： ```java interface ListIterator extends Iterator { void add(Object); ... } ``` `ListIterator`还提供了反向遍历列表的方法： - `previous()`：返回前一个对象。如果已经到达列表开头，则抛出`NoSuchElementException`异常。 - `hasPrevious()`：如果反向遍历时还有前一个元素可访问，则返回`true`。 以下是使用`ListIterator`在链表中间添加元素的示例： ```java ListIterator iter = staff.listIterator(); iter.next(); iter.add("Juliet"); ``` 此外，`ListIterator`还有`set`方法，用于替换最后一次调用`next`或`previous`返回的元素： ```java ListIterator iter = list.listIterator(); Object oldValue = iter.next(); // returns first element iter.set(newValue); // sets first element to newValue ``` 需要注意的是，链表迭代器会检测并发修改。如果一个迭代器发现集合被另一个迭代器或集合自身的方法修改，则会抛出`ConcurrentModificationException`异常。为避免此异常，可遵循以下规则：可以为一个容器附加多个只读迭代器，或者附加一个可读写的迭代器。 链表还有一些其他有用的方法，如`toString`用于调试，`contains`用于检查元素是否存在。但链表不支持快速随机访问，`get`方法效率较低，不建议使用整数索引来访问链表元素。 下面是一个链表操作的完整示例代码： ```java import java.util.*; /** * This program demonstrates operations on linked lists. */ public class LinkedListTest { public static void main(String[] args) { List a = new LinkedList(); a.add("Angela"); a.add("Carl"); a.add("Erica"); List b = new LinkedList(); b.add("Bob"); b.add("Doug"); b.add("Frances"); b.add("Gloria"); // merge the words from b into a ListIterator aIter = a.listIterator(); Iterator bIter = b.iterator(); while (bIter.hasNext()) { if (aIter.hasNext()) aIter.next(); aIter.add(bIter.next()); } System.out.println(a); // remove every second word from b bIter = b.iterator(); while (bIter.hasNext()) { bIter.next(); // skip one element if (bIter.hasNext()) { bIter.next(); // skip next element bIter.remove(); // remove that element } } System.out.println(b); // bulk operation: remove all words in b from a a.removeAll(b); System.out.println(a); } } ``` #### 3. 数组列表（Array Lists） `List`接口描述了一个有序集合，其中元素的位置很重要。访问元素有两种方式：通过迭代器和通过`get`、`set`方法进行随机访问。对于链表，随机访问方法效率较低，而对于数组则很合适。Java集合库提供了`ArrayList`类来实现`List`接口，它封装了一个动态重新分配的`Object[]`数组。 与`Vector`相比，`ArrayList`的方法不是同步的，因此在单线程环境下使用`ArrayList`效率更高。 #### 4. 哈希集（Hash Sets） 链表和数组可以指定元素的排列顺序，但查找特定元素时可能需要遍历整个集合，效率较低。哈希表则可以快速查找元素。哈希表通过计算对象的哈希码来确定对象在表中的位置。 哈希表是一个链表数组，每个链表称为一个桶（bucket）。为了找到对象在表中的位置，先计算其哈希码，然后对桶的总数取模，得到的结果就是该对象所在桶的索引。 以下是哈希集的一些重要信息： - 哈希集是不包含重复元素的集合。`HashSet`类实现了基于哈希表的集合。 - 可以通过构造函数指定初始桶的数量和负载因子。负载因子决定了哈希表何时需要重新哈希。 - 哈希集的`add`方法会先检查对象是否已存在，只有不存在时才添加。`contains`方法通过检查单个桶中的元素来快速查找元素。 以下是一个使用哈希集的示例： ```java import java.util.*; import java.io.*; /** * This program uses a set to print all unique words in System.in. */ public class SetTest { public static void main(String[] args) { Set words = new HashSet(59999); long totalTime = 0; try { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String line; while ((line = in.readLine()) != null) { StringTokenizer tokenizer = new StringTokenizer(line); while (tokenizer.hasMoreTokens()) { String word = tokenizer.nextToken(); long callTime = System.currentTimeMillis(); words.add(word); callTime = System.currentTimeMillis() - callTime; totalTime += callTime; } } } catch (IOException e) { System.out.println("Error " + e); } Iterator iter = words.iterator(); while (iter.hasNext()) System.out.println(iter.next()); System.out.println(words.size() + " distinct words. " + totalTime + " milliseconds"); } ```