• This article has been published with permission on OpenFlutter.

Version all, reproduced please indicate the source.

Dart has several built-in Collections, such as sets, Lists, and Maps. Understanding their implementation strengths and weaknesses will help you figure out how to use them.

This article is demonstrated under Dart 2.1.1. Please correct any mistakes.

What is the Map

A Map is an associative container that maps keys to values. Keys are unique and can point to one and only one value, but the value can be repeated. The key cannot be NULL, but the value can be NULL.

The Map literals

Dart supports Map literals, so you can create a Map object as follows:

var gifts = {
  // Key: Value
  'first': 'partridge'.'second': 'turtledoves'.'fifth': 'golden rings'
};
Copy the code

The specification states that Map literals must maintain insertion order. This means that Gifts are instances of LinkedHashMap. Let’s verify:

   print("type of gifts:${gifts.runtimeType}");
   //type of gifts:_InternalLinkedHashMap<String, String>
Copy the code

new Map()

Dart supports factory constructors, so we could also create a Map like this:

var gifts= new Map();
Copy the code

Starting with Dart2,new is optional. No longer mention.

Map, however, is an abstract class, which means that the code above is actually an instance created by a subclass of Map. So what is the type of gifts? Again, let’s print:

   print("type of gifts:${gifts.runtimeType}");
  // type of gifts:_InternalLinkedHashMap<dynamic, dynamic>
Copy the code

In fact, in earlier versions of Dart, new Map() actually created a HashMap. However, Dart Bug 5803 says that in order for {} and new Map() to return the same type, new Map will soon return an instance of LinkedHashMap.

LinkedHashMap

LinkedHashMap is ordered and iterates over keys in insertion order:

 var ordered = new LinkedHashMap();
   ordered['32352'] = 'Alice';
   ordered['95594'] = 'Bob';

   for (var key in ordered.keys) {
     print(key); } // print 32352 and then 95594Copy the code

Changing the value of a key does not change the order in which the key is inserted, but deleting it before adding it changes the order in which the key is inserted:

 var ordered = new LinkedHashMap();
   ordered['32352'] = 'Alice';
   ordered['95594'] = 'Bob';
   ordered['45684'] = 'Kal';

   for (var key in ordered.keys) {
     print("Traversal only:$key");
   }

   ordered['95594'] = 'James';
   for (var key in ordered.keys) {
     print("Change a value:$key");
   }
   
   ordered.remove('95594');
   ordered['95594'] = 'Kobe';
   for (var key in ordered.keys) {
     print("Change a value:$key");
   }
Copy the code

The output is as follows:

Only traversal: 32352 Only traversal: 95594 Only traversal: 45684 Change a value: 32352 Change a value: 95594 Change a value: 45684 Delete again add: 32352 Delete again add: 45684 Delete again add: 95594Copy the code

HashMap

A HashMap does not guarantee the insertion order of the maintained data. When traversing a HashMap, the order of key-value pairs is not guaranteed. You can create a HashMap as follows:

import 'dart:collection';
main() {
  var gifts= new HashMap();
}
Copy the code

You can use HashMap when you don’t care about the order of key-value pairs. The source code for HashMap is here.

SplayTreeMap

A spread tree (split tree) is a self-balanced binary search tree with fast access to the most recently accessed elements. It can insert, find, and delete in order log n.

import 'dart:collection';
main() {
  var gifts= new SplayTreeMap();
}
Copy the code

SplayTreeMap requires that all keys be of the same type:

   var splayTreeMap = SplayTreeMap();
   splayTreeMap["1"] = "s";
   splayTreeMap[1] = "2";
Copy the code

The above code syntax is fine, but not allowed at runtime:

type 'int' is not a subtype of type 'String' of 'other'
Copy the code

SplayTreeMap is a good choice for frequently stored and accessed data, such as caching. The reason is that they use tree rotation to move an element to the root for more frequent access. Performance comes from tree self-optimization. That is, frequently visited elements move closer to the top. However, it makes little sense to use SplayTreeMap if you also access the tree frequently.

For example, modem routers receive network packets at very high rates. The modem must decide which packets go to which line. This can be done using a Map, where the key is IP and the value is the destination line. SplayTreeMap is a good choice for this situation, because most IP addresses will be used multiple times, so they can be found from the root of the tree.

conclusion

This article briefly explains the differences between maps in Dart, but hopefully it will help, although it doesn’t explain the implementation. Our QQ group: 892398530.