jdkに1つまたは別の標準アルゴリズムの実装があるかどうかを定期的にチェックして、同様のレビューを行うというアイデアが浮上しました。 興味深いのは、多くの既知のデータ構造の存在/不在の理由です。
レビューの形式-jdkの構造とアルゴリズムの主要なプロパティと機能のみ、詳細と詳細-javadocで記述されているか、ソースで簡単に見つけることができます。
何かを見逃した場合は、建設的な批判と集合的な心を願っています。
十分なイントロなので、現在のjdk 7に含まれるものとその理由を見てみましょう。
構造
スタック
Jdkには古いスタック（ Stack ）があります。これは、javaのリリース以降に存在し、推奨されなくなりました。複雑で奇妙です。Vectorから継承します。
なぜこれがすべて通常のスタックであり、なぜインターフェイスではないのですか？完全に明確ではありませんが（ 2回以上説明されています： 1、2 ）、それはベクター自体と同じ設計エラーのように見えます。
さらに、javadoc自体は、 代わりにDequeの使用を推奨しています 。
Dequeは、スタック操作（プッシュ、ポップ、isEmpty、サイズ）を含む双方向キュー （OのLIFO + FIFO（1））のインターフェイス（api）です。 少し前のjdk（1.6以降）で利用可能。
もちろん、これらのスタック操作がStackインターフェイスにあり、Dequeがそれを継承する場合は簡単ですが、Stackが既に存在し、下位互換性がJavaの「すべて」であるため、通常のデザインを犠牲にする必要がありました。
Dequeの実装はArrayDequeとLinkedListであり、これらを組み合わせて通常のキューも実装するため、後で検討します。
キュー
次に、キューを確認します。 ここですべてがうまく、デザインはまともです。
キュー -FIFOキューインターフェイス（api）、先頭に追加、Oで末尾から削除（1）。
主な実装はArrayDeque 、動的に拡張する配列に基づいた循環バッファー （いっぱいになると2倍になる）、およびLinkedList （従来の二重リンクリスト）で、サイズは制限されません。 奇妙なことに、最初のものはランダムアクセス （インデックス付きの追加/削除/取得）をサポートしません。2番目のものはリンクリストのO（n）反復中にサポートします。
同じ実装は、前述の双方向キューを実装します。つまり、末尾からの削除と先頭への追加もO（1）です。
次に、jdk 1.5+でPriorityQueueが追加されました。これは実際にはキューコントラクトに違反しています。 要素は末尾から取得されるのではなく（先頭にも配置されない）、それらの優先順位に従って取得されます。
これは、上部にある拡張可能なバイナリヒープに基づいて構築されます -最小要素（そのコンパレータによる）、いっぱいになると、サイズが1.5倍になります。 したがって、追加/削除はO（log N）、最小（ヘッド）への参照はO（1）です。
BlockingQueue、TransferQueue、ConcurrentLinkedQueue、ConcurrentLinkedDequeなど、残りのタイプのキューはマルチスレッドです。
BlockingQueueの実装（ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue）は、オリジナルの同期バージョンの一種です。 ほとんどすべての操作は同期的に実行されます（ブロックされます）。 これにはDelayQueueも含まれます。これも同期され、内部でPriorityQueueを使用します。
SynchronousQueue、TransferQueue（LinkedTransferQueue）、ConcurrentLinkedQueue、ConcurrentLinkedDequeは異なるアプローチに基づいていますが、マルチプロセッサ環境で並列化されたCAS命令を使用してリンクリストで非ブロッキングキューアルゴリズムを使用します。 詳細な説明はソースにあります。
このクラスのアルゴリズムは非常に広範囲で新しい素材であり、まだ完全に標準化および構造化されているわけではないため、このレビューの範囲外であり、別の記事のトピックではありません。
優先度キュー（ヒープ）
すでに述べたように、1.5からはユニバーサルPriorityQueueがあり、さらにjdkのヒープの別の実装があります。 これは古くからあるTimerであり、TaskQueueの内部クラシックです（上に-最小待機時間のタスク）。 当然、これは閉じた実装であり、タイマーとは別に使用できません。
リスト
ご存知のように、シーケンシャルアクセスおよび/またはランダムアクセスがあります。
Javaでは、リストはリストであり、2つの主要な実装、最初はArrayListであり、 動的に拡張する配列の中心でランダムアクセスをサポートします（充填時に1.5倍になります）が、要素を削除するときにそれ自体を狭めません、これのために提供されたメソッド（trimToSize ）
2つ目は、すでに説明したLinkedList、つまり二重にリンクされたシーケンシャルアクセスリストです。サイズは、空きjvmメモリによってのみ制限されます。 ランダムアクセスメソッド（インデックスによる）も存在しますが、既に述べたように、ここではO（n）で実行されます
何らかの理由で、Javaコレクションには単純な単一リンクリストはありませんが、単純なスタックだけでなく、おそらく害はありません（リンクオーバーヘッドが2倍少なくなります）。
マルチスレッド環境でリストを使用するには、CopyOnWriteArrayList（変更操作はO（n））、ラッパー（synchonizedList）、および古いVectorがあります。
キャラクターテーブル
バイナリツリーとハッシュテーブルで表されます。
ツリーはTreeMap（TreeSet）、SortedMap（SortedSet、それぞれ）の実装であり、古典的な赤黒木に基づいています 。 O（log N）に対して保証された、バランスのとれた基本操作、サイズ無制限。
jdkには他の種類のツリーはありません。
ハッシュテーブル-HashMap（HashSet）は、おそらくチェーンで動的に拡張するハッシュテーブル上に構築されたJavaで最もよく使用される構造であり、それが意味するすべてのことです。パフォーマンスは、最悪の場合O（N）の関数のハッシュに依存します。 サイズが指定されたloadFactorに達すると、サイズは2倍になります。 また、不正なハッシュ関数から保護するために、hashCode（）呼び出しの結果にトリッキーなビット演算が適用されるダブルハッシュが使用されることも注目に値します。
ハッシュテーブルのjdk実装があり、 オープンアドレッシング（線形プローブ）があります。 それらの1つはIdentityHashMapです。これは、データキャッシングを改善するために、キーと値が同じ配列に隣り合って格納される場合の古典的な線形プローブの最適化も使用します（javadoc：
2番目の実装は非常に具体的です。ThreadLocal要素（内部の非表示の古典的なThreadLocalMap）の格納にのみ使用され、もちろん使用できません。
マルチスレッドバージョン：ConcurrentHashMap、synchronizedMapラッパー、HashtableおよびConcurrentSkipListMap。 ラッパーは当然、通常のHashMapの単なるブロッキングバージョンであり、Hashtableも同じです。ConcurrentHashMapは 、重要なセクションをカットできるようにするロックストライピングバージョンです（ JCiPで読むのが良いです 、 ここからの抜粋です ）。
ConcurrentSkipListMapは、ハッシュテーブルに適合した同じ名前のアルゴリズムの非ブロッキングバージョンです（詳細については、ソースを参照してください）。
セットはハッシュテーブルを介して実装されているため、セットセット（重複を許可しない）はセットであるため、ハッシュテーブルについて述べられていることはすべてセットに当てはまります。
カウント
グラフ構造とアルゴリズムはjdkで表されません。 したがって、この場合、サードパーティのライブラリのみを使用することになります
行
標準実装は、Unicode文字の配列に基づいています。 バージョン1.7_17から、サブストリングがコピーされるため、サブストリングのパフォーマンスがO（n）になったことを思い出してください。
部分文字列を検索するために、最悪の場合にO（N * M）を与える単純な検索アルゴリズムが使用され、有限状態マシン（Knuth-Morris-Prattなど）で構築された効率的なアルゴリズムではないことが興味深いです。
いくつかの理由があります：第一に、再び、アルファベットサイズがUTF文字（〜65K）で大きいため、ステートマシンを格納するためのオーバーヘッドが大きくなりますが、検索アルゴリズムはインプレース（追加のメモリは使用されません）です。
そして、第二に、平均的なラインでのパフォーマンス-これでは、明らかに、検索は他のアルゴリズムに大きな損失を与えません。
ソートでも同じです。 カウントによる行の効率的なソート （LSD、MSDなど）がありますが、jdkはオブジェクトの標準を使用し、ほとんどの行がそれほど変わらない場合（Mは平均行長）にO（M * N * log N）を与えます。
理由は同じです。カウントソートでは、UTFアルファベットサイズの補助配列が使用されるため、平均的な統計入力データでは非効率的になります。
アルゴリズム
仕分け
ソートオプションに関してjdk7には多くの変更があり、トピックは繰り返し議論されています。このトピックに関する情報と記事はたくさんあります。 このレビューをさらに詳しくアドバイスできます。
要するに、jdkで現在利用可能な並べ替えの実装の実際のリスト： TimSort-デフォルトでオブジェクトを並べ替え、 マージ -オブジェクト、古いバージョン（システムプロパティに含まれる）、プリミティブではデュアルピボットクイックソート 、バイト/文字配列用カウントソートが使用され、すべての場合に小さな配列に対して挿入ソートが使用されます。
コレクションの並べ替えCollections.sort（List ...）は、配列にコピーし、並べ替えてからコレクションを上書きすることで引き続き実行されます。 したがって、オーバーヘッドなしでは、これは標準ツールでは実行できませんが、リンクリストのインプレースソートはおそらく害になりません。
文字列を並べ替えるには、オブジェクトバージョンも使用されます。その理由は上記のとおりです。
検索する
従来のバイナリ検索は 、ランダムアクセスをサポートするリストだけでなく、プリミティブとオブジェクトのすべての配列に対して存在します。
さらに、コレクションにはリンクリストのバージョンがあります。 リンクリストの並べ替えは意味をなさないことがわかりましたが、バイナリ検索が必要でしたが、そこにはO（log N）に近いパフォーマンスがないため、あまり意味がありませんでした。
正規表現
非決定性有限状態マシン（ NFA ）およびバックトラッキングに基づく従来の実装が使用されます。 つまり 指数関数的複雑度 O（m ^ N）、縮退値の最悪の場合、例：
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".matches("(a|aa)*b")
いわゆる 「順序付けられた交替」（通常の代替？）-これは、最も具体的（長い）ではなく、いくつかから最初の一致を見つけた直後に検索が停止する場合です。
ハッシュ関数、チェックサム
jdkのhashCode計算には6つの整数アルゴリズムがあり、デフォルトではPark-Miller_random_number_generatorが使用されます。これはHaberに関する最新の記事です。
標準的な業界標準のハッシュアルゴリズム（SHA- *、MD5、およびバリエーション）もあります-MessageDigest
チェックサムを計算するために、 Adler-32 （ javadoc ）およびCRC32 （ javadoc ）アルゴリズムの実装がまだあります
圧縮
Jdkには、標準のdeflate圧縮アルゴリズム（Deflater）の実装と、それに基づくzip / gzipがあります。 これはすべてjava.util.zipパッケージに含まれています
おわりに
ご覧のとおり、javaの古典的なデータ構造は完全には表現されていませんが、ほぼ同時に、スレッドセーフバージョンにはいくつかのオプションがあります。
不足しているのは未解決の質問です。 たとえば、jdkでUnion-Findが必要かどうかを議論できますが、最も普遍的であると主張する言語のソーシャルネットワーク時代のグラフ構造とアルゴリズムの欠如-