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

Разница между HashSet, LinkedHashSet и TreeSet

Хотя в Dart нет точных аналогов этих Java-классов, концепции остаются актуальны. Рассмотрю их различия и аналоги в Dart.

HashSet

HashSet использует хеш-функцию для хранения элементов.

Характеристики:

• Поиск: O(1) в среднем случае
• Вставка: O(1) в среднем случае
• Удаление: O(1) в среднем случае
• Порядок: Не гарантируется (случайный)
• Производительность: Лучшая для поиска

Аналог в Dart:

final hashSet = <String>{}; // Set по умолчанию использует хеш
hashSet.add('apple');
hashSet.add('banana');
hashSet.add('cherry');

print(hashSet.contains('apple')); // O(1) - быстро!
for (var item in hashSet) {
  print(item); // Порядок не гарантирован
}

LinkedHashSet

LinkedHashSet — это HashSet, который дополнительно сохраняет порядок вставки элементов.

Характеристики:

• Поиск: O(1) в среднем случае
• Вставка: O(1) в среднем случае
• Удаление: O(1) в среднем случае
• Порядок: Сохраняется порядок вставки
• Память: Больше, чем HashSet (дополнительные указатели)

Аналог в Dart:

final linkedSet = <String>{...}; // Dart Set по умолчанию сохраняет порядок!
linkledSet.add('apple');
linkledSet.add('banana');
linkledSet.add('cherry');

for (var item in linkedSet) {
  print(item); 
  // apple (первый)
  // banana (второй)
  // cherry (третий)
}

TreeSet

TreeSet использует красно-черное дерево для хранения отсортированных элементов.

Характеристики:

• Поиск: O(log n)
• Вставка: O(log n)
• Удаление: O(log n)
• Порядок: Сортированный (требует Comparable)
• Производительность: Медленнее HashSet, но элементы отсортированы

Аналог в Dart:

Dart не имеет встроенного TreeSet, но можно реализовать через List с сортировкой:

// Простой вариант для небольших наборов
class SortedSet<T extends Comparable<T>> {
  final List<T> _items = [];

  void add(T item) {
    final index = _binarySearch(item);
    if (index < 0) {
      _items.insert(~index, item);
    }
  }

  int _binarySearch(T item) {
    return _items
        .toList()
        .indexWhere((e) => e.compareTo(item) == 0);
  }

  bool contains(T item) => _items.contains(item);

  Iterable<T> get items => _items;
}

final sortedSet = SortedSet<int>();
sortedSet.add(3);
sortedSet.add(1);
sortedSet.add(2);
print(sortedSet.items); // [1, 2, 3] - отсортировано!

Сравнительная таблица

Операция      | HashSet | LinkedHashSet | TreeSet
──────────────┼─────────┼───────────────┼────────
Добавление    | O(1)    | O(1)          | O(log n)
Поиск         | O(1)    | O(1)          | O(log n)
Удаление      | O(1)    | O(1)          | O(log n)
Порядок       | Нет     | Вставки       | Сорти-
              |         |               | ровано
Память        | Низкая  | Средняя       | Средняя
Утечка памяти | Нет     | Возможна      | Нет

Примеры в Dart

HashSet для проверки уникальности (быстро):

final uniqueIds = <int>{};  // Set по умолчанию
const largeList = [1, 2, 2, 3, 4, 4, 5, 6, 6];

for (var id in largeList) {
  uniqueIds.add(id);
}

print(uniqueIds);  // {1, 2, 3, 4, 5, 6}
print(uniqueIds.contains(3));  // O(1) - очень быстро!

LinkedHashSet для сохранения порядка:

// Dart Set сохраняет порядок вставки по умолчанию
final users = <String>{};
users.add('Alice');
users.add('Bob');
users.add('Charlie');

print(users); // {Alice, Bob, Charlie} - в порядке добавления

// Если нужно явно
final orderedSet = LinkedHashSet<String>();
orderedSet.add('First');
orderedSet.add('Second');
orderedSet.add('Third');
print(orderedSet); // First, Second, Third

TreeSet для отсортированных данных:

// Работа со скрингом, где нужны отсортированные оценки
class SortedScores {
  final _scores = <int>[];

  void addScore(int score) {
    _scores.add(score);
    _scores.sort();
  }

  void removeScore(int score) {
    _scores.remove(score);
  }

  List<int> getTopScores(int count) {
    return _scores.reversed.take(count).toList();
  }
}

final scores = SortedScores();
scores.addScore(85);
scores.addScore(92);
scores.addScore(78);
print(scores.getTopScores(2)); // [92, 85]

Практический выбор в Flutter

Используй HashSet когда:

• Нужна максимальная производительность поиска/добавления
• Порядок элементов не важен
• Проверка уникальности
• Удаление дубликатов из списка

final uniqueEmails = <String>{};
for (var email in emailList) {
  uniqueEmails.add(email);
}

Используй LinkedHashSet (обычный Set в Dart) когда:

• Нужно сохранить порядок добавления
• Нужна хорошая производительность
• Сохранение истории (но FIFO лучше использовать Queue)

final recentSearches = <String>{};
recentSearches.add('flutter');
recentSearches.add('dart');
recentSearches.add('mobile');
// Порядок будет: flutter, dart, mobile

Используй TreeSet (SortedSet) когда:

• Нужны элементы в отсортированном виде
• Нужна работа с диапазонами
• Редкие добавления/удаления
• Частый доступ к отсортированным данным

// Лидерборд
final leaderboard = SortedSet<Player>();
leaderboard.add(Player(name: 'Alice', score: 100));
leaderboard.add(Player(name: 'Bob', score: 85));
// Элементы хранятся отсортированы по score

Вывод

В Dart Set по умолчанию уже сочетает преимущества HashSet и LinkedHashSet (O(1) операции + сохранение порядка). Для отсортированных данных нужна собственная реализация или использование List с sort(). Выбор правильной структуры зависит от конкретных требований: скорость поиска, сохранение порядка или отсортированность.