Как на самом деле устроен тип Map в Golang? | Golang под капотом
Рет қаралды 64,092
Күн бұрынВ этом видео мы в деталях разберемся, как устроен тип Map в Go и сможем ответить на некоторые очень интересные вопросы:
- зачем заранее аллоцировать память под мапы?
- почему порядок их обхода случайный?
- почему нельзя взять ссылку на элемент мапы?
- и др.
----
❤️ Если у вас есть желание поддержать развитие канала:
/ tuzov
boosty.to/nikolay.tuzov
- 👾 Мой канал в Telegram: t.me/ntuzov
- 🗣 Чат в Telegram: t.me/+zsSZ63wEJDs3NGVi
- 👀 Golang Digest: t.me/golang_digest - мои регулярные подборки интересных материалов по Go.
----
Видео про Хэш-таблицы: • Хэш-таблицы за 10 минут
Видео про дженерики: • Пробуем дженерики Go н...
Видео про Slice: • GoLang Slice в деталях...
----
Исходный код Map в официальном репозитории Go: github.com/golang/go/blob/mas...
Тайм-коды
00:00 Вступление
00:24 Что такое Map?
00:55 Простая реализация - перебор
01:56 Как сделать лучше - разбиваем на бакеты
03:21 Хэш-функция - равномерное распределение по бакетам
05:08 Как реализовать Map без дженериков?
08:20 v = m[k]: во что на самом деле это скомпилируется?
09:25 Все преобразования операций с Map
10:27 Внутренняя структура Map
11:33 Low order bits (LOB) - выбор бакета
13:39 Структура бакета
15:31 Исходный код заголовка Map (hmap)
16:05 Исходный код поиска значения в Map (mapaccess1)
23:30 Переполнение бакета
24:47 Рост Map при заполнении
27:05 Эвакуация данных
28:02 Как избежать эвакуацию данных и ускорить программу - аллокация памяти
28:39 Почему нельзя взять указатель на элемент Map
29:26 Или можно..?
30:12 Порядох обхода мапы - почему он случайный?
31:47 Вывод функции fmt.Println() - почему он фиксированный?
33:14 Подводим итоги
33:45 Заключение
#golang #go #tuzov
@nikolay_tuzov Жыл бұрын
👾Мой канал в Telegram: t.me/ntuzov Пишу там новости, анонсы своих активностей и просто интересные мысли Также с его помощью я получаю от вас оперативный фидбэк по роликам - что нравится, что не нравится, какой ролик делать следующим и т.п. ❤ Если у вас есть желание поддержать развитие канала: Секретный телеграм-канал: - В рублях: t.me/+1UPXV_DGnG1mODJi - В евро: t.me/+hedI8LevYTc5MDM6 boosty.to/nikolay.tuzov www.patreon.com/tuzov
@crazy_fedor 10 ай бұрын
Это лучшее видео о внутренней кухне языка которое я видела. Бесконечная благодарность 💔💐
@user-cb1ig3zt2o Жыл бұрын
В самое сердце! Продолжай нести добро в этот мир!
@mini_clop Жыл бұрын
Очень нравиться такой подход, а именно углубление в изучение решений разработчиков с разбором. Крайнее полезно, спасибо!
@theeasywaytr4293 Жыл бұрын
Как же я Вам благодарен! Один из лучших каналов в данном сегменте, спасибо!
@user-fw9fe5os9h Жыл бұрын
Огромное спасибо автору за подробный разбор темы!!!!!!!!!! То что надо!
@AnnaKopteva Жыл бұрын
Спасибо большое за ваш труд! Смотрю все ролики с большим удовольствием:)
@alexvol7903 Жыл бұрын
Спасибо, отличное видео, хорошо освежает знания в памяти, ждем видео про устройство типов в го!
@elvirakharunova1589 3 ай бұрын
Спасибо огромное за такое подробное и подкрепленное исходным кодом объяснение! :) Ждем видео о том, как устроены типы данных в Go! :) Это будет просто пушка :)
@bakelev 2 ай бұрын
Спасибо за труд. Хорошо объясняешь. Ждем продолжения
@liz2k 5 ай бұрын
Спасибо большое за все эти уроки по ГО. Я очень люблю Low-Level понимание процессов и на каждом видео получил необычайное удовольствие. Этот материал как раз тот, которого мне не хватало чтобы начать работать с ГО. (я не новичок и мне просто не хватало хорошего материала которые разъясняет все эти нюансы)
@user-ew2pd6fq8j Жыл бұрын
Друг ты реально топ))), вот это мужик!!! Спасибо за старания!!!
@gaidarraskolnikov7195 Жыл бұрын
Да уж, спасибо тебе за труд в подготовке таких качественных материалов!
@user-uq1sc3ir2k Жыл бұрын
Очень круто, спасибо! Отдельное спасибо за разбор исходного кода Go
@user-fm4do1eh7b Ай бұрын
Лучшее видео про map! Спасибо)
@SuperSpongeBobik Жыл бұрын
Большое спасибо за Ваш труд! Это самое подробное и понятное описание мап
@tigranrostomyan9231 9 ай бұрын
Невероятно. Огромное спасибо!!
@alexpanov4678 Жыл бұрын
Очень интересный урок. Спасибо!
@victorklimov3175 Жыл бұрын
Отличное видео! Огромное спасибо автору!
@simonmo3golom Жыл бұрын
Спасибо за ваш труд! Намного понятнее стал принцип работы с бакетами внутри map :)
@user-kl4ii1nd1e 10 ай бұрын
Самое крутое в ролике, что какие-то моменты ты проговорил один раз, но потом прошелся по моменту ещё раз, чтобы подробней объяснить тяжелые вещи, спасибо!
@user-pt4iz2py6k Жыл бұрын
Что хочется поставить во главу угла, так это слова - Ролик отличный! Я смотрел его после видео про мапы с GopherCona 2016 года + прочтения пары небольших статей на эту тему) Мне казалось, что я уже смаплен на знания мап, и, по-началу ролика так и было, вы, мистер Старший разработчик категории 2, уточняли и чуть дополняли те моменты, что я выудил из GopherCon-a, и я уже было думал такой, что сейчас напишу - неплохойперезаливпереводролика2016годасгоферконамэн! Но в один момент я начал понимать, что просто начинаю понимать, а до этого я лишь думал, что я понимаю. Всё настолько просто и последовательно, с таким желанием, с подготовленной последовательной структурой, с желанием научить и быть полезным - прям топовый топ! Спасибо, Николай - это было отличные и очень полезные 34 минуты и 32 секунды! Даже для того, кому казалось, что он уже что-то понимает!) Ждём шедулер!)
@user-uv7jl8vl3r Ай бұрын
Ну мужиик 👍!! Спасибо огромное за видео!
@mikhaildiesperov2345 Жыл бұрын
Я очень рад, что нашёл этот канал. Продолжай!
@Dantesik1 Жыл бұрын
Спасибо! Теперь я знаю как устроен тип map!
@vladimirmakarov6344 11 ай бұрын
Николай, спасибо за видео
@andrewpopov9910 Жыл бұрын
Спасибо. Познавательно.
@vangog63 Жыл бұрын
Спасибо за отличное объяснение!
@pavel_trpn Жыл бұрын
Лучшее лекция по ИТ что я видел за долгое время
@roudder6606 Жыл бұрын
подробное хорошее видео, спасибо
@zhanbolatnurutdin30 Жыл бұрын
Здравствуйте, Николай. Спасибо за очень классные видео))) Однозначно лайк, подписка, колокольчик)))
@vladkorsak2163 Жыл бұрын
Круто. Спасибо!
@smittychannel3252 Жыл бұрын
о класс..сейчас чайка налью... и смотреть))).Всем приятного!!!🎉
@izqbr8493 Жыл бұрын
Да это просто клад!
@virtualriot4062 Жыл бұрын
Объяснение великолепное, канал - супер. Очень хотелось бы увидеть в вашем исполнении разбор интерфейсов, а именно их внутренне устройство, что "под капотом" и как работает
@nikolay_tuzov Жыл бұрын
С удовольствием расскажу об этом, такая тема уже есть в планах 😊
@virtualriot4062 Жыл бұрын
@@nikolay_tuzov очень жду!)
@sergiusnovikov Жыл бұрын
великолепное видео. спасибо большое. подписался, колокольчик тыкнул)
@Kuchaian Жыл бұрын
Очень крутое видео!
@andreipopov2700 Жыл бұрын
Просто лучший! 🙂
@mrmarkovniktgv3058 9 ай бұрын
Николай, на 15:20 вы сказали, что планируете отдельный ролик про внутреннее устройство типов данных в Go. Было бы очень интересно посмотреть видео на эту тему. Большое спасибо за контент)
@sovrinfo Жыл бұрын
Спасибо за видео. Коммент в поддержку!
@4sat564 Жыл бұрын
хорошее видео. Хотелось бы подобное про интерфейсы
@sudobooo Жыл бұрын
Чел, ты жётский, спасибо большое, очень грамотно объясняешь
@vladsvyatobatko5613 Жыл бұрын
Спасибо большое!
@ide9827 7 ай бұрын
Николай красавец вперед дерзай
@user-iy7rm7dt8x Ай бұрын
Лайк поставил. Интересно. GO!!!
@_po1nt Жыл бұрын
топ. продолжай, пожалуйста
@illia_v Ай бұрын
Не умопянули ещё одну важную вещь. При удалении елементов в мапе, бакеты не уменьшаются и занимают место в памяти. Поэтому иногда лучше создать новую мапу и скопировать туда елементы. Предыдущую мапу удалит сборщик мусора. Второй вариант это использовать поинтеры для значений. Сегментов будет такое же количество, но занимать они будут меньше места (8 байт для x64 на одну ссылку). Но если ключ или значение больше 128 байт, то поинтеры будут созданы автоматически. Ну и третий вариант это комбинация первых двух.
@batpyiiikob7245 5 ай бұрын
Человечище!
@user-ee1lx1pe7n Жыл бұрын
Спасибо!
@vladtokarev146 7 ай бұрын
Отличный канал бро, уже на третьем видео залипаю
@ArtemCYOU Жыл бұрын
лайк) стоило еще рассказать про конкурентную работу с мапой и какой фейл там может произойти
@nikolay_tuzov Жыл бұрын
Конкурентная работа с мапой - неплохая тема для отдельного ролика. Не хотелось затягивать, и так на пол часа вышло =) Но одну важну деталь я дейстивтельно забыл упомянуть - с мапой можно выполнять параллельные читающие операции, поскольку эвакуация данных не происходит во время поиска значения.
@AndriiKuftachov 9 ай бұрын
Супер!!!
@user-yi9yo8bd4j 26 күн бұрын
А про выравнивание типов нет видео еще? Было бы интересно посмотреть
@nekruzrabiev1351 Жыл бұрын
Спасибо за лекцию. Как происходит удаление ключа из бакета ? Ключ удаляется или помечается как удаленный?
@alexricher2554 27 күн бұрын
Антоха МС решил не останавливаться на построении муз карьере и решил строить карьеру в IT на гошке. Лайк этому трудяге
@dshyryayev Ай бұрын
Super!!!
@OmgOrganic 10 ай бұрын
Посмотрел на одном дыхании, хоть я вообще питонист и с го никогда не работал :)
@daniyarkhairutdinov5275 7 ай бұрын
В структуре map-ы никакая криптостойкость от хэш функции не требуется, не нужно путать хэш функции используемые для криптографии и для шардирования.
@eduardmart1237 2 сағат бұрын
Да. Да. Прям бросается в глаза. Но тут можно наверное притянуться за уши то что это опять поотравномерность, и что все элементы не попадут в один бакет.
@valerypyzhyk5881 Жыл бұрын
Даёшь ролик про подробное устройство типов данных в Go!))
@TaranKonstantin 5 ай бұрын
Спасибо за видео, очень доступно. Возникает вопрос, если мы создаем мапу make(map[string]int, 10) можем ли мы быть уверены что положив туда 10 элементов точно не произойдет выделения доп памяти и эвакуации данных? По идеи не можем, ведь возможны коллизии и теоретически все эти 10 элементов могут указывать на 1 бакет. Поэтому не очень понятно что именно происходит когда указываем конкретный размер мапы в make()?
@artemkashipov9865 2 ай бұрын
Там не совсем в два раза увеличение происходит при эвакуации бакетов. Там вроде как специальная формула есть, которая меняется в зависимости от текущего размера
@d33pF41L Жыл бұрын
бакеты бакеты бакеты ничего не понятно, но очень интересно (с)
@antoniusupov Жыл бұрын
Ты крутой
@vladimirsaraikin6888 4 ай бұрын
А можно, пожалуйста, еще раз объяснить, почему на мапу должны выделять память через make? я понимаю, что иначе будет nil, но что такого в устройстве ее особенного? или можно таймкод скинуть, где я это упустил
@EndlessPloex Жыл бұрын
Привет. Подскажи, асимптотическая сложность вставки в мапу это 10? А удаления? Получение получается 01? Можешь объяснить в кратце этот момент? Честно не понимаю к чему такие сложности, ну принцип работы мапы ясен, задаёшь размер памяти изначально, для чего все эти углубления, про асимптотику и тп непонятно для меня))) Функции же уже определены под капотом, как на них влиять в процессе, помимо ограничений в памяти?
@nikolay_tuzov Жыл бұрын
Это довольно простая тема, но в комментариях всё равно сложно объяснить. Крайне рекомендую почитать книгу "Грокаем алгоритмы" - она довольно маленькая и написана очень понятным языком. Уверяю, после неё подобных вопросов не останется.
@user-gj1ce7og3f Жыл бұрын
Доброго времени суток. Разберите, пожалуйста, структуры и собственные типы данных с указателями
@deadlydenier6469 Жыл бұрын
Спасибо, отличное видео! Планируется ли видео об указателях?
@nikolay_tuzov Жыл бұрын
Пока не планируется. Даже не знаю, что о них можно рассказать на целое видео =) Есть идеи?
@deadlydenier6469 Жыл бұрын
@@nikolay_tuzov Прям подробный рассказ со всеми нюансами и тонкостями
@naneri 7 ай бұрын
Думал - чо такое длинное видео, на 34 минуты. Так его еще и на 0.75 пришлось смотреть, чтобы не потерять суть.
@zhanbolatnurutdin30 Жыл бұрын
Хотел задать вопрос один, насчет эвакуацией данных. Когда слайс из бакетов заполняется, и надо новую память аллоцировать для списка бакетов, го также, вдвое больше берет памяти или по какому то другому алгоритму увеличивает память?
@nikolay_tuzov Жыл бұрын
Я об этом говорил в части про бакеты - 27:05 Будет выделено в 2 раза больше бакетов.
@zhanbolatnurutdin30 Жыл бұрын
@@nikolay_tuzov да, спасибо, я что то упустил видимо этот момент когда писал себе лекцию))) Еще раз, спасибо
@izet2240 Жыл бұрын
Я про старшие и младшие биты хэша немного не понял. Когда используются LOB, а когда HOB?
@victorklimov3175 Жыл бұрын
3:58 Даже если hash-функция будет очень медленной, то от этого мапа работать за константное время не перестанет. O-нотация не задает ограничения на время работы опереции. Можно придумать примеры, когда алгоритм работающий за линейное время будет работать быстрее, чем другой алгоритм работающий за константное время. Естественно не на большом количестве данных, но все же.
@nikolay_tuzov Жыл бұрын
Согласен, вы правы. Когда я называл медленной функцию с линейным временем, я имел ввиду ассимптотику. Наверное, стоило это уточнить.
@alexfederov7772 Жыл бұрын
@@nikolay_tuzov подскажите с чего начать изучение если в целом общее представления о всех понятиях в go имею, но ролики Ваши про хэш таблицы и мэпы как на китайском для меня пока что даже 5% не понятно из того что говорите, go это первый язык с которым я столкнулся , прочитал пока пару книг и пытаюсь практиковаться повторяя за обучающими роликами ..
@nikolay_tuzov Жыл бұрын
@@alexfederov7772 Во-первых, я бы не советовал начинать с Го. На мой взгляд, лучше начать с Python. Он и проще, и область применения намного шире. Но это субъективно, тут решай сам, сравнивай разные мнения. Во-вторых, я бы посоветовал много практиковаться, и писать самому. В плане алгоритмов, на первых порах можно ограничиться замечательной книгой "грокаем алгоритмы". Она написана супер простым и понятным языком, быстро освоишь основы. Самое главное - не переживай на счет того, что многое по началу непонятно. Так всегда и у всех. Со временем все само в голове уложится, если на это тратить время и практиковаться. Ну и заглядывай в мои телеграм каналы и чатик, я частенько там делюсь советами и т.п. (ссылки есть в описании видео)
@alexfederov7772 Жыл бұрын
@@nikolay_tuzov большое спасибо за развернутый ответ!
@user-rp5ej1ui4g 7 ай бұрын
Спасибо за видео. Но для меня некоторые места остались темными. 1. когда вычисляется lob то количество бит равно логарифму от количества бакетов. А если количество бакетов не равно степени двойки, то не будет однозначного соответствия между бакетами и значениями lob. Нет ли такого, что внутри поддерживается что количество бакетов всегда равно степени двойки, и если мы делаем make(m[int]int, 1000) то бакетов будет 1024? 2. Не очень понятно как происходит эвакуация. Допустим коэффициент заполнения стал больше 6.5 мы алоцировали новую мапу с количеством бакетов в два раза большим. Теперь у нас есть операции получения, удаления, вставки (которая может быть просто перезаписью) и итерации по мепе. окей, если это не итерация, то можно сходит в две мепы и сделать все что нужно. Потом после нескольких таких операций происходит итерация по мепе, и вот тут вообще не понятно что происходит. часть данных эвакуировалось, а часть нет, но также у нас могли быть новые значения, которые нет в старой мепе.
@TheDavBag Жыл бұрын
сложно =) но достаточно интересно
@markarkron8443 Жыл бұрын
А если у нас нечетное кол-во бакетов какое будет поведение?
@def9572 Жыл бұрын
Николай, по мимо go есть ли опыт в других языках?
@nikolay_tuzov Жыл бұрын
Да, я на разных писал - php, python, java и др. Но если говорить про коммерческие проекты, то в основном php и go
@almassagyndyk4707 24 күн бұрын
Получается если алоцировать Мапу с длинной равной 2 у нас в структуре мапы будет один бакет?
@user-do4gc6ys5y Жыл бұрын
В Kotlin есть LinkedHashMap. Там происходит итерация по элементам в порядке добавления в Map.
@nikolay_tuzov Жыл бұрын
Всё зависит от целей разработчиков языка, чему они отдают приоритет - памяти, скорости, каким-то фичам вроде фиксированного порядка и т.п. Это всегда какой-нибудь trade-off
@galandec2000 6 ай бұрын
у меня вчера мапа вывелась один раз не оп очереди вставленных элементов, а потом да еще 10 разу отсортировано.)) так и не смог поймать еще раз тоже состояние что было изначально показано. скорее всего игра кеша ибо через run запускал а не билдил.))
@user-fw9fe5os9h Жыл бұрын
Такой вот вопрос: Действительно ли нельзя взять адрес элемента мапы из-за миграции? В слайсе у нас тоже происходит перевыделение памяти, и там мы можем взять адрес, хоть он так же может потерять свою актуальность.
@nikolay_tuzov Жыл бұрын
Эвакуация данных не делает процедуру взятия указателя принципиально невозможной. Просто реализация становится очень сложной. Слайс, всё же, намного проще мапы - там внутри простой массив, а не сложная структура бакетов. Да и процесс копирования данных у слайса происходит сразу, а не постепенно. Но вполне возможно, что я что-то ещё упускаю.
@nikolay_tuzov Жыл бұрын
Вообще, это очень хороший вопрос. Если в целом тебе подобные темы интересны, заглядывай в наш чатик, будем обсуждать. t.me/+WyjmnP6la_QyYjAy
@user-sc9xm3gp7l 5 ай бұрын
будет такое же видео об интерфейсах, сборщике мусора, горутинах?
@nikolay_tuzov 5 ай бұрын
Да, будет
@user-ev5ig3jl3k 25 күн бұрын
28:35 Николай: мы можем указать размер мапы, таким образом, ЭВАКУАЦИИ ДАННЫХ НЕ ПРОИЗОЙДЕТ 29:13 Также Николай: мы не можем взять указатель, потому что в какой-то момент ПРОИЗОЙДЕТ ЭВАКУАЦИЯ ДАННЫХ 😂😂
@nikolay_tuzov 25 күн бұрын
Очевидно, что эвакуация не произойдёт, если мы добавим ровно столко элементов, сколько запланировали, не больше. Но компилятор наши намерения не знает, эвакуация всегда должна быть возможна, поэтому указатель взять нельзя.
@user-ev5ig3jl3k 25 күн бұрын
@@nikolay_tuzov да, я это понимаю, но неужели компилятор и рантайм го настолько глупый? условно, там же есть оптимизации, когда слайс растет х2, потом х1.25, неужели с эвакуацией мапы нет ничего такого?
@user-ev5ig3jl3k 25 күн бұрын
Например, для мапы с постоянным размером отдельный тип const size map под капотом, который позволяет брать указатели Как для массива есть тип отдельный, а для непостоянного слайса другой тип (array с заданным размером и slice - разные типы в го)
@ziliboba73 Жыл бұрын
Спасибо большое, я бы тебя украл и дома посадил :))) Все быстро, четко и главное на понятном русском языке.
@_uncle_bob_ 8 ай бұрын
go смердит как старый добрый с, то количество ограничений, которое в него вколотили создатели ( видимо в угоди скорости компиляции ) полностью отбивает какое либо желание с ним работать. Видео хорошее, на мой взгляд немного перегружено кишочками и наверное будет неудобо варимо для начинающих.
@niklkelbon3662 Ай бұрын
Такой херни даже в самом плохом С редко увидишь
@user-jx8jl7nc3j Жыл бұрын
Как понять в: бакете лежит 6 с половиной значений?) kzfaq.info/get/bejne/hsWDi7eGzqeRaY0.html
@nikolay_tuzov Жыл бұрын
Ключевая фраза - "в среднем". Например, если у тебя 2 бакета, и в одном лежит 7 значений, в другом 6, то среднее значение будет - 6.5: (7 + 6)/2 = 6.5
@xotamxudoyberganov5847 Жыл бұрын
eta tochno shto make rabotayet dlya map ?? ya gdeta videl shto gavarili make bespolezniy dlya map
@ilyadruzh 11 ай бұрын
Не слайсы, а срез. Про мэп вообще молчу 😂
@nikolay_tuzov 11 ай бұрын
Ну да, надо было говорить - карта Как устроены карты в Go?
@ilyadruzh 11 ай бұрын
@@nikolay_tuzov а ты типы данные хорошо знаешь? Какие типы данных из компьютерных наук соответствуют типу map? Там есть подходящие, кали тебе не нравится слово карта. Да и можно «карты», в английском это слово ровно это значит и никого не стремает это. Только наших застенчивых и закомплексованных кодеров смущает прямое значение слов.
@nikolay_tuzov 11 ай бұрын
@@ilyadruzh а зачем что-то выдумывать, если есть уже привычные map и слайс? Они вошли в обиход, и чаще всего говорят / пишут именно так.
@ilyadruzh 11 ай бұрын
@@nikolay_tuzov ага, хомяки именно так говорят и потом плавают в сутевой части, несопосбные объяснить почему слайсы это именно слайсы и мапы. Как попугайчики выучившие красивые слова)) Используемые термины - показатель квалификации и умение думать, а не повторять.
@rumartru Жыл бұрын
Лайк поставил, ибо материал хороший, но подача... монотонное чтение... три раза начинал смотреть, но так и не осилил.
@pawelf.7568 Жыл бұрын
Спасибо! Прям удивился что можно вот так вот просто и доходчиво этот материал изложить! А можно пж про реализацию хеш-функции рассказать? Мне кажется это было бы тоже интересно и полезно.
@nikolay_tuzov Жыл бұрын
У меня есть видео про хэш-таблицы, и там есть и про хэш-функции (самые простые)
@pawelf.7568 Жыл бұрын
@@nikolay_tuzov Да, я его залайкал. Я имел ввиду - особенности так сказать гошной хеш функции. У меня такое спрашивали по крайней мере на собесе
@0xGod Жыл бұрын
А я откуда знаю? Чо ты у меня спрашиваешь?
Николай Тузов — Golang
Рет қаралды 50 М.
Comedy Club
Рет қаралды 164 М.