Dartの異なるMap実装の違いは何ですか？

Question

DartにはMap型があり、HashMap、LinkedHashMap、SplayTreeMapなどの実装があります。これらの異なるMap実装の違いは何ですか？

Answer 1

Dartには、List、Set、Mapなどのコレクションの組み込みサポートが組み込まれています。 Dartは異なるMap実装を持っています。実装間の長所と短所を理解することで、情報に基づいた決定を下すことができます。

（注：これは、ダートM3の頃に書かれているので、次にくるものが、この時点でドキュメントを一致しない場合があります）

地図とは何ですか？

マップは、キーを値にマッピングする関連コンテナです。キーは一意であり、唯一の値を指すことができます。キーはnullでもかまいませんが、値はnullでもかまいません。このようなダートを地図リテラルをサポートしてい

地図リテラル、：

var accounts = {'323525': 'John Smith', '588982': 'Alice Jones'}; 

スペックマップリテラルが挿入秩序を維持しなければならないことを述べています。つまり、accountsはLinkedHashMapのインスタンスです。

マップリテラルキーは文字列でなければならないという仕様もあります。これは将来変更される可能性があります。

var accounts = new Map(); 

Mapクラスは、抽象的である工場のコンストラクタは、実際に作成されます意味：あなたはこのような地図の新しいインスタンスを作成できるように

新しいマップ（）

ダーツは、工場出荷時のコンストラクタをサポートしていますMapのサブクラスのインスタンスです。では実際のタイプはaccountsですか？

ダーツの以前のバージョンでは、new Map()コンストラクタからHashMapという新しいインスタンスが作成されました。しかし、Dart bug 5803は{}とnew Mapが同じタイプを返すように、new MapはすぐにLinkedHashMapのインスタンスを返すと述べています。

のLinkedHashMap（又は、InsertionOrderedMap）は、挿入された同じ順序でキーと値を介して、

LinkedHashMap反復。

注： LinkedHashMapはおそらくInsertionOrderedMapに名前が変更されます。進行状況はDart bug 2349に従ってください。ここ

は一例であり：ここ

import 'dart:collection'; 
main() { 
    var ordered = new LinkedHashMap(); 
    ordered['32352'] = 'Alice'; 
    ordered['95594'] = 'Bob'; 

    for (var key in ordered.keys) { 
    print(key); 
    } 

    // guaranteed to print 32352, then 95594 
} 

はsource code for LinkedHashMapあります。 （このリンクが動作しなくなった場合は、クラスの名前が変更されたため、それはおそらくです）

HashMapの

AのHashMapは挿入秩序を維持する保証はありません。HashMapのキーや値を反復処理すると、特定の順序を期待できません。

HashMapは、hash tableを使用して実装されています。あなたがHashMapを使用して、挿入秩序を維持を気にしない場合は

import 'dart:collection'; 
main() { 
    var accounts = new HashMap(); 
} 

：ここ

は新しいHashMapを作成する例です。

ここにはsource code of HashMapがあります。

SplayTreeMap

スプレー木は最近アクセス要素が再びアクセスするために迅速な追加プロパティを持つ自己均衡二分探索木です。それは、O（log（n））償却時間内の挿入、参照および除去などの基本的な操作を実行します。

import 'dart:collection'; 
main() { 
    var accounts = new SplayTreeMap(); 
} 

SplayTreeMapでは、すべてのキーが同じタイプである必要があります。

スプレイツリーは、キャッシュのように頻繁に格納され、アクセスされるデータに適しています。その理由は、ツリーローテーションを使用して、より頻繁にアクセスするためにルートに要素を持ち込むからです。パフォーマンスは、ツリーの自己最適化に由来します。すなわち、頻繁にアクセスされる要素は、より近くに移動される。しかし、ツリーがまったく同じように頻繁にアクセスされる場合、スプレイツリーマップを使用する点はほとんどありません。

非常に高いレートでネットワークパケットを受信するモデムルーターがその例です。モデムは、どのパケットがどの回線に入るかを決定する必要があります。キーがIPで、値が宛先であるマップ実装を使用できます。ほとんどのIPアドレスは複数回使用されるため、ツリーのルートから見つけることができるので、このシナリオではスプレイツリーマップが適しています。