Какова временная сложность доступа к элементу в `map` в Go?

Временная сложность доступа к элементу в map в Go составляет O(1) в среднем (амортизированная сложность).

Детальное объяснение:

• 
  

  Средний случай (O(1)): Внутренне map в Go реализована как хеш-таблица. При доступе к элементу ключ хешируется, и по значению хеша определяется "корзина" (bucket), где хранится значение. Этот процесс занимает константное время.

  
  
• 
  

  Худший случай (O(n)): В редких случаях, когда множество ключей имеют одинаковый хеш (коллизия), они попадают в одну и ту же корзину. Тогда для поиска нужного элемента потребуется перебрать все элементы в этой корзине, что приводит к сложности O(n), где n — количество элементов в корзине.

  
  

Амортизированная сложность означает, что стоимость редких дорогих операций (как перестройка таблицы при её росте) "размазывается" по всем операциям, и в среднем каждая операция остается очень быстрой.

Пример кода:

m := make(map[string]int)
m["key"] = 100

// Эта операция в среднем занимает O(1)
value := m["key"]