Skip to content

Карта (map)

В следующих главах ты узнаешь:

  • что такое map (карта), какие особенности есть у карт Go и при чем тут хэш-функция;

  • четыре свойства хэш-карты;

  • как хэш-карты реализуются в Go и других языках программирования;

  • использует ли среда выполнения Go interface{};

  • использует ли компилятор генерацию кода;

  • как происходит переписывание времени компиляции.

Что такое map (карта)

Значением карты является ссылка на внутреннюю структуру рантайма runtime.hmap.

Чтобы понять, как работает карта, давай сначала поговорим об идее функции карты. Функция карт — соединить ключ и значение. То есть значение карты можно получить с помощью его ключа.

Карта будет не очень полезной, если мы не сможем добавить в нее какие-либо данные. Нам понадобится функция, которая добавляет данные на карту.

Также нужна функция, удаляющая данные с карты.

Существуют и другие интересные свойства реализаций карты, такие как, например, запрос на наличие ключа в карте, но они выходят за рамки того, что мы собираемся обсудить далее. Вместо этого мы просто сосредоточимся на этих свойствах карт: вставка, удаление и сопоставление ключей со значениями.

Карта Go — это хэш-карта (hash map)

Конкретная реализация карты, которую мы рассмотрим, — это hashmap, потому что эту же реализацию использует среда выполнения Go. Хэш-карта — это классическая структура данных, предлагающая в среднем O(1) операций поиска и O(n) в худшем случае. То есть, когда все работает хорошо, время выполнения поиска значения в maps почти постоянно.

Размер этой константы является частью дизайна хэш-карты, и точка, в которой карта переходит от времени доступа O(1) к O(n), определяется ее хэш-функцией .

Хэш-функция

Хеш-функция принимает ключ неизвестной длины и возвращает значение фиксированной длины.

Это хэш__-значение почти всегда является целым числом по причинам, которые мы вскоре увидим.

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

Важные свойства хэш-функции

Хэш функции в Golang превращают ключ в значение с типом int.

Важно говорить о свойствах хорошей хеш-функции, поскольку качество хеш-функции определяет, насколько вероятно, что функция отображения будет работать около O (1).

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

Второе свойство — хорошее распределение. Учитывая два почти идентичных ключа, результат должен сильно отличаться. Это важно по двум причинам. Во-первых, как мы увидим, значения в хэш-карте должны быть равномерно распределены по корзинам, иначе время доступа не будет равно O(1). Во-вторых, поскольку пользователь может контролировать некоторые аспекты ввода хэш-функции, он может контролировать вывод хэш-функции, что приводит к плохому распределению, которое может стать вектором для DDoS атак в некоторых языках. Это свойство также известно как устойчивость к коллизии.

Структура данных hashmap

Вторая часть хэш-карты — это способ хранения данных.

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

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

Имея в виду эту структуру данных, если бы у нас была карта имен проектов со звездами GitHub, как бы мы вставили значение в карту?

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

Теперь давай воспользуемся той же диаграммой для поиска значения на нашей карте. Процесс аналогичен. Мы хэшируем ключ, как и раньше, затем маскируем младшие 3 бита, поскольку наш массив сегментов содержит восемь записей, чтобы перейти к пятому сегменту (101 в двоичном формате). Если наша хэш-функция верна, то строка "moby/moby " всегда будет иметь одно и то же значение хэша. Поэтому мы знаем, что ключ не будет находиться ни в одном другом сегменте. Теперь это случай линейного поиска в корзине со сравнением предоставленного ключа с ключом записанного значения.

Четыре свойства хеш-карты

Чуть выше было высокоуровневое объяснение классической хеш-карты. Мы видели, что для реализации хэш-карты нам нужны четыре свойства:

  1. Хэш-функция для ключа.

  2. Функция равенства для сравнения ключей.

  3. Размер ключа

  4. Размер значения, потому что это влияет на размер структуры сегмента, которую компилятор должен знать, когда мы проходим или вставляем в эту структуру информацию о том, как далеко нужно продвигаться в памяти.