Javaのデータ構造とは何ですか?-＆＃＆はじめる-php.cn

Java データ構造には、1. List、2. Vector、3. ArrayList、4. LinkedList、5. Set、6. HashSet、7. LinkedHashSet、8. SortedSet、9. Map、10. HashMap が含まれます。。

Javaのデータ構造とは何ですか?

#この記事の動作環境: Windows10 システム、Java 1.8、thinkpad t480 コンピューター。

Java には一般的に使用されるデータ構造がいくつかあります。それらは主に 2 つの主要なインターフェイスに分かれています: コレクションとマップ (インターフェイスはメソッドを提供するだけで実装は提供しません)、およびプログラムで最終的に使用されるデータ構造です。インターフェースのデータ構造クラスから継承されます。

Collection---->Collections   
Map----->SortedMap------>TreeMap          Map------>HashMap
Collection---->List----->(Vector \ ArryList \ LinkedList)
Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)

ログイン後にコピー

List (インターフェイス)

List は順序付けされたコレクションです。このインターフェイスを使用して、各要素の挿入位置を正確に制御します。ユーザーはインデックス (配列の添字と同様にリスト内の要素の位置) を使用してリスト内の要素にアクセスできます。これは Java 配列と同様です。

Vector

配列に基づくリスト (Array) は、実際には、配列にはない使用できるいくつかの関数をカプセル化するため、配列の制限を回避するのは難しく、パフォーマンスも低下します。配列を超えては不可能です。したがって、可能であれば、配列をもっと使用する必要があります。もう 1 つの非常に重要な点は、Vector がスレッド同期 (同期) されることです。これは、Vector と ArrayList の重要な違いでもあります。

ArrayList

Vector と同様、配列に基づくリンクリストですが、ArrayList が同期されていない点が異なります。そのため、パフォーマンスの点では Vector よりも優れていますが、マルチスレッド環境で実行する場合は、スレッドの同期を自分で管理する必要があります。

LinkedList

LinkedList は、前の 2 つのリストとは異なり、配列に基づいていないため、配列のパフォーマンスによって制限されません。

各ノード (Node) には、コンテンツの 2 つの側面が含まれています:

1. ノード自体のデータ;

2. 次のノード (nextNode) の情報。

したがって、LinkedList にアクションを追加したり削除したりするときに、配列ベースの ArrayList のように大量のデータを移動する必要はありません。 nextNodeの関連情報を変更するだけで実現できるのがLinkedListの利点です。

リストの概要

すべてのリストは、キーと値のペアではなく、異なるタイプの単一のオブジェクトで構成されるテーブルのみを保持できます。例: [tom,1,c]

すべてのリストには同じ要素を含めることができます。たとえば、Vector には [tom,koo,too,koo] を含めることができます。

すべてのリストには There を含めることができます[tom,null,1] などの null 要素です。

配列ベースのリスト (Vector、ArrayList) はクエリに適していますが、LinkedList は追加および削除操作に適しています

Set (インターフェイス)

Set は繰り返し要素を含まない Collection です

HashSet

Set と List はどちらも Collection インターフェイスを実装していますが、実装方法はまったく異なります。リストは基本的に配列に基づいています。ただし、Set は HashMap に基づいて実装されており、これが Set と List の根本的な違いです。 HashSet の格納方法は、HashMap の Key を Set の対応する格納項目として使用します。 HashSet の add(Object obj) メソッドの実装を見れば一目瞭然です。

LinkedHashSet

HashSet のサブクラス、リンクリスト。

SortedSet

Ordered Set は SortedMap を通じて実装されます。

Map (インターフェイス)

Map はキーオブジェクトと値オブジェクトを関連付けるコンテナであり、値オブジェクトは Map などになることがあり、複数レベルのマッピングを形成します。 Set などのキーオブジェクトの場合、Map コンテナ内のキーオブジェクトを繰り返すことはできません。これは、検索結果の一貫性を維持するためです。同じキーオブジェクトが 2 つある場合は、値を取得する必要があります。そのキーオブジェクトに対応するオブジェクトです。問題が発生します。おそらく、取得したものは、あなたが考えていた値オブジェクトではなく、その結果、混乱が生じるでしょう。したがって、キーの一意性は非常に重要であり、キーの性質と一致しています。セット。

もちろん、使用中に、特定のキーに対応する値オブジェクトが変更される場合がありますが、この場合、最後に変更された値オブジェクトがそのキーに対応します。値オブジェクトには一意性の要件はありません。値オブジェクトに任意の数のキーを問題なくマッピングできます (ただし、使用に不便が生じる可能性があります。何を取得しているのかわかりません。それに対応する値オブジェクトは鍵）。

(無料ビデオチュートリアル共有:

java ビデオチュートリアル)

HashMap

ハッシュテーブルに基づいた Map インターフェイスの実装。この実装では、すべてのオプションのマッピング操作が提供され、null 値と null キーが許可されます。 (HashMap クラスは、同期されていないことと null を許可することを除いて、Hashtable とほぼ同じです。) このクラスはマップの順序を保証せず、特に順序が不変であることを保証しません。さらに、HashMap はスレッドセーフではありません。つまり、Hashtable はスレッドセーフですが、マルチスレッド環境では問題が発生する可能性があります。

TreeMap

TreeMap はキーを順番に格納します。

HashTable

(1) Hashtable はハッシュテーブルであり、格納される内容がキー Valueペア（キーと値）のマッピング。

(2) Hashtable は Dictionary を継承し、Map、Cloneable、および java.io.Serializable インターフェイスを実装します。

(3) ハッシュテーブル関数はすべて同期的です。つまり、スレッドセーフです。キーも値も null にすることはできません。

一般的に使用されるいくつかのクラスの違い

1. ArrayList: 単一要素、高効率、主にクエリ

2 に使用されます。ベクター: 単一要素、スレッドセーフ、主にクエリ

3 に使用されます。 LinkedList: 単一要素。主に挿入と削除に使用されます

4。 HashMap: 要素はペアになっており、要素は空の場合もあります (

5)。ハッシュテーブル: 要素はペアであり、スレッドセーフであり、要素を空にすることはできません

Vector、ArrayList、LinkedList

ほとんどの場合、パフォーマンスの点では ArrayList が最高ですが、要素がコレクションに必要な LinkedList は頻繁に挿入と削除を行うとパフォーマンスが向上しますが、これら 3 つのパフォーマンスは配列ほど良くありません。また、Vector はスレッド同期されます。したがって:

配列を使用できる場合 (要素の型と配列の長さが固定)、List の代わりに配列を使用してみてください。

頻繁に削除がない場合は、スレッドの問題については、ArrayList を優先します。

マルチスレッド条件で使用する場合は、Vector を検討できます。

削除と挿入が頻繁に行われる場合は、Vector を検討してください。挿入が必要な場合は、LinkedList が機能します。

何も分からない場合は、ArrayList を使用しても問題ありません。

スタック

スタックは、一方の端でのみ挿入および削除できる特殊な線形リストです。先入れ後出しの原則に従ってデータを保存します。最初に入力されたデータはスタックの一番下にプッシュされ、最後の

データはスタックの一番上に置かれます。読み取られる場合、データはスタックの一番上からポップされます (最後のデータはスタックの一番下にプッシュされます)。1 つが読み取られます)。

Queue

テーブルの前端 (前) での削除操作と、テーブルの後端 (後) での挿入操作のみを許可する特殊な線形テーブル。

挿入操作を実行する端はキューの末尾と呼ばれ、削除操作を実行する端はキューの先頭と呼ばれます。キュー内に要素が存在しない場合、それは空のキューと呼ばれます。

配列

プログラミングでは、処理の便宜上、同じ型の複数の変数が順序付けられた形式で編成されます。同様のデータ要素を順番に並べたものを配列と呼びます。 C 言語では、配列は構築されたデータ型です。配列は複数の配列要素に分解でき、これらの配列要素は基本データ型または構築型になります。したがって、配列要素の種類に応じて、配列は数値配列、文字配列、ポインタ配列、構造体配列などのさまざまなカテゴリに分類できます。

リンクリスト

物理ストレージユニット上の非連続かつ非順次のストレージ構造。データ要素の論理的順序は、リンクリスト内のポインタリンク順序によって実現されます。

リンクリストは一連のノードで構成され (リンクリストの各要素はノードと呼ばれます)、ノードは実行時に動的に生成できます。各ノードは 2 つの部分で構成されます。

1 つはデータ要素を格納するデータフィールドで、もう 1 つは次のノードのアドレスを格納するポインタフィールドです。

ツリー

ツリーはn個(n>0)のノードを含む有限集合Kであり、Kには関係Nが定義されています。Nは次の条件を満たします。

(1) ノード k0 は 1 つだけあり、関係 N に対する先行ノードはありません。K0 はツリーのルートノードと呼ばれます。ルート (ルート)

(2) K0 を除いて、k の各ノードは関係 N の先行ノードを 1 つだけ持ちます。

(3) K の各ノードは、関係 N に対して m 個の後続ノード (m>=0) を持つことができます。

ヒープ

コンピュータサイエンスでは、ヒープは特別なツリーデータ構造であり、各ノードには値があります。通常、ヒープのデータ構造と呼ばれるものは、バイナリヒープを指します。ヒープの特徴は、ルートノードが最小 (または最大) の値を持ち、ルートノードの 2 つのサブツリーもヒープであることです。

ハッシュテーブル