Какая сложность операций с map в худшем случае при коллизиях?

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

Тем не менее, в стандартной реализации Go предусмотрены механизмы перераспределения и рехеширования, которые минимизируют вероятность такого сценария. Поэтому на практике худший случай встречается крайне редко.