道の始まり
今日は「 Java Collections Framework」、または簡単に言うとコレクションについての興味深いトピックについて話したいと思います。コードの作業のほとんどは、何らかの形式でデータを処理することです。ユーザーのリストを取得したり、アドレスのリストを取得したりします。何らかの方法でそれらを並べ替え、検索を実行し、比較します。コレクションに関する知識がコアスキルとみなされているのはこのためです。だからこそ、それについて話したいと思います。さらに、Java 開発者のインタビューで最も一般的な質問の 1 つはコレクションです。たとえば、「コレクションの階層を描画する」とします。オンライン コンパイラは、その過程で役立ちます。たとえば、「Tutorialspoint
Online Java Compiler」または
Repl.itを使用できます。データ構造を理解するための道は、通常の変数 (変数) から始まります。Oracle Web サイトでは、さまざまなトピックが「パス」またはトレイルとして表されます。そこで、Java を理解するためのパスを「
トレイル: Java 言語の学習: 目次」と呼びます。そして、言語の基礎 (つまり、言語の基礎) は変数から始まります。したがって、簡単なコードを書いてみましょう。
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
このコードは 1 つの変数に対してのみ優れていて美しいということを理解していることを除いて、すべてにおいて優れています。それらが複数ある場合はどうすればよいですか? 配列は、1 種類のデータを格納するために発明されました。Oracle からの同じトレイルには、配列専用の別のセクションがあります。このセクションは「
配列」と呼ばれます。配列の操作も非常に簡単です。
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
配列は、複数の値を 1 か所に保存するという問題を解決します。ただし、配列のサイズは一定であるという制限があります。例のように、size = 2 と指定した場合、それは 2 に等しくなります。それだけです。より大きな配列が必要な場合は、新しいインスタンスを作成する必要があります。また、配列の場合、要素を見つけるのも難しいことです。というメソッドがあります
Arrays.binarySearchが、この検索はソートされた配列に対してのみ機能します (ソートされていない配列の場合、結果は未定義であるか、単純に予測できません)。つまり、検索では毎回ソートが必要になります。削除しても値がクリアされるだけです。したがって、実際に配列内にどれだけのデータがあるのかはまだわかりません。配列内にセルが何個あるかだけがわかります。配列に関する知識を更新するには、次の手順を実行します。
そして、Java 言語の開発の結果として、今日説明する JDK 1.2 に Java Collections Framework が登場しました。
コレクション
最初から原価計算を始めます。なぜコレクションなのか? この用語自体は、「型理論」や「抽象データ型」などに由来しています。しかし、高度な事柄に目を向けなければ、いくつかの物があるとき、それらを「物の集合」と呼ぶことができます。アイテムを集めている人。一般に、収集という言葉自体はラテン語に由来しています。collectionio「集める、集める」。つまり、コレクションは何かのコレクション、つまりいくつかの要素のコンテナです。したがって、要素のコレクションができました。それを使って何がしたいか:
ご覧のとおり、私たちは非常に論理的なものを望んでいるかもしれません。また、複数のコレクションを使用して何かをしたい場合があることも理解しています。
したがって、Java 開発者は、すべてのコレクションに対するこの一般的な動作を記述する
java.util.Collectionインターフェースを作成しました。Collection インターフェイスは、すべてのコレクションの発信元です。コレクションはアイデアであり、すべてのコレクションがどのように動作するかについてのアイデアです。したがって、「コレクション」という用語はインターフェイスとして表現されます。当然のことながら、インターフェイスには実装が必要です。インターフェース
java.util.Collectionには抽象クラス
AbstractCollection、つまり他の実装のスケルトンを表す「抽象コレクション」があります (クラスの上の JavaDoc に記述されているように
java.util.AbstractCollection)。コレクションについて話しますが、コレクションを反復処理する必要があることを思い出してください。これは、要素を 1 つずつ反復処理することを意味します。これは非常に重要な概念です。したがって、インターフェイス
Collectionは から継承されます
Iterable。これは非常に重要なので... まず、Iterable はすべて、その内容に基づいて Iterator を返すことができなければなりません。そして第二に、Iterable のものはすべてループ内で使用できます
for-each-loop。そして、 、 、など
AbstractCollectionのメソッドが実装されるのは、反復子の助けを借りてです。そして、コレクションを理解するための道は、最も一般的なデータ構造の 1 つであるリストから始まります。。
containstoArrayremoveList
リスト
したがって、リストはコレクションの階層において重要な位置を占めます。
ご覧のとおり、リストは
java.util.Listインターフェースを実装しています。リストは、ある順序で次々に配置された要素のコレクションがあることを表します。各要素にはインデックスがあります (配列の場合と同様)。通常、リストでは同じ値を持つ要素を含めることができます。上で述べたように、
Listそれは要素のインデックスについて知っています。
getこれにより、インデックスによって要素を取得 ( ) したり、特定のインデックスの値を設定 (
set) したりすることができます。コレクション メソッド
add、
addAll、
removeを使用すると、コレクション メソッドを実行するインデックスを指定できます。さらに、 y に
Listは、 と呼ばれる独自のバージョンの反復子があります
ListIterator。この反復子は要素のインデックスを認識しているため、前方だけでなく後方にも反復できます。コレクション内の特定の場所から作成することもできます。すべての実装の中で、最もよく使用されるのは
ArrayListと の2 つです
LinkedList。まず、配列（ ）に基づく
ArrayListリスト（ ）です。
これにより、要素への「ランダム アクセス」を実現できます。ランダム アクセスとは、目的のインデックスを持つ要素が見つかるまですべての要素を反復処理するのではなく、インデックスによって要素を即座に取得する機能です。これを実現できるのはアレイの基盤です。逆に、リンクリストです。リンクされたリストの各エントリは、データ自体と、次 (next) および前 (previous) へのリンクを格納する形式で表されます。したがって、「シーケンシャルアクセス
」が実装されます。5 番目の要素を見つけるには、最初の要素から最後の要素まで移動する必要があることは明らかです。5 番目の要素に直接アクセスすることはできません。4 番目の要素からのみアクセスできます。両者のコンセプトの違いは次のとおりです。
ListArrayLinkedListEntryEntryLinkedList
ご存知のとおり、仕事においても違いがあります。たとえば、要素を追加します。要素
LinkedListは単純にチェーンのリンクのように接続されています。ただし、
ArrayList要素は配列に格納されます。そして、ご存知のとおり、配列のサイズは変更できません。それではどのように機能するのでしょうか
ArrayList？そしてそれは非常に簡単に機能します。配列内のスペースがなくなると、1.5 倍に増加します。ズーム コードは次のとおりです。
int newCapacity = oldCapacity + (oldCapacity >> 1); 操作のもう 1 つの違いは、要素のオフセットです。たとえば、要素を途中で追加または削除する場合です。
LinkedList要素から削除するには、この要素への参照を削除するだけです。の場合、
ArrayListを使用して要素を毎回シフトする必要があります
System.arraycopy。したがって、要素が多いほど、より多くのアクションを実行する必要があります。より詳細な説明は、次の記事にあります。
ArrayList を調べてみると、その「前身」であるjava.util.Vectorクラスを思い出さずにはいられません。コレクションを操作するためのメソッド (追加、削除など) が同期されるという点が
Vector異なります。
ArrayListつまり、1 つのスレッド (
Thread) が要素を追加すると、他のスレッドは最初のスレッドが作業を完了するまで待機します。
ArrayListスレッド セーフは必要ない場合が多いため、クラスの JavaDoc に明示的に記載されているように、そのような場合にはクラスを使用することをお勧めします
Vector。さらに、
Vectorサイズは1.5倍ではなく
ArrayList2倍に増加します。それ以外の場合、動作は同じです。
Vector配列形式での要素の格納は非表示になり、要素の追加/削除は の場合と同じ結果になります
ArrayList。実際、
Vector私たちがこれを思い出したのには理由がありました。Javadoc を見ると、「直接の既知のサブクラス」に
java.util.Stackなどの構造が表示されます。スタックは、LIFO
last-in-first-out(後入れ先出し) 構造である興味深い構造です。英語から翻訳されたスタックはスタックです（たとえば、本の積み重ねのような）。スタックは追加のメソッド
peek(look、look)、
pop(push)、
push(push) を実装します。この方法
peekは look と翻訳されます (たとえば、
バッグの中を覗くと「
バッグの中を見る」、
鍵穴を覗くと「
鍵穴を覗く」と翻訳されます)。このメソッドを使用すると、スタックの「一番上」を見ることができます。スタックから削除せずに (つまり削除せずに) 最後の要素を取得します。このメソッドは
push新しい要素をスタックにプッシュ (追加) して返し、要素メソッドは
pop削除された要素をプッシュ (削除) して返します。3 つのケースすべて (つまり、ピーク、ポップ、プッシュ) で、最後の要素 (つまり、「スタックの最上位」) のみを処理します。これがスタック構造の最大の特徴です。ちなみに、書籍「プログラマーのキャリア」（クラッキング・コーディング・インタビュー）にスタックを理解するための興味深いタスクがあり、「スタック」構造（LIFO）を使用して「キュー」を実装する必要があるという興味深いタスクがあります。 ”構造（FIFO）。次のようになります。
このタスクの分析については、「
スタックを使用したキューの実装 - キュー ADT (LeetCode の「スタックを使用したキューの実装」)」を参照してください。したがって、新しいデータ構造であるキューにスムーズに移行します。
列
キューは、私たちが昔からよく知っている構造です。店にも医者にも行列。最初に来た人 (先入れ) が最初にキューから離れることになります (先出し)。Java では、キューは
java.util.Queueインターフェースで表されます。キューの Javadoc によると、キューには次のメソッドが追加されています。
ご覧のとおり、オーダー メソッド (実行に失敗すると例外が発生します) とリクエスト メソッド (実行できなくてもエラーにはなりません) があります。要素を削除せずに取得することもできます (ピークまたは要素)。キュー インターフェイスには、便利な後継インターフェイス
Dequeもあります。これはいわゆる「双方向キュー」です。つまり、このようなキューを使用すると、最初と最後の両方からこの構造を使用できます。ドキュメントには、「Deques は LIFO (Last-In-First-Out) スタックとしても使用できます。このインターフェイスは、従来の Stack クラスよりも優先して使用する必要があります。」と記載されています。つまり、代わりに Deque 実装を使用することをお勧めします。スタック。Javadoc には、Deque インターフェースでどのようなメソッドが記述されているかが示されています。
どのような実装があるのか見てみましょう。そして、興味深い事実がわかります - LinkedList はキュー陣営に入りました) つまり、LinkedList は
Listと の両方を実装します
Deque。ただし、たとえば「キューのみ」もあります
PriorityQueue。彼女のことはあまり思い出されませんが、無駄です。まず、このキューでは「比較できないオブジェクト」を使用できません。Comparator を指定するか、すべてのオブジェクトが比較可能である必要があります。2 番目に、「この実装では、メソッドのエンキューとデキューに O(log(n)) 時間がかかります」。対数的な複雑さには理由があります。ヒープに基づいて PriorityQueue を実装しました。Javadoc には、「プライオリティ キューはバランスのとれたバイナリ ヒープとして表される」と記載されています。このストレージ自体は通常の配列です。必要に応じて成長します。ヒープが小さい場合は 2 倍に増加します。そして50％ずつ。コードのコメント: 「小さい場合はサイズが 2 倍、そうでない場合は 50% 増加します。」優先キューとバイナリ ヒープは別のトピックです。詳細については、次のとおりです。
実装として、
java.util.ArrayDequejava.util.Dequeクラスを使用できます。つまり、リストはリンク リストと配列を使用して実装でき、キューも配列またはリンク リストを使用して実装できます。およびインターフェイスには、「ブロッキング キュー」を表す子孫があります:および。通常のキューと比較したインターフェイスの変更は次のとおりです。
QueueDequeBlockingQueueBlockingDeque
キューをブロックする例をいくつか見てみましょう。しかし、それらは興味深いものです。たとえば、 BlockingQueue は、
PriorityBlockingQueue、
SynchronousQueue、 ArrayBlockingQueue 、
DelayQueue、
LinkedBlockingQueueによって実装されます。ただし、
BlockingDeque標準の Collection Framework のすべてを実装します
LinkedBlockingDeque。各キューは個別のレビューのトピックです。そして、このレビューの枠組みの中で、 だけでなく
List、 を使用してクラス階層を表現します
Queue。
図からわかるように、Java Collections Framework のインターフェイスとクラスは高度に絡み合っています。階層の別のブランチを追加しましょう -
Set。
セット
Set—「セット」と訳されます。
Setこれは、要素のストレージをより抽象化している点で、キューやリストとは異なります。
Set- 物体が入った袋のようなもので、物体がどのように配置され、どのような順序で置かれているかが不明です。Java では、このようなセットは
java.util.Setインターフェースで表されます。ドキュメントに記載されているように、
Setこれは「重複する要素を含まないコレクション」です。興味深いことに、インターフェイス自体は
Set新しいメソッドをインターフェイスに追加するのではなく
Collection、要件 (重複を含めるべきではないこと) を明確にするだけです。さらに、前の説明から、
Set要素を単純に取得することはできないことがわかります。イテレータは要素を取得するために使用されます。
Setさらにいくつかのインターフェースが関連付けられています。1つ目は です
SortedSet。名前が示すように、
SortedSetこのようなセットがソートされていることを示し、したがって要素はインターフェイスを実装する
Comparableか、指定されます
Comparator。さらに、
SortedSetいくつかの興味深いメソッドも提供しています。
さらに、
first(値による最小要素) および
last(値による最大要素) というメソッドもあります。
SortedSet跡継ぎがいる――
NavigableSet。このインターフェースの目的は、適切な要素をより正確に識別するために必要なナビゲーション方法を記述することです。興味深いのは、
NavigableSet通常の反復子 (最小値から最大値へ) に逆順の反復子を追加していることです
descendingIterator。さらに、要素が逆の順序になっている自分自身のビュー (View) を取得する
NavigableSetメソッドを使用することもできます。これは、結果の要素を通じて元の要素の要素を変更できるために
descendingSet呼び出されます。つまり、本質的には、元のデータを別の方法で表現したものであり、コピーではありません。興味深いことに、は、 と同様に、 （最小）要素と（最大）要素を処理できます。つまり、この要素を取得し、セットから削除します。どのような実装がありますか? まず、最も有名な実装はハッシュ コード
HashSetに基づいています。同様によく知られているもう 1 つの実装は、赤黒ツリー
TreeSetに基づいています。図を完成させましょう。
ViewSetNavigableSetQueuepollFirstpollLast
コレクション内では、隠者という階層を整理することが残っています。一見脇に見えるのは――
java.util.Map。
地図
マップは、データがキーごとに格納されるデータ構造です。たとえば、キーは ID または都市コードである可能性があります。そして、このキーによってデータが検索されます。カードが別々に表示されているのが面白いです。開発者によると (「
Java Collections API Design FAQ」を参照)、キーと値のマッピングはコレクションではありません。そして、マップは、キーのコレクション、値のコレクション、キーと値のペアのコレクションとして考えることができます。これはとても興味深い動物です。カードはどのようなメソッドを提供しますか? Java API インターフェース
java.util.Mapを見てみましょう。なぜなら マップはコレクションではない (コレクションから継承しない) ため、 は含まれません
contains。そしてこれは論理的です。マップはキーと値で構成されます。このメソッドでは次のどれを確認する必要がありますか
contains?また、混乱しないようにするにはどうすればよいですか? したがって、インターフェイスには、 (キーを含む) と(値を含む)
Mapの 2 つの異なるバージョンがあります。これを使用すると、一連のキー (同じキー) を取得できます。そして、このメソッドを使用すると、マップ内の値のコレクションを取得できます。マップ内のキーは一意であり、これはデータ構造によって強調されます。値は繰り返すことができますが、これはコレクション データ構造によって強調されます。さらに、このメソッドを使用すると、キーと値のペアのセットを取得できます。どのようなカード実装があるかについては、最も詳細な分析で詳しく読むことができます。
containsKeycontainsValuekeySetSetvaluesSetentrySet
また、 とに
HashMapよく似ているものも見てみたいと思います。これらには、、、、 などの同様のインターフェイスもあります。最終的なマップは次のようになります。
HashSetTreeMapTreeSetNavigableSetNavigableMapSortedSetSortedMap
最後に、コレクションが
Set内部で を使用し
Map、追加された値がキーであり、その値がどこでも同じであるという興味深い事実で終わります。これは
Mapコレクションではなく
Set、コレクションではありますが実際には として実装された を返すため、興味深いものです
Map。ちょっと非現実的ですが、結果的にはこんな感じでした）
結論
良いニュースは、これでこのレビューが終了するということです。悪いニュースは、これが非常にレビュー記事だということです。各コレクションの各実装については、また、私たちの目から隠されている各アルゴリズムについても、個別の記事に値します。ただし、このレビューの目的は、それらが何であるか、およびインターフェイス間の接続が何であるかを思い出すことです。じっくり読んだ後、記憶に基づいてコレクションの図を描けるようになれば幸いです。
さて、いつものように、いくつかのリンク:
#ヴィアチェスラフ
GO TO FULL VERSION