Java 数据结构

Java - 集合框架 (现代数据结构)

在编程中，高效地存储和操作对象组至关重要。虽然存在基本的数组，但 Java 通过强大的**Java Collections Framework（Java集合框架）**提供了一套精密且强大的现代数据结构，该框架主要位于 java.util 包中。

**关于遗留类的注意事项：**较旧的 Java 版本包含 Vector、Stack、Hashtable、Dictionary 等类以及 Enumeration 接口。**这些现在被认为是遗留的，在新代码中通常应避免使用。**现代 Collections Framework 提供了更优越的性能、灵活性和 API 设计。

本教程重点介绍现代 Collections Framework 的核心概念和常用组件。

Collections Framework 的核心接口

该框架围绕一组核心接口构建，这些接口定义了不同类型的集合：

• **Collection：**根接口，表示一组对象（元素）。它定义了基本操作，例如添加、删除、检查大小和迭代。它很少直接使用，但为其他接口提供了共同的基础。
• **List：**一个有序的集合（序列），允许包含重复元素。可以通过其整数索引（位置）访问元素。可以将其视为一个动态数组。常见实现：ArrayList、LinkedList。
• **Set：**一个不允许包含重复元素的集合。通常不保证元素的顺序（尽管某些实现会维护顺序）。用于存储唯一项。常见实现：HashSet、LinkedHashSet、TreeSet。
• **Queue：**用于在处理之前保存元素的集合，通常遵循 FIFO（先进先出）顺序。常见实现：LinkedList、PriorityQueue。
• **Deque：**双端队列，允许从两端添加/删除元素。它扩展了 Queue。常见实现：LinkedList、ArrayDeque。
• Map<K, V>：（注意：不扩展 Collection）将键映射到值的对象。每个键都必须是唯一的。用于键值查找。常见实现：HashMap、LinkedHashMap、TreeMap。

、 和 符号表示泛型（generics），允许您指定集合将持有的元素、键或值的类型，从而在编译时提供类型安全（type safety）。

常见实现类

您通常使用实现这些接口的具体类：

ArrayList（实现 List）：

内部使用动态大小调整的数组。通过索引（get(index)）提供快速的随机访问。添加/删除元素可能较慢，如果需要调整大小或移动元素，尤其是在中间位置。

import java.util.ArrayList;
import java.util.List;

// ...

List<String> names = new ArrayList<>(); // Use Interface type for variable
names.add("Alice");
names.add("Bob");
names.add(0, "Charlie"); // Add at specific index

String secondName = names.get(1); // Access by index (gets "Alice")
System.out.println("Names: " + names); // Output: Names: [Charlie, Alice, Bob]
System.out.println("Second name: " + secondName);

LinkedList（实现 List, Deque）：

内部使用双向链表。在开头或结尾添加/删除元素更快。与 ArrayList 相比，通过索引进行随机访问较慢，因为它需要遍历列表。

import java.util.LinkedList;
import java.util.List;

// ...

List<Integer> scores = new LinkedList<>();
scores.add(95);
scores.add(88);
((LinkedList<Integer>) scores).addFirst(100); // Use Deque methods via casting or Deque variable

System.out.println("Scores: " + scores); // Output: Scores: [100, 95, 88]

HashSet（实现 Set）：

使用哈希表（hash table）存储唯一元素。提供快速的添加、删除和包含操作（平均时间复杂度 O(1)）。不保证元素的任何特定顺序。

import java.util.HashSet;
import java.util.Set;

// ...

Set<String> uniqueTags = new HashSet<>();
uniqueTags.add("java");
uniqueTags.add("programming");
uniqueTags.add("java"); // Duplicate, will be ignored

System.out.println("Contains 'java'? " + uniqueTags.contains("java")); // true
System.out.println("Tags: " + uniqueTags); // Output order not guaranteed, e.g., Tags: [java, programming]

LinkedHashSet（实现 Set）：

类似于 HashSet，但维护元素的插入顺序。

TreeSet（实现 SortedSet）：

以排序顺序（自然顺序或使用自定义 Comparator）存储唯一元素。添加/删除比 HashSet 慢 (O(log n))。

HashMap<K, V>（实现 Map）：

使用哈希表存储键值对。通过给定键提供快速的值检索（平均时间复杂度 O(1)）。不保证顺序。

import java.util.HashMap;
import java.util.Map;

// ...

Map<String, Integer> ageMap = new HashMap<>();
ageMap.put("Alice", 30);
ageMap.put("Bob", 25);
ageMap.put("Charlie", 35);
ageMap.put("Alice", 31); // Replaces the previous value for key "Alice"

int aliceAge = ageMap.get("Alice"); // Retrieve value by key
System.out.println("Alice's age: " + aliceAge); // Output: Alice's age: 31
System.out.println("Map contains Bob? " + ageMap.containsKey("Bob")); // true
System.out.println("Ages: " + ageMap); // Order not guaranteed

LinkedHashMap<K, V>（实现 Map）：

类似于 HashMap，但维护键的插入顺序。

TreeMap<K, V>（实现 SortedMap）：

按键排序（自然顺序或使用自定义 Comparator）存储键值对。查找比 HashMap 慢 (O(log n))。

遍历集合

您可以使用几种方法遍历集合中的元素：

1. 增强型 for 循环（适用于简单遍历）：

List<String> fruits = List.of("Apple", "Banana", "Orange"); // Java 9+ immutable list
for (String fruit : fruits) {
    System.out.println(fruit);
}

2. Iterator（迭代器）：

提供 hasNext()、next() 和可选的 remove() 方法。如果您需要在迭代期间删除元素，则需要使用迭代器。

import java.util.Iterator;
// ...
Set<Integer> numbers = new HashSet<>(List.of(1, 2, 3, 4, 5));
Iterator<Integer> iterator = numbers.iterator();
while (iterator.hasNext()) {
    Integer number = iterator.next();
    if (number % 2 == 0) {
        iterator.remove(); // Safely remove the current element
    }
}
System.out.println("Odd numbers: " + numbers); // Output: Odd numbers: [1, 3, 5] (order may vary)

3. Streams API（流 API，Java 8+）：

提供一种强大的函数式方法来处理集合（过滤、映射、归约等）。

List<String> words = List.of("Java", "Collections", "Framework", "Stream");
words.stream()
   .filter(s -> s.length() > 5) // Keep words longer than 5 chars
   .map(String::toUpperCase)    // Convert to uppercase
   .forEach(System.out::println); // Print each result
// Output:
// COLLECTIONS
// FRAMEWORK

选择合适的集合

• 需要具有快速索引访问的有序列表？使用 ArrayList。
• 需要有序列表，且频繁在两端添加/删除？使用 LinkedList。
• 需要快速存储唯一元素且不关心顺序？使用 HashSet。
• 需要存储按插入顺序排列的唯一元素？使用 LinkedHashSet。
• 需要存储按排序顺序排列的唯一元素？使用 TreeSet。
• 需要快速的键值查找且不关心顺序？使用 HashMap。
• 需要存储按插入顺序排列的键值对？使用 LinkedHashMap。
• 需要存储按键排序的键值对？使用 TreeMap。

Java Collections Framework 非常广泛。请查阅 java.util 包的文档，了解更多专用集合和工具类（utility classes），如 Collections 和 Arrays。