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

こんにちは！何かをマスターするのに何時間かかりますか? 「何かの達人になるには、10,000時間費やす必要がある」というようなことをよく聞きます。恐ろしい数字ですね。 しかし、これは本当なのでしょうか？そして、私はプログラミングの技術を習得するためにすでに何時間を費やしたかを常に把握しようとしています。そして、その大切な10,000時間を超えてマスターになったとき、この違いを感じるでしょうか？それとも、私は気づかないうちにずっと前にそれらを踏み越えてしまったのでしょうか？いずれにしても、プログラマーになるために、それほど膨大な時間を投資する必要はありません。重要なのは、それを賢く使うことです。あなたの主な目標は面接に合格することです。また、新人面接では理論を最初に聞かれるので、理論に強くなければなりません。実際、面接の準備をするときの仕事は、Java 開発者の基本理論におけるギャップをすべて発見し、知識で埋めることです。そして今日、私は最もよくある質問を分析し続けるためにここにいるので、この問題についてお手伝いします。それでは続けましょう！

89. ArrayList は LinkedList とどう違うのですか?

これは、 HashMap の内部構造に関する質問と並んで、最も人気のある質問の 1 つです。面接なしには面接は成立しません。したがって、面接に対する答えは「歯に跳ね返る」はずです。明らかな名前の違いに加えて、内部構造も異なります。以前にArrayListとLinkedListの両方の内部構造を調べたので、それらの実装の詳細については説明しません。ArrayListは内部配列に基づいて実装され、次の式に従って必要に応じて増加することを 思い出してください。

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

同時に、LinkedList は内部二重リンク リストに基づいて実装されます。つまり、リストの先頭/末尾の値を除き、各要素には前後へのリンクがあります。人々は、あなたを捕まえることを期待して、 「 ArrayListとLinkedList のどちらが良いですか?」という形式でこの質問をするのを好みます。結局のところ、どちらかを答えとして挙げると、それは不正解になります。 代わりに、インデックスへのアクセスやリストの途中への挿入など、具体的にどのような状況について話しているのかを明確にする必要があります。答えに応じて、自分の選択を説明できるようになります。ある状況でArrayListとLinkedList がどのように機能するかを以前に説明しました。比較のために同じページに並べてこれを要約してみましょう: 要素の追加 (add)

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

結論: LinkedList では、アルゴリズムの複雑さはO(1)からO(n/2)の範囲になります。つまり、挿入がリストの末尾または先頭に近づくほど、挿入が速くなります。同時に、ArrayListの場合、その範囲はO(1)からO(n)です。挿入がリストの末尾に近づくほど、挿入が速くなります。 要素の設定 (set) この操作は、リスト内の指定された位置に要素を書き込み、以前の要素があれば上書きします。LinkedListでは、この操作は追加に似ています。ここでの最大の困難は要素を見つけることです。要素の書き換えはリンクのペアを書き換えることによって行われるため、ここでもアルゴリズムの複雑さはリストの末尾または先頭からの位置の距離に応じてO(1)からO(n/2) の範囲になります。その時点で、このインデックス操作に必要なセルがArrayList内で見つかり、新しい要素がそこに書き込まれます。この操作と同様、インデックス検索のアルゴリズムの複雑さはO(1)です。 インデックスによる要素の取得 (get) LinkedList では、要素の取得は、他の操作の検索と同じ原理に従って行われます (末尾または先頭からの距離に応じて)。O(1)からO(n/2)まで。前に述べたように、 ArrayListでは、インデックスによる配列内の要素の検索の複雑さはO(1)です。 インデックスによる要素の削除 (削除) LinkedList の場合、その動作原理はここでも機能します。最初に要素が見つかり、次にリンクが上書きされます。要素の隣接要素が相互に参照し始め、この要素への参照が失われます。その後、ガベージ コレクターによって削除されます。つまり、アルゴリズムの複雑さはO(1)からO(n/2)まで同じです。ArrayListの場合、この操作は新しい要素を追加する操作 (add) に似ています。まず、必要な要素O(1)が見つかり、それが削除され、その右側にあるすべての要素が 1 単位左に移動されて、結果として生じるギャップが閉じられます。削除操作には、追加操作と同じアルゴリズムの複雑さ ( O(1)からO(n)まで) があります。削除がリストの最後に近づくほど、アルゴリズムの複雑さは少なくなります。実際、これらはすべて主要な操作でした。思い出してもらいたいのですが、これら 2 つのリストを比較するときは、どのような特定の状況について話しているのかを明確にする必要があります。そうすれば、提示された質問に明確に答えることができます。

90. ArrayList は HashSet とどう違うのですか?

ArrayListとLinkedList を操作の観点から比較できれば (どちらのほうが優れていますが)、ArrayListとHashSetを比較するのはそれほど簡単ではありません。これらはまったく異なるコレクションであるためです。ある甘い料理を別の料理と比較することはできますが、肉料理でもうまくいきます。それらはあまりにも違います。ただし、それらの違いをいくつか挙げてみたいと思います。

• ArrayList はListインターフェイスを実装し、HashSet はSetインターフェイスを実装します。

• ArrayListでは、要素インデックスによってアクセスが可能です。get操作のアルゴリズムの複雑さはO(1)ですが、HashSetでは必要な要素は総当たりでのみ取得でき、これはO(1)からO(n)までです。 ;

• ArrayList では要素の重複が許可されます。HashSetでは、すべての要素が一意です。コレクション内にすでに存在する類似要素を持つ要素をHashSetに追加することはできません (ハッシュコードを使用して重複がチェックされるため、このコレクションの名前が付けられています)。

• ArrayList は内部配列を使用して実装され、HashSetは内部HashMap を使用して実装されます。

• ArrayList は要素の挿入順序を維持しますが、HashSet は順序付けされていないセットであり、要素の順序は維持しません。

• ArrayList では、任意の数の空の値 (null) を許可しますが、 HashSetに挿入できる null 値は 1 つだけです(結局のところ、要素の一意性のため)。

91. Java にはなぜこれほど多様な動的配列実装があるのですか?

そうですね、これはむしろ哲学的な質問です。では、なぜ彼らはこれほど多くの異なる新技術を思いつくのでしょうか? 快適さのために。実際、これは多くの動的配列の実装でも同じです。それらはどれも最良または理想とは言えません。特定の状況ではそれぞれに利点があります。そして私たちの仕事は、それらの違い、長所/短所を知り、適切な状況で最も適切なものを使用できるようにすることです。

92. Java にはこれほど多様なキーと値のストレージ実装があるのはなぜですか?

ここでの状況は、動的配列実装の場合と同じです。誰が一番優れているということはなく、それぞれに長所と短所があります。そしてもちろん、私たちは自分たちの強みを最大限に活用しなければなりません。 例:多くのマルチスレッド テクノロジを含む並行パッケージには、独自の並行コレクションがあります。同じConcurrentHashMap は、通常のHashMapと比較して、データを扱うマルチスレッド作業の安全性において利点がありますが、非マルチスレッド環境では速度が低下します。まあ、どんな状況でも最強ではない実装は徐々に使われなくなっていきます。 例: Hashtable は当初、スレッドセーフなHashMapであることを目的としていましたが、マルチスレッド環境では ConcurrentHashMap のパフォーマンスが向上し、Hashtableは最終的に忘れ去られ、使用されなくなりました。

93. 要素のコレクションを並べ替える方法は?

まず最初に言っておきたいのは、コレクション要素クラスはComparableインターフェイスとそのCompareToメソッドを実装する必要があるということです。または、コンパレータメソッドを備えたComapratorを実装するクラスが必要です。詳細については、この投稿をご覧ください。どちらのメソッドも、特定のタイプのオブジェクトを比較する方法を指定します。並べ替える場合、要素を比較する原理を理解する必要があるため、これは非常に重要です。これを行う主な方法は、並べ替えるクラスに直接実装されるComparableを実装することです。同時に、Comparatorの使用はあまり一般的ではありません。Comparable実装を持たないライブラリのクラスを使用しているが、それを何らかの方法でソートする必要があるとします。このクラスのコードを (拡張する場合を除いて) 変更することはできませんが、Comparatorの実装を作成して、このクラスのオブジェクトをどのような原理で比較するかを指定できます。そしてもう一つの例。同じタイプのオブジェクトを並べ替えるために異なる原則が必要なため、さまざまな状況で使用する複数のコンパレーターを作成したとします。原則として、多くのクラスはそのままの状態で既にComparableインターフェイス(同じString )を実装しています。実際に使ってみると、どうやって比較するか考える必要はありません。それらを取り出して使用するだけです。 最初の最も明白な方法は、 TreeSetまたはTreeMap型のコレクションを使用することです。これは、要素クラス コンパレータに従ってすでにソートされた順序で要素を格納します。TreeMap はキーを並べ替えますが、値は並べ替えないことに注意してください。Comparableの代わりにComparator実装を使用する場合は、作成時にそのオブジェクトをコレクション コンストラクターに渡す必要があります。

TreeSet treeSet = new TreeSet(customComparator);

しかし、別の種類のコレクションがある場合はどうなるでしょうか? どうやって並べ替えるの？この場合、Collectionsユーティリティ クラスの2 番目のメソッド、sort()メソッドが適しています。これは静的であるため、必要なのはクラスの名前と、必要なリストが渡されるメソッドだけです。例えば：

Collections.sort(someList);

ComparableではなくComparator の実装 を使用している場合は、それを 2 番目のパラメータとして渡す必要があります。

Collections.sort(someList, customComparator);

その結果、渡されたリストの要素の内部順序が変更され、要素のコンパレータに従って並べ替えられます。転送される要素のリストは変更可能である必要があることに注意してください。変更可能な場合、それ以外の場合、メソッドは機能せず、UnsupportedOperationExceptionがスローされます。3 番目の方法として、 Comparable実装が使用されている場合にコレクションの要素を並べ替えるStream sort操作を使用できます。

someList = someList.stream().sorted().collect(Collectors.toList());

コンパレータ の場合:

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

ストリーム について詳しくは、この記事をご覧ください。 4 番目の方法は、バブル ソートやマージ ソートなどの並べ替えを手動で実装することです。

クラスオブジェクト。Equals と HashCode

94. Javaのクラスオブジェクトについて簡単に説明してください

分析の 2 番目の部分では、 Objectクラスのメソッドについてすでに説明しましたが、 Objectクラスが Java のすべてのクラスの祖先であることを思い出してください。これには 11 のメソッドがあり、それに応じてすべてのクラスによって継承されます。 11 のメソッドすべてに関する情報は、ディスカッションの 後半部分に記載されています。

95. Java では Equals と HashCode は何に使用されますか?

hashCode() は、すべてのクラスに継承されるObjectクラスのメソッドです。そのタスクは、特定のオブジェクトを表す数値を生成することです。このメソッドの使用例は、ローカル ハッシュコードをさらに決定するためにキー オブジェクトのHashMapで使用することです。これにより、ペアが格納される内部配列 (バケット) のセルが決定されます。HashMapの働きについては分析のパート 9 で詳しく説明したので、これについてはあまり詳しく説明しません。 また、原則として、このメソッドはオブジェクトのアイデンティティを決定するための主要ツールの 1 つとして、 equals()メソッドで使用されます。equals()は、オブジェクトを比較し、それらが等しいかどうかを判断するObjectクラスのメソッドです。==を使用した通常の比較はオブジェクトには適していないため、このメソッドはオブジェクトを比較する必要があるあらゆる場所で使用されます。それらへのリンクのみを比較します。

96. Java における Equals と HashCode の間の契約について教えてください。

最初に言っておきますが、equals() メソッドとhashCode()メソッドが正しく動作するには、それらを正しくオーバーライドする必要があるということです。この後、彼らは次のルールに従わなければなりません。

• 等号による比較が true を返す同一のオブジェクトは、同じハッシュコードを持つ必要があります。
• 同じハッシュ コードを持つオブジェクトは常に等しいとは限りません。

この時点で、分析の次の部分まで一時停止します。