Что такое хеш-таблица (map в Go) и каковы её ключевые особенности?

Хеш-таблица — это структура данных, которая реализует ассоциативный массив (пары «ключ-значение»). В Go она встроена в язык как тип map.

Как это работает?
Её главная особенность — очень быстрое выполнение операций (вставка, поиск, удаление) в среднем за константное время O(1). Это достигается за счет использования хеш-функции, которая преобразует ключ в индекс (хеш-код) в нижележащем массиве (называемом "бакетами" или "корзинами"). Если несколько ключей дают одинаковый хеш (коллизия), они сохраняются в одном бакете в виде списка.

Ключевые особенности map в Go:

• Скорость: Средняя сложность операций — O(1). В худшем случае (при большом количестве коллизий) может деградировать до O(n).
• Неупорядоченность: Порядок итерации по элементам map не гарантирован и может меняться от запуска к запуску. Если важен порядок, используйте отдельный слайс для хранения ключей.
• Нулевое значение: При чтении по несуществующему ключу map вернет нулевое значение для типа значения (например, 0 для int, "" для string, nil для указателей).
• Проверка наличия ключа: Для различения отсутствующего ключа и нулевого значения используется идиома value, ok := m[key].
• Не потокобезопасность: Стандартный map не является потокобезопасным. Для конкурентного доступа из нескольких горутин необходимо использовать sync.Mutex или sync.RWMutex для защиты, либо использовать sync.Map.
• Типы ключей: Ключом может быть любой тип данных, для которого определена операция сравнения (== и !=), например: int, string, struct (без слайсов, карт и функций).

Пример в Go:

// Создание и инициализация
m := make(map[string]int)
m["apple"] = 5
m["banana"] = 7

// Чтение значения
fmt.Println(m["apple"]) // Выведет: 5

// Проверка наличия ключа
val, ok := m["orange"] 
if !ok {
    fmt.Println("orange not found") // Ключа нет
}

// Удаление элемента
delete(m, "apple")