Detailed explanation of various common traversal methods in Java

The following editor will bring you a summary and detailed comparison of several methods of Java collection traversal. The editor thinks it’s pretty good, so I’ll share it with you now and give it as a reference. Let’s follow the editor to take a look at it.

The general traversal method of collection class, use iterator to iterate:

Iterator it = list.iterator();
while(it.hasNext()) {
　　Object obj = it.next();
}

Map traversal method:

1. Get all the keys according to the key Traverse

//Set<Integer> set = map.keySet(); //得到所有key的集合
for (Integer in : map.keySet()) {
  String str = map.get(in);//得到每个key多对用value的值
}

2. Use iterator to traverse key and value through Map.entrySet

Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
   Map.Entry<Integer, String> entry = it.next();
    System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

3. Traverse key and value through Map.entrySet, recommended, especially when the capacity is large

for (Map.Entry<Integer, String> entry : map.entrySet()) {
  //Map.entry<Integer,String> 映射项（键-值对） 有几个方法：用上面的名字entry
  //entry.getKey() ;entry.getValue(); entry.setValue();
  //map.entrySet() 返回此映射中包含的映射关系的 Set视图。
  System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

4. Traverse all values ​​through Map.values(), but not the key

for (String v : map.values()) {
  System.out.println("value= " + v);
}

List traversal method:

First type:

for(Iterator iterator = list.iterator();iterator.hasNext();){          
  int i = (Integer) iterator.next();          
  System.out.println(i);        
}

Second type:

Iterator iterator = list.iterator();
while(iterator.hasNext()){
  int i = (Integer) iterator.next();
  System.out.println(i);
}

The third type:

for (Object object : list) { 
  System.out.println(object); 
}

The fourth type:

for(int i = 0 ;i<list.size();i++) { 
  int j= (Integer) list.get(i);
  System.out.println(j); 
}

How are data elements stored in memory?

There are two main storage methods:

1. Sequential storage, Random Access (Direct Access):

In this way, adjacent data elements are stored in the same place. Among adjacent memory addresses, the entire memory address is continuous. The memory address can be directly calculated based on the position of the element and read directly. The average time complexity of reading an element at a specific position is O(1). Normally, only collections implemented based on array have this feature. Java is represented by ArrayList.

2. Chain storage, Sequential Access:

In this way, each data element does not need to be in an adjacent position in the memory. Each data element contains the memory address of its next element. . The memory address cannot be calculated directly based on the position of the element, the elements can only be read in sequence. The average time complexity of reading an element at a specific position is O(n). Mainly represented by linked lists. Represented by LinkedList in Java.

What is the implementation principle of each traversal method?

1. Traditional for loop traversal, counter-based:

The traverser maintains a counter outside the collection, and then reads the elements at each position in turn. When the last one is read After the element, stop. The main thing is to read elements according to their position.

2. Iterator traversal, Iterator:

Every concrete implementation of the data setcombination generally needs to provide the corresponding Iterator. Compared with the traditional for loop, Iterator eliminates the explicit traversal counter. Therefore, an Iterator based on sequentially stored collections can directly access data by position. The normal implementation of Iterator based on chained storage collections requires saving the current traversed position. Then move the pointer forward or backward according to the current position.

3, foreachLoop traversal:

According to the decompiled bytecode, it can be found that foreach is also implemented internally using Iterator, but the Java compiler generates these codes for us.

What is the performance of each traversal method for different storage methods?

1. Traditional for loop traversal, based on counter:

Because it is based on the position of the element, it is read by position. So we can know that for sequential storage, because the average time complexity of reading an element at a specific position is O(1), the average time complexity of traversing the entire collection is O(n). For chained storage, because the average time complexity of reading an element at a specific position is O(n), the average time complexity of traversing the entire collection is O(n2) (n squared).

Code for reading ArrayList by position: read directly by element position.

transient Object[] elementData;

public E get(int index) {
  rangeCheck(index);
  return elementData(index);
}

E elementData(int index) {
  return (E) elementData[index];
}

Code for reading LinkedList by position: Each time you need to read backwards from the 0th element. In fact, it has also made small optimizations internally.

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 traversal, 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和foreach字节码如下：

//使用Iterator的字节码：
  Code:
    0: new      #16         // class java/util/ArrayList
    3: dup
    4: invokespecial #18         // Method java/util/ArrayList."<init>":()V
    7: astore_1
    8: aload_1
    9: invokeinterface #19, 1      // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
   14: astore_2
   15: goto     25
   18: aload_2
   19: invokeinterface #25, 1      // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   24: pop
   25: aload_2
   26: invokeinterface #31, 1      // InterfaceMethod java/util/Iterator.hasNext:()Z
   31: ifne     18
   34: return
 
 
//使用foreach的字节码：
  Code:
    0: new      #16         // class java/util/ArrayList
    3: dup
    4: invokespecial #18         // Method java/util/ArrayList."<init>":()V
    7: astore_1
    8: aload_1
    9: invokeinterface #19, 1      // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
   14: astore_3
   15: goto     28
   18: aload_3
   19: invokeinterface #25, 1      // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   24: checkcast   #31         // class loop/Model
   27: astore_2
   28: aload_3
   29: invokeinterface #33, 1      // InterfaceMethod java/util/Iterator.hasNext:()Z
   34: ifne     18
   37: 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。
}

【相关推荐】

1. Java免费视频教程

2. 极客学院Hava视频教程

3. JAVA教程手册

The above is the detailed content of Detailed explanation of various common traversal methods in Java. For more information, please follow other related articles on the PHP Chinese website!