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

Question

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

Answer 1

Dart内置了对List,Set和Map等集合的支持.Dart有不同的Map实现.了解实现之间的利弊可以帮助您做出明智的决策.

(注意:这是在Dart M3的时间写的,所以下面的内容可能与此时的文档不匹配.)

什么是地图？

Map是一个关联容器,将键映射到值.键是唯一的,可以指向一个且只能指向一个值.键不能为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 bug 5803声明为了制作{}和new Map返回相同的类型,new Map很快就会返回一个实例LinkedHashMap.

LinkedHashMap(或,InsertionOrderedMap)

A 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
}

这是LinkedHashMap的源代码.(如果此链接停止工作,可能是因为该类已重命名)

HashMap中

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要求所有键都属于同一类型.

对于经常存储和访问的数据(如缓存),splay树是一个不错的选择.原因是他们使用树旋转将一个元素调到根,以便更频繁地访问.性能来自树的自我优化.也就是说,频繁访问的元素移动到更靠近顶部.但是,如果同时经常访问树,那么使用splay树映射几乎没有意义.

示例情况是调制解调器路由器以非常高的速率接收网络数据包.调制解调器必须决定哪个数据包进入哪个线路.它可以使用映射实现,其中键是IP,值是目标.对于这种情况,splay树映射是一个不错的选择,因为大多数IP地址将被多次使用,因此可以从树的根目录找到它们.