Javaコレクションインタビューの質問
1.はじめに
Javaコレクションは、Java開発者のための技術面接でよく出てくるトピックです。この記事では、よく寄せられるいくつかの重要な質問について説明します。
2.質問
** Q1. Collections型の階層を記述する主なインターフェースは何ですか?またそれらの違いは?
-
Iterable
インタフェースは、
for-each
ループを使用して反復できる任意のコレクションを表します。
Collection
** インタフェースは
Iterable
を継承し、要素がコレクション内にあるかどうかをチェックし、要素をコレクションに追加したり削除したり、サイズを決定するための一般的なメソッドを追加します。 -
List
、
Set
、および
Queue
** インターフェースは
Collection
インターフェースから継承します。 -
List
** は順序付きコレクションであり、その要素はリスト内のインデックスによってアクセスできます。 -
Set
** は、集合の数学的概念と同様に、個別の要素を持つ順序付けられていないコレクションです。 -
Queue
** は、要素を追加、削除、検証するための追加のメソッドを含むコレクションです。処理前に要素を保持するのに便利です。 -
Map
** インターフェースもコレクションフレームワークの一部ですが、
Collection
を拡張するものではありません。これは意図的なものであり、共通の抽象化の下で収集するのが難しいコレクションとマッピングの違いを強調するためのものです。
Map
インタフェースは、一意のキーを持ち、各キーに複数の値を持たないキー値データ構造を表します。
Q2.
Map
インターフェースのさまざまな実装とそのユースケースの違いを説明してください.
Map
インターフェースの最もよく使用される実装の1つは
HashMap
です。これは、要素に一定時間またはO(1)でアクセスすることを可能にする典型的なハッシュマップデータ構造ですが、
順序を保存せず、スレッドセーフではありません
。
要素の挿入順序を維持するために、
HashMap
を拡張し、さらに要素をリンクリストに結び付ける
LinkedHashMap
クラスを使用できます。
-
TreeMap
** クラスは、その要素を赤黒の木構造で格納します。これにより、対数時間、またはO(log(n))で要素にアクセスできます。ほとんどの場合、これは
HashMap
よりも遅くなりますが、
Comparator
に従って要素を順番に並べることができます。 -
ConcurrentHashMap ** は、ハッシュマップのスレッドセーフな実装です。
(
get
操作はロックを必要としないため)検索の完全な同時実行性と更新の高い同時実行性を提供します。
-
Hashtable
** クラスはバージョン1.0以来Javaにあります。これは非推奨ではありませんが、ほとんど時代遅れと見なされています。これはスレッドセーフなハッシュマップですが、
ConcurrentHashMap
とは異なり、そのすべてのメソッドは単に
synchronized
です。つまり、このマップに対するすべての操作は独立した値の取得でさえもブロックします。
** Q3.
LinkedList
と__ArrayListの違いを説明してください.
-
ArrayList
** は、配列に基づく
List
インターフェースの実装です。
ArrayList
は、要素が追加または削除されたときに、この配列のサイズ変更を内部的に処理します。配列内のインデックスによって、その要素に一定時間アクセスできます。ただし、要素を挿入または削除すると、結果として得られるすべての要素の移動が推論されます。配列が巨大で、挿入または削除された要素がリストの先頭に近い場合は速度が遅くなる可能性があります。 -
LinkedList
** は二重リンクリストです。前の要素と次の要素を参照する
Node
オブジェクトに単一の要素が入ります。この実装は、特にリストが大きい場合など、リストのさまざまな部分に多数の挿入または削除がある場合、
ArrayList
よりも効率的に見えることがあります。
ただし、ほとんどの場合、
ArrayList
は
LinkedList
よりも優れています。
ArrayList
内でシフトしている要素であっても、O(n)操作でありながら、非常に高速な
System.arraycopy()
呼び出しとして実装されています。それは、
Node
オブジェクトをインスタンス化し、その下で複数の参照を更新する必要がある
LinkedList
s O(1)の挿入よりも速く見えることさえあります。
LinkedList
は、複数の小さな
Node
オブジェクトが作成されるため、大きなメモリーオーバーヘッドが発生する可能性があります。
Q4.
HashSet
と
TreeSet
の違いは何ですか?
-
HashSet
クラスと
TreeSet
** クラスはどちらも
Set
インタフェースを実装し、個別の要素のセットを表します。さらに、
TreeSet
は
NavigableSet
インタフェースを実装しています。このインタフェースは要素の順序を利用するメソッドを定義します。
HashSet
は内部的に
HashMap
に基づいており、
TreeSet
はそのプロパティを定義する
TreeMap
インスタンスによってサポートされています。
HashSet
内の要素を反復すると、それらがシャッフルされた順序で生成されます。一方、
TreeSet
は、事前定義された
Comparator
に従って順序どおりに要素を生成します。
Q5.
HashMap
はJavaでどのように実装されていますか?その実装はオブジェクトの
hashCode
と
equals
メソッドをどのように使用しますか?そのような構造から要素を入れたり取得したりする時間の複雑さは何ですか?
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
の初期容量と負荷率パラメータの目的は何ですか?デフォルト値は何ですか?
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個の要素を入れることができ、サイズは変更されません。内部的には
HashMap
インスタンスによって支えられている
HashSet
についても同じことが言えます。
したがって、あなたのニーズを満たす
initialCapacity
を考え出すのは簡単なことではありません。これが、Guavaライブラリに
Maps.newHashMapWithExpectedSize()
メソッドと
Sets.newHashSetWithExpectedSize()
メソッドがあるためです。これらのメソッドを使用すると、サイズ変更せずに必要な数の要素を保持できる
HashMap
または
HashSet
を構築できます。
====
Q7. 列挙型の特別コレクションを説明してください. 通常のコレクションと比較してそれらの実装の利点は何ですか?
-
EnumSet
および
EnumMap
** は、
Set
およびの特殊な実装です.
それに対応して
Map
インターフェース. あなたはいつもこれらを使うべきです
列挙型を扱っているときの実装は、
効率的です.
EnumSet
は、位置に「1」を含む単なるビットベクトルです.
セットに存在するenumの序数値に対応します. 確認する
enum値がセットに含まれている場合、実装は単に次のことをチェックするだけでよい
ベクトルの対応するビットは「1」です. これは非常に簡単です.
操作. 同様に、
EnumMap
は列挙型でアクセスされる配列です.
インデックスとしての序数値.
EnumMap
の場合、以下の必要はありません.
ハッシュコードを計算するか衝突を解決します.
====
Q8. フェイルファーストとフェイルセーフの反復子の違いは何ですか?
異なるコレクションに対するイテレータは、フェイルファーストかフェイルセーフです.
同時変更に対する反応によって異なります. コンカレント
変更は他からのコレクションの変更だけではありません
スレッドだけでなく、同じスレッドからの変更も別のスレッドを使用
イテレータまたはコレクションを直接変更する.
-
Fail-fast ** 反復子(
HashMap
、
ArrayList
、および
他のスレッドセーフではないコレクション)は、コレクションの
内部データ構造
同時発生を検出した直後の
ConcurrentModificationException
変形. -
フェイルセーフ** イテレータ(以下のようなスレッドセーフなコレクションによって返される)
ConcurrentHashMap
、
CopyOnWriteArrayList
)のコピーを作成します.
それらが繰り返す構造. 彼らは同時から安全を保証します
修正それらの欠点には、過度のメモリ消費が含まれます.
コレクションが更新された場合には、古くなっている可能性のあるデータに対する反復処理
修正しました.
====
Q9.
Comparable
および
Comparator
インターフェースを使用してコレクションを並べ替えることができますか?
Comparable
インタフェースは、次のものになる可能性のあるオブジェクトのインタフェースです.
いくつかの順序に従って比較しました. その唯一の方法は
compareTo
です.
これは2つの値、オブジェクト自身と引数オブジェクトに作用します.
同じタイプです. たとえば、
Integer
、
Long
、その他の数値
型はこのインタフェースを実装します.
String
もこのインタフェースを実装しています、
その
compareTo
メソッドは辞書順で文字列を比較します.
Comparable
インターフェースは対応するオブジェクトのリストをソートすることを可能にします
Collections.sort()
メソッドを使用して、反復順序を
SortedSet
と
SortedMap
を実装しているコレクション. あなたの物が
いくつかのロジックを使ってソートすることができます、彼らは
Comparable
を実装するべきです
インタフェース.
Comparable
インターフェースは通常、自然順序付けを使用して実装されます.
要素の. たとえば、すべての
Integer
番号は
小さい値から大きい値まで. しかし時々あなたは実装したいかもしれません
たとえば、別の種類の順序付け
降順.
Comparator
インターフェースがここで役に立ちます.
ソートしたいオブジェクトのクラスは実装する必要はありません.
このインターフェース実装クラスを作成して、
2つのオブジェクトを受け取り、順序付け方法を決定する
compare
メソッド
それら. その後、このクラスのインスタンスを使用して、
Collections.sort()
メソッドまたは
SortedSet
の自然な順序
SortedMap
インスタンス.
Comparator
インターフェースは機能的なインターフェースなので、置き換えることができます.
次の例のように、これはラムダ式で表します. それが示している
自然順序付けを使用してリストを順序付ける(
Integer
´s
Comparable
カスタムイテレータ(
Comparator <Integer>
)の使用
インタフェース).
[source、java、gutter:、true]—-
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));
次 ** "** https://www.baeldung.com/java-type-system-interview-questions[Java Type システムインタビューの質問]