Как на самом деле устроен тип Map в Golang? | Golang по… — Transcript

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

на элемент map и некоторые другие вопросы. А меня зовут Николай Трусов, и я рад приветствовать вас на своем канале. Давайте представим, что мы инженеры Google, и перед нами поставлена задача реализовать тип мэр. Будучи хорошим инженером, и конечно же, начнем с того, что

сначала разберемся, что же вообще такое тип map. И мы по то некая абстрактная структура данных, которая умеет выполнять три простых действия: это вставка, удаление и поиск элемента по ключу. Плюс к этому есть одно обязательное требование. Она заключается в том, что все операции

должны выполняться за константное время, то есть скорость выполнения должна зависеть от количества имеющихся данных. Давайте придумаем для него не будет простенькую реализацию, например, простой перебор. Как мы это сделаем? Мы заведем тип entry, которая состоит из двух полей: key и value, то есть ключ и значение.

Iso мама по будет представлять из себя список или в случае gaslight из значений типа n 3. Давайте представим, как в ней будет выполняться поиск по ключу. Допустим, этим будет заниматься функция lookup. На вход она принимает саму маму и

ключ, по которому мы ищем. Далее мы перебираем все значения map и сравниваем ключ каждого из них с тем ключом, который мы получили. И если мы что-то находим, то возвращаем значение, и если мы ничего не нашли, то вопроса возвращаем 0. Казалось

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

зависеть линейная, то есть работать оно будет довольно медленно, и таким образом она нам не подходит. Давайте подумаем, как сделать лучше. Мы можем разбить по какому-нибудь признаку все наши данные на небольшие группы с фиксированным 1 миром. Такие группы называются бакетами, и

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

мы подберем bucket и таким образом, чтобы в каждом из них было не более четырех значений. Если данных накапливается много, мы просто добавляем количество пакетов, то есть разбиваем на более мелкие группы, и у нас все ещё будет четыре человека в

каждом пакете, то есть количество элементов, которые мы перебираем при каждом поиске, будет фиксированным, то есть константным. Получается, что время поиска константное, и она не зависит от количества элементов. Таким образом, этот вариант нам вполне подходит. Но давайте посмотрим еще вот на такой пример.

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

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

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

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

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

теряется, то есть наша мама не будет работать за константное время, и это плохо. Следующее свойство — это инкриминированность. Она заключается в том, что для одного и того же ключа хэш-функция должна возвращать один и тот же номер bucket, а суть его, я думаю, очевидна.

То есть если мы положили что-то в бакет по ключу, то мы также должны найти это по тому же самому ключу в том же самом бакете и сделать это неограниченное количество раз. И последнее свойство — это клип, устойчивость. Это уже более интересное

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

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

Естественно, немного посложнее, со своими нюансами, но главное, что базовую идею мы поняли. Теперь давайте немного приземлимся и посмотрим, как реализовать все эти наши задумки в языке. Сейчас мы видим синтаксис получения значения по ключу, и мы ожидаем, что эта строчка

компилируется примерно вот так: в пакете runtime будет какая-то функция lookup, ожидающая на вход маму и ключ, по которому мы ищем значение. Давайте подумаем, как может выглядеть сигнатура такой функции. На самом деле она должна выглядеть примерно вот так. Эта строчка

говорит нам о том, что нам нужны generique. Это вполне логично, потому что у ключа и у значения могут быть разные типы данных, и заранее мы даже не знаем, какой именно тип мы получим. Кстати, если вы не понимаете, при чем тут же generique и что это вообще такое, то можете найти у меня на канале отдельный ролик по ним. Я там подробно рассказываю и показываю их на практике, но для понимания текущей ситуации generique особо не нужны, потому что в реализации мэп они не участвуют, тем более что они

появились относительно недавно. И сразу скажу, что интерфейса здесь также не используются. Что же, давайте разберемся, как разработчики обошлись без generique и интерфейса в случае, когда функция на вход принимает аргументы, у которых тип данных не определен. Во-первых, все операции выполняются с помощью interface{} и

pointer. Его фишка в том, что он может указывать на что угодно, то есть ячейка памяти, на которую указывает такой указатель, может относиться к любому типу данных. Но естественно, что когда мы получаем такой вот unsafe pointer, нам нужно понять, что там вообще лежит и как

с этим чем-то работать. Для этого используются так называемые дескрипторы типов, то есть вся информация о типе, которая нам нужна для работы, хранится в таком вот type и скрипте re. В частности, чтобы работать каким-то значением, нам естественно нужно понимать, как, например,

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

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

тип nat type, и в нем есть поля key и value соответственно. В них хранится информация о ключах и о значении, с которыми работает эта мапа. И теперь я предлагаю посмотреть, как все эти типы выглядят в коде самого языка. Это, во-первых, позволит

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

нам наладить более тесные отношения с гор и также это позволит убедиться что я тут ничего не сочиняю во-первых давайте посмотрим на тот самый тип map type и здесь мы видим что действительно и у ключа и у значение то есть у элементов

чётко определён без фильтр типа и также давайте передём к определению дескриптора типа и посмотрим из чего он состоит здесь мы действительно видим что в дескрипторы хранится и размер ее та же самая функция эквол и другая информация но к сожалению я здесь не вижу функцию с

помощью которой мы будем хэшировать значение потому что я вас похоже обманул и такая функция на самом деле содержится структуре mathtype поле которое содержит называется фишер и если верить и комментарием разработчиков то это действительно то самое поле что же

двигаемся дальше и уже с полученной информации давайте представим как будет выглядеть компиляции этой строчке здесь код будет чуточку посложнее поэтому давайте разберем его прямо построчно во первых что проведем с ключом как вы выяснили внутри map мы работаем только

сенсеев pointer поэтому нам сначала нужно получить указатель на этот ключ и потом сконвертировать его badass моисеев помнить их теперь мы можем по смотреть как выглядит сигнатуру функции лука на вход она получает три аргумента во первых это тот самый map type который мы

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

с ним работу нам нужно провести некие манипуляции манипуляции нехитрые и выглядят следующим образом мы сначала приводим он сейф pointer кука залью на нужный нам тип данных и потом берем его значение то есть проводим так называемые разыменования и в конечном итоге мы

наконец получили то значение которое собственно искали аналогичные преобразование так же происходит и с другими операциями и со ставкой и с удалением и давайте посмотрим на их полный список во-первых мы видим что на самом деле функция которая превращается строчка получения значения называется не

look up a map xs1 почему один потому что как мы знаем у этой операции есть два варианта во первых мы можем получить одно значение и это будет то значение которое собственно хранится в mapi и у нас есть также вариант получить два

значения это все еще будет тот элемент который хранится в маке плюс некий флаг который говорит о том что в mapi вообще что-то хранилось по такому плечу я надеюсь что с этим синтаксисом вы в целом знакомому если нет то почитайте

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

функциям даже разберем их колота пока давайте вернемся к структуре им об их так как же нам все-таки выглядит на самом деле она состоит из двух частей во первых это тот самый хедер которым я говорил ранее их ядер хранит в себе

общую информацию про маму во-первых это конечно же размер то есть количество элементов который хранится в мафии во вторых это количество пакетов и вот количеством bucket of есть один интересный момент на самом деле это значение храниться не в чистом виде де

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

и действительно в этом убедимся также мы видим здесь параметр hair set и он позволяет нам выполнить условия безопасности которые мы предъявляли к нашей мамы чуть ранее то есть он усложняет подбора ключей таким хитрым образом чтобы заполнить одни bucket и

больше чем на другие и наконец самый важный параметр это указатель на вторую часть map и то есть на список пакетов по сути это действительно просто список пакетов но здесь есть один очень важный и интересный момент мы видим что каждого

баки то соответствует так называемый младший бит их сша или ордер pets их назначение очень простое они просто помогают искать нам bucket и из предоставленные хэш-функции но давайте все же становимся на ней поподробнее и посмотрим как они устроены и это котла

ордер bid что это такое премьера у нас есть какой-то ключ мы применяем к нему хэш-функцию и выходе получаем число но число это очень большое a bucket of у нас например всего 4 штуки и каким образом за поставить это число багетa

делается это очень просто с помощью остатка от деления мы делим число на количество баки так смотрим остаток и собственно этот остаток будет соответствовать уже непосредственно баки то и конечно же для ускорения вычислений операция в вычислении остатка отделения выполняется побитого то есть во первых

мы приводим число к двоичному виду и дальше для того чтобы получить остаток от деления на 0 сюрприз потребуется логарифм открыть что bucket of именно тот самый логарифм который хранится в заголовке map и это будет логарифм по основанию 2 то есть степень двойки

другими словами чтобы получить количество баксов или же число 4 нам нужно возвести двойку вторую степень и соответственно остатку отделения будут соответствовать 2 бита младшего порядка если бы качество bucket охранялась например 8 то логарифм был бы равен трем потому что для того чтобы получить 8 нам

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

дальше что же мы получили остаток от деления это число соответствует и кому-то баки tool и мы даем ему имя ордер bid то есть тот самый параметр r кубе который мы видели ранее что же мы разобрались со структуры самой map и мы поняли как с

помощью сша находить нужные багеты и теперь давайте заглянем в эти самые багет и как они выглядят внутри во-первых их можно также условно разбить на две части во первых это 8 слотов уже для старших битов хэша и процедуры их

получения точно такая же как процедура получения младших битов суть этих значений заключается в том чтобы быстро проверить наличие ключа в текущем боккетти то есть вместо того чтобы сразу перебирать все ключи и сравнивать их с искомым ключом мы сначала пройдёмся по

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

операция более тяжеловесная также я большую ваше внимание на то что количество слипов равняется 8 и действительно в каждом боккетти может храниться не более 8 значений таковы правила игры и так двигаемся дальше и теперь я скажу что на самом деле я

немножко упростил внешний вид bucket а на самом деле он выглядит вот таким образом то есть ключи и значения хранятся в виде обычного списка сначала идут ключ и затем пустые слоты если записи и меньше 8 и дальше идут значения

кстати такой порядок расположения не случайный мы могли бы разместить и ключей и по другому то есть чередовать их со значениями то есть идет ключ потом значение потом снова ключ потом стал значение и так далее но разработчики почему-то поместили все ключи начала и

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

достаточно понимает что это сделано для экономии памяти здесь я основу предлагаю взглянуть на исходный код языка go во-первых давайте посмотрим на тот самый заголовок map и о котором я рассказывал это все так же обычная структура и здесь как мы видим хранится количество всех

элементов также мы видим здесь количество пакетов и к сожалению нам здесь об этом говорит не имя параметры а танки комментарий к нему и действительно это логарифм по основанию 2 также мы видим так называемый хасид о котором я говорил и естественно самое главное

ссылка на список самих bucket of давайте посмотрим на функцию map xs1 то есть это та самая функция lookup которая ищет нам значение com api на самом деле код получения значения из баг это не такое уж и сложно как мы могли подумать

давайте его разберем но будем разбирать только самое важное во первых здесь мы видим код который отвечает за состояние гонки на нем мы не будем подробно останавливаться потому что это очень сложная тема и увезет нас далеко в сторону и начнем мы вот с этого блока

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

получение кэша от переданного ключа для этого используются а та самая функция фишер из типа mathtype следующие строчки мы видим вызов некое функции bucket мозг и на самом деле несмотря на название это функция для получения тех самых младших битов сша то есть получение остатка и

отделения давайте в нее заглянем и убедимся что она не такая уж страшная комментарии нам подсказывает что здесь выполняется сдвиг единички на количество пакетов вернее не на количество багетов она степень двойки то есть на тот самый логарифм и от значения после этого с 2

отнимается единица суть эта операция очень простая давайте вам попробую наглядно это показать например 300 баксов нас будет равно четырем как в том примере которые я вам показывал и соответственно логарифм будет равен тум то есть логарифм от четверки равен

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

выполняем сдвиг этой единички то есть мы двигаем ее на два шага влево получаем вот такое число и последним действием мы отнимаем от этого числа единичку и в результате уже это операции мы получаем вот такое конечное число единичка пропадает и в конце появляется две новые

единички это универсальная операция если бы у нас единичка лежала например вот в этом разряде и мы снова бы отнять единицу то она также пропала бы из этого разряда и все нолики идущие за ней стали бы также единичками и

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

сделать мы воспользуемся битовой маской у которой все разряды равны нулю кроме тех разрядов которые мы хотим получить и если мы выполним вот такую операцию то есть операция and то на выходе мы их раз получил два последних бита изначального

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

двигаемся к следующей строчки здесь мы видим уже довольно хитрую операцию ее суть заключается в неком аналоги ссылочной арифметики то есть мы получаем ссылку на начало массива пакетов далее мы применяем нашу убита вую маску для получения остатка от hishe то есть эти

самые lawyer beats хэш и умножаем на размер пакета то есть еще раз детально и очень простым языком что мы сейчас проделали вот мы получили какой-то указатель на какую-то ячейку в памяти по сути это просто обычное число и это

число по сути соответствует первому bucket у из набора то есть баффету с номером 0 если же мы хотим получить доступ к следующему bucket у то нам нужно перепрыгнуть наш предыдущий bucket то есть вот bucket вот в нем акита лежат

значения и нам нужно перепрыгнуть из его начало в его конец и собственно мы окажемся перед вторым баки там то-есть багет с номером 1 и на самом деле у него должен быть точно такой же размер соответственно дальше идет 3 bucket и

так далее и ровно это мы здесь и проделываем мы посмотрим на размер bucket а далее смотрим на его номер то есть остаток от деления и мы знаем через сколько bucket of нам нужно перепрыгнуть ее к у них размер надеюсь это понятно и

я думаю вам очень интересно как выглядит функция f внутри потому что на самом деле не ходят ссылочные ритмики в год не бывает и это некое и эмуляция что же здесь фактически происходит мы преобразуем на шансов pointer фу тип

winter а это не что иное как обычное число далее мы прибавляем к нему необходимый сдвиг и возвращаем снова в отсек pointer все предельно просто двигаемся дальше и видим что здесь нам приходится работать с некими от baker их мы разберем чуть позже а пока давайте их

пропустим следующая строчка это получение топ hash это как раз те самые хай ордер bid стоит старшие биты хэша и они помогают провести быструю проверку на наличие ключа в боккетти здесь внутри тоже также нечего сказать естественно это просто обычный по битовый сдвиг и мы

получаем 8 старших битов нашего хэша далее мы видим ни что иное как просто прибор всех записи пакете во-первых как мы выяснили сначала устанавливается именно ой ордер bid то есть стоп каждого из значений если соответствие 11 а мы пропускаем текущую

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

текущие записи с тем ключом который передан функцию это выполняется с помощью функций и cool которой хранится descried три типа этого хэша если на сравнение было успешным то дальше выполняется все тоже нехитрая ссылочная их нити к которая помогает нам получить

значение соответствующие искомому ключу и в конце концов мы это значение возвращаем если же найти ничего не удалось то значит в багет ничего нету и мы возвращаем zero белье и собственно мы только что разобрали основные сценарии функции map xs1 то есть по сути теперь

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

функция который мы здесь видим это мой ps2 и как мы видим это функции действительно соответствует второму варианту использования получения элемента по ключу это вариант двумя значениями второе значение это логический тип вот здесь примерно такой же и я не вижу смысла его разбирать

подробно тоже возвращаемся назад к теории и теперь как раз давайте обсудим то самое переполнение как мы уже поняли в каждом пакете хранится 8 значений и не больше если же возникла такая неприятная ситуация что в баке нужно положить девятое значение то в таком случае

создается новый пакет и ссылка на него сохраняется в изначальном боккетти то есть здесь мы видим что первый bucket переполнен мы пытаемся добавить в него девятое значение для этого создался отдельный пустой bucket и это значение сохранилась уже в нем и собственно за

это и отличает от блок кода который мы пропустили на самом деле ситуации когда происходит переполнение баки то очень нежелательно потому что вычисление становятся медленными и как я говорил изначально когда рассказывал вам про идеи bucket of суть в том что размер

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

крайнем случае когда все данные попали в один пакет мы получаем простой обход и это все тоже линейное время поэтому разработчики и всячески стараются избегать таких ситуаций и именно с этой проблемой связан особый способ порядка ростом об и вспомним что слайсы примеру

растут в тот момент когда они полностью переполнены то есть когда мы хотим запихнуть и ходит элемент слайд и он туда уже не влезает то именно это становится триггером для выделения памяти под новый слайд и смотрю к сожалению все не так потому что если мы

будем забивать map до отказа то будет все больше и переполняет их bucket of потому что распределение все-таки не до конца равномерная и операция будет выполняться медленно для того чтобы разобраться какой все же момент будет выделено память под новую маму давайте

вернемся к коду для того чтобы это выяснить разработчики заботливо оставили нас такой длиннющий комментарий здесь разработчик простым человеческим языком объясняет нам чем он руководствовался здесь он говорит что если не киловатт фактор то есть степень заполнения нашей map и будет слишком большая то мы

получаем слишком много переполненных bucket of если же этот фактор будет маленьким то переполненных bucket of будет конечно гораздо меньше но мы будем тратить лишнюю память далее он говорит что он написал простенькую программу чтобы посчитать некие параметры которые напрямую зависит от этого лова сектора я

не буду подробно останавливаться на каждом из этих параметров тем более что все тот же разработчик все также подробно нам объяснил суть каждого из них здесь нам достаточно того что для создания триггера для роста map и выбранного вот строчка и более конкретно

но фактор здесь равен 6 половиной и из этого следует что память под новую марку выделяется в тот момент когда процент заполнения всех bucket of в среднем равняется 6 половиной то есть когда в каждом банкете в среднем лежи по 6

половиной значений а кстати если вам захочется самостоятельно знакомиться с этой таблицы с комментариями разработчика и со всеми теми функциями которые я сегодня показывал то все это лежит в одном и том же файле пакет runtime и файл желает самим . go и

собственно это исходный код версии языка 118 но он скорее всего предыдущих версиях он примерно такой же ссылку на этот файл и гитхабе я приложу в описании к этому видео что же возвращаемся к нашим лот фактору и когда он достиг

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

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

то есть это выполняется инка ментально и в ходе этого процесса данный просто равномерно распределяется по новым батчатом здесь важно понимать что хоть мы и избежали пауз выполнение операции но теперь эти операции будут работать медленнее потому что в момент эвакуации

нам нужно смотреть в двух местах и в старые банкетах и в новых и единственный способ избежать таких проблем это выделять память под нужное количество элементов mapi заранее то есть примеры если мы заранее знаем что в нашей маме будет 1000 записей там и при создании

map и таки говорим мы говорим компилятору сделай нам мапу нужного типа и у нее будет вот такой вот размер то есть синтезис полностью аналогичен с индексу слайс off слайсы памяти лоцируется аналогичным образом таком случае при заполнении time об

эвакуации данных не произойдет и наш код будет работать намного быстрее и также именно с процессом эвакуации связано следующее ограничение языка мы не можем взять указатель на элемент map и то есть попробуем действительно это сделать вот мы обращаемся к нашей mapi получаем

какое-то значение по ключу и говорим что мы именно хотим получить указатель на это значение здесь нам компиляторы прямым текстом говорит что он просто не может взять указатель на это значение давайте пробуем это запустить и видим все то же

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

соответствие ячейки памяти кстати данный момент возможно самые внимательные из вас могли обратить внимание что какой-то момент мы все же умудряемся получить значения на элемент map и давайте посмотрим когда это происходит а происходит это например в уже знакомой и

известной нам функцией map xs1 она возвращает указатели и это как раз указатель на значение назначение которое хранится в mapi и здесь фишка в том что указатель сразу же разыменовываются то есть сразу же получается значение на которой он указывает и сам указать

удаляется эти действия гарантированно происходит до того момента как произойдет непосредственно эвакуации поэтому все безопасную по крайней мере мы может надеяться и еще один момент на который я бы хотела обратить ваше внимание как вы наверняка знаете порядок обход map или всегда

случайный то есть когда мы пытаемся перебрать значения которые лежат в этом api каждый раз мы будем получать и какой-то рандомный порядок и действительно очень сложно реализовать такую маму в которой все ключи будут им то образом упорядоченные потому что

оператор который перебирает значение он ходит по нашим баффетом и более того он хоть и пасторы и по новым пакетом если происходило catia получается такая ситуация что порядок следования элементов зависит от очень большого количества факторов то есть это и какая

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

разработчики оставили нам о такую интересную пасхалку здесь мы видим функцию map этапе нет и она отвечает за инициализацию и троттера который собственно и совершает обход по значениям об и спускаемся немного ниже и видим такой интересный момент здесь вызывается

функция fast ранд и она отвечает за то чтобы решить с этого места начнется обход map и то есть это не как-то случайно рандомизации которая получилась процессе конструкции map и это именно четкое решение авторов языка они запускают по-честному теле генератор

случайных чисел и собственно к предок входом об и каждый раз будет разным и сейчас те из вас кто пользуется функции f em тип int n но при этом ничего не слышали по случайный порядок обхода возможно возмутятся потому что они

всегда видели что эта функция всегда возвращает отсортированный список значений папе давайте в этом убедимся например присвоим наши только что созданным это их виды значения только уберем здесь пока что локацию памяти и давайте выведем на экран содержимое этой map и

здесь мы видим что включил порядочные по возрастанию но возможно нам просто повезло и давайте запустим программу еще раз при следующем запуске возможно будет другой порядок нет порядок все тот же и давайте пробуем запустить это еще пару раз мы видим что

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

и если он выйдет maple то он просто и и сортирует и сортирует он ее кстати классическим образом просто берёт слайсы и ключей и значений сортирует слайс и возвращает нам результат собственно и в этом месте create функции и функции

printer and что же а на этом у меня все и давайте предложим те самые интересные вопросы на которые нам удалось найти ответы в процессе во-первых мы узнали зачем заранее лоцировать под маму память то есть мы поняли почему это будет

ускорять наш код далее мы поняли почему порядок обхода map и случайны и дальше убедились в этом своими глазами также мы узнали как растет maple какой момент это происходит что такое го класса данных и как это связано с следующим пунктом

почему нельзя взять указатель на элемент map и что же на этом у меня пожалуй все если вы хотите поддержать развитие моего канала то в описании к этому видео будут ссылки на patreon и busty можете ими воспользоваться за этот кроме прочего

вам полагается некоторые плюшки также я напоминаю что у меня есть свой канал с играми в котором я пишу и прагу и про я колики и другие вещи которые мне интересны и и также иногда пишу про свои ролики например там вы можете узнать

когда будет мой следующий ролики некую он будет тему по его канала у меня free грамме есть еще свой чатик в котором мы также обсуждаем go и иногда мои ролики в общем если вы хотите пообщаться ног живую то добро пожаловать и ссылка на

чатик также в описании что же она это у меня окончательно все еще раз большое спасибо за просмотр и до встречи в следующем видео