Ответ 1

Dart имеет встроенную поддержку для таких коллекций, как List, Set и Map. Дарт имеет различные реализации карты. Понимание плюсов и минусов между реализациями может помочь вам принять обоснованное решение.

(Примечание: это написано во время Dart M3, поэтому последующие могут не соответствовать документам в данный момент.)

Что такое карта?

Карта - это ассоциативный контейнер, отображающий ключи на значения. Ключи уникальны и могут указывать на одно и только одно значение. Ключ не может быть нулевым, но значение может быть нулевым.

Карта Литералы

Dart поддерживает литералы Map, например:

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

В спецификации сказано, что литералы карты должны поддерживать порядок вставки. Это означает, что accounts являются экземпляром LinkedHashMap.

В спецификации также сказано, что литеральные ключи Map должны быть Strings. Это может быть изменено в будущем.

новая карта()

Dart поддерживает фабричные конструкторы, поэтому вы можете создать новый экземпляр Map следующим образом:

var accounts = new Map();

Класс Map является абстрактным, что означает, что конструктор фабрики фактически создает экземпляр подкласса Map. Так каков реальный тип accounts?

Более ранние версии Dart создавали новый экземпляр HashMap из new Map(). Однако ошибка Dart 5803 гласит, что для того, чтобы {} и new Map возвращали один и тот же тип, new Map вскоре вернет экземпляр LinkedHashMap.

LinkedHashMap (или, InsertionOrderedMap)

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:

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

Если вы не заботитесь о поддержании порядка вставки, используйте HashMap.

Вот исходный код HashMap.

SplayTreeMap

Splay-дерево - это самобалансирующееся бинарное дерево поиска с дополнительным свойством, которое позволяет недавно получить доступ к недавно полученным элементам. Он выполняет основные операции, такие как вставка, поиск и удаление за время амортизации O (log (n)).

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

SplayTreeMap требует, чтобы все ключи были одного типа.

Splay-дерево - хороший выбор для данных, которые часто хранятся и к которым обращаются, например, кэш-памяти. Причина в том, что они используют повороты деревьев, чтобы поднять элемент к корню для лучшего частого доступа. Производительность происходит от самооптимизации дерева. То есть часто используемые элементы перемещаются ближе к вершине. Если, однако, к дереву одинаково часто обращаются со всех сторон, то нет смысла использовать карту Splay Tree.

Примером является модем-маршрутизатор, который принимает сетевые пакеты с очень высокой скоростью. Модем должен решить, какой пакет пойти в каком проводе. Он может использовать реализацию карты, где ключом является IP, а значением является пункт назначения. Карта Splay Tree является хорошим выбором для этого сценария, поскольку большинство IP-адресов будут использоваться более одного раза, и поэтому их можно найти в корне дерева.

Ответ 2

Есть альтернатива.

Multimap

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
}