What are the differences between the different Map implementations in Dart?

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

Solution 1:

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.