Java 開発者の職の面接での質問と回答を調査します。パート9

プログラマーになるのは簡単ではありません。常に何か新しいことを学ぶことができます。そして、他のあらゆる努力と同様に、最も難しいのは始めること、つまり目標に向かって最初の一歩を踏み出すことです。しかし、あなたはすでにここに来てこの記事を読んでいるので、最初のステップは完了したことになります。これは、速度を落としたり横にそれたりせずに、意図的に目標に向かって進む必要があることを意味します。あなたの目標は、Java 開発者になること、またはすでに開発者である場合は知識を強化することだと思います。もしそうなら、引き続き Java 開発者インタビューの質問の広範なリストに取り組んでみましょう。 続けましょう！

コレクション

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 という標準実装があります。

2 番目のコレクション階層はマップ階層であり、次の構造を持ちます。 このコレクション階層にはサブコレクションへの分割がありません (マップ階層自体が独立したサブコレクションのようなものであるため)。標準のMap実装は、 Hashtable (非推奨)、LinkedHashMap、およびTreeMapです。実際には、人々がCollectionsについて尋ねるとき、それは通常両方の階層を意味します。

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) になります。

つまり、このメソッドの時間計算量は、要素が挿入される場所に応じて O(1) から O(N) までの範囲になります。2. set(<Index>, <Element>) — リスト内の指定された位置に要素を書き込みます。要素がその位置にすでに存在する場合、メソッドはそれを上書きします。この演算の時間計算量は O(1) です。シフト演算が含まれていないためです。インデックスを使用して、計算量 O(1) の配列内のセルのアドレスを計算し、新しい要素を書き込みます。 。3.remove (<index>) — 内部配列内のインデックスに基づいて要素を削除します。リストの最後にない項目を削除する場合、削除によって生じるギャップを埋めるために、削除された項目の右側にあるすべての項目を 1 セル左に移動する必要があります。したがって、要素を途中で追加する場合の時間計算量はadd(<Index>, <Element>)と同じ O(N/2) になります。結局、要素の半分を 1 セル左にシフトする必要があります。そして始まりについて話すなら、O(N)。または、最後であれば、何も移動する必要がないため、O(1) になります。

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) になります。

3. set(<Index>, <Element>) — リスト内の指定された位置に要素を書き込みます。この操作の時間計算量は O(1) から O(N/2) の範囲で、これも新しい要素が先頭、末尾、または中央にどれだけ近いかによって決まります。4.remove (<index>) — 削除された要素の前の要素 ( Previous ) が削除された要素の後の要素 ( next ) を参照するようにすることで、リストから要素を削除します。逆も同様です。つまり、削除された要素の後の要素が、削除された要素の前の要素を参照するようになります。 このプロセスは、インデックスによる追加 ( add(<Index>, <Element>) )の逆です。

88. HashMap の内部構造は何ですか?

これは、Java 開発者候補者に対する面接で最もよく聞かれる質問の 1 つかもしれません。HashMapはキーと値のペアで機能します。それらはHashMap自体の内部にどのように保存されますか? HashMapにはノードの内部配列があります。

Node<K,V>[] table

デフォルトでは、配列のサイズは 16 で、配列が要素で満たされるたびに 2 倍になります (つまり、 LOAD_FACTOR に達すると、配列がどの程度満たされるかについてのしきい値が指定されます。デフォルトでは0.75です)。 。各ノードには、キーのハッシュ、キー、値、および次の要素への参照が格納されます。 この場合、「次の要素への参照」とは、単一リンクのリストを扱っていることを意味します。ここで、各要素には次の要素へのリンクが含まれています。言い換えれば、HashMapはそのデータを単一リンクされたリストの配列に格納します。しかし、すぐに言っておきますが、テーブル配列のセルに複数の要素で構成される単一リンクのリストがある場合、それは良くありません。この現象を衝突といいます。しかし、まず最初に。putメソッドを使用して新しいペアがどのように保存されるかを見てみましょう。まず、メソッドはキーのhashCode()を取得します。これは、 HashMapが正しく動作するには、使用するキーがこのメソッドをオーバーライドするクラスである必要があることを意味します。このハッシュ コードは内部hash()メソッドで使用され、テーブル配列内のセルのインデックスを決定します。結果として得られるインデックスにより、テーブル配列の特定のセルにアクセスできるようになります。ここには 2 つのケースがあります。

1. セルは空です。この場合、新しいNode値がセルに格納されます。
2. セルは空ではありません。この場合、キーの値が比較されます。それらが等しい場合、新しいNode値が古い Node 値を上書きします。等しくない場合は、次の値がアクセスされ、そのキーが比較されます...というように、新しい値が古い値を上書きするか、単一リンクされたリストの最後に到達してそこに新しい値を保存するまで繰り返されます。最後の要素。

キーによって要素を検索する場合 ( get(<key>)メソッドを使用)、キーのhashCode()が計算され、配列内のそのインデックスがhash()を使用して計算されます。結果の数値はテーブル配列内のセルのインデックスです。ノードを反復処理し、目的のノードのキーと現在のノードのキーを比較することで検索します。理想的には、Map操作のアルゴリズムの複雑さは O(1) です。配列にアクセスしているため、配列に含まれる要素の数に関係なく、覚えているとおり、アルゴリズムの複雑さは O(1) です。しかし、私たちは理想的なケースを扱っているわけではありません。セルが空ではなく (2)、すでにいくつかのノードを格納している場合、正しい場所を見つける前に要素を反復処理する必要があるため、アルゴリズムの複雑さは O(N) (線形) になります。Java 8 以降、単一リンクリストの形式のノードに 8 つを超える要素 (衝突) がある場合、バイナリ ツリーに変換されることに触れずにはいられません。この場合、アルゴリズムの複雑さはもはや O(N) ではなく、O(log(N)) になります。それはまったく別の問題ですよね。 HashMapは大きなトピックであり、人々は就職面接で HashMap についての質問をするのが好きです。したがって、それを手の甲のように知っておくことをお勧めします。私個人としては、 HashMapに関する質問が含まれない面接を受けたことがありません。それが今日のすべてです。つづく...