Краткий ответ:
- вычисляется хэш от ключа;
- с помощью значения хэша вычисляется используемый для хранения bucket;
- вычисляется дополнительный хэш - первые 8 бит уже полученного хэша;
- в полученном bucket последовательно сравнивается каждый из 8 его дополнительных хэшей с дополнительным хэшем ключа;
- если дополнительные хэши совпали, то получаем ссылку на значение и возвращаем его;
- если дополнительные хэши не совпали, и в bucket больше нет дополнительных хэшей, алгоритм переходит в следующий bucket, ссылка на который хранится в текущем;
- если в текущем bucket нет ссылки на следующий bucket, а значение так и не найдено, возвращается дефолтное значение.
Теперь чуть подробнее.
Хэширование ключа
Этот процесс преобразует ключ из его исходного формата в хэш-код, который затем используется для определения местоположения значения в мапе.
- Хорошая хэш-функция должна быть детерминированной, то есть один и тот же ключ всегда приводит к одному и тому же хэш-коду.
- Хорошая хэш-функция производит хэш-коды, которые равномерно распределены по возможному диапазону значений, чтобы минимизировать коллизии (когда разные ключи дают один и тот же хэш-код).
- Хорошая хэш-функция должна быть быстрой, чтобы не стать узким местом при работе с мапой.
- Изменение даже одного бита ключа должно приводить к значительному изменению хэш-кода, чтобы схожие ключи не группировались в одном и том же бакете.
В Go, хэш-функция зависит от типа ключа:
- Для примитивных типов данных, таких как int или string, используется предварительно определенные хэш-функции, которые оптимизированы для этих типов.
- Для более сложных или пользовательских типов, таких как структуры, Go применяет хэш-функцию ко всем экспортируемым полям структуры.
Определение бакета
Бакет — это место, где хранятся пары ключ-значение, и они используются для организации данных внутри хэш-таблицы для быстрого доступа.
Хэш-код используется для определения индекса бакета, где должна храниться пара ключ-значение. Хэш-код обычно представляет собой 32- или 64-битное целое число, в зависимости от архитектуры.
Индекс бакета обычно определяется путем применения битовой маски к хэш-коду или использования модульной арифметики - взятие остатка от деления хэш-кода на общее количество бакетов.
Когда мапа растет и достигает определенного уровня заполнения, она может автоматически изменить размер, чтобы сохранить эффективность операций. Это изменение размера включает в себя создание новой, большей таблицы бакетов и перераспределение всех существующих записей - эвакуация данных.
Поиск ключа в бакете
После определения соответствующего бакета перебираются элементы в этом бакете, чтобы найти точное совпадение ключа. Поскольку количество элементов в бакете обычно невелико, этот процесс достаточно быстр.
Сравнение ключей
Если найдено совпадение в одном из бакетов, выполняется более детальное сравнение, чтобы убедиться, что ключи идентичны, так как разные ключи могут иметь одинаковый хэш — коллизия.
Возврат значения
Если ключ найден (т.е. и хэш-код, и сам ключ совпадают с искомым), возвращается соответствующее значение. Если совпадение не найдено, возвращается нулевое значение для типа значения мапы.
--------
Особенности:
Рост и сжатие: Мапы могут динамически увеличивать и уменьшать количество бакетов для поддержания эффективности операций.
Обработка коллизий: Коллизии решаются различными методами, в зависимости от реализации:
- Метод открытой адресации: Значение сохраняется в следующую свободную ячейку. Можно перепрыгивать через одну или несколько или идти в обратном порядке. Можно повторно применять хэш-функцию к полученному числу до тех пор пока не найдем свободную ячейку — пробирование
- Метод цепочек: В ячейки сохраняется не сами значения, а ссылки на них. Когда при добавлении следующего элемента получаем коллизию в ячейке, то предыдущей сохраненной ссылке добавляем ссылку на текущий элемент
Конкурентный доступ: Cтандартные мапы в Go не являются потокобезопасными, если одна горутина изменяет мапу, другие должны использовать синхронизацию, например, с помощью sync.Mutex. В противном случае это может привести к гонкам за данные.
Итерация по мапе: Итерация по элементам мапы не гарантирует какой-либо определённый порядок.
Почему нельзя брать указатель на значение, хранящееся по ключу в map?
Значения, хранящиеся в определённой ячейки памяти в текущий момент времени, в следующий момент уже могут там не храниться из-за эвакуации данных.
Как избежать эвакуация данных
Выделять память под нужное количество элементов заранее. Если заранее знаем, что map содержит 1000 элементов, то при создании указываем размер: