这篇文章主要介绍了 Java 遍历集合方法分析(实现原理、算法性能、适用场合)的相关资料, 需要的朋友可以参考下
Javascript 是一种由 Netscape 的 LiveScript 发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言,主要目的是为了解决服务器端语言,比如 Perl,遗留的速度问题,为客户提供更流畅的浏览效果。
概述
Java 语言中,提供了一套数据集合框架,其中定义了一些诸如 List、Set 等抽象数据类型,每个抽象数据类型的各个具体实现,底层又采用了不同的实现方式,比如 ArrayList 和 LinkedList。
除此之外,Java 对于数据集合的遍历,也提供了几种不同的方式。开发人员必须要清楚的明白每一种遍历方式的特点、适用场合、以及在不同底层实现上的表现。下面就详细分析一下这一块内容。
数据元素是怎样在内存中存放的?
数据元素在内存中,主要有 2 种存储方式:
1、顺序存储,Random Access(Direct Access):
这种方式,相邻的数据元素存放于相邻的内存地址中,整块内存地址是连续的。可以根据元素的位置直接计算出内存地址,直接进行读取。读取一个特定位置元素的平均时间复杂度为 O(1)。正常来说,只有基于数组实现的集合,才有这种特性。Java 中以 ArrayList 为代表。
2、链式存储,Sequential Access:
这种方式,每一个数据元素,在内存中都不要求处于相邻的位置,每个数据元素包含它下一个元素的内存地址。不可以根据元素的位置直接计算出内存地址,只能按顺序读取元素。读取一个特定位置元素的平均时间复杂度为 O(n)。主要以链表为代表。
Java 中以 LinkedList 为代表。
Java 中提供的遍历方式有哪些?
1、传统的 for 循环遍历,基于计数器的:
遍历者自己在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后,停止。主要就是需要按元素的位置来读取元素。这也是最原始的集合遍历方法。
写法为:
- for (int i = 0; i < list.size(); i++) {
- list.get(i);
- }
2、迭代器遍历,Iterator:
Iterator 本来是 OO 的一个设计模式,主要目的就是屏蔽不同数据集合的特点,统一遍历集合的接口。Java 作为一个 OO 语言,自然也在 Collections 中支持了 Iterator 模式。
写法为:
- Iterator iterator = list.iterator();
- while (iterator.hasNext()) {
- iterator.next();
- }
3、foreach 循环遍历:
屏蔽了显式声明的 Iterator 和计数器。
优点:代码简洁,不易出错。
缺点:只能做简单的遍历,不能在遍历过程中操作(删除、替换)数据集合。
写法为:
- for (ElementType element : list) {
- }
每个遍历方法的实现原理是什么?
1、传统的 for 循环遍历,基于计数器的:
遍历者自己在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后,停止。主要就是需要按元素的位置来读取元素。
2、迭代器遍历,Iterator:
每一个具体实现的数据集合,一般都需要提供相应的 Iterator。相比于传统 for 循环,Iterator 取缔了显式的遍历计数器。所以基于顺序存储集合的 Iterator 可以直接按位置访问数据。而基于链式存储集合的 Iterator,正常的实现,都是需要保存当前遍历的位置。然后根据当前位置来向前或者向后移动指针。
3、foreach 循环遍历:
根据反编译的字节码可以发现,foreach 内部也是采用了 Iterator 的方式实现,只不过 Java 编译器帮我们生成了这些代码。
各遍历方式对于不同的存储方式,性能如何?
1、传统的 for 循环遍历,基于计数器的:
因为是基于元素的位置,按位置读取。所以我们可以知道,对于顺序存储,因为读取特定位置元素的平均时间复杂度是 O(1),所以遍历整个集合的平均时间复杂度为 O(n)。而对于链式存储,因为读取特定位置元素的平均时间复杂度是 O(n),所以遍历整个集合的平均时间复杂度为 O(n2)(n 的平方)。
ArrayList 按位置读取的代码:直接按元素位置读取。
- transient Object[] elementData;
- public E get(int index) {
- rangeCheck(index);
- return elementData(index);
- }
- E elementData(int index) {
- return (E) elementData[index];
- }
LinkedList 按位置读取的代码:每次都需要从第 0 个元素开始向后读取。其实它内部也做了小小的优化。
- transient int size = 0;
- transient Node<E> first;
- transient Node<E> last;
- public E get(int index) {
- checkElementIndex(index);
- return node(index).item;
- }
- Node<E> node(int index) {
- if (index < (size >> 1)) { //查询位置在链表前半部分,从链表头开始查找
- Node<E> x = first;
- for (int i = 0; i < index; i++)
- x = x.next;
- return x;
- } else { //查询位置在链表后半部分,从链表尾开始查找
- Node<E> x = last;
- for (int i = size - 1; i > index; i--)
- x = x.prev;
- return x;
- }
- }
2、迭代器遍历,Iterator:
那么对于 RandomAccess 类型的集合来说,没有太多意义,反而因为一些额外的操作,还会增加额外的运行时间。但是对于 Sequential Access 的集合来说,就有很重大的意义了,因为 Iterator 内部维护了当前遍历的位置,所以每次遍历,读取下一个位置并不需要从集合的第一个元素开始查找,只要把指针向后移一位就行了,这样一来,遍历整个集合的时间复杂度就降低为 O(n);
(这里只用 LinkedList 做例子)LinkedList 的迭代器,内部实现,就是维护当前遍历的位置,然后操作指针移动就可以了:
代码:
- public E next() {
- checkForComodification();
- if (!hasNext())
- throw new NoSuchElementException();
- lastReturned = next;
- next = next.next;
- nextIndex++;
- return lastReturned.item;
- }
- public E previous() {
- checkForComodification();
- if (!hasPrevious())
- throw new NoSuchElementException();
- lastReturned = next = (next == null) ? last : next.prev;
- nextIndex--;
- return lastReturned.item;
- }
3、foreach 循环遍历:
分析 Java 字节码可知,foreach 内部实现原理,也是通过 Iterator 实现的,只不过这个 Iterator 是 Java 编译器帮我们生成的,所以我们不需要再手动去编写。但是因为每次都要做类型转换检查,所以花费的时间比 Iterator 略长。时间复杂度和 Iterator 一样。
使用 Iterator 的字节码:
- Code:
- new # // class java/util/ArrayList
- dup
- invokespecial # // Method java/util/ArrayList."<init>":()V
- astore_
- aload_
- invokeinterface #, // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
- astore_
- goto
- aload_
- invokeinterface #, // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
- pop
- aload_
- invokeinterface #, // InterfaceMethod java/util/Iterator.hasNext:()Z
- ifne
- return
使用 foreach 的字节码:
- Code:
- new # // class java/util/ArrayList
- dup
- invokespecial # // Method java/util/ArrayList."<init>":()V
- astore_
- aload_
- invokeinterface #, // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
- astore_
- goto
- aload_
- invokeinterface #, // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
- checkcast # // class loop/Model
- astore_
- aload_
- invokeinterface #, // InterfaceMethod java/util/Iterator.hasNext:()Z
- ifne
- return
各遍历方式的适用于什么场合?
1、传统的 for 循环遍历,基于计数器的:
顺序存储:读取性能比较高。适用于遍历顺序存储集合。
链式存储:时间复杂度太大,不适用于遍历链式存储的集合。
2、迭代器遍历,Iterator:
顺序存储:如果不是太在意时间,推荐选择此方式,毕竟代码更加简洁,也防止了 Off-By-One 的问题。
链式存储:意义就重大了,平均时间复杂度降为 O(n),还是挺诱人的,所以推荐此种遍历方式。
3、foreach 循环遍历:
foreach 只是让代码更加简洁了,但是他有一些缺点,就是遍历过程中不能操作数据集合(删除等),所以有些场合不使用。而且它本身就是基于 Iterator 实现的,但是由于类型转换的问题,所以会比直接使用 Iterator 慢一点,但是还好,时间复杂度都是一样的。所以怎么选择,参考上面两种方式,做一个折中的选择。
Java 的最佳实践是什么?
Java 数据集合框架中,提供了一个 RandomAccess 接口,该接口没有方法,只是一个标记。通常被 List 接口的实现使用,用来标记该 List 的实现是否支持 Random Access。
一个数据集合实现了该接口,就意味着它支持 Random Access,按位置读取元素的平均时间复杂度为 O(1)。比如 ArrayList。
而没有实现该接口的,就表示不支持 Random Access。比如 LinkedList。
所以看来 JDK 开发者也是注意到这个问题的,那么推荐的做法就是,如果想要遍历一个 List,那么先判断是否支持 Random Access,也就是 list instanceof RandomAccess。
比如:
- if (list instanceof RandomAccess) {
- //使用传统的for循环遍历。
- } else {
- //使用Iterator或者foreach。
- }
以上所述是小编给大家介绍的 Java 遍历集合方法分析(实现原理、算法性能、适用场合),希望对大家有所帮助!
来源: http://www.phperz.com/article/17/0225/266189.html