52

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

4

2 回答 2

81

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

（注意：这是在 Dart M3 的时候写的，所以下面的内容可能与目前的文档不匹配。）

什么是地图？

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

地图文字

Dart 支持Map 文字，如下所示：

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

规范说地图文字必须保持插入顺序。这意味着accounts是 的一个实例LinkedHashMap。

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

新地图（）

Dart 支持工厂构造函数，所以你可以像这样创建一个新的 Map 实例：

var accounts = new Map();

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

HashMap早期版本的 Dart从new Map()构造函数中创建了一个新的实例。但是，Dart 错误 5803指出，为了生成{}和new Map返回相同的类型，new Map将很快返回LinkedHashMap.

LinkedHashMap（或 InsertionOrderedMap）

ALinkedHashMap按照插入的顺序遍历键和值。

注意： 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
}

这是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 回答
-1

有一个替代方案。

多图

import 'package:quiver/collection.dart';

algorithms() {
  var ordered = new ListMultimap();
  ordered.add('32352', 'Alice');
  ordered.add('95594', 'Bob');
  ordered.add('32352', 'Alice2');

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

  for (var value in ordered.values) {
    print(value);
  }

  // print in ascending order
  // flutter: 32352
  // flutter: 95594
  // flutter: Alice
  // flutter: Alice2
  // flutter: Bob
}
于 2019-05-28T06:52:48.723 回答