HashMap,LinkedHashMap,ConcurrentHashMap,synchronizedMap(五.まとめ)について

2699 ワード
java データ構造
前に簡単にMapと言いましたが、ここで簡単にまとめてみます.
HashMap
データ構造
配列+チェーンテーブル+赤黒ツリー.
メリット
理想的な状態:挿入と検索時間の複雑さはO(1)である.
欠点
  • 無秩序:アクセス順にソートすることも、挿入順にソートすることもできません.
  • は高同時性をサポートしていません.マルチスレッドの場合、その拡張メカニズムはデッドサイクルになります.

    • この2つの欠点に基づいて、開発者は対応するMapクラスを作成しました.
    順番のあるMap-LinkedHashMap
    データ構造
    整然としているので、HashMapに加えて、双方向チェーンテーブルを追加しました.したがって、そのデータ構造は、配列+二重チェーンテーブル+赤黒ツリーである.また、挿入順序だけでなく、そのフィールドaccessOrder(boolean)はLRUルールを開き、アクセス数に応じてソートすることができます.
        /**
     * The iteration ordering method for this linked hash map: true
     * for access-order, false for insertion-order.
     * true：    ，false：    
     * @serial
     */
    final boolean accessOrder;

    メリット
    HashMapに基づいて秩序化されたストレージを実現した.
    欠点
    HashMapと同様:高同時性はサポートされていません.
    高同時性Map_1:ConcurrentHashMap
    ConcurrentHashMapは最も多くの処理で高同時のHashMapです
    データ構造
    ConcurrentHashMapがAbstractMap実装ConcurrentMapを継承していることがわかります.ConcurrentMapはMapを継承しています.したがって,高い同時性を実現する点ではHashMapと異なるだけでなく,器データ構造も配列+チェーンテーブルである.
    メリット
  • はCASアルゴリズムを使用しており、高同時処理が可能である.しかも速度が速い.
  • は、1つのデータを処理する際に、他のデータを操作することができる.

    • 欠点
    無秩序
    高同時性Map_2:synchronizedMap
    データ構造
    前の兄弟とは違ってsynchronizedMapはCollolectionsクラスにあります.ソースコードを読むことで、synchronizedMapはsynchronizedによってオブジェクトをロックしていることがわかりますが、方法全体ではありません.呼び出しの方法はMapです.同じ配列+チェーンテーブルです
    メリット
    高同時処理可能
    欠点
    速度はConcurrentHashMapよりかなり遅く、秩序化はサポートされていません
    高同時性Map_3:Hashtable
    Hashtableは廃棄されていますが、やはり言ってみましょう
    データ構造
    Hashtableはメソッドの前にsynchronizedを付けるだけで、下位はHashMapです.だから配列+チェーンテーブル+赤黒樹です.
    メリット
    高同時処理可能
    欠点
  • 遅いです.
  • は、1つのデータを処理する際に、Map全体がロックされ、他のデータを操作することができず、限界が大きすぎる.とても実用的ではありません.

    • その他のMap
    実はTreeMap、WeakHashMapもありますが、ここでは詳しくは言いません.確かにあまり使われていません.
    各Mapまとめ:
    Map
    とくせい
    HashMap
    Mapはハッシュテーブルの実装に基づいています(Hashtableの代わりになります).キー値ペアの挿入とクエリーのオーバーヘッドは固定されています.コンテナのパフォーマンスを調整するには、コンストラクタで容量と負荷係数を設定します.
    LinkedHashMap
    HashMapと似ていますが、反復する場合、キー値ペアを取得する順序は挿入順序、または最も最近使用されていない(LRU)順序で、HashMapよりも少し遅いだけです.反復アクセスでは、チェーンテーブルを使用して内部順序を維持するため、かえって速くなります.
    TreeMap
    赤黒樹の実現に基づいている.「キー」または「キー値ペア」を表示すると、それらはソートされます(順序はComparableまたはComparatorによって決定されます).これは、結果がソートされたことを特徴とします.TreeMapはsubMap()メソッドを持つ唯一のMapであり、サブツリーに戻ることができます.
    WeakHashMap
    弱いキーマッピングで、マッピングが指すオブジェクトを解放できます.これはある特殊な問題を解決するために設計されたものです.マッピング以外にキーが参照されていない場合、このキーはゴミ回収期間で回収できます.
    ConcurrentHashMap
    同期ロックに関与しないスレッドの安全なMapです.CASアルゴリズムによる実装
    IdentityHashMap
    equals()の代わりに"="を使用してキー"を比較するハッシュマッピング.特殊な問題を解決するために設計された
    【訳】レスポンスCSSアニメーション
    systemd で CoreOS 上の Docker コンテナのログを集約・ルーティングする