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

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

Операция update (обновление значения по существующему ключу) имеет сложность, которая зависит от типа Map. Давайте разберем каждый вариант.

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

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

class HashMapUpdate<K, V> {
  void update(K key, V newValue) {
    // Шаг 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.value = newValue;
        return; // Выходим
      }
      current = current.next;
    }
    // Ключ не найден - ничего не делаем
  }
}

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

Важное отличие от insert:

• update: ищем существующий ключ → O(1) в среднем
• insert/put: может потребоваться resize() → O(n) в худшем

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

TreeMap использует самобалансирующееся бинарное дерево поиска.

class TreeMapUpdate<K, V> {
  void update(K key, V newValue) {
    // Шаг 1: Найти узел в дереве бинарным поиском → O(log n)
    TreeNode<K, V>? node = _findNode(key);

    if (node != null) {
      // Шаг 2: Обновить значение → O(1)
      node.value = newValue;
      // Деревло не переестраивается - структура остается той же
    }
  }

  TreeNode<K, V>? _findNode(K key) {
    TreeNode<K, V>? current = root;
    int steps = 0;

    while (current != null) {
      steps++; // Максимум log(n) шагов
      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)
// Не зависит от коллизий, как в HashMap

Преимущество: гарантированная O(log n) без худших случаев

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

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

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

    while (entry != null) {
      if (entry.key == key) {
        // Шаг 2: Обновить значение → O(1)
        entry.value = newValue;
        // Шаг 3: Порядок в LinkedList остается прежним (обновление, не перемещение)
        return;
      }
      entry = entry.next;
    }
  }
}

// Сложность: O(1) в среднем
// Порядок элементов не меняется при update

4. Почему update не требует resize?

В отличие от insert, update не меняет размер таблицы:

// INSERT требует проверки load factor
void insert(K key, V value) {
  // ...
  size++; // Размер увеличился
  if (size / capacity > 0.75) {
    _resize(); // Может потребоваться! O(n)
  }
}

// UPDATE НЕ меняет размер
void update(K key, V newValue) {
  // Ищем существующий ключ
  // Обновляем значение
  // size не меняется!
  // resize не требуется
}

Поэтому update ВСЕГДА быстрее чем insert.

5. Сравнение операций в HashMap

6. Практический пример: update vs put vs get

class UserCache {
  final Map<String, User> cache = HashMap();

  // O(1) - просто получить
  User? getUser(String id) {
    return cache[id];
  }

  // O(1) в среднем, но может быть O(n) с resize
  void addUser(User user) {
    cache[user.id] = user; // put
  }

  // O(1) - обновить существующего пользователя
  void updateUserName(String id, String newName) {
    final user = cache[id];
    if (user != null) {
      cache[id] = user.copyWith(name: newName); // update
    }
  }

  // Более эффективно - обновление внутри объекта
  void updateUserNameInPlace(String id, String newName) {
    final user = cache[id];
    if (user != null) {
      user.name = newName; // Просто меняем поле! O(1)
    }
  }
}

7. Оптимизация: update vs мутация

// Вариант 1: Пересоздание значения (update map)
class Point {
  int x, y;
  Point(this.x, this.y);
}

final map = HashMap<String, Point>();

// O(1) - update в map, но создание нового объекта
map['point1'] = Point(10, 20);

// Вариант 2: Мутация существующего объекта
final point = map['point1'];
if (point != null) {
  point.x = 15; // O(1) - прямое изменение
}

// Вариант 2 быстрее если:
// - Объекты большие
// - Часто обновляются
// - Нет необходимости в immutability

8. Практический тест производительности

void main() async {
  final map = HashMap<int, String>();

  // Заполнить карту
  for (int i = 0; i < 100000; i++) {
    map[i] = 'value_$i';
  }

  // Тестируем update
  final updateStart = DateTime.now();
  for (int i = 0; i < 100000; i++) {
    map[i] = 'updated_$i'; // update
  }
  final updateTime = DateTime.now().difference(updateStart);

  print('Update time: ${updateTime.inMilliseconds}ms');
  // Вывод: примерно 20-30ms на 100k операций → O(1) в среднем
}

Вывод

• HashMap: update = O(1) в среднем, O(n) в худшем
• TreeMap: update = O(log n) всегда (гарантированно)
• LinkedHashMap: update = O(1) в среднем (Dart default)

Key difference: update НЕ требует resize, поэтому всегда быстрее чем put (insert). В среднем случае обе операции O(1) для HashMap, но update имеет меньше констант.