Реализация хэш-карты Go

Теперь давай поговорим о том, как реализация hashmap в Go позволяет нам сохранить многие из преимуществ лучших реализаций карт, которые мы видели, не платя за выше описанные недостатки.

Точно так же как C++ и Java, хэш-карта Go написана на Go__. Но Go не предоставляет универсальные типы. Тогда как же мы можем написать хэш-карту, которая работает (почти) для любого типа в Go?

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

Нет, среда выполнения Go не использует interface{} для реализации свой хэш-карты. Хотя у нас есть container/{list,heap} пакеты, которые используют пустой интерфейс, реализация карты во время выполнения (в рантайме) не использует interface{}.

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

Нет, в бинарном файле Go есть только одна копия реализации карты. Существует только одна реализация карты, и, в отличие от Java, она не использует interface{} как бокс или контейнер. Итак, как же это работает?

Ответ состоит из двух частей, и обе они связаны с взаимодействием между компилятором и средой выполнения.

Кодогенерация во время компиляции

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

Также полезно отметить, что то же самое происходит с каналами, но не со срезами.

Причина в том, что каналы являются сложными типами данных. Отправка, получение и выбор имеют сложные взаимодействия с планировщиком, поэтому они делегируются среде выполнения. Для сравнения, срезы представляют собой гораздо более простые структуры данных, поэтому компилятор изначально обрабатывает такие операции, как доступ к слайсам, len и cap откладывает сложные случаи использования copy и append во время выполнения.

Только одна копия кода карты

Теперь мы знаем, что компилятор переписывает код операции сопоставления с обращениями к среде выполнения или другими словами к runtime. Мы также знаем, что внутри среды выполнения (runtime) есть только одна вызываемая функция mapaccess, одна вызываемая функция mapaccess2 и так далее.

Итак, как компилятор может переписать это

в это

без использования чего-то вроде interface{}? Самый простой способ объяснить, как типы карт работают в Go — показать фактическую подпись runtime.mapaccess1.

Пройдемся по параметрам.

key является указателем на ключ, это значение, которое мы указали в качестве ключа.
h является указателем на runtime.hmapструктуру. hmap — это структура хэш-карты среды выполнения, которая содержит сегменты и другие служебные значения.
t является указателем на maptype.

Зачем нам нужен *maptype, если у нас уже есть *hmap? *maptype — это особая структура, благодаря которой дженерик *hmap работает почти с любой комбинацией типов ключа и значения. В вашей программе есть maptype значение для каждого уникального объявления карты. Будет одна, описывающая карты от strings до ints, от strings до http.Headers и так далее.

Вместо полной реализации карты для каждого уникального объявления типа карты, как в C++, компилятор Go создает maptype во время компиляции и использует эту структуру при вызове функций карты среды выполнения (runtime.mapaccess, runtime.mapinsert).

Каждый maptype содержит подробную информацию о свойствах этого вида карты от ключа до элемента. Он содержит информацию о ключе и элементах. maptype.key содержит информацию об указателе на ключ, который нам передали. Мы называем эти дескрипторы типов.

В _type типе есть такие параметры, как его размер. Это важно, потому что у нас есть лишь указатель на значение ключа, но при этои нужно знать, насколько оно велико, что это за тип: это целое число, это структура и так далее. Нам также нужно знать, как сравнивать значения этого типа и как хэшировать их, для этого предназначено _type.alg поле.

В твоей программе Go есть одно typeAlg значение для каждого типа_._

Собрав все вместе, получаем runtime.mapaccess1 функцию, слегка отредактированную для лучшего понимания.

Отметим, что h.hash0 параметр передается в alg.hash. h.hash0 — это случайное значение (random seed), сгенерированное при создании карты. Именно так среда выполнения Go избегает коллизии хэшей.

Начальное значение добавляет некоторую степень случайности в хеш-функцию, обеспечивая некоторую защиту от атак столкновений.

Реализация карты в Go представляет собой восхитительный компромисс между C++ и Java, в котором используется хорошая часть опыта из других языков с учетом недостатков в других языках.

В отличие от Java, ты можешь использовать скалярные значения, такие как символы и целые числа, без накладных расходов на упаковку. В отличие от C++, вместо N runtime.hashmap реализаций в финальном двоичном файле есть только N runtime.maptype значений, что существенно экономит место в программе и время компиляции.

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

Дополнительно о структуре runtime.hmap ты можешь прочитать в следующих материалах: