迭代器性能：选择合适的遍历方式

不同场景的性能差异

迭代器的性能取决于底层数据结构和遍历方式。

---

ArrayList 的迭代性能

ArrayList 基于数组，随机访问极快：

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) list.add(i);

long start = System.nanoTime();
int sum = 0;

// 方式 1：普通 for 循环（最快的遍历方式）
for (int i = 0; i < list.size(); i++) {
    sum += list.get(i);
}
System.out.printf("普通 for: %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);

// 方式 2：for-each（底层是 Iterator）
start = System.nanoTime();
sum = 0;
for (int n : list) {
    sum += n;
}
System.out.printf("for-each: %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);

// 方式 3：forEach + Lambda
start = System.nanoTime();
sum = 0;
list.forEach(n -> sum += n);
System.out.printf("forEach:  %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);

// 典型输出（ArrayList 100 万元素）：
// 普通 for: 8 ms   ← 数组下标访问，极快
// for-each: 10 ms  ← 底层是 Iterator，性能接近
// forEach:  15 ms  ← Lambda 有一点点开销

结论：ArrayList 的各种遍历方式性能相近，差异主要来自 Java 的 JIT 优化和 Lambda 的调用开销。

---

LinkedList 的迭代性能

LinkedList 基于链表，随机访问很慢：

LinkedList<Integer> linked = new LinkedList<>();
for (int i = 0; i < 10_000; i++) linked.add(i);

long start = System.nanoTime();
int sum = 0;

// ❌ 普通 for 循环：灾难性的性能
for (int i = 0; i < linked.size(); i++) {
    sum += linked.get(i); // O(n) 每步！总共 O(n²)
}
System.out.printf("for 循环: %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);

// ✅ for-each / Iterator：O(n)，正确的方式
start = System.nanoTime();
sum = 0;
for (int n : linked) {
    sum += n;
}
System.out.printf("for-each: %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);

// 典型输出（LinkedList 1 万元素）：
// for 循环: 2000 ms ← O(n²)，每次 get() 都要从头遍历
// for-each: 2 ms   ← O(n)，只遍历一次

结论：LinkedList 绝对不要用 get(i) 遍历。必须用 Iterator 或 for-each。

---

HashSet 的迭代性能

HashSet 的迭代顺序不确定，但遍历本身是 O(n)：

HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < 1_000_000; i++) set.add(i);

long start = System.nanoTime();
int count = 0;
for (int n : set) {
    count++;
}
System.out.printf("HashSet 遍历: %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);
// 典型输出：~30 ms（O(n)）

---

并行迭代：parallelStream

大数据量时并行遍历可以加速：

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10_000_000; i++) list.add(i);

long start = System.nanoTime();
long sum = list.stream().mapToLong(Integer::intValue).sum();
System.out.printf("串行: %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);

start = System.nanoTime();
long sum2 = list.parallelStream().mapToLong(Integer::intValue).sum();
System.out.printf("并行: %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);

// 典型输出（8 核 CPU）：
// 串行: 120 ms
// 并行:  40 ms  ← 约 3 倍加速

并行遍历的注意事项：

1. 不保证顺序（forEach 无序），用 forEachOrdered 保持顺序
2. 小数据量反而更慢（并行开销大于收益）
3. 线程安全：并发修改同一个集合会有问题

---

性能对比总表

集合	最佳遍历方式	不推荐
ArrayList	for (int i=0...) 或 for-each	—
LinkedList	for-each / Iterator	get(i)
HashSet	for-each / Iterator	—
TreeSet	for-each / Iterator	—
HashMap	map.forEach() 或 for-each	—

---

实际建议

场景	推荐方式
ArrayList 简单遍历	for-each（最简洁）
ArrayList 需索引	普通 for 循环
LinkedList 遍历	for-each（不要用 get）
Map 遍历	map.forEach((k,v) -> ...)
大数据量并行	parallelStream
遍历时删除	Iterator.remove()

---

总结

要点	说明
ArrayList	各种遍历方式性能相近
LinkedList	禁止用 get(i)，用 Iterator
大数据量	parallelStream 可加速 2-4 倍
安全删除	iterator.remove() 是唯一正确方式

一句话：ArrayList 用 for 循环最快，LinkedList 永远不要用 get(i)。

---

相关链接

• Iterator 迭代器
• ArrayList 性能
• LinkedList 性能