Dart中不同的Map实现之间有什么区别？ [英] What are the differences between the different Map implementations in Dart?

问题描述

Dart有一个Map类型，实现类似于HashMap，LinkedHashMap和SplayTreeMap。这些不同的Map实现有什么区别？

解决方案

Dart内置对集合的支持如列表，集合和地图。 Dart有不同的Map实现。了解实施之间的利弊可以帮助您作出明智的决定。

（注意：这是围绕Dart M3的时间写的，因此以下可能不匹配

什么是地图？

地图是关联容器，映射键到值。键是唯一的，并且可以指向一个且只有一个值。

地图文字

Dart支持地图文字，像这样：

  var accounts = {'323525'：'John Smith'，'588982' ：'Alice Jones'}; 
  

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

规范还说，映射键必须是字符串。

new Map（）

Dart支持工厂构造函数，因此您可以创建Map的新实例，如下所示：

  var accounts = new Map 
  

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





早期版本的Dart创建了一个<$ c $从新的Map（）构造函数中创建c> HashMap 。但是， Dart bug 5803 声明，为了使 { } 和新映射返回相同的类型， new Map LinkedHashMap 。

LinkedHashMap（或InsertionOrderedMap）

注意：

/ em> LinkedHashMap可能会被重命名为InsertionOrderedMap。按照 Dart bug 2349 获取进度。

这是一个例子：

  import'dart： 
 main（）{
 var ordered = new LinkedHashMap（）; 
 ordered ['32352'] ='Alice'; 
 ordered ['95594'] ='Bob'; 
 
 for（var key in ordered.keys）{
 print（key）; 
} 
 
 //保证打印32352，然后95594 
} 
  

b $ b

以下是源代码LinkedHashMap 。 （如果此链接停止工作，则可能是因为该类已重命名）

HashMap

保证插入顺序。当你遍历一个HashMap的键或值，你不能期望一个特定的顺序。

HashMap是使用哈希表。

下面是创建一个新的HashMap的示例：

  import'dart：collection'; 
 main（）{
 var accounts = new HashMap（）; 
} 
  

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

这是 HashMap的源代码。

SplayTreeMap

- 具有附加属性的平衡二叉搜索树，最近访问的元素可以快速访问。它在O（log（n））分摊时间中执行基本操作，例如插入，查找和移除。

  import'dart：collection'; 
 main（）{
 var accounts = new SplayTreeMap（）; 
} 
  

SplayTreeMap要求所有键的类型相同。

展开树对于经常存储和访问的数据（如高速缓存）是一个不错的选择。原因是它们使用树旋转将元素带到根以更好地频繁访问。性能来自树的自优化。也就是说，频繁访问的元素被移动到更靠近顶部。

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

Dart has a Map type, with implementations like HashMap, LinkedHashMap, and SplayTreeMap. What's the difference between those different Map implementations?

解决方案

Dart has built-in support for collections like List, Set, and Map. Dart has different Map implementations. Understanding the pros and cons between implementations can help you make an informed decision.

(Note: this is written around the time of Dart M3, so what follows might not match the docs at this moment.)

What is a Map?

A Map is an associative container, mapping keys to values. Keys are unique, and can point to one and only one value. A key cannot be null, but a value can be null.

Map Literals

Dart supports Map literals, like this:

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

The spec says that map literals must maintain insertion order. This means that accounts is an instance of LinkedHashMap.

The spec also says that Map literal keys must be Strings. This might be changed in the future.

new Map()

Dart supports factory constructors, so you can create a new instance of Map like this:

var accounts = new Map();

The Map class is abstract, which means the factory constructor actually creates an instance of a subclass of Map. So what is the actual type of accounts ?

Earlier versions of Dart created a new instance of HashMap from the new Map() constructor. However, Dart bug 5803 states that in order to make {} and new Map return the same type, new Map will soon return an instance of LinkedHashMap.

LinkedHashMap (or, InsertionOrderedMap)

A LinkedHashMap iterates through keys and values in the same order they were inserted.

Note: LinkedHashMap will probably be renamed to InsertionOrderedMap. Follow Dart bug 2349 for progress.

Here is an example:

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
}

Here is the source code for LinkedHashMap. (if this link stops working, it's probably because the class was renamed)

HashMap

A HashMap has no guarantee of maintaining insertion order. When you iterate through a HashMap's keys or values, you cannot expect a certain order.

A HashMap is implemented using a hash table.

Here is an example of creating a new HashMap:

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

If you don't care about maintaining insertion order, use HashMap.

Here is the source code of HashMap.

SplayTreeMap

A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log(n)) amortized time.

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

A SplayTreeMap requires that all keys are of the same type.

A splay tree is a good choice for data that is stored and accessed frequently, like caches. The reason is that they use tree rotations to bring up an element to the root for better frequent accesses. The performance comes from the self-optimization of the tree. That is, frequently accessed elements are moved nearer to the top. If however, the tree is equally often accessed all around, then there's little point of using a splay tree map.

An example case is a modem router that receives network packets at very high rates. The modem has to decide which packet go in which wire. It can use a map implementation where the key is the IP and the value is the destination. A splay tree map is a good choice for this scenario, because most IP addresses will be used more than once and therefore those can be found from the root of the tree.

这篇关于Dart中不同的Map实现之间有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！