Java 컬렉션 순회 방법 분석(구현 원리, 알고리즘 성능, 적용 사례)_javascript 기술

개요

Java 언어는 List 및 Set과 같은 일부 추상 데이터 유형을 정의하는 일련의 데이터 수집 프레임워크를 제공합니다. 각 추상 데이터 유형에는 특정 구현이 있으며 하위 계층에서는 ArrayList 및 LinkedList와 같은 다양한 구현 방법을 채택합니다.

또한 Java는 데이터 컬렉션을 탐색하는 여러 가지 방법을 제공합니다. 개발자는 다양한 기본 구현에서 각 순회 방법의 특성, 적용 가능한 상황 및 성능을 명확하게 이해해야 합니다. 아래에서 이 내용을 자세히 분석해 보겠습니다.

데이터 요소는 메모리에 어떻게 저장되나요?

데이터 요소는 메모리에 저장되며 두 가지 주요 저장 방법이 있습니다.

1. 순차저장, 랜덤액세스(직접접속):

이런 방식으로 인접한 데이터 요소는 인접한 메모리 주소에 저장되며 전체 메모리 주소는 연속적입니다. 메모리 주소는 요소의 위치를 ​​기반으로 직접 계산하여 직접 읽을 수 있습니다. 특정 위치에서 요소를 읽는 평균 시간 복잡도는 O(1)입니다. 일반적으로 배열을 기반으로 구현된 컬렉션에만 이 기능이 있습니다. Java는 ArrayList로 표현됩니다.

2. 체인 스토리지, 순차 접근:

이런 방식으로 각 데이터 요소는 메모리에서 인접한 위치에 있을 필요가 없습니다. 각 데이터 요소에는 다음 요소의 메모리 주소가 포함됩니다. 메모리 주소는 요소의 위치를 ​​기반으로 직접 계산할 수 없으며 요소는 순서대로만 읽을 수 있습니다. 특정 위치의 요소를 읽는 평균 시간 복잡도는 O(n)입니다. 주로 연결리스트(Linked List)로 표현됩니다.

Java에서는 LinkedList로 표현됩니다.

Java에서 제공하는 순회 메소드는 무엇인가요?

1. 카운터 기반의 전통적인 for 루프 탐색:

순회자는 컬렉션 외부에 카운터를 유지한 다음 각 위치의 요소를 순서대로 읽고 마지막 요소를 읽으면 중지됩니다. 가장 중요한 것은 위치에 따라 요소를 읽는 것입니다. 이는 가장 원시적인 컬렉션 순회 방법이기도 합니다.

은 다음과 같이 작성됩니다.

for (int i = 0; i < list.size(); i++) {
list.get(i);
} 

2. 반복자 순회, 반복자:

Iterator는 원래 OO의 디자인 패턴입니다. 주요 목적은 다양한 데이터 컬렉션의 특성을 보호하고 컬렉션 탐색을 위한 인터페이스를 통합하는 것입니다. OO 언어로서 Java는 자연스럽게 컬렉션에서 반복자 모드를 지원합니다.

은 다음과 같이 작성됩니다.

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

3. foreach 루프 순회:

Shield는 반복자와 카운터를 명시적으로 선언했습니다.

장점: 코드가 간결하고 오류가 발생할 가능성이 적습니다.

단점: 단순 순회만 수행할 수 있으며 순회 과정 중 데이터 수집 작업(삭제, 교체)을 수행할 수 없습니다.

은 다음과 같이 작성됩니다.

for (ElementType element : list) {
}

각 순회 방식의 구현 원리는 무엇인가요?

1. 카운터 기반의 전통적인 for 루프 탐색:

순회자는 컬렉션 외부에 카운터를 유지한 다음 각 위치의 요소를 순서대로 읽고 마지막 요소를 읽으면 중지됩니다. 가장 중요한 것은 위치에 따라 요소를 읽는 것입니다.

2. 반복자 순회, 반복자:

특별히 구현된 각 데이터 컬렉션은 일반적으로 해당 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遍历集合方法分析（实现原理、算法性能、适用场合），希望对大家有所帮助！