面接で尋ねられる可能性のあること: Java のデータ構造。パート2

パート 1 ここでは、すべての Java 開発者が知っておくべき基本について説明します。すべてが始まる古典的な知識について。今日は、 Java のインタビュー データ構造の基本的なトピックの 1 つについて触れたいと思います。ですから、無駄なことをするのではなく、始めてみましょう。面接中にこのトピックに関して尋ねられる可能性のある質問リストの続きをご覧ください。

6. リストについて教えてください

List は、リストと呼ばれるオブジェクトの順序付けされた構造を表すインターフェイスです。この構造の「トリック」は、 Listに含まれる要素がインデックス、つまりListの内部識別子によって挿入、変更、または削除できることです。つまり、インデックスとは「リストの先頭から何番目の要素なのか」を意味します。最初のList要素のインデックスは 0、2 番目の要素のインデックスは 1 などとなります。したがって、5 番目の要素はリストの先頭から 4 要素離れています。上で述べたように、項目をリストに追加する順序は重要です。このため、データ構造はリストと呼ばれます。インデックスによる要素の操作を目的とした、この構造に固有のメソッドをリストします。

• get - 指定された位置にある要素を（インデックス値によって）返します。
• 削除- 指定された位置にある要素を削除します。
• set - 指定された位置の要素をメソッドで指定された要素に置き換えます。

主な実装はArrayListとLinkedListです。それらについては後ほど詳しく説明します。 Vectorはスレッドセーフなリストであるため、このクラスの各メソッドは同期されます。ただし、一部のリスト アクションを保護したい場合は、一連の操作全体を同期することになることに注意してください。また、個々の操作を同期すると、安全性が低くなり、速度も大幅に低下します。もちろん、ロックが必要ない場合でも、Vectorにはロックのオーバーヘッドもあります。したがって、このクラスは現在廃止されているとみなされ、使用されません。ちなみに、ArrayList はVectorに似ていますが、ロックを使用しないため、あらゆる場所で使用されます。 Stack は、1 つのデフォルト コンストラクターとVectorクラスのすべてのメソッドに加えて、独自のメソッドをいくつか備えたVectorクラスのサブクラスです(これらについては後で説明します)。例として、プロセスをドキュメントを含むフォルダーのスタックとして想像できます。スタックの最上位に 1 つのフォルダーを配置します。これらのフォルダーは、上から順に逆の順序でのみ取得できます。実際には、これはLIFOタイプのメカニズムです。つまり、後入れ先出し、最後に来たものが最初に去るという仕組みです。スタックは独自のメソッドを実装します。

• Push - 渡された要素をスタックの先頭に追加します。
• Peak - スタックの最上位にある要素を返します。
• Pop - スタックの最上位にある要素も返しますが、それを削除します。
• empty - スタックが空かどうかをチェックします - trueかそうでないか - false。
• search - スタック内で指定された要素を検索します。要素が見つかった場合は、スタックの先頭からの相対的なシーケンス番号が返されます。要素が見つからない場合は、値 -1 が返されます。

現時点では、Stackサブクラスはその単純さと柔軟性に欠けるため実際には使用されていませんが、それでも使用される可能性があります。たとえば、何らかのエラーが発生し、コンソールにそれに関する大量のメッセージが表示されるとします。スタックとキューの詳細については、この記事を参照してください。

7. 地図について教えてください

上で述べたように、マップはインターフェイスとその実装の別個の構造を持つコレクションです。ここでは値が一度に 1 つずつ保存されるのではなく、「キーと値」のペアで保存されるため、これは分離されています。基本的なマップのメソッド:

• put(K key, V value) - マップに要素を追加します。
• get(Object key) - キーによって値を検索します。
• containsKey(Object key) — マップにこのキーが存在するかどうかを確認します。
• containsValue(Object value) - マップにこの値が存在するかどうかを確認します。
• Remove(Object key) - キーによって値を削除します。

ご覧のとおり、ほとんどの操作はキーを使用して行われます。原則として、不変オブジェクトがキーとして選択されます。このオブジェクトの典型的な例はStringです。基本的なマップの実装:

1. HashMap - 値をランダムな順序で保存するように設計されていますが、マップ要素をすばやく検索できます。nullキーワードを使用してキーを指定できますが、指定できるのは 1 回だけです。同じキーを持つペアは互いに重ねて書き込まれます。主な条件はキーの一意性です。値は繰り返すことができます (複数の null 値が存在する可能性があります)。
2. LinkedHashMap は、追加された順序で値を保存するHashMap の類似物です。したがって、LinkedListと同様に、ヘッダー(二重リンクリストの先頭)があります。初期化すると、それ自体を指します。

   LinkedHashMap には、イテレータの使用時に要素にアクセスする方法を指定するaccessOrderもあります。accessOrder がfalseの場合、要素が挿入された順序でアクセスが実行されます。trueの場合、要素は最後にアクセスされた順序になります (最後にアクセスされた要素が最後に配置されます)。

3. TreeMap は、要素をキー値で並べ替えるMapです。TreeSetに似ていますが、キー値に基づくペア用です。TreeMap の並べ替えルールを設定するには、キーにComparableインターフェイスを実装する必要があります。それ以外の場合は、キー指向のコンパレーター( TreeMapコンストラクターで指定されているもの)、TreeSet (内部に TreeMap オブジェクトを実装して)が存在する必要があります。実際、そこですべての魔法が行われます。

   赤黒ツリーを使用した TreeMap での並べ替えの詳細については、TreeMap の機能に関する記事を参照してください。

4. Hashtable はHashMapに似ていますが、null をキーまたは値として格納することはできません。マルチスレッドの観点から注意深く同期されているため、マルチスレッドの観点からは安全であることがわかります。しかし、この実装は時代遅れで遅いため、現在では多かれ少なかれ新しいプロジェクトでHashtable が使用されることはありません。

8. ArrayList と LinkedList の比較。どちらを使用するのが望ましいでしょうか?

この質問はおそらくデータ構造に関して最も人気のある質問ですが、いくつかの落とし穴が伴います。それに答える前に、これらのデータ構造について詳しく学びましょう。 ArrayList はListインターフェイスを実装し、必要に応じて展開される内部配列を操作します。内部配列が完全に埋まり、新しい要素を挿入する必要がある場合、(oldSize * 1.5) +1 のサイズで新しい配列が作成されます。この後、古い配列のすべてのデータが新しい + 新しい要素にコピーされ、古い配列はガベージ コレクターによって削除されます。addメソッドは、配列の最後の空のセルに要素を追加します。つまり、すでに 3 つの要素がある場合、次の要素が 4 番目のセルに追加されます。基本的なメソッドのパフォーマンスを見てみましょう。

• get(int index) - インデックスによる配列内の要素の取得は、O(1)で最も高速です。
• add(Object obj) - 内部配列に新しい要素用の十分なスペースがある場合、追加の対象は最後のセルであるため、 通常の挿入ではO(1)時間がかかります。

  新しい配列を作成してその内容をコピーする必要がある場合、時間は配列O(n)の要素の数に直接比例します。

• Remove(int index) - たとえば要素を中央から削除する場合、その要素の右側にある要素を 1 セル後ろに移動する必要があるため、O(n/2) 時間がかかります。したがって、リストの先頭から削除する場合は O(n)、末尾から削除する場合は - O(1) になります。
• add(int index, Object obj) - 削除と同様の状況です。中央に追加する場合、右側の要素を 1 セル前に移動する必要があるため、時間は O(n/2) です。もちろん、最初から - O(n)、終わりから - O(1);
• set(int index, Object obj) - ここでは状況が異なります。目的の要素を見つけて、残りを移動せずに上書きするだけでよいため、O(1) になります。

ArrayListについて詳しくは、この記事をご覧ください。 LinkedList は、 ListとQueue という2 つのインターフェイスを同時に実装するため、両方のデータ構造に固有のプロパティとメソッドを持ちます。彼はリストからインデックスによって要素にアクセスし、キューから「先頭」と「末尾」の存在を取得しました。内部的には、二重リンクリストを表すデータ構造として実装されます。つまり、「尾」と「頭」を除いて、各要素には前後の要素へのリンクがあります。

• get(int index) - リストの中央にある要素を検索する場合、目的の要素が見つかるまですべての要素を順番に検索し始めます。論理的には、検索にはO(n/2)かかるはずですが、LinkedList には末尾もあるため、検索は両側から同時に実行されます。したがって、時間はO(n/4)に短縮されます。

  要素がリストの先頭または末尾に近い場合、時間はO(1)になります。

• add(Object obj) - 新しい要素を追加するとき、「tail」要素には追加された次の要素へのリンクが含まれ、新しい要素はこの前の要素へのリンクを受け取り、新しい「tail」になります。したがって、時間はO(1)になります。
• Remove(int Index) - get(int Index)メソッドと同様のロジック。リストの中央から要素を削除するには、まずその要素を見つける必要があります。これもO(n/4)ですが、隣接するオブジェクトのポインタを変更するだけなので、削除自体は実際には何もかかりません (相互参照を開始します)。要素が先頭または末尾にある場合は、再度 - O(1) ;
• add(int index, Object obj)およびset(int index, Object obj) -ほとんどの時間は要素の検索に費やされるため、これらのメソッドの時間計算量はget(int index) と同じになります。したがって、リストの中央についてはO(n/4)、リストの先頭についてはO(1) となります。

LinkedListの操作の詳細については、この記事で説明されています。これらすべてを表で見てみましょう。 すでにおわかりかと思いますが、この質問に明確に答えることは不可能です。結局のところ、状況が異なれば、動作速度も異なります。したがって、このような質問をされた場合は、このリストが何に焦点を当てているのか、どのような操作が最も頻繁に実行されるのかをすぐに尋ねる必要があります。ここから始めて、なぜそうなるのかの説明を含めて答えてください。比較をまとめてみましょう: ArrayList:

• 最も頻繁に行われる操作が要素の検索や要素の上書きである場合に最適な選択です。
• 操作が先頭から中間での挿入と削除である場合は、右側の要素のシフト操作が行われるため、最悪の選択です。

リンクリスト:

• 頻繁に行う操作が先頭から中間での挿入と削除である場合に最適です。
• 最も一般的な操作が検索である場合、最悪の選択です。

9. 要素は HashMap にどのように保存されますか?

HashMapコレクションには内部配列Node[] tableが含まれており、そのセルはバケットとも呼ばれます。 ノードには以下が含まれます:

• key - キーへのリンク、
• value — 値への参照、
• ハッシュ- ハッシュ値、
• next - 次のノードへのリンク。

table[]配列の 1 つのセルには、次のNode要素へのリンクを持つNodeオブジェクトへの参照が含まれる場合があり、また、別の Node 要素へのリンクが含まれる場合もあり、以下同様です。その結果、これらのNode要素は、単一リンクされたリスト。次へのリンクを持つ要素を含みます。この場合、1 つのチェーンの要素のハッシュ値は同じになります。少し脱線しましたが、要素がHashMapにどのように格納されるかを見てみましょう。

1. キーはnullかどうかチェックされます。nullの場合、 null のハッシュ コードは常に 0 であるため、キーはtable[0]セルに格納されます。
2. キーがnullでない場合、キー オブジェクトのhashcode()メソッドが呼び出され、そのハッシュ コードが返されます。このハッシュ コードは、Node オブジェクトが格納される配列セルを決定するために使用されます。
3. 次に、このハッシュコードは、ハッシュコードを計算する内部hash()メソッドに配置されますが、そのサイズはtable[]配列のサイズ内に収まります。
4. 次に、ハッシュ値に応じて、table[]配列の特定のセルに Node が配置されます。
5. 現在のNode要素を保存するために使用されるtable[]セルが空ではなく、すでに何らかの要素がある場合、最後の要素に到達するまでNode要素は次の値に対して反復されます。つまり、次のフィールドがnullのものです。

   この検索中に、保護されたNodeオブジェクトのキーが検索対象の Node オブジェクトのキーと比較されます。

   • 一致が見つかった場合、検索は終了し、一致が見つかったノードが新しいノードで上書きされます (その値フィールドのみが上書きされます)。
   • 一致するキーが見つからない場合、新しいノードがこのリストの最後になり、前のノードにはそのノードへの次のリンクが設定されます。

面接中によく質問されるのは、「対立とは何ですか?」という質問です。table[]配列のセルに 1 つの要素ではなく、2 つ以上の要素が連鎖して格納される状況を衝突と呼びます。単一のtable[]セルに 1 つの要素のみが格納される通常の場合、 HashMapの要素へのアクセスの時間計算量は一定のO(1)になります。ただし、目的の要素を持つセルに要素のチェーン (衝突) が含まれている場合は、O(n)になります。この場合、時間はソートされる要素の数に正比例するためです。

10. イテレータについて説明する

上のコレクション階層マッピング図では、コレクションインターフェイスが階層全体の開始点でしたが、実際はまったく同じではありません。コレクションは、 Iterator <E>インターフェイスを実装するオブジェクトを返すiterator()メソッドを持つインターフェイスを継承します。Iterator インターフェイスは次のようになります。

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - このメソッドを呼び出すと、次の要素を取得できます。 hasNext() - 次の要素があるかどうか、およびコレクションの終わりに到達したかどうかを確認できます。まだ要素がある場合、hasNext() はtrueを返します。通常、hasNext() はnext()メソッドの前に呼び出されます。これは、next() がコレクションの最後に到達するとNoSuchElementExceptionをスローするためです。 Remove() - next() への最後の呼び出しによって取得された要素を削除します。Iterator の目的は、要素を反復処理することです。例えば：

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

実際、for-each ループは反復子を使用して内部で実装されています。詳細については、こちらをご覧ください。 List は、独自のバージョンのイテレーターを提供しますが、よりクールで洗練されたバージョンであるListIterator を提供します。このインターフェイスはIteratorを拡張し、追加のメソッドがあります。

• hasPrevious は、コレクション内に前の要素がある場合は true を返し、そうでない場合は false を返します。
• Previous は現在の要素を返し、前の要素に移動します。何もない場合は、NoSuchElementException がスローされます。
• add は、次のnext()呼び出しによって返される要素の前に、渡されたオブジェクトを挿入します。
• set は、現在の要素に渡されたオブジェクトへの参照を割り当てます。
• nextIndex は、次の要素のインデックスを返します。そのようなものが存在しない場合は、リストのサイズが返されます。
• previousIndex は、前の要素のインデックスを返します。何もない場合は、数値 -1 が返されます。

さて、今日はここまでです。この記事を読んだ後、あなたが開発者になるというあなたの大切な夢にさらに近づくことを願っています。