52

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

4

2 に答える 2

81

Dart には、List、Set、Map などのコレクションのサポートが組み込まれています。Dart にはさまざまな Map 実装があります。実装間の長所と短所を理解することは、十分な情報に基づいた決定を下すのに役立ちます。

(注: これは Dart M3 の頃に書かれているため、以下の内容は現時点ではドキュメントと一致しない可能性があります。)

マップとは

Map は連想コンテナであり、キーを値にマッピングします。キーは一意であり、1 つの値のみを指すことができます。キーを null にすることはできませんが、値を null にすることはできます。

マップ リテラル

Dart は、次のようにMap リテラルをサポートしています。

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

仕様によると、マップ リテラルは挿入順序を維持する必要があります。これaccountsは のインスタンスであることを意味しますLinkedHashMap。

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

新しいマップ()

Dart はファクトリ コンストラクターをサポートしているため、次のように Map の新しいインスタンスを作成できます。

var accounts = new Map();

このMapクラスは抽象的です。つまり、ファクトリ コンストラクターは実際に のサブクラスのインスタンスを作成しますMap。では、実際の型はaccounts何ですか?

Dart の以前のバージョンは、コンストラクターHashMapからの新しいインスタンスを作成しましたnew Map()。ただし、Dart バグ 5803は、同じ型を作成{}して返すために、すぐに のインスタンスを返すと述べています。new Mapnew MapLinkedHashMap

LinkedHashMap (または InsertionOrderedMap)

ALinkedHashMapは、挿入されたのと同じ順序でキーと値を反復処理します。

注: LinkedHashMap は、おそらく InsertionOrderedMap に名前が変更されます。進行状況については、Dart バグ 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
}

LinkedHashMapのソース コードは次のとおりです。(このリンクが機能しなくなった場合、おそらくクラスの名前が変更されたことが原因です)

ハッシュマップ

HashMap には、挿入順序が維持されるという保証はありません。HashMap のキーまたは値を反復処理する場合、特定の順序は期待できません。

HashMap は、ハッシュ テーブルを使用して実装されます。

新しい HashMap を作成する例を次に示します。

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

挿入順序を維持する必要がない場合は、HashMap を使用してください。

HashMapのソースコードは次のとおりです。

SplayTreeMap

スプレイ ツリーは、最近アクセスした要素にすばやくアクセスできるようにする追加のプロパティを備えた自己均衡二分探索ツリーです。O(log(n)) の償却時間で、挿入、検索、削除などの基本的な操作を実行します。

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

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

スプレイ ツリーは、キャッシュなど、頻繁に保存およびアクセスされるデータに適しています。その理由は、ツリーのローテーションを使用して要素をルートに移動し、より頻繁にアクセスできるようにするためです。パフォーマンスは、ツリーの自己最適化によってもたらされます。つまり、頻繁にアクセスされる要素が上部に移動されます。ただし、ツリーがどこからでも等しく頻繁にアクセスされる場合、スプレイ ツリー マップを使用する意味はほとんどありません。

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

于 2013-02-18T06:54:58.730 に答える