Java コレクションの面接で大企業が最もよく尋ねる質問

いわゆる大企業の JAVA 面接の質問をいくつか読んだところ、どの企業も JAVA コレクション クラスの使用を非常に重視していることがわかりましたが、私はこの点についてはほとんど知らないので、時間をかけて学ぶ必要があります。

java.util パッケージには、一連の重要なコレクション クラスが含まれています。コレクション クラスの場合、主に習得する必要があるのは、その内部構造とコレクションを走査するための反復モードです。

インターフェイス: コレクション

コレクションは、最も基本的なコレクション インターフェイスであり、オブジェクトのセット、つまりコレクションの要素を表します。コレクションによっては、同一の要素を許可するものと許可しないものがあります。ある種のものとそうでないものがあります。 Java SDK は Collection を直接継承するクラスを提供しません。Java SDK が提供するクラスはすべて、List や Set など、Collection を継承する「サブインターフェイス」です。

Collection インターフェイスを実装するすべてのクラスは、2 つの標準コンストラクターを提供する必要があります。パラメーターなしのコンストラクターは空のコレクションを作成するために使用され、Collection パラメーターを持つコンストラクターは新しいコレクションを作成するために使用されます。この新しいコレクションには、コレクションと同じ要素があります。渡されたコレクション。後者のコンストラクターを使用すると、ユーザーはコレクションをコピーできます。

メインインターフェイスメソッド: boolean add(Ojbect c)
これは boolean を返しますが、追加が成功したかどうかを示すものではありません。この戻り値の意味は、add() の後にコレクションの内容が変更されたかどうかです。が実行されます (つまり、要素の数、位置などが変更されたかどうか)。同様の addAll、remove、removeAll、remainAll も同じです。

コレクションを走査するには反復子モードを使用します

コレクションには、コレクションのすべての要素を走査するための反復子 (反復子) を返す重要なメソッド iterator() があります。 Iterator パターンは、さまざまなコレクション クラスからアクセス ロジックを抽象化できるため、コレクションの内部構造がクライアントに公開されるのを回避できます。典型的な使用法は次のとおりです:

Iterator it = collection.iterator(); // 获得一个迭代器
while(it.hasNext()) {
    Object obj = it.next(); // 得到下一个元素
}

コレクションを走査するための「ポインター」を維持する必要はありません。すべての内部状態は Iterator によって維持され、この Iterator はファクトリ メソッドを通じてコレクション クラスによって生成されます。

各コレクション クラスによって返される Iterator の具体的な型は異なる場合がありますが、それらはすべて Iterator インターフェイスを実装しているため、Iterator インターフェイスの種類を気にする必要はありません。これはインターフェイスの利点であり、オブジェクト指向の力です。

トラバースプロセスがスムーズに完了することを保証するには、トラバースプロセス中にコレクションの内容が変更されないことを保証する必要があります(Iteratorのremove()メソッドを除く)。したがって、信頼性の高いトラバースを保証するための原則となります。このコレクションを 1 つのスレッドでのみ使用するか、スレッド内のトラバーサル コードを同期します。

Collection インターフェースから派生した 2 つのインターフェースは、List と Set です。

List インターフェース

List は順序付けられたコレクションです。このインターフェースを使用すると、各要素の挿入位置を正確に制御できます。ユーザーは、Java の配列に似たインデックス (配列の添え字に似たリスト内の要素の位置) を使用して、リスト内の要素にアクセスできます。以下で説明する Set とは異なり、List では同じ要素が許可されます。

Collection インターフェイスに必要な iterator() メソッドに加えて、List には ListIterator インターフェイスを返す listIterator() メソッドも用意されており、標準の Iterator インターフェイスと比較して、ListIterator には追加の add() メソッドやその他のメソッドが追加されています。要素を追加、削除、設定し、前方または後方に移動します。

List インターフェイスを実装する一般的なクラスは、LinkedList、ArrayList、Vector、Stack です。

LinkedList クラス

LinkedList は List インターフェースを実装し、null 要素を許可します。さらに、LinkedList は、LinkedList の先頭または末尾に追加の get、remove、および insert メソッドを提供します。これらの操作により、LinkedList をスタック、キュー、または両端キューとして使用できるようになります。

LinkedList には同期されたメソッドがないことに注意してください。複数のスレッドが同時にリストにアクセスする場合、スレッド自体がアクセス同期を実装する必要があります。解決策の 1 つは、リストの作成時に同期されたリストを構築することです:
List list = Collections.synchronizedList(new LinkedList(…));

ArrayList クラス

ArrayList は可変サイズの配列を実装します。 null を含むすべての要素が許可されます。 ArrayList は同期されていません。
size、isEmpty、get、set メソッドの実行時間は一定です。ただし、add メソッドのコストは償却定数であり、n 個の要素を追加するには O(n) 時間がかかります。他の方法では実行時間が直線的になります。

各 ArrayList インスタンスには容量 (Capacity) があり、これは要素を格納するために使用される配列のサイズです。この容量は、新しい要素が追加されると自動的に増加しますが、増加アルゴリズムは定義されていません。多数の要素を挿入する必要がある場合は、挿入前に ensureCapacity メソッドを呼び出して ArrayList の容量を増やし、挿入効率を向上させることができます。

LinkedList と同様に、ArrayList も非同期です。

Vector クラス

Vector は ArrayList に非常に似ていますが、Vector は同期されています。 Vector で作成された Iterator は ArrayList で作成された Iterator と同じインターフェイスを持ちますが、Vector は同期されているため、Iterator が作成されて使用されると、別のスレッドによって Vector の状態が変更されます (たとえば、要素の追加や削除など)。 , Iterator メソッドを呼び出すと ConcurrentModificationException がスローされるため、例外をキャッチする必要があります。

Stack クラス

Stack は Vector を継承し、後入れ先出しスタックを実装します。 Stack には、Vector をスタックとして使用できるようにする 5 つの追加メソッドが用意されています。基本的なプッシュ メソッドとポップ メソッド、およびピーク メソッドはスタックの先頭にある要素を取得し、空のメソッドはスタックが空かどうかをテストし、検索メソッドはスタック内の要素の位置を検出します。スタックは、作成後の空のスタックです。

Set インターフェイス

Set は、重複する要素を含まない Collection です。つまり、任意の 2 つの要素 e1 と e2 には e1.equals(e2)=false があり、Set には最大 1 つの null 要素があります。

明らかに、Set コンストラクターには、渡された Collection パラメーターに重複した要素を含めることができないという制約があります。

注意: 可変オブジェクトは注意して扱う必要があります。 Set 内の可変要素の状態が変化して Object.equals(Object)=true になると、いくつかの問題が発生します。

Map インターフェイス

Map は Collection インターフェイスを継承しないことに注意してください。キーと値のマッピングは提供されません。マップに同じキーを含めることはできず、各キーは 1 つの値のみをマップできます。 Map インターフェイスは、3 種類のセット ビューを提供します。Map のコンテンツは、キー セットのセット、値セットのセット、またはキーと値のマッピングのセットと見なすことができます。

Hashtableクラス

HashtableはMapインターフェースを継承し、キーと値のマッピングのハッシュテーブルを実装します。 null 以外の任意のオブジェクトをキーまたは値として使用できます。

データを追加するには put(key, value) を使用し、データを削除するには get(key) を使用します。これら 2 つの基本的な操作の時間コストは一定です。

ハッシュテーブルは、初期容量と負荷率という 2 つのパラメーターを通じてパフォーマンスを調整します。通常、デフォルトの負荷係数 0.75 を使用すると、時間と空間のバランスがより良くなります。負荷率を増やすとスペースを節約できますが、それに対応する検索時間が増加し、get や put などの操作に影響します。

ハッシュテーブルを使用する簡単な例は次のとおりです。ハッシュテーブルに 1、2、および 3 を入力します。それぞれのキーは「1」、「2」、「3」です。
ハッシュテーブルの番号 = new Hashtable();
numbers.put(「1」、新しい整数(1));
numbers.put(「2」、新しい整数(2));
numbers.put(「3」、新しい整数(3));

2 などの数値を取り出すには、対応するキーを使用します:
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);

キーとして使用されるオブジェクトはハッシュ関数を計算することによって対応する値の位置を決定するため、キーとして使用されるオブジェクトはすべて hashCode メソッドと equals メソッドを実装する必要があります。 hashCode メソッドと equals メソッドは、ルート クラス Object を継承します。カスタム クラスをキーとして使用する場合、ハッシュ関数の定義に従って、2 つのオブジェクトが同じである場合、つまり obj1.equals( obj2)=true の場合、それらのハッシュコードは同じである必要がありますが、2 つの異なるオブジェクトのハッシュコードが同じである場合、この現象は競合と呼ばれます。ハッシュ テーブルの操作にかかる時間のオーバーヘッドが増加するため、ハッシュ テーブルの操作を高速化するために、明確に定義された hashCode() メソッドを定義するようにしてください。

同じオブジェクトに異なる hashCode がある場合、ハッシュ テーブルの操作で予期しない結果が生じます (予想される get メソッドが null を返す)。この問題を回避するには、1 つのことだけを覚えておく必要があります。それは、equals メソッドと hashCode をオーバーライドすることです。メソッドを 1 つだけ書くのではなく、同時に実行します。

ハッシュテーブルは同期です。

HashMap クラス

HashMap は Hashtable に似ていますが、HashMap が非同期で null、つまり null 値と null キーを許可する点が異なります。ただし、HashMap を Collection として扱う場合 (values() メソッドは Collection を返すことができます)、そのイテレータ操作時間のオーバーヘッドは HashMap の容量に比例します。したがって、反復操作のパフォーマンスが非常に重要な場合は、HashMap の初期容量を高く設定しすぎたり、負荷率を低く設定しすぎたりしないでください。

WeakHashMap クラス

WeakHashMap は、キーへの「弱参照」を実装する改良された HashMap で、キーが外部から参照されなくなった場合、そのキーは GC によってリサイクルできます。

概要

スタックやキューなどの操作が含まれる場合は、要素の高速な挿入と削除のために List の使用を検討する必要があります。要素への高速なランダム アクセスが必要な場合は、ArrayList を使用する必要があります。

プログラムがシングルスレッド環境にある場合、またはアクセスが 1 つのスレッドでのみ実行される場合は、より効率的な非同期クラスを検討してください。複数のスレッドが同時にクラスを操作する可能性がある場合は、同期クラスを使用する必要があります。

ハッシュ テーブルの操作には特に注意してください。キーとして使用されるオブジェクトは、equals メソッドと hashCode メソッドを正しく上書きする必要があります。

将来 ArrayList を LinkedList に置き換える必要がある場合に、クライアント コードを変更する必要がないように、ArrayList の代わりに List を返すなど、実際の型ではなくインターフェイスを返すようにしてください。これは抽象化のためのプログラミングです。