Java開発者へのインタビューからの質問と回答の分析。パート9

花火！プログラマーになるのは簡単ではありません。常に学ぶ必要があり、常に何か新しいことを学ぶ必要があります。しかし、他のビジネスと同様に、最も難しいのは始めること、つまり目標に向かって最初の一歩を踏み出すことです。そして、あなたはこのサイトに座ってこの記事を読んでいるということは、最初のステップを完了したことになります。これは、速度を落としたり、途中で道を逸したりせずに、目的に向かって意図的に進む必要があることを意味します。私の理解が正しければ、あなたの目標は Java 開発者になるか、Java 開発者であれば知識を高めることです。もしそうなら、あなたは正しい場所にいます。私たちは 250 以上の Java 開発者インタビューの質問の広範なリストを分析し続けるからです。 続けましょう！

コレクション

84. イテレータとその使用法について教えてください

コレクションは Java 開発者インタビューで人気のトピックの 1 つであり、コレクション階層について話すとき、候補者はコレクションインターフェイスから始まるとよく言います。しかし、これは真実ではありません。このインターフェイスの上には別のインターフェイスであるIterableがあるからです。このインターフェイスはiterator()メソッドを表し、現在のコレクションのIteratorオブジェクトを呼び出すことができます。では、このIteratorオブジェクトとは一体何なのでしょうか? Iterator は、ユーザーが特定のコレクションの実装を知らなくても、コレクション内を移動して要素を反復処理できる機能を提供するオブジェクトです。つまり、これはコレクションの要素への一種のポインタであり、いわばコレクション内の特定の場所を参照します。イテレータには次のメソッドがあります。

• hasNext() -ポインターの後に要素がある場合はtrueを返します(このメソッドを使用すると、コレクションの終わりに到達したかどうかを確認できます)。
• next() - ポインターの次の要素を返します。何もない場合は、NoSuchElementExceptionがスローされます。つまり、このメソッドを使用する前に、hasNext()を使用して要素が存在することを確認することをお勧めします。
• Remove() - next()メソッドを使用して、コレクションから受け取った最後の要素を削除します。Remove () が呼び出される前にnext() が一度も呼び出されなかった場合、例外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()メソッドによって返された最後の要素を置き換えます。

ご覧のとおり、このイテレータの機能はさらに興味深いものです。これにより、要素を操作するときに両方向に移動でき、手を解放できます。また、人々がイテレータについて話すとき、それはパターンそのものを意味することがあります。トラブルに巻き込まれることを避け、説得力を持って説明するには、Iterator パターンに関するこの記事をお読みください。

85. Java Collection Frameworkのコレクション階層とは何ですか?

Java には 2 つのコレクション階層があります。 最初の階層は、次の構造を持つ コレクション階層そのものです。さらに、次のサブコレクションに分割されます。

• Set は、そのようなデータ構造を、順序付けされていない一意の (反復しない) 要素を含むセットとして記述するインターフェイスです。インターフェイスには標準実装 - TreeSet、HashSet、およびLinkedHashSetがあります。
• List は、順序付けられたオブジェクトのシーケンスを格納するデータ構造を記述するインターフェイスです。Listに含まれるインスタンスは、このコレクション内のインデックスによって挿入および削除できます (配列に似ていますが、動的なサイズ変更が可能です)。このインターフェイスには、ArrayList、Vector (廃止され、実際には使用されていない)、およびLinkedList という標準実装があります。
• Queueは、 FIFO 先入れ先出しルールに従うキューの形式で要素を格納するデータ構造を記述するインターフェイスです。このインターフェイスには、LinkedList (はい、 Queueも実装します) とPriotityQueueの標準実装があります。

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

86. ArrayList の内部構造は何ですか?

ArrayListは配列に似ていますが、動的に拡張する機能を備えています。それはどういう意味ですか？実際、ArrayList は通常の配列に基づいて動作します。つまり、要素を内部配列 (デフォルトのサイズは 10 セル) に格納します。内部配列がいっぱいになると、新しい配列が作成され、そのサイズは次の式で決定されます。

<размерТекущегоМассива> * 3 / 2  + 1

つまり、配列のサイズが 10 の場合、新しい配列のサイズは 10 * 3 / 2 + 1 = 16 になります。 次に、最初の (古い) 配列のすべての値が、ネイティブの System.arraycopy ()メソッドを実行すると、最初の配列が削除されます。実際には、これがArrayList の動的な拡張性を実装する方法です。最もよく使用されるArrayListメソッドを見てみましょう。 1. add(<Element>) - 要素を配列の末尾 (最後の空のセル) に追加し、最初にこの配列にスペースがあるかどうかを確認します。存在しない場合は、要素がコピーされる新しい配列が作成されます。この演算の対数計算量は O(1) です。同様のメソッドadd(<Index>,<Element>)があります。要素をリスト (配列) の末尾ではなく、引数として指定されたインデックスを持つ特定のセルに追加します。この場合、対数複雑度は追加される場所に応じて異なります。

• これがリストのほぼ先頭の場合、新しい要素の右側にあるすべての要素を 1 セル右に移動する必要があるため、対数複雑度は O(N) に近くなります。
• 要素が中央に挿入された場合 - O(N/2) リスト要素の半分だけを 1 セル右に移動する必要があります。

つまり、このメソッドの対数計算量は、要素が挿入される場所に応じて O(N) から O(1) の範囲になります。2. set(<Index>,<Element>) - リスト内の指定された位置に要素を書き込みます。その位置に要素がすでに存在する場合は、それを上書きします。この操作の対数複雑さは O(1) です。シフトがないためです。覚えているとおり、複雑さは O(1) である配列内のインデックスによる検索と、要素の書き込みだけです。3.remove (<index>) - 内部配列内のインデックスによって要素を削除します。リストの最後にない項目を削除する場合は、その右側にあるすべての項目を 1 セル分左に移動して、項目を削除した後に残った隙間を埋める必要があります。したがって、要素が中央にある場合、対数複雑度はadd(<Index>,<Element>)と同じになります- O(N/2) - 要素の半分を 1 つ左にシフトする必要があるためです。したがって、最初であれば - O(N)。まあ、最終的に O(1) であれば、何も移動する必要はありません。このトピックをさらに詳しく知りたい方のために、 ArrayListクラスの分析を含む記事へのリンクを残しておきます。

87. LinkedListの内部構造は何ですか?

ArrayListに内部配列の要素が含まれている場合、 LinkedList は二重リンク リストの形式になります。これは、各要素に前の要素 ( Previous ) と次の要素 ( Next ) へのリンクが含まれていることを意味します。最初の要素には前の要素 (最初の要素) へのリンクがありませんが、リストの先頭とみなされ、LinkedList にはその要素への直接リンクがあります。実際、最後の要素には次の要素がなく、リストの末尾であるため、LinkedList自体にその要素への直接リンクがあります。したがって、リストの先頭または末尾にアクセスする場合の対数計算量は O(1) です。 ArrayListでは、リストが大きくなると内部配列も増加しますが、ここではすべてがより単純に行われます。要素を追加すると、いくつかのリンクが変更されるだけです。最もよく使用されるLinkedlListメソッドのいくつかを見てみましょう。 1. add(<Element>) - リストの最後に追加します。最後の要素 (5) の後に、新しい要素へのリンクがnextとして追加されます。新しい要素には、前の要素と同様に最後の (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>) ) と逆のプロセスになります。LinkedList の内部構造について詳しく知りたい方は、この記事を読むことをお勧めします。

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

おそらく、Java 開発者にインタビューするときに最もよく聞かれる質問の 1 つです。 HashMap v はキーと値のペアで動作します。それらはHashMapv自体の内部にどのように保存されますか? HashMap内にはノードの配列があります。

Node<K,V>[] table

デフォルトでは、配列のサイズは 16 で、要素が詰め込まれるたびに 2 倍になります ( LOAD_FACTORに達すると、一定の割合の満杯になり、デフォルトでは0.75になります)。各ノードには、キーのハッシュ、キー、値、および次の要素へのリンクが格納されます。 実際、「次の要素へのリンク」とは、各要素にリンクが含まれる単一リンクのリストを扱っていることを意味します。次のもの。つまり、HashMap は、単一リンクされたリストの配列にデータを格納します。ただし、すぐに注意します。テーブル配列の 1 つのセルに、複数の要素で構成される同様の単一リンク リストへのリンクがある場合、これは良くありません。この現象を衝突といいます。しかし、まず最初に。putメソッドを使用して新しいペアがどのように保存されるかを見てみましょう。まず、キーのhach​​Code() が取得されます。したがって、ハッシュマップが正しく機能するには、このメソッドがキーとしてオーバーライドされるクラスを取得する必要があります。このハッシュ コードは内部メソッドhash()で使用され、テーブル配列のサイズ内の数値を決定します。次に、受け取った番号を使用して、テーブル配列の特定のセルにアクセスします。ここでは 2 つのケースがあります。

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

キーによって要素を検索する場合 ( get(<key>)メソッド)、キーのhashCode が計算され、次にhash()を使用して配列内の値が計算され、結果の数値を使用してテーブル配列のセルが検索されます。この場合、検索はノードを列挙し、目的のノードのキーと現在のノードのキーを比較することによってすでに実行されています。理想的な状況では、Mapでの操作のアルゴリズムの複雑さは O(1) です。これは、操作が配列にアクセスするためであり、ご存知のとおり、要素の数に関係なく、配列に対する操作の複雑さは O(1) です。 。しかし、これは理想的です。使用されている配列セルが空ではなく (2)、そこにすでにいくつかのノードがある場合、適切な場所を見つける前に要素を反復処理する必要があるため、アルゴリズムの複雑さは線形 O(N) になります。これについては触れずにはいられません。Java 8 以降、単一リンクされたリスト ノードに 8 つを超える要素 (衝突) がある場合、バイナリ ツリーに変わります。この場合、アルゴリズムの複雑さは O(N) ではなく、O(log(N)) になります。それは別の問題ですよね。 HashMapは大きなトピックであり、人々はインタビューで HashMap について質問することを好みます。したがって、それを詳しく理解することをお勧めします（歯に跳ね返されるように）。個人的には、 HashMap の質問なしで面接を受けたことはありません。HashMapについては、この記事で詳しく説明しています。今日はここまで、続きは…