Какая временная сложность delete в map?

Временная сложность операции delete в Map

Ответ зависит от типа Map и его реализации. Давайте разберем все варианты.

1. HashMap — O(1) в среднем, O(n) в худшем

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

class HashMapExample<K, V> {
  void delete(K key) {
    // Шаг 1: Вычислить хеш ключа → O(1)
    int hash = key.hashCode;

    // Шаг 2: Найти bucket по индексу → O(1)
    int index = hash % capacity;

    // Шаг 3: Поискать элемент в цепочке (chaining) → O(1) в среднем
    Entry<K, V>? current = buckets[index];
    while (current != null) {
      if (current.key == key) {
        // Шаг 4: Удалить из связного списка → O(1)
        current.prev.next = current.next;
        current.next.prev = current.prev;
        size--;
        return;
      }
      current = current.next;
    }
  }
}

// Средний случай: O(1) — находим элемент сразу
// Худший случай: O(n) — все элементы в одном bucket

Когда происходит O(n)?

• Очень плохая хеш-функция (много коллизий)
• Все ключи хешируются в один bucket
• Элемент в конце длинной цепочки

2. TreeMap (Red-Black Tree) — O(log n)

TreeMap хранит элементы в отсортированном порядке (как Red-Black Tree).

// Внутри TreeMap используется бинарное дерево поиска
class TreeMapExample<K, V> {
  void delete(K key) {
    // Шаг 1: Найти узел в дереве → O(log n)
    TreeNode<K, V>? node = _findNode(key);
    if (node == null) return;

    // Шаг 2: Удалить узел → O(log n)
    _removeNode(node);

    // Шаг 3: Балансировать дерево (Red-Black rebalancing) → O(log n)
    _rebalance();
  }

  TreeNode<K, V>? _findNode(K key) {
    TreeNode<K, V>? current = root;
    while (current != null) {
      int cmp = key.compareTo(current.key) as int;
      if (cmp == 0) return current;
      current = cmp < 0 ? current.left : current.right;
    }
    return null;
  }
}

// Сложность: O(log n) всегда

Преимущества TreeMap:

• Гарантированная O(log n) сложность
• Элементы отсортированы
• Итерация в порядке ключей

Недостатки:

• Медленнее, чем HashMap на практике
• Требует реализации Comparable/Comparator

3. LinkedHashMap — O(1) в среднем

Комбинирует HashMap (быстрый поиск) с LinkedList (сохранение порядка вставки).

class LinkedHashMapExample<K, V> {
  void delete(K key) {
    // Шаг 1: Найти в HashMap → O(1) в среднем
    int index = key.hashCode % capacity;
    Entry<K, V>? entry = buckets[index];

    while (entry != null) {
      if (entry.key == key) {
        // Шаг 2: Удалить из HashMap → O(1)
        entry.prev.next = entry.next;
        entry.next.prev = entry.prev;

        // Шаг 3: Удалить из LinkedList → O(1)
        entry.linkPrev?.linkNext = entry.linkNext;
        entry.linkNext?.linkPrev = entry.linkPrev;

        size--;
        return;
      }
      entry = entry.next;
    }
  }
}

// Сложность: O(1) в среднем, O(n) в худшем (как HashMap)

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

5. Практический пример на Dart

void main() {
  final hashMap = HashMap<String, int>();
  final linkedHashMap = LinkedHashMap<String, int>();
  final treeMap = {}; // Dart использует LinkedHashMap по умолчанию

  // Вставка 1000 элементов
  for (int i = 0; i < 1000; i++) {
    hashMap['key_$i'] = i;
    linkedHashMap['key_$i'] = i;
  }

  // Удаление: O(1) для HashMap и LinkedHashMap
  final startHash = DateTime.now();
  hashMap.remove('key_500');
  print('HashMap delete: ${DateTime.now().difference(startHash).inMicroseconds} мкс');

  final startLinked = DateTime.now();
  linkedHashMap.remove('key_500');
  print('LinkedHashMap delete: ${DateTime.now().difference(startLinked).inMicroseconds} мкс');
}

// Вывод (примерно):
// HashMap delete: 5 мкс
// LinkedHashMap delete: 8 мкс

6. Когда используется каждый тип

HashMap:

• Максимальная скорость
• Нужен быстрый поиск
• Порядок не важен

final cache = HashMap<String, CachedData>();
cache.remove('expired_key'); // O(1)

TreeMap:

• Нужна сортировка
• Нужна гарантированная O(log n) сложность
• Критична предсказуемость

// Аналог TreeMap в Dart нужно реализовать через package
final sortedMap = SortedMap<String, int>();
sortedMap.remove('middle_key'); // O(log n)

LinkedHashMap:

• Нужно сохранить порядок вставки
• Нужна скорость как HashMap

final userVisits = LinkedHashMap<String, DateTime>();
userVisits.remove('old_user'); // O(1) + сохраняется порядок

Вывод

• HashMap: O(1) в среднем → выбирай для максимальной скорости
• TreeMap: O(log n) гарантированно → выбирай если нужна сортировка
• LinkedHashMap: O(1) + порядок вставки → выбирай в Dart по умолчанию

В большинстве случаев (при хорошей хеш-функции) HashMap показывает лучшую производительность благодаря O(1) сложности удаления.