Javaコレクションのインタビューの質問
1. 序章
Javaコレクションは、Java開発者向けの技術面接でよく取り上げられるトピックです。 この記事では、最も頻繁に尋ねられ、正しく理解するのが難しいかもしれないいくつかの重要な質問をレビューします。
2. 質問
Q1。 コレクションタイプ階層について説明します。 主なインターフェースは何ですか、そしてそれらの違いは何ですか？
Iterable インターフェースは、for-eachループを使用して反復できるコレクションを表します。 Collection インターフェイスは、 Iterable を継承し、要素がコレクションにあるかどうかを確認したり、コレクションに要素を追加および削除したり、サイズを決定したりするための汎用メソッドを追加します。
List 、 Set 、および Queue インターフェースは、Collectionインターフェースを継承します。
List は順序付けられたコレクションであり、その要素にはリスト内のインデックスからアクセスできます。
Set は、セットの数学的概念に似た、個別の要素を持つ順序付けられていないコレクションです。
Queue は、要素を追加、削除、および検査するための追加のメソッドを備えたコレクションであり、処理前に要素を保持するのに役立ちます。
Map インターフェイスもコレクションフレームワークの一部ですが、Collectionを拡張していません。 これは、一般的な抽象化では収集が難しいコレクションとマッピングの違いを強調するための設計によるものです。 Map インターフェースは、一意のキーを持ち、キーごとに1つ以下の値を持つKey-Valueデータ構造を表します。
Q2。 マップインターフェイスのさまざまな実装とそれらのユースケースの違いについて説明します。
Map インターフェースの最も頻繁に使用される実装の1つは、HashMapです。 これは、一定時間、つまりO（1）で要素にアクセスできる典型的なハッシュマップデータ構造ですが、は順序を保持せず、スレッドセーフではありません。
要素の挿入順序を維持するために、 LinkedHashMap クラスを使用できます。このクラスは、 HashMap を拡張し、さらに要素をリンクリストに結び付けます。
TreeMap クラスは、その要素を赤黒木構造に格納します。これにより、対数時間、つまりO（log（n））で要素にアクセスできます。 ほとんどの場合、 HashMap よりも低速ですが、一部のコンパレータに従って要素を整理することができます。
ConcurrentHashMap は、ハッシュマップのスレッドセーフな実装です。 これは、取得の完全な同時実行性（ get 操作はロックを伴わないため）と、予想される更新の同時実行性を提供します。
Hashtable クラスは、バージョン1.0以降Javaに含まれています。 これは非推奨ではありませんが、ほとんどの場合廃止されたと見なされます。 これはスレッドセーフなハッシュマップですが、 ConcurrentHashMap とは異なり、そのすべてのメソッドは単純に同期されます。つまり、このマップブロックに対するすべての操作、さらには独立した値の取得も可能です。
Q3。 LinkedlistとArraylistの違いを説明してください。
ArrayList は、配列に基づくListインターフェイスの実装です。 ArrayList は、要素が追加または削除されたときに、この配列のサイズ変更を内部的に処理します。 配列内のインデックスによって、一定時間でその要素にアクセスできます。 ただし、要素を挿入または削除すると、結果として生じるすべての要素がシフトすることを意味します。これは、配列が大きく、挿入または削除された要素がリストの先頭に近い場合は遅くなる可能性があります。
LinkedList は、二重にリンクされたリストです。単一の要素が、前後のNodeへの参照を持つNodeオブジェクトに配置されます。 リストのさまざまな部分に多くの挿入または削除がある場合、特にリストが大きい場合、この実装はArrayListよりも効率的に見える場合があります。
ただし、ほとんどの場合、ArrayListはLinkedListよりも優れています。 ArrayList でシフトする要素でさえ、O（n）操作でありながら、非常に高速な System.arraycopy（）呼び出しとして実装されます。 LinkedList のO（1）挿入よりも速く表示される場合があります。これには、 Node オブジェクトをインスタンス化し、内部で複数の参照を更新する必要があります。 LinkedList は、複数の小さな Node オブジェクトが作成されるため、大きなメモリオーバーヘッドが発生する可能性もあります。
Q4。 ハッシュセットとツリーセットの違いは何ですか？
HashSetクラスとTreeSetクラスはどちらも、 Set インターフェイスを実装し、個別の要素のセットを表します。 さらに、TreeSetはNavigableSetインターフェースを実装します。 このインターフェースは、要素の順序を利用するメソッドを定義します。
HashSetは内部的にHashMapに基づいており、TreeSetはTreeMapインスタンスによってサポートされています。 は、要素を特定の順序で保持しません。 HashSet の要素を反復処理すると、シャッフルされた順序で要素が生成されます。 一方、 TreeSet は、事前定義されたコンパレータに従って要素を順番に生成します。
Q5。 ハッシュマップはJavaでどのように実装されていますか？ その実装はどのようにハッシュコードを使用し、オブジェクトのメソッドを等しくしますか？ そのような構造から要素を配置および取得する時間の複雑さは何ですか？
HashMap クラスは、特定の設計上の選択肢がある典型的なハッシュマップデータ構造を表します。
HashMap は、2の累乗のサイズを持つサイズ変更可能な配列によって支えられています。 要素がHashMapに追加されると、最初にその hashCode が計算されます（ int 値）。 次に、この値の下位ビットの特定の数が配列インデックスとして使用されます。 このインデックスは、このキーと値のペアを配置する必要がある配列のセル（バケットと呼ばれます）を直接指します。 配列内のインデックスによって要素にアクセスすることは、ハッシュマップ構造の主な機能である非常に高速なO（1）操作です。
hashCode は一意ではありませんが、 hashCodes が異なっていても、同じ配列位置を受け取る場合があります。 これは衝突と呼ばれます。 ハッシュマップデータ構造の衝突を解決する方法は複数あります。 JavaのHashMapでは、各バケットは実際には単一のオブジェクトではなく、このバケットに到達したすべてのオブジェクトの赤黒木を参照します（Java 8より前は、これはリンクリスト）。
したがって、 HashMap がキーのバケットを決定すると、このツリーをトラバースして、キーと値のペアをその場所に配置する必要があります。 そのようなキーを持つペアがバケットにすでに存在する場合は、新しいものと交換されます。
キーでオブジェクトを取得するには、HashMapはキーのhashCodeを再度計算し、対応するバケットを見つけ、ツリーをトラバースし、equalsを呼び出す必要があります。ツリー内のキーを選択し、一致するキーを見つけます。
HashMap には、要素の配置と取得のO（1）の複雑さ、または一定時間の複雑さがあります。 もちろん、衝突が多いと、すべての要素が1つのバケットに収まる場合、最悪の場合、パフォーマンスがO（log（n））時間計算量に低下する可能性があります。 これは通常、一様分布の優れたハッシュ関数を提供することで解決されます。
HashMap 内部配列がいっぱいになると（次の質問で詳しく説明します）、自動的に2倍のサイズにサイズ変更されます。 この操作は、コストのかかる再ハッシュ（内部データ構造の再構築）を推測するため、HashMapのサイズを事前に計画する必要があります。
Q6。 ハッシュマップの初期容量と負荷率パラメーターの目的は何ですか？ それらのデフォルト値は何ですか？
HashMapコンストラクターのinitialCapacity引数は、 HashMap の内部データ構造のサイズに影響しますが、マップの実際のサイズについて推論するのは少し注意が必要です。 。 HashMap の内部データ構造は、2の累乗のサイズの配列です。 したがって、 initialCapacity 引数の値は次の2の累乗に増加します（たとえば、10に設定すると、内部配列の実際のサイズは16になります）。
HashMap の負荷率は、要素数をバケット数で割った比率です（つまり、 内部配列サイズ）。 たとえば、16バケット HashMap に12個の要素が含まれている場合、その負荷率は12/16=0.75です。 負荷率が高いということは、衝突が多いことを意味します。つまり、マップのサイズを2の次の累乗に変更する必要があります。 したがって、 loadFactor 引数は、マップの負荷率の最大値です。 マップがこの負荷率に達すると、内部配列のサイズを次の2の累乗の値に変更します。
initialCapacity はデフォルトで16であり、loadFactorはデフォルトで0.75であるため、デフォルトのコンストラクターでインスタンス化された HashMap に12個の要素を配置でき、サイズは変更されません。 同じことがHashSetにも当てはまります。これは、内部でHashMapインスタンスによってサポートされています。
したがって、ニーズを満たすinitialCapacityを思い付くのは簡単ではありません。 これが、Guavaライブラリに Maps.newHashMapWithExpectedSize（）および Sets.newHashSetWithExpectedSize（）メソッドがあり、HashMapまたはHashSetを作成できる理由です。 サイズを変更せずに予想される数の要素を保持できます。
Q7。 列挙子の特殊コレクションについて説明します。 通常のコレクションと比較して、それらの実装の利点は何ですか？
EnumSetおよびEnumMapは、それぞれSetおよびMapインターフェースの特別な実装です。 これらの実装は非常に効率的であるため、列挙型を扱う場合は常にこれらの実装を使用する必要があります。
EnumSet は、セットに存在する列挙型の順序値に対応する位置に「1」が付いたビットベクトルです。 列挙値がセットに含まれているかどうかを確認するには、実装はベクトル内の対応するビットが「1」であるかどうかを確認するだけで済みます。これは非常に簡単な操作です。 同様に、 EnumMap は、列挙型の序数値をインデックスとして使用してアクセスされる配列です。 EnumMap の場合、ハッシュコードを計算したり、衝突を解決したりする必要はありません。
Q8。 フェイルファストイテレータとフェイルセーフイテレータの違いは何ですか？
さまざまなコレクションのイテレータは、同時変更への反応に応じて、フェイルファストまたはフェイルセーフのいずれかになります。 同時変更は、別のスレッドからのコレクションの変更だけでなく、同じスレッドからの変更でもありますが、別のイテレーターを使用するか、コレクションを直接変更します。
Fail-fast イテレーター（ HashMap 、 ArrayList 、およびその他の非スレッドセーフコレクションによって返されるイテレーター）は、コレクションの内部データ構造を反復処理し、スローします。 ConcurrentModificationException は、同時変更を検出するとすぐに。
フェイルセーフイテレーター（ ConcurrentHashMap 、 CopyOnWriteArrayList などのスレッドセーフコレクションによって返される）は、反復する構造体のコピーを作成します。 それらは、同時変更からの安全性を保証します。 それらの欠点には、過剰なメモリ消費と、コレクションが変更された場合の古いデータの反復が含まれます。
Q9。 比較可能およびコンパレータインターフェイスを使用してコレクションを並べ替えるにはどうすればよいですか？
Compareable インターフェースは、ある順序に従って比較できるオブジェクトのインターフェースです。 その単一のメソッドはcompareToであり、オブジェクト自体と同じタイプの引数オブジェクトの2つの値を操作します。 たとえば、 Integer 、 Long 、およびその他の数値タイプは、このインターフェイスを実装します。 String もこのインターフェイスを実装し、そのcompareToメソッドは辞書式順序で文字列を比較します。
Compareable インターフェイスを使用すると、 Collections.sort（）メソッドを使用して対応するオブジェクトのリストを並べ替え、SortedSetおよびを実装するコレクションの反復順序を維持できます。 SortedMap。 オブジェクトを何らかのロジックを使用して並べ替えることができる場合は、Compareableインターフェイスを実装する必要があります。
Compareable インターフェースは通常、要素の自然な順序を使用して実装されます。 たとえば、すべての Integer 番号は、小さい値から大きい値の順に並べられます。 ただし、番号を降順で並べ替えるなど、別の種類の順序を実装したい場合もあります。 コンパレータインターフェースがここで役立ちます。
並べ替えるオブジェクトのクラスは、このインターフェイスを実装する必要はありません。 実装クラスを作成し、 compare メソッドを定義するだけです。このメソッドは、2つのオブジェクトを受け取り、それらの順序を決定します。 次に、このクラスのインスタンスを使用して、 Collections.sort（）メソッドまたはSortedSetおよびSortedMapインスタンスの自然な順序をオーバーライドできます。
コンパレータインターフェイスは機能的なインターフェイスであるため、次の例のように、ラムダ式に置き換えることができます。 自然な順序付けを使用してリストを順序付けすることを示しています（ 整数の同程度のインターフェイス）およびカスタムイテレータの使用（ コンパレータ
List<Integer> list1 = Arrays.asList(5, 2, 3, 4, 1);
Collections.sort(list1);
assertEquals(new Integer(1), list1.get(0));
List<Integer> list1 = Arrays.asList(5, 2, 3, 4, 1);
Collections.sort(list1, (a, b) -> b - a);
assertEquals(new Integer(5), list1.get(0));