Java コレクションフレームワークについては、この記事を読むだけで十分です-＆＃＆チュートリアル-php.cn

さっそく、次の図に直接進みましょう。

Java コレクション (コンテナーとも呼ばれます) , 主に2 つの主要なインターフェイス (インターフェイス)から派生します:
Collection と Map

名前が示すように、コンテナーはデータを保存するために使用されます。

これら 2 つのインターフェイスの違いは次のとおりです:

コレクションは単一の要素を格納します;
マップはキーと値のキーを格納します-値のペア。

つまり、シングルはコレクションに配置され、カップルはマップに配置されます。 (それで、あなたはどこに属しますか?

これらのコレクションフレームワークを学習すると、次の 4 つの目標があると思います:

各インターフェイスとクラスの対応関係を明確にする;
各インターフェイスとクラスで一般的に使用される API に精通する;
適切なデータ構造を選択し、さまざまなデータ構造の長所と短所を分析できるようにするシナリオ;
ソースコードの設計を学び、インタビューに答えられるようになります。

Map については、以前の HashMap の記事が非常に徹底的かつ詳細に説明されています。なので、この記事では詳しくは書きませんが、まだ記事を読んでいない方は、公式アカウントにアクセスして「HashMap」とリプライして記事を読んでみてください~

コレクション

まずトップレベルのコレクションを見てみましょう。

コレクションには多くのメソッドも定義されており、これらのメソッドは各サブインターフェイスや実装クラスにも継承されます。これらの API の使用は、日常業務や面接でもよく行われるテストです。まずはこれらのメソッドを見てください。

操作のコレクションは、「追加、削除、変更、確認」の 4 つのカテゴリにすぎず、CRUD:

Create、Read とも呼ばれます。

次に、これらの API を次の 4 つのカテゴリに分類します:

以下で詳しく見てみましょう:

追加:

boolean add(E e);

ログイン後にコピー

add()データ型メソッドによって渡されます。オブジェクトである必要があるため、基本的なデータ型を記述するときに、自動ボックス化とアンボックス化が実行されます。

別のメソッドaddAll()があり、別のコレクションからこのコレクションに要素を追加できます。

boolean addAll(Collection c);

ログイン後にコピー

Delete:

boolean remove(Object o);

ログイン後にコピー

remove()は、削除する指定された要素です。

これはaddAll()に対応します。
には当然、セット B 内のすべての要素を削除するremoveAll()があります。

boolean removeAll(Collection c);

ログイン後にコピー

変更:

コレクションインターフェイスの要素を変更する直接操作はありませんが、削除と追加で変更を完了できます。

查：

查下集合中有没有某个特定的元素：

boolean contains(Object o);

ログイン後にコピー

查集合 A 是否包含了集合 B：

boolean containsAll(Collection c);

ログイン後にコピー

还有一些对集合整体的操作：

判断集合是否为空：

boolean isEmpty();

ログイン後にコピー

集合的大小：

int size();

ログイン後にコピー

把集合转成数组：

Object[] toArray();

ログイン後にコピー

以上就是 Collection 中常用的 API 了。

在接口里都定义好了，子类不要也得要。

当然子类也会做一些自己的实现，这样就有了不同的数据结构。

那我们一个个来看。

List

List 最大的特点就是：有序，可重复。

看官网说的：

An ordered collection (also known as a sequence).

Unlike sets, lists typically allow duplicate elements.

今回はSetの特徴についても触れましたが、Listとは真逆で、Setはunorderであり、が繰り返されません。

最初は、データ構造が
必要な機能を完了できるかどうかを検討することです;両方を完了できる場合、2 つ目は、どちらの
がより効率的であるかを検討してください。(すべてはこのようなものです。

これら 2 つのクラスの API とその時間計算量を具体的に見てみましょう:

#Change コレクションインターフェイスに # がありません#check Others # #List は、LinkedList と ArrayList の 2 つの方法で実装できます。面接で最もよく聞かれる質問は、これら 2 つのデータ構造のどちらを選択するかということです。このタイプの選択問題の場合:

関数	メソッド
Add	add()/addAll()
削除	delete()/removeAll( )

contains()/ containsAll()
isEmpty()/size()/toArray()

#関数メソッド ArrayList LinkedList ##increase Add 削除削除 #O(n) set(intindex, E e) get(int インデックス)

add(E e) O(1) O(1)

add(int インデックス, E e) O(n) O(n)

削除(int インデックス) O(n) O(n)

remove(E e) O(n) #Change

O(1) O(n) Check

O(1) ＃＃＃＃＃＃の上）＃＃＃＃＃＃＃＃＃＃＃＃

いくつかの説明:

add(E e)は末尾に要素を追加することです。ArrayList は拡張される可能性がありますが、償却時間計算量 ) は依然として O(1) です。

add(intindex, E e)は、特定の位置に要素を追加することです。LinkedList は、最初にこの位置を見つけてから、この要素を追加する必要があります。これは単純な「add」ですが、 " アクション O(1) ですが、この位置を見つけるのはまだ O(n) です。 (これを O(1) だと考える人もいます。面接官に明確に説明し、責任を負うことを拒否してください。

remove(int Index)は、remove のインデックス上の要素です。したがって、

ArrayList 内でこの要素を見つけるプロセスは O(1) ですが、削除後、後続の要素は 1 位置前に移動する必要があるため、償却された複雑さは O(n );
LinkedList も最初にインデックスを見つける必要があります。このプロセスは O(n) であるため、全体のプロセスも O(n) です。

は、remove によって検出される最初の要素です。その後、

ArrayList は最初にこの要素を見つける必要があります。このプロセスは O(n) です。除算後、O(n) である 1 つの位置を前に移動する必要がありますが、合計は依然として O(n) です;

LinkedList も検索する必要があります最初にこのプロセスは O(n) )、その後削除され、このプロセスは O(1) になり、合計は O(n) になります。
理由は何ですか?時間計算量の違いは?

回答

配列にはランダムにアクセスできる (ランダムアクセス)
.

#この機能により、添字を使用すると O(1) 時間で任意の位置の数値を取得できますが、リンクリストではそれができず、先頭から 1 つずつしかたどることができません。

つまり、「変更と確認」の2つの機能で配列にランダムにアクセスできるため、ArrayListは効率が高いです。

「追加と削除」についてはどうでしょうか？

この要素を見つける時間を考慮しない場合、

配列は物理的に連続しているため、要素を追加したり削除したりする場合は末尾でも大丈夫ですが、他の場所に移動すると後続の要素が削除されるため、効率が低下しますが、リンクリストでは次の要素との接続が簡単に切断されるため、新しい要素を直接挿入したり、古い要素を削除したりすることができます。

しかし、実際には、要素を見つけるまでの時間を考慮する必要があります。。。また、データ量が多い場合はArrayListを最後尾で動作させると高速になります。

##つまり:

#検索を変更して ArrayList を選択します。
##最後に追加と削除を行う場合は ArrayList を選択します;
その他の場合、時間計算量が同じであれば、ArrayList を選択することをお勧めしますオーバーヘッドが小さいため、またはメモリがより効率的に使用されるためです。

#Vector

Vector も ArrayList と同様に java.util.AbstractList

から継承し、最下層も配列を使用して実装されます。

しかし、追加される同期が多すぎるため、現在は非推奨になっています。

すべての利点にはコストが伴います。スレッドセーフのコストは効率の低下であり、一部のシステムではボトルネックになりやすいため、現在はデータ構造レベルで同期を追加するのではなく、代わりに転送します。私たちのプログラマー==

よくある面接の質問: Vector と ArrayList の違いは何ですか? これに答えるだけでは、あまり包括的ではありません。

スタックオーバーフローに関する投票の多かった回答を見てみましょう:

2 つ目は、拡張時に必要な拡張量の違いです。

これについてはソースコードを参照する必要があります:

演算は、この数値の 2 進数を 1 ビット右に移動し、左端の

が符号ビットを補いますが、容量には負の数がないため、やはり 0 を加算します。1 ビットを右にシフトすると、 2 で除算され、定義される新しい容量は元の容量の1.5 倍

になります。

Vector をもう一度見てみましょう:

通常、capacityIncrement を定義しないため、デフォルトでは2 回拡張されます。

この2点に答えていただければ、間違いなく問題ありません。

Queue と Deque

Queue は、一方の端が入力でもう一方の端が出力である線形データ構造であり、Deque両端ですので全て出入り可能です。

Queue

Java の Queue インターフェイスは少しわかりにくいです。一般的に、セマンティクスは次のとおりです。キューの数これらはすべて先入れ先出し(FIFO) です。

しかし、ここには例外があります。つまり、PriorityQueue (ヒープとも呼ばれます) は、入力された時間順に出力されるのではなく、指定された優先順位に従って出力され、その操作は O ではありません。 (1)、時間複雑さの計算は少し複雑なので、後ほど別の記事で説明します。

Queue メソッド公式ウェブサイト^[1]すべてをまとめました。2 つの API セットがあり、基本的な機能は同じですが、次のとおりです。

一方のグループは例外をスローし、
#もう一方のグループは特別な値を返します。

#関数追加 ##削除 remove() poll() Look element() peek()

例外をスロー戻り値

add(e) offer(e)

なぜ例外がスローされるのでしょうか?

たとえば、キューが空の場合、remove() は例外をスローしますが、poll() は null を返し、element() は例外をスローしてピークを返します。 () は null を返すだけです。

add(e) が例外をスローするのはなぜですか?

一部のキューには、BlockingQueueなどの容量制限があります。最大容量に達していて拡張されない場合は、例外がスローされます。ただし、オファー (e ) の場合、false が返されます。

それでは、どのように選択すればよいでしょうか? ：

まず、これを使用する場合は、同じ API セットを使用してください。、表と裏を統一する必要があります。
##第二に、ニーズに応じて。例外をスローする必要がある場合は、例外をスローするものを使用しますが、アルゴリズムの問題を実行する場合は基本的に使用されないため、特別な値を返すものを選択してください。

DequeDeque は両端から出入りできるため、当然のことながら次のターゲットになります。操作と最後の側の操作、各側には 2 つのグループがあり、1 つのグループは例外をスローし、もう 1 つのグループは特別な値を返します:

Function ##increase addFirst(e)/ addLast(e) offerFirst( e)/ offerLast(e) Delete removeFirst()/removeLast() pollFirst()/ pollLast() Look getFirst()/ getLast()

例外をスローします戻り値

#peekFirst()/ PeakLast()

使用する場合も同様ですので、使用する場合は同じグループを使用してください。

Queue と Deque のこれらの API の時間計算量は O(1) です。正確には、これは償却時間計算量です。

実装クラス

実装クラスには次の 3 つがあります:

つまり、

「通常のキュー - 先入れ先出し」のセマンティクスを実装したい場合は、LinkedList または ArrayDeque を使用してそれを実現します。 #If 「優先キュー」のセマンティクスを実現したい場合は、PriorityQueue を使用します;
「スタック」のセマンティクスを実現したい場合は、ArrayDeque を使用します。
1 つずつ見てみましょう。

LinkedList と ArrayDeque のどちらを選択すればよいですか?

StackOverflow

[2]

で最も投票数の多かった回答を見てみましょう:

概要 LinkedList には他の追加のオーバーヘッドがある一方で、効率が高い ArrayDeque を使用することをお勧めします。

ArrayDeque と LinkedList の違いは何ですか?

同じ質問がまだありますが、これが私が考える最良の要約です。

ArrayDeque これは、展開可能な配列、LinkedList はリンクリスト構造です。

ArrayDeque は null 値を保存できませんが、LinkedList は保存できます。
ArrayDeque in It is more先頭と末尾の追加と削除の操作は効率的ですが、LinkedList の削除は、中間の要素を削除する必要があり、その要素が見つかった場合にのみ O(1) になります。
#ArrayDeque はメモリ使用量の点でより効率的です。
したがって、null 値を保存する必要がない限り、ArrayDeque を選択してください。
それでは、非常に上級の面接官から尋ねられた場合、どのような状況で LinkedList の使用を選択すべきでしょうか?

答：Java 6 以前。。。因为 ArrayDeque 在 Java 6 之后才有的。。

为了版本兼容的问题，实际工作中我们不得不做一些妥协。。

那最后一个问题，就是关于 Stack 了。

Stack

Stack 在语义上是后进先出（LIFO）的线性数据结构。

有很多高频面试题都是要用到栈的，比如接水问题，虽然最优解是用双指针，但是用栈是最直观的解法也是需要了解的，之后有机会再专门写吧。

那在 Java 中是怎么实现栈的呢？

虽然 Java 中有 Stack 这个类，但是呢，官方文档都说不让用了！

原因也很简单，因为 Vector 已经过被弃用了，而 Stack 是继承 Vector 的。

那么想实现 Stack 的语义，就用 ArrayDeque 吧：

Deque stack = new ArrayDeque<>();

ログイン後にコピー

Set

最后一个 Set，刚才已经说过了 Set 的特定是无序，不重复的。

就和数学里学的「集合」的概念一致。

Set 的常用实现类有三个：

HashSet: 采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。

LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。

TreeSet: 采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。

那每个 Set 的底层实现其实就是对应的 Map：

値はマップ内のキーに配置され、PRESENT は値に配置されます。これはプレースホルダーに相当する静的オブジェクトであり、各キーはこのオブジェクトを指します。

つまり、具体的な実装原則、追加、削除、変更、チェック4 つの操作、およびハッシュ競合、hashCode( )/equals()などについては HashMap の記事で説明しているのでここでは詳しく説明しませんが、まだ見ていない友達は公式アカウントの背景で「HashMap」と返信することもできます記事を参照するには~