Какова алгоритмическая сложность добавления или обновления элемента в `map` в Go?

Алгоритмическая сложность добавления, обновления или получения элемента из map в Go:

• 
  

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

  
  
• 
  

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

  
  

Также операция O(n) может произойти, когда map достигает определенного коэффициента загрузки и ей требуется вырасти, что влечет за собой перераспределение всех существующих ключей в новую, большую хеш-таблицу.

package main

func main() {
    m := make(map[string]int)

    // Эти операции в среднем имеют сложность O(1)
    m["apple"] = 1
    m["orange"] = 2
}