Java遍历全攻略：从数组到二叉树，彻底搞懂遍历方式与坑

提到Java遍历我第一反应不是去背API而是先问一句你要遍历的到底是什么结构是数组、List、Set还是Map遍历过程中要不要删除元素数据量大不大需不需要并行这些听起来像面试题但实际写业务代码时如果不想清楚很容易踩坑。这篇内容我把Java里能用的遍历方法几乎全部过了一遍数组、集合、Map、二叉树层序全都有每个方法都讲清楚怎么用、优缺点是什么、适合什么场景同时附上我在实际项目里踩过的坑和排查思路。无论你是准备面试还是日常写代码想选个合适的方式应该都能从中找到答案。1. 想清楚再遍历遍历的本质与分类1.1 遍历到底在遍历什么我之前面试过不少Java开发问起遍历方法很多人张口就是for循环、foreach、迭代器但问到他遍历的数据底层是什么结构就卡壳了。遍历的本质其实就一句话按某种规则把容器里的元素一个一个取出来处理。这个“规则”受限于数据结构的组织方式。数组和ArrayList元素在内存里是连续排列的所以用下标访问最快复杂度O(1)。LinkedList是双向链表内存不连续用下标get就是O(n)这时候用迭代器或者foreach反而更合适。HashMap底层是数组加链表加红黑树它的遍历顺序和插入顺序通常不一致除非用LinkedHashMap。TreeMap底层是红黑树遍历时按key的自然顺序或比较器顺序输出。理解这一点很多选择就顺理成章了。不是哪种遍历方式“最好”而是你的数据长什么样决定了哪种方式最合适。1.2 数据结构决定遍历方式我把遍历方式按“访问机制”分成三类这个分类比单纯罗列API更实用索引访问靠下标取元素典型就是for i循环。适合数组、ArrayList但不适合LinkedList。迭代器访问Iterator、增强for、ListIterator都是这一类通过hasNext和next逐个取不依赖下标适合链表、Set、Map等所有Collection。函数式访问forEach和Stream底层其实还是迭代器或Spliterator但把逻辑封装在了Lambda表达式里代码更紧凑还支持并行流。从实现原理来看增强for循环本质上就是语法糖编译后用的就是Iterator只是把hasNext和next隐藏了。这也是为什么在增强for里删除元素会抛ConcurrentModificationException——因为迭代器的modCount校验机制被触发了。2. 数组与List的遍历全家桶2.1 下标遍历最原始也最可控先看最基础的数组遍历int[] arr {1, 2, 3, 4, 5}; for (int i 0; i arr.length; i) { System.out.println(arr[i]); }List结合下标遍历ListString list new ArrayList(); for (int i 0; i list.size(); i) { String item list.get(i); // do something }这种方式的优点非常直白能拿到当前下标方便在遍历时修改元素比如把每个数字翻倍也可以根据自己的需求控制步长比如每隔一个取一个。缺点是如果list是LinkedListget(i)每次都要从头往后找复杂度变成O(n²)数据一多性能直接崩。我真实遇到过用for i循环遍历一个十万级的LinkedList接口响应从几十毫秒变成十几秒后来换成foreach就好了。所以我的建议是数组和ArrayList用下标遍历没问题LinkedList千万别这么玩。另外要注意边界条件下标从0开始循环里不要随意修改list的size不然容易数组越界。2.2 增强for与Iterator代码更好看了但小心隐藏的坑增强for适用于数组和所有Collection子类for (String item : list) { System.out.println(item); }代码写起来很干净不会出现下标越界也不容易漏元素。但它的缺点也明显没有下标不能在循环体里直接删除元素修改集合元素本身是可以的因为拿到的是引用但如果用list.remove()就会触发fail-fast。Iterator是增强for的底层自己写出来会有更多控制力IteratorString iterator list.iterator(); while (iterator.hasNext()) { String item iterator.next(); if (bad.equals(item)) { iterator.remove(); } }这个remove方法很关键它是迭代器自己在遍历过程中调用了集合的remove并且会把expectedModCount同步因此不会抛异常。如果你需要在遍历时删除符合条件的元素Iterator是Java 8之前最正统的写法。还要提一个ListIterator它是继承Iterator的只在List接口里有ListIteratorString listIterator list.listIterator(); while (listIterator.hasNext()) { String item listIterator.next(); } while (listIterator.hasPrevious()) { String previous listIterator.previous(); }ListIterator支持双向遍历还能在遍历时用add往当前节点插入元素用set替换当前元素。实际开发中反向遍历一个LinkedList时用它特别方便比先整体反转再遍历性能好很多。2.3 forEach与Stream函数式风格带来的改变Collection接口在Java 8之后有了默认的forEach方法list.forEach(item - System.out.println(item)); list.forEach(System.out::println);Map也有自己的forEach参数是BiConsumermap.forEach((k, v) - System.out.println(k v));这种方式的优点是语义清晰、代码简短也避免了显式处理下标或迭代器。缺点是没有索引且不能在中途使用break或return退出只能通过抛异常来中断实际开发里很少这样干。另外lambda里需要用到的变量如果是在循环外定义的必须保证是final或effectively final这点容易踩坑。再来说Streamlist.stream().forEach(item - System.out.println(item)); list.parallelStream().forEach(item - System.out.println(item));Stream本身不直接存储数据它是对集合操作的一层抽象。stream().forEach和Collection.forEach底层差别不大但Stream有更多衍生操作比如filter、map、sorted、collect能在一个链式调用里完成过滤、转换、汇总。parallelStream就更有意思了它支持多线程并行遍历数据量大时能明显提速。但并行流有代价线程切换、分割开销、线程安全问题都需要考虑。举个并行流翻车的例子我用parallelStream给一个共享的HashMap塞数据结果偶发丢数据原因就是多个线程同时put导致覆盖或扩容问题。后来改成用ConcurrentHashMap或者用Collectors.toMap收集才稳定下来。所以并行流不是不能碰而是要确保你的处理逻辑是线程安全的且数据量够大才划算。2.4 List删除元素的三种正确姿势遍历删除是面试高频题也是平时最容易出bug的地方。我归纳了三种安全的删除方式使用Iterator的remove方法刚才已经演示过了。使用Java 8的removeIf最简洁list.removeIf(item - bad.equals(item));先收集要删除的元素循环结束后统一删除ListString toRemove new ArrayList(); for (String item : list) { if (bad.equals(item)) { toRemove.add(item); } } list.removeAll(toRemove);如果你用传统的for i循环正向删除假设列表是[a,b,c]删掉下标0的a之后b变成了下标0循环下标到1时处理的是c等于把b漏掉了。如果改用倒着遍历就能避免这个问题但代码不够直观不推荐。顺带说一句如果集合本身是CopyOnWriteArrayList那么直接在增强for里删除也不会抛异常因为它的迭代器是弱一致性的遍历的是快照。但写操作本身有锁和数组复制的成本不能因为能删就无脑使用。3. Set与Map的遍历路线图3.1 Set遍历明明是集合为什么顺序总不对Set在Java里不是一个单独的类而是HashSet、LinkedHashSet、TreeSet这些实现的统称。Set没有get方法也不支持下标访问所以遍历方式比List少很多基本就是增强for、Iterator、forEach、Stream。SetString set new HashSet(); set.add(a); set.add(b); for (String s : set) { System.out.println(s); }HashSet的遍历顺序是不保证的它由哈希桶位置和链表/红黑树的组织结构决定。LinkedHashSet则按插入顺序遍历适合需要保持顺序的场景。TreeSet底层是红黑树遍历结果是按元素的自然顺序或Comparator排序的。所以当你发现Set遍历结果和预期不一致时先检查你用的是哪个实现而不是怀疑遍历代码写错了。Set遍历时删除元素同样有讲究。增强for里删除会抛异常Iterator.remove是安全的total removeIf也可以用。我的习惯是如果整个Set要清空直接用set.clear()别在循环里一个个删。3.2 Map三大视图entrySet、keySet、values到底怎么选Map不是Collection它有自己的三套遍历入口entrySet遍历键值对。keySet遍历所有key再通过get(key)拿value。values只遍历value。代码示例// 方式1entrySet for (Map.EntryString, Integer entry : map.entrySet()) { System.out.println(entry.getKey() : entry.getValue()); } // 方式2keySet for (String key : map.keySet()) { System.out.println(key : map.get(key)); } // 方式3values for (Integer value : map.values()) { System.out.println(value); }面试里经常问三种方式哪个性能最好。答案很明确遍历key和value都需要的场景用entrySet。因为它一次性拿到键值对不需要再通过key去查一遍value。keySet的方式需要额外调用get(key)等于多做了一次hash查找HashMap的数据量大了以后这部分开销很明显。如果只需要value那就直接用values()省去key的遍历。LinkedHashMap的entrySet遍历顺序就是插入顺序这个特性在做LRU缓存的时候非常有用。TreeMap的entrySet则是按key排序的可以直接实现排行榜之类的需求。3.3 Map的forEach和Stream遍历以及Lambda的坑Map也有forEachmap.forEach((key, value) - System.out.println(key value));这里的Lambda接收两个参数第一个是key第二个是value。如果只想遍历key可以用map.keySet().forEach只想遍历value就map.values().forEach。如果不小心把Lambda参数顺序写反会在运行时才发现因为类型都是推断出来的。Stream遍历Map可以配合entrySetmap.entrySet().stream() .filter(entry - entry.getValue() 100) .forEach(entry - System.out.println(entry.getKey()));甚至可以收集回MapMapString, Integer filtered map.entrySet().stream() .filter(entry - entry.getValue() 100) .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));这里有一个容易踩的坑如果原始的Map里有重复的新keyCollectors.toMap会直接抛IllegalStateException。比如一个MapString, List 经过grouping之后想转成MapString, Integer如果value聚合时没有处理好就会重复key。解决方法是给toMap传入第三个参数mergeFunction例如(k1, k2) - k1告诉它遇到冲突时保留哪个。Map遍历时修改同样要当心。HashMap不是线程安全的如果在遍历过程中另一个线程修改它会抛ConcurrentModificationException。即使在单线程里你在foreach中调用map.put新的key也可能抛异常。推荐的模式是先记录要修改的内容遍历结束后批量处理或者直接用ConcurrentHashMap配合compute等方法实现原子更新。4. 特殊场景遍历二叉树、层序与链表4.1 二叉树前中后序遍历的递归与迭代二叉树的遍历在面试和算法题里出现频率极高和集合遍历不一样它要处理的不是线性结构而是树形结构。前序、中序、后序的本质区别在于根节点被访问的时机前序遍历根在前顺序是根、左、右。中序遍历根在中间顺序是左、根、右。后序遍历根在最后顺序是左、右、根。递归版本最简单void preOrder(TreeNode node) { if (node null) return; System.out.println(node.val); preOrder(node.left); preOrder(node.right); } void inOrder(TreeNode node) { if (node null) return; inOrder(node.left); System.out.println(node.val); inOrder(node.right); } void postOrder(TreeNode node) { if (node null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.val); }递归的优点是代码简洁、逻辑清晰缺点是如果树的深度很大递归层数过深会爆栈。迭代版本就要用到栈来模拟递归过程。以前序遍历为例void preOrderIter(TreeNode root) { if (root null) return; DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); System.out.println(node.val); if (node.right ! null) stack.push(node.right); if (node.left ! null) stack.push(node.left); } }注意这里压栈顺序是先压右子树再压左子树这样弹出时才会先访问左子树。中序遍历的迭代稍微复杂一点要先一路走到最左节点再慢慢弹栈访问右子树。后序遍历迭代版本最绕可以考虑用双栈法或者用标记法记录节点是否已经访问过左右子树。4.2 层序遍历的队列实现层序遍历就是按层从上到下、从左到右遍历属于广度优先遍历。核心工具是队列void levelOrder(TreeNode root) { if (root null) return; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node queue.poll(); System.out.println(node.val); if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } }很多面试题会在此基础上让区分每一层的元素比如按层输出或求每层最大值。解决办法是记录当前层的节点数用一个内层循环消费完这一层while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { TreeNode node queue.poll(); // 处理当前层节点 if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } }这里的size必须在循环前先取出因为offer新节点会改变queue.size()如果直接在循环条件里写queue.size()会多遍历新加入的下一层节点导致层级错乱。这个坑我踩过一次调试了半天才发现是size动态变化。4.3 链表遍历与快慢指针实战链表遍历和数组不太一样普通遍历就是从head开始一个节点一个节点next下去ListNode cur head; while (cur ! null) { System.out.println(cur.val); cur cur.next; }如果是遍历链表的同时需要删除节点要保留prev指针如果是双向链表可以直接用node.prev。链表的经典技巧是快慢指针比如判断链表是否有环boolean hasCycle(ListNode head) { ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) return true; } return false; }这个思路也属于遍历的一种变体关键在于控制两个指针的步长。求链表中间节点时fast走两步slow走一步fast到末尾时slow正好在中间。用这种方式遍历链表比先算长度再走一半要高效得多也避免了两次遍历。5. 遍历性能对比与实战选型5.1 不同数据量下的性能表现很多人喜欢纠结for、foreach、stream哪个性能最好。我觉得应该分情况讨论而不是一刀切。先说结论在ArrayList这种支持随机访问的结构里for i循环的性能通常是最高的因为JIT可以优化边界检查而且不涉及迭代器的对象分配。增强for底层也是迭代器但编译器会针对数组和ArrayList做优化性能差距很小大多数场景可以忽略。stream().forEach的性能比传统for i略低一点因为它有额外的抽象开销但差距通常不到10%除非你开启了并行流。但在LinkedList的场景里for i就是性能灾难因为每次get都要遍历链表。同样是10w条数据for i遍历LinkedList比foreach慢几个数量级。所以最根本的还是要看你用的是什么数据结构。我用JMH做过简单测试百万级ArrayList遍历for i和foreach差不到5%stream慢10%-15%左右。但换成parallelStream后在四核机器上能快3倍左右。注意这个结论只适用于CPU密集型的处理如果处理内容涉及IO或锁争用并行流很可能更慢。5.2 遍历过程中的修改问题与并发安全遍历中能不能修改集合是判断你是否真正理解迭代器机制的最好问题。我总结了四条经验增强for、stream、forEach遍历过程中单线程直接调用集合的add/remove会抛ConcurrentModificationException。Iterator的remove方法是安全删除当前元素的唯一传统方式。使用CopyOnWriteArrayList或ConcurrentHashMap可以避免遍历时的并发修改异常但引入的是读写分离或锁机制写性能会下降。自己写的业务代码里如果确实要边遍历边修改最稳妥的方案是先构建一个待操作列表遍历结束后统一处理。还有一个小众场景遍历过程中替换元素本身比如把一个列表里的所有空字符串改成default这个没问题因为list.get(i)或list.set(i, ...)不会触发modCount变化。这里要说清楚“修改”指的是改集合结构比如增删元素而不是改元素内容。5.3 一个参考选型表我把常见遍历场景和推荐方式整理成表方便直接查阅数据结构遍历场景推荐方式需要注意数组需要下标for i注意边界ArrayList只读遍历for/i、foreach差距不大LinkedList顺序遍历foreach、Iterator禁止for i getList边遍历边删Iterator.remove、removeIf增强for会抛异常Set无序遍历foreach、iterator顺序依赖实现类Mapkey和valueentrySet避免keySet重复查表Map只查keykeySet再取值开销大二叉树层序Queue队列记得先记录size大数据集CPU密集处理parallelStream注意线程安全这个表不是金科玉律但作为日常开发选型的起点是够用的。6. 常见问题排查与个人心得6.1 ConcurrentModificationException到底怎么来的这个问题我在团队里讲过很多次。它并不是修改和遍历同时进行就会必然出现而是Java集合的fail-fast机制在起作用。以ArrayList为例内部有个modCount字段每次结构性修改add、remove等都会加1。迭代器初始化时会把expectedModCount记为当前modCount每次调用next或remove时都会检查modCount是否仍然等于expectedModCount一旦不等就抛ConcurrentModificationException。所以即使你在单线程里用foreach遍历到一半时调用了list.add也会抛异常。解决办法还是前面那几招用Iterator的remove或者用removeIf或者先收集后统一删。另外HashMap的keySet、entrySet、values迭代器同样有fail-fast机制遍历中直接put新key也可能触发。如果业务要求弱一致性可以换用ConcurrentHashMap它的迭代器不会抛ConcurrentModificationException但也看不到遍历开始后新增的元素。6.2 陷阱速查这些场景我踩过的坑我把特意踩过和复盘过的坑列出来都是实战里容易翻车的用了for i循环遍历LinkedList性能暴跌。排查方法很简单看一眼集合在内存中的结构或者用StopWatch把各部分耗时打出来。在增强for里调用list.remove程序执行到一半抛异常数据状态被破坏。后续必须改用removeIf或Iterator。用keySet遍历大Map然后每次get明明entrySet一步能解决的事多花了大量时间重算hash。Map的forEach遍历时Lambda里引用外部可变变量编译器报错说variable used in lambda expression should be effectively final。二叉树层序遍历时在循环条件里直接写queue.size()导致一次循环把多层节点都处理了数据错乱。parallelStream处理共享ArrayList并add结果数据丢失甚至ArrayIndexOutOfBounds但用list.parallelStream().collect(Collectors.toList())就没事。用Stream的toMap收集时遇到重复key抛IllegalStateException没给mergeFunction就把整个任务打挂。这些坑每个都有对应的排查思路核心就是多打印、分段测别一开始就怀疑JDK有问题。6.3 个人心得从面试到实战的遍历经验最后说说我自己的体会。其实遍历本身不是一个难题但它非常能体现一名工程师对数据结构和Java集合底层是否熟悉。面试里我会先问“你会几种遍历”然后层层挖到并发修改、性能差异、底层实现这些问题能很快筛出只是背了API的人。真正到了生产环境遍历的最优解往往不是性能最好的那个而是代码最易读、最少出错的那个。我现在的习惯是纯读取用foreach或stream需要下标操作就用for i但先确认集合是ArrayList遍历删除一律用removeIf复杂逻辑用IteratorMap遍历直接上entrySet需要并行处理大集合时优先用parallelStream加collect处理过程不放共享状态。遇到拿不准的场景先写一个几十万条数据的测试用例看耗时和异常情况用数据说话。再一次说别小看遍历。很多线上事故表象是数据不对根源就是遍历时改了集合结构。把这个基础打好后面写业务代码会顺畅很多。