Which Java Container is Useful for Competitive Programming?

2025年5月2日 | 阅读 15 分钟

在竞争性编程中,使用高效可靠的库确实能极大地提高生产力和性能。在本教程中,我们将重点介绍 Collection Framework 中最重要的容器。

Java 标准库包含以下数据结构

1. ArrayList

ArrayList 是 Java 集合框架的一部分,属于 java.util 包。ArrayList 提供了一种使用可调整大小的 数组 的方式,这对于大小的动态更改非常有用,因此 ArrayList 在许多编程场景中都可能受到青睐,包括竞争性编程,因为其中经常使用动态数组操作。它提供直接访问,并且在列表大小不固定时可能适用。

关键特性

  1. 索引访问:元素可以通过整数索引进行访问,提供快速的随机访问(O(1) 时间复杂度)。
  2. 维护插入顺序:元素按照插入的顺序存储。
  3. 非同步:默认情况下不是线程安全的。对于多线程环境,可以使用 Collections.synchronizedList(new ArrayList<>())。

文件名:ArrayListExample.java

输出

 
Initial list: [10, 20, 30, 40]
First element: 10
List after modification: [10, 20, 25, 40]
List after removing element at index 1: [10, 25, 40]
List after removing element with value 40: [10, 25]
List contains 30: false
Size of the list: 2
Elements in the list: 10 25 
Elements in the list (using indices): 10 25 
Sorted list: [5, 10, 25, 35]
List after clearing all elements: []   

2. LinkedList

LinkedList 是 Java 集合框架的一部分,位于 java.util 包中。它提供了双向链表 数据结构 的实现。LinkedList 中的每个元素都存储在一个节点中,该节点包含指向下一个节点和上一个节点的引用,这使得在列表的两端以及特定位置进行高效的插入和删除成为可能。

关键特性

  1. 双向链表:每个节点都包含指向下一个和上一个节点的引用,支持双向遍历。
  2. 高效的插入/删除:如果已知位置,插入和删除是 O(1) 操作,不像数组需要移动元素。
  3. 索引访问:由于需要从头部或尾部进行遍历,按索引访问元素的时间复杂度为 O(n)。
  4. 维护插入顺序:元素按照插入的顺序存储。
  5. 非同步:默认情况下不是线程安全的。对于多线程环境,可以使用 Collections.synchronizedList(new LinkedList<>())。

文件名:LinkedListExample.java

输出

 
Initial list: [Apple, Banana, Orange, Mango]
List after additions: [Grapes, Apple, Strawberry, Banana, Orange, Mango, Pineapple]
First fruit: Grapes
Last fruit: Pineapple
Fruit at index 2: Strawberry
List after modification: [Grapes, Apple, Strawberry, Cherry, Orange, Mango, Pineapple]
List after removals: [Apple, Cherry, Orange, Mango]
List contains 'Banana': false
Elements in the list: Apple Cherry Orange Mango 
List after clearing all elements: []   

3. HashMap

HashMap 是 Java 集合框架的一部分,位于 java.util 包中。它提供了使用哈希表数据结构的 Map 接口的实现。HashMap 存储键值对,并允许基于其键快速检索值。它在添加、删除和检索元素等操作方面提供了高效的性能,因此是许多编程任务的流行选择。

关键特性

  1. 哈希表实现:HashMap 内部使用哈希表存储键值对。
  2. 快速访问:假设哈希 函数 和元素分布均匀,基本操作(add、remove、containsKey、get)的平均时间复杂度为 O(1)。
  3. 无序集合:与 LinkedHashMap 不同,HashMap 中的元素顺序不保证一致。
  4. 允许空值:HashMap 中的键和值都可以为 null。
  5. 非同步:默认情况下不是线程安全的。对于多线程环境,可以使用 Collections.synchronizedMap(new HashMap<>())。
  6. 初始容量和负载因子:HashMap 允许指定初始容量和负载因子来控制性能和内存使用。

文件名:HashMapExample.java

输出

 
Initial HashMap: {Bob=28, Alice=30, John=25}
HashMap after additions: {Emily=35, Bob=28, Alice=30, John=25, Dave=40}
Age of John: 25
HashMap after modification: {Emily=35, Bob=28, Alice=32, John=25, Dave=40}
HashMap after removal: {Emily=35, Alice=32, John=25, Dave=40}
HashMap contains 'Alice': true
HashMap contains age 40: true
Size of the HashMap: 4
Iterating over keys:
Key: Emily
Key: Alice
Key: John
Key: Dave
Iterating over values:
Value: 35
Value: 32
Value: 25
Value: 40
Iterating over key-value pairs:
Key: Emily, Value: 35
Key: Alice, Value: 32
Key: John, Value: 25
Key: Dave, Value: 40
HashMap after clearing all elements: {}   

4. Queue

Java 中的 Queue 接口是 java.util 包的一部分,表示一个为在处理前保存元素而设计的集合。它遵循先进先出 (FIFO) 原则,其中元素添加到队列的末尾并从前端移除。该接口扩展了 Collection 接口,并提供了用于插入、移除和检查元素的各种方法。

关键特性

  1. 接口:Queue 是一个接口,因此它需要由 LinkedList、PriorityQueue 和 ArrayDeque 等具体类实现。
  2. 阻塞队列:对于线程安全操作,可以使用 ArrayBlockingQueue、LinkedBlockingQueue 和 PriorityBlockingQueue 等 BlockingQueue 实现。
  3. 非阻塞队列:LinkedList 和 PriorityQueue 等标准 Queue 实现不是线程安全的。

文件名:QueueExample.java

输出

 
Initial Queue: [10, 20, 30, 40]
Head of the Queue: 10
Removed Element: 10
Queue after removal: [20, 30, 40]
Queue after adding another element: [20, 30, 40, 50]
Polled Element: 20
Queue after polling: [30, 40, 50]
Queue contains 20: false
Iterating over elements in the queue:
30
40
50
Queue after clearing: []
Is the queue empty: true   

5. Stack

Java 中的 Stack 类 是 java.util 包的一部分,表示一个后进先出 (LIFO) 的对象栈。它扩展了 Vector 类,并提供了五个允许将向量视为堆栈的操作。提供了常见的 push 和 pop 操作,以及一个用于查看堆栈顶部项的 方法、一个用于测试堆栈是否为空的方法,以及一个用于搜索堆栈中的项并发现其距离顶部的距离的方法。

关键特性

  1. 扩展 Vector:Stack 继承了 Vector 的同步方法,这使其成为线程安全的。
  2. 类型安全:泛型实现允许类型安全的堆栈。
  3. 实用工具:提供标准的堆栈操作,如 push、pop、peek、empty 和 search。

文件名:StackExample.java

输出

 
Initial Stack: [10, 20, 30, 40]
Top Element: 40
Popped Element: 40
Stack after pop: [10, 20, 30]
Is the stack empty: false
Position of 20 in the stack: 2
Iterating over elements in the stack:
10
20
30
Stack after clearing: []   

6. Deque

Java 中的 Deque 接口是 java.util 包的一部分,代表“双端队列”。它是一个线性集合,支持在两端插入和删除元素,使其比标准队列更灵活。Deque 可以兼作 FIFO(先进先出)队列和 LIFO(后进先出)堆栈。

关键特性

  1. 多功能性:可用作队列 (FIFO) 或堆栈 (LIFO)。
  2. 接口:Deque 是一个接口,实现包括 ArrayDeque 和 LinkedList。
  3. 容量限制:某些实现可能具有容量限制(例如,ArrayDeque),而其他实现(如 LinkedList)则没有。
  4. 空元素:大多数实现不允许空元素。

文件名:DequeExample.java

输出

 
Initial Deque: [5, 10, 20, 25]
First Element: 5
Last Element: 25
Removed First Element: 5
Removed Last Element: 25
Deque after removals: [10, 20]
Deque after push: [30, 10, 20]
Popped Element: 30
Deque after pop: [10, 20]
Peek First Element: 10
Peek Last Element: 20
Size of Deque: 2
Is Deque Empty: false
Iterating over elements in the deque:
10
20
Deque after clearing: []   

7. HashSet

HashSet 是 Java 集合框架的一部分,并实现了 Set 接口。它使用哈希表进行存储,假设哈希函数能正确地将元素分散到存储桶中,从而为 add、remove、contains 和 size 等基本操作提供恒定的时间性能。

关键特性

  1. 无重复:HashSet 不允许重复元素。如果尝试添加重复元素,add 方法将返回 false。
  2. 顺序:HashSet 不保证任何特定的元素顺序。元素是根据它们的哈希码存储的,并且迭代顺序可能会随时间而改变。
  3. 空元素:HashSet 允许一个空元素。
  4. 非同步:HashSet 不是同步的。如果多个线程并发访问一个哈希集,并且至少有一个线程修改了该集,则必须在外部进行同步。

文件名:HashSetExample.java

输出

 
Initial HashSet: [Apple, Cherry, Date, Banana]
Is 'Apple' added again: false
HashSet after adding duplicate: [Apple, Cherry, Date, Banana]
Contains 'Banana': true
Is 'Date' removed: true
HashSet after removal: [Apple, Cherry, Banana]
Iterating over elements in the HashSet using for-each loop:
Apple
Cherry
Banana
Iterating over elements in the HashSet using iterator:
Apple
Cherry
Banana
Size of HashSet: 3
Is HashSet empty: false
HashSet after clearing: []   

8. TreeMap

TreeMap 是 Java 集合框架的一部分,并实现了 NavigableMap 接口。它是一种基于红黑树的实现,可确保映射按照其键的自然顺序或按指定的比较器以排序顺序排列。当您需要一个维护顺序的映射时,TreeMap 非常有用。

关键特性

  1. 排序顺序:TreeMap 按键的升序维护其元素。
  2. NavigableMap 功能:它提供了通过映射进行导航的方法(例如,firstEntry()、lastEntry()、ceilingEntry()、floorEntry() 等)。
  3. 性能:由于底层的红黑树结构,基本操作(get、put、remove)的时间复杂度为 O(log n)。

文件名:TreeMapExample.java

输出

 
Initial TreeMap: {1=One, 2=Two, 3=Three, 4=Four, 5=Five}
Value for key 3: Three
TreeMap after removing key 2: {1=One, 3=Three, 4=Four, 5=Five}
TreeMap contains key 1: true
TreeMap contains value 'Five': true
First key: 1
Last key: 5
Ceiling key for 3: 3
Floor key for 3: 3
Iterating over elements in the TreeMap:
1 => One
3 => Three
4 => Four
5 => Five
Size of TreeMap: 4
Is TreeMap empty: false
TreeMap after clearing: {}   

下一个主题Prim's 算法 Java