Оптимизация Go map{-}{-}

[Sly_tom_cat]

Нет ни слова про размер тестового набора.

Что покажут тесты с увеличением тестового набора на 2 порядка? А если на 4 порядка увеличим?

[ilya_dt]

Про тесты ни слова, потому что я взял одинаковый набор из головы для всех случаев.

Можно взять несколько наборов, но тогда непонятно какие лучше брать. В общем можно с наборами поиграться и взять средний в ответ.

[eee]

Хэшмапы это по факту массивы, в которых лежат ссылки на бакеты. Хэш-функция вычисляет лишь индекс до этого бакета, а дальше поиск искомого значения происходит перебором. Чем больше коллизий у хешфункции, тем более значений лежат в каждом бакете. Так что непонятно, что здесь воспринимать за операцию в О-нотации. С точки зрения пользователя да, индекс находится за О(1), но это в лучшем случае, если не было коллизий. Ещё нужно не забывать, что если размер бакетов превысит заданный threshold, то произойдет увеличение размера массива (на 75% в реализации на Go ЕМНИП) и начнется копирование данных в новый массив с перебалансировкой бакетов.

Пробовал ли автор заранее указать capacity для мапы, если заранее известно количество ключей?