dart - Dart 中不同的 Map 实现之间有什么区别？

Question

Dart 有一个 Map 类型，其实现如 HashMap , LinkedHashMap ，和SplayTreeMap 。这些不同的 Map 实现之间有什么区别？

Answer 1

Dart 内置了对 List、Set 和 Map 等集合的支持。 Dart 有不同的 Map 实现。了解实现方案之间的优缺点可以帮助您做出明智的决定。

(注意:这是在 Dart M3 左右编写的，因此接下来的内容可能与目前的文档不匹配。)

什么是 map ？

Map 是一个关联容器，将键映射到值。键是唯一的，并且只能指向一个值。键不能为空，但值可以为空。

map 文字

Dart 支持 Map literals ，像这样:

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

规范规定映射文字必须保持插入顺序。这意味着 accounts 是 LinkedHashMap 的实例。

规范还规定 Map 文字键必须是字符串。这将来可能会改变。

新 map ()

Dart 支持工厂构造函数，因此您可以像这样创建一个新的 Map 实例:

var accounts = new Map();

Map 类是抽象的，这意味着工厂构造函数实际上创建 Map 子类的实例。那么帐户的实际类型是什么？

早期版本的 Dart 从 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

HashMap 不能保证维持插入顺序。当您迭代 HashMap 的键或值时，您不能期望特定的顺序。

HashMap 是使用 hash table 实现的.

以下是创建新 HashMap 的示例:

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

如果您不关心维护插入顺序，请使用 HashMap。

这是source code of HashMap .

SplayTreeMap

伸展树(Splay Tree)是一种自平衡二叉搜索树，具有最近访问的元素可以快速再次访问的附加属性。它在 O(log(n)) 摊余时间内执行插入、查找和删除等基本操作。

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

SplayTreeMap 要求所有键都具有相同类型。

对于频繁存储和访问的数据(例如缓存)，伸展树(Splay Tree)是一个不错的选择。原因是它们使用树旋转将元素带到根，以便更频繁地访问。性能来自于树的 self 优化。也就是说，经常访问的元素被移动到靠近顶部的位置。然而，如果树周围的访问频率相同，那么使用伸展树(Splay Tree)映射就没有意义了。

一个示例是调制解调器路由器，它以非常高的速率接收网络数据包。调制解调器必须决定哪个数据包进入哪条线路。它可以使用映射实现，其中键是 IP，值是目的地。对于这种情况，伸展树(Splay Tree)图是一个不错的选择，因为大多数 IP 地址都会被多次使用，因此可以从树的根部找到这些地址。