Javaデータ構造

インタフェース一覧

このインターフェイスの2つの最も使用される実装は、ArrayListとLinkedListです.各々についてより深く行きましょう

アレイリスト

この構造体の名前から、内部のそれが単純な配列を使用することを理解します.
しかし、この構造は動的なサイジングを持っています.許可ensureCapacity() 使用する単純配列を増やすメソッドです.このメソッドがコールされた場合、それは使用される配列のロードをチェックし、必要に応じて容量を持つ新しい配列を作成します.呼び出しによってSystem.arraycopy 古い配列から新しい要素まですべての要素をコピーします.get , remove要素は単純な配列を持っているので、o ( 1 ) -定数時間をとります.インデックス操作による検索はo ( n )操作を行います.なぜなら、全ての配列に対してトラバースする必要があるからです.

リンケリスト

この構造体は、リスト内の次と前のオブジェクトへのリンクを持つオブジェクトに基づいています.この構造体は、ArrayListから1つだけの利点を持ち、ArrayListで実行するよりも速く実行を開始します.それで、この構造はいくつかの仕事によいかもしれません、しかし、私はこの仕事に直面しませんでした.

スタック

この構造は、次のメソッドを提供します.また、LIFOを実装しています.たとえば、スタック要素10 , 2123 -を呼び出しポップまたはロールで設定すると、123となります.しかし、ポップからポップ123をポップします.poll要素をスタックから削除しない.内部では単純な配列を使用します.

インタフェースセット

このデータ構造は、ストア専用の要素のみを作成します.その要素をチェックする方法は、コレクションに含まれていません.このためにいくつかの実装があります.それについて話しましょう.最初のハッシュ設定は、オブジェクトからEqualsを呼ぶことによって、要素を比較するでしょう.番目のトレセットは、比較的インターフェイスを実装する要素のみを格納するか、またはTreeSetのコンストラクター実装を使用して比較器を提供する必要があります.

ハセット

内部ではHashMapを使用します.この構造体は挿入順序を保証しません.これは、挿入順序から他の順序で要素を取得するこのコレクションを横断しようとします.この実装では、基本操作のための一定の時間があります.それは定数関数のために実行されるハッシュ関数によって提供されました.

トリーレット

ハッシュマップに基づいてハッシュされているなら、treemapに基づくtreeset.このデータ構造は、add、remove、includeのような操作のための時間o(log(n))を保証します.ツリーを使用しているので、これは提供されます.このコレクションは、自然注文を保証します.例えば、

Set numbers = new TreeSet<>();

numbers.add(2);

numbers.add(1);

for(Integer number : numbers) { System.out.println(number);} 

コンソールで印刷されます

1
2

リンケダットセット

このコレクションは次のように有名です-以前の実装とは異なり、挿入順序を保証します.したがって、このデータ構造を反復処理することにより、挿入順序で要素が表示されます.LinkedHashMapを使用して、以前の設定実装のように.要素を追加しようとすると、Alredyはコレクションに追加されます-このアクションは要素の順序に影響しません.基本的な操作のために、追加のためのcontant時間o(n)を提供します、除去、操作は含みます.NULL要素を含めることができます.このコレクションのパフォーマンスのために、2つの変数-初期容量とloadfactorを使用します.最初に、内部の使用されたマップの初期容量を記述してください、そして、マップでバケツのカウントが増加しなければならないとき、2番目はdeclareです.

定着する

この実装は特にenum型で作成されました.ContainsAllのような各マス操作は、このメソッドenumsetインスタンスに渡すと、より高速に実行されます.このセットを繰り返すと、要素の自然な順序が表示されます.返された反復子がConcurrenctModificationExceptionをスローしません.また、イテレータは変更を示すかもしれません.すべての基本的な操作は、contant時間で実行されます.

Navigableset

この実装では、セットのナビゲーションなどの良いオプションがあります.それは、私たちが提供するより低いかより大きい要素を得るかもしれないことを意味します.また、私たちは、我々が提供したより大きいかより低い要素のセットを得るかもしれません.また、このコレクションを逆シリアルメソッド

インタフェースキュー

このコレクションは、最初のin、first outを意味するFIFOメカニズムを使用します.このコレクション要素では、いくつかの操作を実行する前に保存します.アドインなどのすべての基本操作が存在します.しかし、この方法は2つのバージョンに存在する.操作が失敗した場合、最初のバージョンは例外をスローし、別のバージョンは例外をスローされず、null . 許可するnull この構造に.しかし、このインターフェイスを実装するLinkedListは、null 要素.このメソッドは、同時アクセスを行うメソッドを提供しません.コンカレント環境で使用キューには、ブロックするメソッドをブロックします.

堤防

この実装では、開始と終了の両方のキューで作業を行うことができます.Deはダブルエンドの頭字語です.が指定されたサイズのキューを作成することもできます.また、キューとして基本操作のメソッドの2つのバージョンが存在します.操作が失敗した場合、もう一つのバージョンは特別な値を返します.インデックスアクセスがない.

アレイ

私たちの名前から、このキューが単純な配列に基づいていることを明確に理解してください.必要に応じて配列の容量を確保し、容量を確保します.より多くの操作は、償却された時間のために実行されます.

prioritydeque

このキューの実装の主な原則は、コレクションに新しい要素を追加するときに、コレクションで正しい順序でソートメソッドを呼び出すことです.この文脈では何が優先ですか?シンプルで、トレセットとして要素を選択する必要がありますいくつかの属性を比較する必要がありますか、このコレクションであなたの要素の正しい順序の比較器を提供する必要があります.メソッドpoll(このコレクションから削除しない)を呼び出すと、現在の時点で最大の優先度を持つ要素が得られます.このコレクションでは、追加などの操作のためのlogariphmの速度を提供しています/削除/プルなどの操作のための線形時間を含む.

インタフェースマップ

ハッシュマップ

この関数は、ハッシュ関数の中でこの構造体をクリアします.また、この構造では、null要素をキーまたは値として置くことができます.これを繰り返すと、要素は挿入順に表示されません.この構造体のパフォーマンスには、コンストラクタを通じて渡される2つのパラメータを使用します.それは負荷率と初期容量です.初期容量は、バケットのカウントを決定します.ロードファクタは、バケツのカウントを確実にするために呼び出しメソッドを決定します.

ConcurrentHashMap

このマップ実装では、同時使用に必要です.代わりにハッシュマップをマップのスレッドセーフ実装です.このマップのエンティティは、すべてのスレッドがこのエンティティの実際のバージョンを持つ必要があることを意味します.

Navigablemap

このインターフェイスはSortMapインターフェイスを拡張し、マップ要素を横切ってナビゲートするメソッドを追加しました.このメソッドはnull . は、StradingingMapを呼ぶことによって、まっすぐで逆の順序で横断します.また、マップのようなマップの一部を抽出する方法を提供するナビゲートメソッドがあります.(サブ/ヘッド/テール)マップメソッドを含むより低い、より高い境界.このメソッドの2つのバージョンが存在するのと同じように、get last and first要素のメソッドがあります.

踏切

それは、ナビゲーション可能な地図に基づく赤い黒い木です.要素は、自然な順序で、または、コンストラクタの向こう側に提供されなければならないコンパレータによって分類されます.

コモン

この構造体の全ては、concurentashmapを除外するのはスレッドセーフではない.つまり、共有リソースを持たなければならないスレッドがいくつかあります.このすべてはあなたの仕事に適していません.
また、あなたが得たトラバース操作でコレクションを変更しようとするときにも気付きましたConcurrentModificationException あなたがトラバース操作でコレクションを変更しようとするための信号.それは許されない!この操作のために、Javaの特別なパッケージにある同時データ構造を使用しなければなりません.
UPD
コメントにも注目ConcurrentModificationException ループを繰り返して要素を削除しようとするとスローされます.繰り返しのコレクションから要素を削除したい場合.イテレータを使用する必要があります.

while(iterator.hasNext()) {
    if (iterator.next() == 1) {
        iterator.remove();
    }
}

ありがとう！

ツイッターで私について来てください