mapЭто основная структура данных в языке Go, которая часто используется в повседневной жизни. Но как это реализовано под капотом?
mapОбщая структура
ГолангmapБазовой реализацией является хеш-таблица, поэтому реализуйтеmapПроцесс на самом деле является процессом реализации разбросанной таблицы. В этой хеш-таблице есть две основные структуры, одна из которых называетсяhmap(a header for a go map), называетсяbucket. Две структуры выглядят следующим образом:
hmap:
На схеме много полей, но разобраться легкоmap, вам нужно заботиться только об одном поле, которое отмечено красным цветом: массив ведер. Структура, используемая для хранения в карте Голанга, представляет собой массив корзин. в то время как ведро (т.е.bmap) какая структура?
ведро:
по сравнению сhmap, структура ведра проще, поля помеченные красным по прежнему "основные", используемmapЗдесь хранятся ключ и значение. Массив «высокого хеш-значения» записывает «индекс», относящийся к ключу в текущем сегменте, который будет подробно описан позже. Другое поле является указателем на развернутое ведро, так что ведро формирует структуру связанного списка. Например, следующая картинка:
Это показываетhmapиbucketОтношения таковы:
Сегмент представляет собой связанный список, поэтому общая структура должна быть такой:
Характерной чертой хеш-таблицы является наличие хеш-функции, которая хэширует ключ, который вы передаете, чтобы получить уникальное значение, которое обычно является числовым значением. голангmapВ , тоже есть такая хеш-функция, и она тоже вычисляет уникальное значение.Голанг тоже очень интересен для использования этого значения.
Golang делит полученное значение на две части по назначению: старшего и младшего порядка.
Как показано, синий соответствует высокому уровню, а красный — низкому.
Затем младшие биты используются для поиска текущего ключа, принадлежащегоhmapкакое ведро в ведре, и старший бит используется, чтобы найти, какой ключ в ведре. Как упоминалось выше: в корзине есть атрибутивное поле, представляющее собой массив «хеш-значений высокого порядка», где хранится синее значение старшего порядка, которое используется для объявления того, какие «ключи» находятся в текущей корзине, который легко найти и найти.
Важно отметить, что мыmapЗначения ключ/значение в хранятся в том же массиве. Порядок в массиве такой:
Это не форма key0/value0/key1/value 1. Преимущество этого заключается в том, что, когда длины ключа и значения различны, можно устранить потери пространства, вызванные заполнением.
Теперь мы можем получить язык GomapВся структурная схема:
Выше приведена общая структура языковой карты Go.
mapрасширение
Когда приведенная выше хеш-таблица вырастет, язык Go удвоит количество массивов сегментов, сгенерирует новый массив сегментов и перенесет данные из старого массива в новый массив.
коэффициент загрузки
Условия для оценки расширения указаны в хеш-таблице.加载因子(т.е. коэффициент нагрузки).
加载因子порог, обычно выражаемый как количество элементов, содержащихся в хэше, деленное на общее количество позиций. Это баланс и компромисс между «конфликтными возможностями» и «использованием пространства»:加载因子Чем меньше значение, тем выше уровень вакантности и меньше коэффициент использования пространства, но加载因子Чем больше значение, тем выше коэффициент использования пространства, но тем выше «возможность конфликта».
Будет по одному для каждой хеш-таблицы加载因子, значение превышает加载因子Это расширит хеш-таблицу.
голангmapиз加载因子Формула:map长度 / 2^BПорог6.5. вBЭто можно понять как количество раз, когда емкость была расширена.
Когда Гоmapдлина увеличивается больше, чем加载因子нужныйmaplength, язык Go сгенерирует новый массив сегментов, а затем переместит старый массив сегментов в поле свойства.oldbucketсередина. Примечание. Вместо того, чтобы сразу экранировать элементы старого массива в новое ведро, только при доступе к определенному ведру данные из ведра будут перенесены в новое ведро.
Как показано на следующем рисунке: При масштабировании GomapВ структуре будут сохранены старые данные и вновь сгенерированный массив
Верхняя часть представляет собой старую корзину с данными, а нижняя часть представляет только что сгенерированную новую корзину. Синий цвет представляет корзины с данными, а оранжевый — пустые корзины.
При расширенииmapНовые данные не будут перенесены немедленно, а старые данные будут перенесены только при доступе к данным исходного старого сегмента, как показано на следующем рисунке:
Примечание. Это не удаляет старую корзину напрямую, но удаляет исходную ссылку и использует GC для очистки памяти.
mapУдаление данных в
если ты понимаешьmapОбщая структура системы, а также основные этапы поиска, обновления и удаления должны быть предельно ясны. Я не буду здесь вдаваться в подробности.
Примечательно, что найденоmapПосле данных в выполните следующие операции для ключа и значения соответственно:
1、如果``key``是一个指针类型的，则直接将其置为空，等待GC清除；
2、如果是值类型的，则清除相关内存。
3、同理，对``value``做相同的操作。
4、最后把key对应的高位值对应的数组index置为空。