Хеш-таблицы в Go: устройство, коллизии и методы их разрешения

Представьте, что вам нужно быстро найти книгу в библиотеке. Можно перебирать все книги подряд — это медленно. А можно иметь каталог, где каждая книга привязана к конкретному стеллажу. Вычислили стеллаж — и книга найдена.

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

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

Где используются хеш-таблицы

Хеш-таблицы — одна из самых востребованных структур данных в программировании. Вот три основных области их применения:

Кэш

Браузеры хранят кэш страниц, чтобы при повторном визите не загружать их заново. Операционные системы кэшируют данные с диска. Везде, где нужно быстро проверить, есть ли уже этот объект, используются хеш-таблицы.

Индексы в базах данных

Когда вы ищите пользователя по email, база данных не сканирует все миллионы записей. Она использует хеш-индекс: вычисляет хеш от email и сразу знает, где искать запись.

Языковые процессоры

Компиляторы и интерпретаторы хранят имена переменных в хеш-таблицах. Когда компилятор встречает переменную count, он должен быстро найти, где она объявлена и какой у неё тип.

Хеш-функция

Хеш-функция — это алгоритм, который берет входные данные сравнимых типов (строки, числа, структуры) и превращает их в число. Это число обычно очень большое и выглядит случайным.

Как это работает на примере

Представьте, что у нас есть таблица на 3 ячейки с индексами 0, 1, 2. Нам нужно сохранить в неё несколько имен.

Шаг 1. Подаём имя на вход хеш-функции

Хеш-функция берет строку «Петя» и выполняет с ней сложные математические преобразования.

Шаг 2. Получаем большое число

На выходе хеш-функция выдаёт большое целое число. Для примера пусть это будет:

"Петя" → хеш-функция → 933

Важно понять: хеш-функция не знает про нашу таблицу из 3 ячеек. Она просто возвращает число. Это число может быть любым — 5, 933, 2581, 777777.

Шаг 3. Сжимаем число до размера таблицы

Таблица имеет только 3 ячейки (индексы 0, 1, 2). Число 933 слишком большое, чтобы быть индексом. Поэтому берем остаток от деления на 3:

933 mod 3 = 0

Пошаговый расчет:

• 3 * 311 = 933
• 933 — 933 = 0 (остаток)

Значит, ключ "Петя" попадёт в ячейку с индексом 0.

Имя "Саша":

"Саша" → хеш-функция → 5
5 mod 3 = 2

"Саша" попадет в ячейку 2.

Имя "Маша":

Маша → хеш-функция → 2581
2581 mod 3 = 1

"Маша" попадет в ячейку 1.

Что будет, если добавить еще одно имя?

Добавляем "Даша":

"Даша" → хеш-функция → 2580
2580 mod 3 = 0

"Даша" тоже хочет попасть в ячейку 0, где уже лежит "Петя". Это и есть коллизия — два разных ключа попали в одну ячейку.

Что происходит при коллизии с хеш-функцией?

Многие думают, что при коллизии хеш-функция вызывается снова, чтобы получить другой индекс. На самом деле, это не так. Хеш-функция вызывается только один раз для каждого ключа. Полученное число не меняется. Хеш-функция вообще не знает, произошла коллизия или нет.

Кто тогда решает проблему?

Проблему коллизии решает метод разрешения коллизий, а не хеш-функция:

Что делаем	Для чего
Хеш-функция (один раз)	Получить уникальное число для ключа
Остаток от деления (один раз)	Получить начальный индекс
Метод пробирования (много раз)	Получить следующий индекс при коллизии

Аналогия из реальной жизни

Представьте, что вы пришли в гостиницу и вам нужен свободный номер.

Хеш-функция = ваш паспорт. Он уникален, и вы не поменяете его по дороге.

Остаток от деления = администратор посмотрел на ваш паспорт и сказал: «Вам на третий этаж».

Коллизия = номер на третьем этаже уже занят.

Пробирование = администратор говорит: «Тогда давайте на четвертый. Тоже занят? Тогда на пятый».

Вы не меняете паспорт, вы меняете номер комнаты, которую проверяете.

Хеш-функция вызывается один раз для каждого ключа. Коллизии обрабатываются методами пробирования или цепочками, а не повторным вызовом хеш-функции.

Свойства хорошей хеш-функции

1. Детерминизм

Для одного и того же ключа хеш-функция всегда должна возвращать одно и то же значение.

hash("Саша") → 5
hash("Саша") → 5 // всегда

Если это свойство нарушить, вы никогда не найдете данные, которые сохранили.

2. Равномерность

Хеш-функция должна распределять ключи по всем ячейкам равномерно. Если функция будет отправлять 90% ключей в ячейку 0, таблица потеряет эффективность.

3. Эффективность

Хеш-функция должна вычисляться быстро. Если вычисление хеша будет занимать секунду, преимущество мгновенного поиска пропадет.

4. Ограниченность

Результат хеш-функции должен попадать в границы таблицы. Обычно это достигается взятием остатка от деления на размер таблицы:

index = hash(key) % tableSize

Коллизии

Коллизия — ситуация, когда два разных ключа попадают в одну и ту же ячейку таблицы.

Почему коллизии неизбежны

Размер таблицы ограничен. Ключей может быть бесконечно много. А ячеек — конечное число. По принципу Дирихле (принципу ящиков), если объектов больше, чем ящиков, то хотя бы один ящик получит больше одного объекта.

Как обрабатывать коллизии

Существует два основных подхода:

1. Открытая адресация — ищем другую свободную ячейку в той же таблице.
2. Метод цепочек — в каждой ячейке хранится связный список (или другая структура).

Разберем оба подхода подробно.

Метод 1. Открытая адресация

При коллизии не паникуем, а ищем первую свободную ячейку в таблице и записываем данные туда.

Процесс последовательного поиска свободной ячейки называется пробированием (probing).

Пример с таблицей из 3 ячеек

Изначально таблица пустая:

[0] → пусто
[1] → пусто
[2] → пусто

Сохраняем "Петя" → хеш → 933 mod 3 = 0:

 
[0] → "Петя"
[1] → пусто
[2] → пусто 

Далее сохраняем "Маша" → хеш → 2581 mod 3 = 1:

 
[0] → "Петя" 
[1] → "Маша"
[2] → пусто 

И затем, сохраняем "Саша" → хеш → 5 mod 3 = 2:

 
[0] → "Петя" 
[1] → "Маша"
[2] → "Саша"

А теперь, если хотим сохранить "Даша" → хеш → 2580 mod 3 = 0 (коллизия — ячейка 0 уже занята).

Начинаем пробирование. Ищем первую свободную ячейку:

 
[0] занято → идём дальше 
[1] занято → идём дальше  
[2] занято → идём дальше (таблица кончилась)

Что если таблица заполнена?

Если при вставке просмотрели все ячейки и не нашли свободного места — таблица заполнена. В реальных реализациях такая ситуация недопустима.

Что делают на практике:

1. Расширение таблицы (rehashing) — создают новую таблицу большего размера и переносят все данные заново.

2. Коэффициент загрузки — когда таблица заполнена на определённый процент (обычно 70-75%), запускаем rehashing.

Коэффициент загрузки = количество элементов / размер таблицы.

loadFactor = count / tableSize

Если loadFactor превышает порог (например, 0.75), таблицу расширяют.

Удаление элемента в открытой адресации

С удалением есть проблема. Нельзя просто взять и очистить ячейку.

Пример проблемы (увеличим таблицу для наглядности до 6 ячеек):

Исходная таблица:

 
[0] → "Петя" 
[1] → "Даша" (попала сюда при коллизии)
[2] → пусто
[3] → пусто
[4] → пусто
[5] → пусто

"Даша" изначально хотела в ячейку 0 (по своему хешу), но попала в ячейку 1 из-за коллизии.

Удаляем «Петя» из ячейки 0 — просто очищаем ячейку:

 
[0] → пусто 
[1] → "Даша"

Теперь ищем «Даша». Её хеш даёт индекс 0. Ячейка 0 пуста. Алгоритм решит, что «Даша» не существует, хотя она есть в ячейке 1.

Решение — маркер удаления:

Вместо очистки ячейку помечают специальным маркером «удалено». При поиске алгоритм продолжает пробирование, увидев маркер. А при вставке можно использовать помеченную ячейку.

 
[0] → (удалено) // не просто пусто, а помечено
[1] → "Даша"

Поиск "Даша": индекс 0 → видим маркер удаления →
→ продолжаем поиск → находим в ячейке 1

Виды пробирования в открытой адресации

Линейное пробирование

При коллизии переходим к следующей ячейке:

index = (hash(key) + i) % tableSize

где i = 1, 2, 3... — номер попытки.

Плюсы: простота реализации, хорошая локальность данных (кеш-процессора эффективен).

Минусы: первичная кластеризация — образуются длинные занятые последовательности, время поиска растёт.

Квадратичное пробирование

Шаг увеличивается квадратично:

 
index = (hash(key) + i²) % tableSize 

где i = 1, 4, 9... — номер попытки.

Плюсы: снижает первичную кластеризацию.

Минусы: может не найти свободную ячейку, даже если она есть (вторичная кластеризация). Не гарантирует обход всех ячеек.

Двойное хеширование

Используем вторую хеш-функцию для вычисления шага:

 
index = (hash1(key) + i * hash2(key)) % tableSize 

Плюсы: отличное распределение, минимальная кластеризация.

Минусы: сложность реализации, требует быстрой второй хеш-функции.

Метод 2. Цепочки (Chaining)

Вместо поиска другой ячейки, в каждой ячейке таблицы хранится связный список (или другая структура) всех ключей, попавших в эту ячейку.

Как это выглядит

После добавления "Петя", "Маша", "Саша", "Даша" (допустим, "Даша" тоже даёт индекс 0):

 
Таблица (размер 3):
[0] → "Петя" → "Даша" → nil
[1] → "Даша" → nil
[2] → "Саша" → nil

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

Плюсы цепочек

1. Простота реализации — не нужно придумывать сложные стратегии пробирования.

2. Нет проблемы удаления — просто удаляем элемент из списка.

3. Не требует расширения при небольшом переполнении — можно хранить много элементов в одной корзине.

Минусы цепочек

1. Расход памяти на ссылки — каждый элемент хранит указатель на следующий.

2. Медленный обход — обход всех элементов требует прохода по всем спискам, что медленнее последовательного обхода в открытой адресации.

Сравнение методов: открытая адресация vs цепочки

Критерий	Открытая адресация	Цепочки
Расход памяти	Меньше (нет ссылок)	Больше (ссылки в списках)
Скорость обхода	Быстрее (данные в одном массиве)	Медленнее (нужно переходить по ссылкам)
Зависимость от способа обхода	Высокая (важен порядок пробирования)	Низкая
Зависимость от размера массива	Высокая (при заполнении — rehash)	Низкая (можно хранить много элементов)
Сложность удаления	Высокая (нужны маркеры)	Низкая (обычное удаление из списка)
Простота реализации	Средняя	Высокая

Как реализованы хеш-таблицы в Go (до версии 1.23)

В версиях Go до 1.23 map использовался метод цепочек со своей спецификой:

• Базовая структура — массив bucket (корзин).
• Каждый bucket содержит 8 слотов для хранения пар ключ-значение.
• В каждом bucket есть поле tophash — старшие 8 бит хеша для быстрого сравнения.
• Когда bucket заполняется, создается overflow bucket — дополнительная корзина, связанная с основной через указатель.

Эта структура называлась hmap и выглядела примерно так:

type hmap struct {
    count   int               // количество элементов
    buckets unsafe.Pointer    // указатель на массив bucket
    oldbuckets unsafe.Pointer // для расширения
    // ... другие поля
}

type bmap struct {
    tophash [8]uint8 // старшие биты для хешей быстрого сравнения
    keys    [8]KeyType 
    values  [8]ValueType
    overflow *bmap  // указатель на следующий bucket при переполнении
}

Почему именно 8 слотов?

Выбор числа 8 — это баланс между эффективность и расходом памяти. 8 слотов хорошо помещаются в кеш-линию процессора, что ускоряет доступ.

Что изменилось в Go 1.24

Начиная с версии Go 1.24, классическая реализация hmap + bucket + overflow была полностью заменена на Swiss Table.

Ключевы изменения:

1. Отказ от overflow-цепочки — теперь используется открытая адресация.
2. Группы по 8 слотов (groups) — минимальная единица пробирования.
3. Контрольные байты (control word) — 64-битное слово, где каждый байт хранит статус слота или младшие 7 бит хеша (H2).
4. Разделение хеша — H1 (57) для выбора группы, H2 (7 бит) для быстрой фильтрации внутри группы.
5. Иерархическая структура — Map → Directory → Table → Group → Slot
6. Локальная расширение — вместо полного rehashing теперь расширяется только переполненная таблица (как в extendible hashing).

Зачем это понадобилось

Классическая реализация с overflow-цепочками работала хорошо, но имела фундаментальные проблемы:

• Ухудшение локальности данных — overflow-бакеты могут быть разбросаны по памяти, что плохо для кеша процессора.
• Линейный поиск при коллизиях — при длинной цепочке поиск превращается в O(n).
• Перерасход памяти — каждый overflow-bucket требовал дополнительной аллокации.

Swiss Table решил эти проблемы за счёт компактного размещения метаданных и batch-обработки при поиске.

Ключевой вывод

Хеш-таблицы — фундаментальная структура данных, которую каждый разработчик Go использует ежедневно. Понимание принципов их работы (хеш-функции, коллизии, открытая адресация, цепочки) остаётся актуальным независимо от конкретной реализации.

Особенно важно запомнить: хеш-функция не решает коллизии, она только даёт начальный индекс. Всю остальную работу делают методы пробирования или цепочки.

Теперь, зная классику, вы будете лучше понимать, почему и как именно оптимизировали map в Go 1.24. А подробный разбор новой реализации Swiss Table — тема для отдельной статьи.

Сталкивались ли вы с проблемами производительности при использовании map в Go? Что помогало в диагностике? Делитесь в комментариях.