Хеш-таблица (или ассоциативный массив, словарь) — это структура данных, которая хранит пары "ключ-значение" (key-value) и позволяет быстро находить, вставлять и удалять элементы по их ключу.
В Golang хеш-таблица реализована как тип map.
Принцип работы:
- Хеширование ключа: Для каждого ключа вычисляется хеш-значение с помощью хеш-функции. Хеш-функция преобразует ключ любого размера в число фиксированного размера.
- Определение индекса: На основе хеш-значения определяется индекс в массиве (корзине или бакетов), где будет храниться пара "ключ-значение". Обычно используется операция по модулю от размера массива.
- Коллизии: Поскольку разные ключи могут давать одно и то же хеш-значение (или определять один и тот же индекс), возникает коллизия. Для разрешения коллизий применяются различные методы, например:
- Метод цепочек (Separate Chaining): В каждом бакете хранится список пар "ключ-значение", которые имеют одинаковый индекс.
- Метод открытой адресации (Open Addressing): При коллизии ищут свободный слот в массиве, используя разные стратегии (линейное зондирование, квадратичное зондирование и т.д.). Golang использует комбинацию этих подходов.
Преимущества хеш-таблиц:
- Высокая скорость доступа: В среднем, операции вставки, удаления и поиска имеют сложность O(1).
- Гибкость: Могут хранить ключи и значения различных типов данных.
Недостатки:
- Возможность коллизий: Производительность может ухудшиться при большом количестве коллизий.
- Зависимость от хеш-функции: Качество хеш-функции напрямую влияет на производительность.
- Потребление памяти: Обычно требуют больше памяти по сравнению с массивами или связными списками.
Пример создания и использования map в Golang:
go