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

В Go map — это реализация хеш-таблицы, которая использует хеш-функцию для обеспечения очень быстрого доступа к данным по ключу.

Основная задача хеш-функции — преобразовать ключ любого допустимого типа (строка, число, структура и т.д.) в целое число (хеш-код). Этот хеш-код используется для определения «корзины» (bucket) — внутреннего массива, где будет храниться пара ключ-значение.

Преимущества такого подхода:

• Скорость: Операции добавления, получения и удаления элемента в среднем выполняются за константное время — O(1).
• Эффективность: Позволяет хранить большие объемы данных с минимальными задержками при доступе.

// Ключ "foo" хешируется для определения его местоположения в памяти
m := make(map[string]int)
m["foo"] = 42 

// При доступе ключ "foo" снова хешируется, чтобы мгновенно найти значение
value := m["foo"] 

Ключевые моменты в реализации Go:

1. Типы ключей: Ключом в map может быть любой тип данных, для которого определена операция сравнения (== и !=). Это все базовые типы, строки, указатели, а также структуры, состоящие из сравниваемых типов. Слайсы, функции и другие map не могут быть ключами.
2. Коллизии: Когда два разных ключа получают одинаковый хеш-код, возникает коллизия. Go решает эту проблему, сохраняя несколько пар ключ-значение в одной «корзине» в виде связанного списка.
3. Порядок итерации: Порядок перебора элементов в map не гарантирован и является случайным. При каждой новой итерации порядок может меняться. Это сделано намеренно, чтобы разработчики не полагались на порядок вставки.
4. Динамический рост: При заполнении map Go автоматически увеличивает количество «корзин» и перераспределяет все элементы (rehashes), чтобы сохранить производительность на уровне O(1).