Javaコレクショントラバーサル手法の分析（実装原理、アルゴリズム性能、適用場面）_javascriptスキル

概要

Java 言語は、List や Set などのいくつかの抽象データ型を定義する一連のデータ収集フレームワークを提供します。各抽象データ型には特定の実装があり、最下層では ArrayList や LinkedList などのさまざまな実装メソッドが採用されます。

さらに、Java はデータ コレクションを横断するためのいくつかの異なる方法も提供します。開発者は、さまざまな基礎となる実装における各トラバーサル メソッドの特性、適用可能な状況、パフォーマンスを明確に理解する必要があります。以下でこの内容を詳しく分析してみましょう。

データ要素はどのようにメモリに格納されますか?

データ要素はメモリに保存されます。主な保存方法は 2 つあります。

1. シーケンシャルストレージ、ランダムアクセス (直接アクセス):

このように、隣接するデータ要素は隣接するメモリアドレスに格納され、メモリアドレス全体が連続します。メモリアドレスは要素の位置に基づいて直接計算され、直接読み取ることができます。特定の位置にある要素を読み取る平均時間計算量は O(1) です。通常、この機能は配列に基づいて実装されたコレクションのみにあります。 JavaはArrayListで表現されます。

2. チェーンストレージ、シーケンシャルアクセス:

このように、各データ要素はメモリ内の隣接する位置にある必要はありません。各データ要素には次の要素のメモリ アドレスが含まれます。メモリ アドレスは要素の位置に基づいて直接計算することはできず、要素は順番に読み取ることしかできません。特定の位置にある要素を読み取る平均時間計算量は O(n) です。主にリンクリストで表されます。

Java では LinkedList で表されます。

Java で提供されるトラバーサル メソッドとは何ですか?

1. カウンタに基づく従来の for ループ走査:

トラバーサーはコレクションの外側にカウンターを保持し、各位置の要素を順番に読み取り、最後の要素が読み取られた時点で停止します。主なことは、要素をその位置に従って読み取ることです。これは、最も原始的なコレクション走査方法でもあります。

は次のように書かれます:

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

2. イテレータのトラバース、イテレータ:

イテレータはもともと OO の設計パターンであり、その主な目的は、さまざまなデータ コレクションの特性を保護し、コレクションを横断するためのインターフェイスを統一することです。オブジェクト指向言語として、Java はコレクションのイテレータ モードを自然にサポートします。

は次のように書かれます:

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

3. foreach ループの走査:

明示的に宣言されたイテレータとカウンタをシールドします。

利点: コードは簡潔で、エラーが発生しにくくなります。

欠点: 単純な走査のみを実行でき、走査プロセス中にデータ収集を操作 (削除、置換) することはできません。

は次のように書かれます:

for (ElementType element : list) {
}

各トラバーサルメソッドの実装原理は何ですか?

1. カウンタに基づく従来の for ループ走査:

トラバーサーはコレクションの外側にカウンターを保持し、各位置の要素を順番に読み取り、最後の要素が読み取られた時点で停止します。主なことは、要素をその位置に従って読み取ることです。

2. イテレータのトラバース、イテレータ:

特別に実装された各データ コレクションは通常、対応するイテレータを提供する必要があります。従来の for ループと比較して、Iterator では明示的なトラバーサル カウンタが不要になります。したがって、順次格納されたコレクションに基づくイテレーターは、位置によってデータに直接アクセスできます。チェーンされたストレージ コレクションに基づく Iterator の通常の実装では、現在のトラバース位置を保存する必要があります。次に、現在の位置に基づいてポインタを前後に移動します。

3. foreach ループの走査:

逆コンパイルされたバイトコードによると、foreach も Iterator を使用して内部で実装されていることがわかりますが、Java コンパイラーがこれらのコードを生成します。

さまざまなストレージ方式に対する各トラバーサル方式のパフォーマンスはどのようなものですか?

1. カウンタに基づく従来の for ループ走査:

要素の位置に基づいているため、位置によって読み取られます。したがって、シーケンシャル ストレージの場合、特定の位置にある要素の読み取りの平均時間計算量は O(1) であるため、コレクション全体を走査する平均時間計算量は O(n) であることがわかります。連鎖ストレージの場合、特定の場所にある要素の読み取りの平均時間計算量は O(n) であるため、コレクション全体を走査する平均時間計算量は O(n2) (n の 2 乗) です。

位置によって 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遍历集合方法分析（实现原理、算法性能、适用场合），希望对大家有所帮助！