Хеш-таблица — структура данных для хранения пар ключ-значение с O(1) доступом. В Go это тип map.
Принцип работы: 1. Ключ подаётся в хеш-функцию → получается число 2. Число определяет индекс в массиве бакетов 3. Значение кладётся/ищется в этом бакете
Коллизии (два ключа → один бакет) решаются через chaining (связный список) или open addressing. Go использует chaining с бакетами по 8 элементов.
m := map[string]int{}
m["key"] = 42 // O(1)
val := m["key"] // O(1)
delete(m, "key") // O(1)Worst case O(n) при большом количестве коллизий, но хорошая хеш-функция делает это крайне маловероятным.