В чем разница между HashSet, LinkedHashSet и TreeSet в Dart?

В Dart эти структуры данных представлены классами HashSet, LinkedHashSet и SplayTreeSet (аналог TreeSet) из пакета dart:collection.

• HashSet<E>: Хранит уникальные элементы без гарантии какого-либо порядка. Основан на хэш-таблице, что обеспечивает константное время O(1) для операций добавления, удаления и проверки наличия элемента (add, remove, contains).

  final hashSet = HashSet<int>();
  hashSet.addAll([3, 1, 4, 1, 5]);
  print(hashSet); // Может вывести {1, 3, 4, 5} (порядок произвольный)

• LinkedHashSet<E>: Сохраняет порядок вставки элементов. Под капотом это HashSet, дополненный связным списком. Операции также O(1), но с чуть большими накладными расходами на поддержку порядка.

  final linkedSet = LinkedHashSet<int>();
  linkedSet.addAll([3, 1, 4, 1, 5]);
  print(linkedSet); // Гарантированно выведет {3, 1, 4, 5}

• SplayTreeSet<E>: Хранит уникальные элементы в отсортированном порядке (по умолчанию — natural order, либо можно задать свой Comparator). Основан на Splay-дереве, которое самооптимизируется под частый доступ к одним и тем же элементам. Операции add, remove, contains выполняются за O(log n).

  final treeSet = SplayTreeSet<int>();
  treeSet.addAll([3, 1, 4, 1, 5]);
  print(treeSet); // Гарантированно выведет {1, 3, 4, 5}

Выбор на практике:

• HashSet — когда нужна максимальная скорость и порядок не важен.
• LinkedHashSet — когда важен порядок добавления (например, для кэша LRU).
• SplayTreeSet — когда элементы должны быть всегда отсортированы, или нужны операции с диапазонами (например, elementsBetween(start, end)).