Какая временная сложность операции обновления элемента в Map в Dart?

В Dart, Map по умолчанию реализован как LinkedHashMap. Временная сложность операции обновления значения по существующему ключу составляет амортизированную O(1).

Почему O(1)? Операция основана на хеш-таблице. При обновлении map[key] = newValue:

1. Вычисляется хеш ключа.
2. Находится соответствующий бакет (bucket).
3. Если ключ найден в бакете, его значение перезаписывается.

Пример:

void main() {
  Map<String, int> priceMap = {
    'apple': 50,
    'banana': 30,
  };
  // Обновление по существующему ключу - O(1)
  priceMap['banana'] = 35;
  print(priceMap); // {apple: 50, banana: 35}
}

Важные нюансы:

• Худший случай O(n): Может произойти при большом количестве коллизий хешей, когда все ключи попадают в один бакет, и поиск становится линейным. На практике в Dart это маловероятно.
• Вставка vs. Обновление: Сложность O(1) относится именно к обновлению существующего ключа. Если ключа нет, операция map[key] = value выполнит вставку, что также имеет амортизированную O(1).