
コレクション
84. イテレータとその使用方法について教えてください
コレクションは、Java 開発者のインタビューでよく取り上げられるトピックです。コレクション階層に関する質問に答えるとき、候補者は多くの場合、コレクションインターフェイスから始まると答えます。しかし、そうではありません。1 レベル上には別のインターフェイスIterableがあります。このインターフェイスはiterator()メソッドで構成されており、これを使用して現在のコレクションのIteratorオブジェクトにアクセスできます。では、このIteratorオブジェクトとは一体何なのでしょうか? Iteratorオブジェクトは、コレクション内を移動し、その要素を反復処理する機能を提供します。ユーザーは、コレクションの特定の実装の詳細を知る必要はありません。言い換えれば、これはコレクションの要素への一種のポインタであり、あたかもコレクションの要素の 1 つを覗いているかのようです。イテレータには次のようなメソッドがあります。-
hasNext() —反復に別の要素がある場合はtrueを返します(このメソッドにより、コレクションの最後に到達したことがわかります)。
-
next() — 反復内の次の項目を返します。存在しない場合は、NoSuchElementExceptionがスローされます。つまり、このメソッドを使用する前に、hasNext()メソッドを使用して次の要素が存在することを確認するのが最善です。
-
Remove() — next()メソッドを使用して受け取った最後の要素をコレクションから削除します。next() が一度も呼び出されなかった場合、 remove()を呼び出すとIllegalStateExceptionがスローされます。
-
forEachRemaining(<Consumer>) — コレクションの各要素に対して渡されたアクションを実行します (このメソッドは Java 8 で登場しました)。
List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
iterator.next();
iterator.remove();
}
System.out.println(list.size());
コンソールには次の内容が表示されます。
iterator.forEachRemaining(x -> System.out.print(x));
しかし、一度これを行うと、反復子はそれ以降の使用には適さなくなります。反復子はリスト全体を走査しており、通常の反復子には逆方向に反復するメソッドがありません。これは、LinkedList 、具体的には、拡張型イテレーターListIteratorを返すそのlistIterator()メソッドの説明への素晴らしい続きとなります。通常の (標準) イテレータのメソッドに加えて、この種類には次のメソッドがあります。
-
add(<Element>) — 新しい要素をリストに追加します。
-
hasPrevious() —次の要素の前に要素がある場合 (前の要素がある場合)、trueを返します。
-
nextIndex() — 次の要素のインデックスを返します。
-
previous() — 前の要素 (次の要素の前の要素) を返します。
-
previousIndex は、前の要素のインデックスを返します。
-
set(<Element>) — next()またはprevious()によって返された最後の要素を置き換えます。

85. Java Collection Frameworkにはどのようなコレクション階層が存在しますか?
Java には 2 つのコレクション階層があります。 最初の階層はコレクション階層であり、次の構造を持っています。
-
Setは、順序付けされていない一意の (反復しない) 要素を含むデータ構造であるセットを記述するインターフェイスです。このインターフェイスには、 TreeSet、HashSet、LinkedHashSet などの標準実装がいくつかあります。
-
List は、順序付けられたオブジェクトのシーケンスを格納するデータ構造を記述するインターフェイスです。リスト内のオブジェクトは、リスト内のインデックスによって挿入および削除できます (配列と同様ですが、動的なサイズ変更が可能です)。このインターフェイスには、ArrayList、Vector (非推奨で実際には使用されていない)、およびLinkedList などの標準実装もあります。
-
Queue は、FIFO (First In First Out)キューに項目を格納するデータ構造を記述するインターフェイスです。このインターフェイスには、 LinkedList (そうです、Queueも実装されています) とPriotityQueue という標準実装があります。


86. ArrayList の内部構造は何ですか?
ArrayList は配列に似ていますが、動的に拡張できます。それはどういう意味ですか?内部では、ArrayList は通常の配列を使用します。つまり、デフォルト サイズが 10 セルである内部配列に要素を格納します。内部配列がいっぱいになると、新しい配列が作成されます。新しい配列のサイズは次の式で決定されます。<size of the current array> * 3 / 2 + 1
したがって、配列のサイズが 10 の場合、新しい配列のサイズは 10 * 3 / 2 + 1 = 16 になります。その後、元の (古い) 配列のすべての値が、組み込み関数を使用してその配列にコピーされます。System.arraycopy()メソッドを実行すると、元の配列が削除されます。一言で言えば、これがArrayList が動的サイズ変更を実装する方法です。最も一般的なArrayListメソッドを考えてみましょう。 1. add(<Element>) — 最初に配列内に使用可能なセルがあるかどうかを確認した後、配列の末尾 (最後の空のセル) に要素を追加します。そうでない場合は、新しい配列が作成され、要素がそこにコピーされます。この操作の時間計算量は O(1) です。同様のadd(<Index>, <Element>)メソッドがあります。要素をリスト (配列) の末尾ではなく、引数として渡されたインデックスによって示される特定のセルに追加します。この場合、時間の計算量は以下を追加する場所によって異なります。
- 追加がリストの先頭に近い場合、新しい要素の右側にあるすべての要素を 1 セル右に移動する必要があるため、時間計算量は O(N) に近くなります。
- 要素が中央に挿入された場合、リスト項目の半分を 1 セル右にシフトするだけでよいため、O(N/2) になります。
87. LinkedList の内部構造は何ですか?
ArrayListには内部配列内の要素が含まれますが、LinkedList には要素が二重リンク リストに格納されます。これは、各要素に前の要素と次の要素へのリンクが含まれていることを意味します。最初の要素は前の要素にリンクしません (結局のところ、それが最初です)。これはリストの先頭とも見なされ、LinkedListオブジェクトはそれへの直接参照を持ちます。同様に、最後の要素はリストの末尾であるため、次の要素を持ちません。LinkedListオブジェクトもそれを直接参照します。これは、リストの先頭または末尾にアクセスする時間計算量が O(1) であることを意味します。 ArrayListでは、リストが大きくなると内部配列も大きくなります。ここではすべてが簡単です。参照の追加は、いくつかのリンクを変更するのと同じくらい簡単です。最もよく使用されるLinkedListメソッドのいくつかを見てみましょう。 1. add(<Element>) — 要素をリストの最後に追加します。つまり、最後の要素 (5) の後に、新しい要素へのリンクが次のように追加されます。 。新しい要素内の以前の参照は、リスト内でその前にある要素 (5) を指します。この操作の時間計算量は O(1) です。これは、最後の要素へのリンクのみが必要であるためです。また、覚えているとおり、LinkedList オブジェクトには末尾への直接参照があり、それにアクセスする際の一定の時間計算量は最小限で済みます。2. add(<Index>, <Element>) — インデックスによって要素を追加します。たとえばリストの途中に要素を追加する場合、このメソッドはまず、目的の場所が見つかるまで要素を先頭と末尾から (両方向に) 繰り返します。(上の図の) 3 番目と 4 番目の要素の間に要素を追加すると、 3 番目の要素の次のリンクが新しい要素を指すようになります。そして、新しく追加された要素の前の要素は 3 番目の要素を指します。次に、古い 4 番目の要素の前のリンクは新しい要素を指し、新しい要素の次のリンクは新しい 4 番目の要素を指すようになります。 このメソッドの時間計算量は、新しい要素のインデックスによって異なります。

- それが先頭または末尾に近い場合、実際には要素を反復処理する必要がないため、操作は O(1) に近づきます。
- 中央に近い場合、メソッドは目的の要素が見つかるまで先頭と末尾から同時に検索するため、O(N/2) になります。

88. HashMap の内部構造は何ですか?
これは、Java 開発者候補者に対する面接で最もよく聞かれる質問の 1 つかもしれません。HashMapはキーと値のペアで機能します。それらはHashMap自体の内部にどのように保存されますか? HashMapにはノードの内部配列があります。Node<K,V>[] table
デフォルトでは、配列のサイズは 16 で、配列が要素で満たされるたびに 2 倍になります (つまり、 LOAD_FACTOR に達すると、配列がどの程度満たされるかについてのしきい値が指定されます。デフォルトでは0.75です)。 。各ノードには、キーのハッシュ、キー、値、および次の要素への参照が格納されます。 
- セルは空です。この場合、新しいNode値がセルに格納されます。
- セルは空ではありません。この場合、キーの値が比較されます。それらが等しい場合、新しいNode値が古い Node 値を上書きします。等しくない場合は、次の値がアクセスされ、そのキーが比較されます...というように、新しい値が古い値を上書きするか、単一リンクされたリストの最後に到達してそこに新しい値を保存するまで繰り返されます。最後の要素。

GO TO FULL VERSION