Java для начинающих. 19.8 HashMap. Теория
Vložit
- čas přidán 10. 07. 2024
- Наконец-то мы дошли до самой мощной и быстрой структуры данных - ассоциативный массив или, по-другому. Map (Карты). Разберем все нюансы работы ее самой распространенный реализации - HashMap, почему она так хороша и когда необходимо использовать.
Ссылка на код с занятия:
github.com/dmdev2020/java-lev...
Для оформления подписки на канал жми ссылку:
/ dmdev
00:00 - Введение
00:48 - Пример Map (Ассоциативный массив)
04:08 - Структура интерфейса Map
05:07 - Структура класса HashMap
06:21 - Hash tables - как работает добавление
11:02 - Hash tables - как работает получение
12:08 - Big O notation
13:03 - Hash tables - коллизии - Věda a technologie
как-то давно сохранил ссылку на этот канал, потому что понравилось объяснение... Теперь захожу, а здесь половина видео доступно только спонсорам! сколько на ютубе, первый раз такое вижу.
Уже почти 2 года как спонсорство подключено. А сам CZcams ввел эту фичу еще раньше. Так что да, давненько ты не заходил на канал))
@@dmdev нужно эти видео как-то разделить в разные плейлисты. Чтобы включил видео и они шли по очереди. Потому что заходишь видео посмотреть, одно посмотрел, а 10 нужно переключать.
@@user-et7vb4ju6v у меня плейлисты разбиты по курсам, а не по платности/бесплатности. Что является более целесообразным для изучения материала.
пересматриваю каждое видео по 2 раза , чтобы ничего не упустить!
Все правильно!!!
Великолепное объяснение. Пожалуй, то, чего не хватало, что бы паззл про хэшмапу сложился в моей голове :)
Очень рад, что смог помочь!
Только нода в мапе перестраивается при capacity >= 64, иначе будет односвязный список😇
@@dmdev Мест у нас ограниченное количество - даже если разные хешкоды - рано или поздно они залетят в бакет где уже есть элемент. Вопрос вам - как часто такое бывает
@@bbrother92 довольно редко при хорошо написанной хэш функции. Так что не стоит об этом переживать (учитывая автоматическое перераспределение элементов, если их стало довольно много для данного ассоциативного массива)
@@dmdev еще мелкий вопрос - я правильно понимаю что equals надо переопределять в основном для хешмапы или есть еще кейсы когда это необходимо обьектам?
Лучшее объяснение, всё по полочкам. Спасибо!
Всегда пожалуйста!
10 лайков бы поставил! Чел ты лучший! Всё встало по полочкам и нода и красночерные деревья понял для чего. Спасибо тебе
Всегда пожалуйста
Раз понравилось это видео, то понравятся и другие - главное последовательно смотри, чтобы ничего не пропустить)
@@dmdev все остальные закрыты как я понял
@@alexandr6055 видео по подписке доступны, либо на других платформах (Udemy, GetCourse)
годное объяснение. Закрепил знания. Посмотрим, что тут еще на канале есть )
Есть еще отличный материал на канале для настоящих джавистов)
Четко! Спасибо
Всегда пожалуйста!
Огромное спасибо за видео! Всё понятно и доходчиво.
Рад, что вам понравилось!
Можете все видео посмотреть моих плейлистов. Уверен, что многое для себя найдете. Главное, последовательно от курса к курсу)
Здорово! Становится понятно, спасибо!)
Круто, очень рад!!!
спасибо за лучшее разъяснение хэшмэпы в рунете)
Всегда пожалуйста
Очень хорошо объяснили. Спасибо.
Всегда пожалуйста
Лучшее объяснение.Спасибо большое.
Рад, что вам понравилось!
У меня все темы такие, смотрите с удовольствием!
Большое спасибо! Шикарное объяснение!
Всегда пожалуйста!
Дякую! Дуже зручне пояснення, як працює хешмапа під капотом
Мені здається найкраще з усіх, що я передивився
Всегда пожалуйста
Красавчик, спасибо большое за понятрое объяснение
👍
Да, реально четко объясняет
Отличное объяснение. Спасибо
Всегда пожалуйста
Супер! Огромное спасибо.
Хорошее видео, прочитала 3 статьи до, было очень сложно въехать, посмотрела это видео стало все понятно, хотя в видео не сказаны моменты с побитовыми сдвигами и прочее, но это не суть, суть как раз таки стала ясна. Ещё бы по КЧД когда, понять как оно там работает... А ещё говорят что математика не нужна программистам :)))) Спасибо вам большое за ваш труд.
И вам спасибо за столько развернутый ответ!
PS. Про КЧД чуть дальше по курсу я рассказываю
Спасибо. Хорошее объяснение.
Привет, всегда пожалуйста!
Чтобы понимать Java Core на высоком уровне и закрыть пробелы в уже имеющихся знаниях, можешь просто по порядку смотреть мои видео по плейлистам, начиная с самого первого. Уверен, не пожалеешь!
Java Level 1:
czcams.com/play/PLnh8EajVFTl6KGYdCWTlHdYPvpuqaBCTf.html
Спасибо!
👍
а я правильно понимаю, чтобы избежать коллизий ключа, лучше для ключа брать String? По нему хэш-код лучше отработает
String - да, один из лучших типов данных, использующихся в качестве ключей ассоциативных массивов.
Но если хорошо написать хэш функцию, то можно любой тип данных использовать в качестве ключа.
оч классно все объяснил, спасибо), и появился вопросик про 1.hashcode() - это же unboxing ?
у целочисленных литералов нет методов, поэтому ты не можешь вызвать 1.hashcode()
Хочу такого наставника :)
Можешь начинать сам по моим видео, только по порядку с первого плейлиста "Java Level 1 czcams.com/play/PLnh8EajVFTl6KGYdCWTlHdYPvpuqaBCTf.html"
Со Светой конечно смешно было)
Ахаха, это да. Чистая случайность)
интересно, но спорно что при get сравниваются ноды по equals, т.к. этом нет смысла. Скорее всего сравниваются хэши, и, если они не равны (см. контракт equals и hashcode) идет к след ноде, а если равны, только тогда сравниваются по equals
Отличное объяснение. Я правильно понял, что формула, по которой Java считает Hash Code от ID не так важна? Или это было в предыдущем видео про Hash Code?
Не совсем понял вопроса. Но суть в том, что ты сам решаешь, по каким полям считать hashCode. Если захотел делать только по полю id - значит будет только по id. Если захотел по всем полям во объекте - будет по всем полям считать. Все зависит от того, как ты сам переопределишь метод hashCode
@@dmdev обязательно переопределять метод hashCode или он будет дефолтным если я не переопределю?
@@user-tt3vu5ob7g Он же есть в класса Object, поэтому всегда есть доступ к методу hashCode у любого класса и, следовательно, объекта. Переопределять нужно тогда. когда ты планируешь его использовать. Обычно это использование таких объектов в коллекциях, которые в свою очередь используют hashCode (ассотиативные массивы например)
@@dmdev да, он native, я посмотрел его в Object как Вы учили. Хочешь прокачиваться изучай исходники.
Но если он реализован, зачем его переопределять? Если стандартное поведение не устраивает?
@@user-tt3vu5ob7g я говорил в своих видео, что по умолчанию equals and hashCode сравнивают объекты по ссылке. Но чаще всего ты заинтересован в сравнении по значению, т.е. поля объектов сравнивать, а не то, что ссылка указывает на ту же область памяти. Поэтому и приходится переопределять equals and hashCode
Я немного запутался, количество buckets моет быть больше 16? Если да, то как мы тогда будем получать значение если сначала количество корзин было 16, а потом увеличилось, в таком случае по формуле мы будем получать не тот индекс, так как будем искать остаток не от 16, а от другого числа.
Перебалансировка идет, т.е. создается новый массив, только уже большего размера, и заново по одному добавляются элементы из предыдущего массива (как в видео, только для нового массива еще раз с самого начала для всех элементов)
@@dmdev То что он расширяется это понятно, я вот понять не могу что происходить с числом 16, ведь если он увеличится в 2 раза то уже будет 32, и тогда если взять число из видео 35 индекс был 3, но теперь когда количество бакетов 32, индекс будет уже не 3. Или в Java балансируется таким образом, что индекс не зависит от колличетва бакетов, хотя я не понимаю как такое возможно если в методе hash написан следующий код (return key == null ? 0 : (h = key.hashCode()) ^ h >>> 16;)
так разницы нет, какой размер массива, просто берешь остаток от деления на размер массива и получишь нужный бакет (ведь все элементы будут заново добавлены со старого массива в новый, поэтому они будут ассоциированы заново с бакетами)
@@Roman-ej3xg конечно не лезем, потому что мы не используем эти клапаны для создания собственной машины. А это именно то, что ты делаешь с помощью Map - создаешь свое приложение. И если не знать, как оно устроено, то как можно создать хороший автомобиль? Более того, принципы hash таблиц используются в сотнях различных инструментов, баз данных и распределенных хранилищ. И опять же, чтобы правильно использовать это все - нужно знать устройство hash таблиц.
Не понял, когда преобразуется в (красно-черное) дерево? Когда сколько элементов в корзине с одинаковым хэшкодом?
Лучше всего заходить внутрь исходного кода и смотреть там, ибо может измениться от одной версии к другой. Пока это число равно 8 элементам:
java.util.HashMap#TREEIFY_THRESHOLD
13:36 не уверен, но вроде бы не просто создаётся новая нода в ячейке, где уже что-то есть (после того, как определили номер ячейки), а сначала проверяется - нет ли уже ноды с помещяемым объектом в этой ячейке (чтобы случайно второй раз одно и то же не поместить). И если вдруг такая нода (с помещяемым объектом) уже есть, то ничего не создаётся.
На 13:36 я уже рассказываю про коллизии, которые возникают, когда хэш совпадает у разных ключей. Само собой происходит проверка на равенство ключей, ибо невозможно поместить 2 одинаковых ключа в map - в этом и есть их суть и для этого и вызывается метод equals, что я и рассказываю в видео
Как называется тема в Intellij Idea ?
Обычная Darcula. Просто еще пару плагинов доставил. В этом видео я рассказывал про них:
czcams.com/video/mqjUSCHLo4s/video.html
Спасибо)
Всем доброго дня! Так, что в итоге? HashMap это способ поиска элементов и их добавления в коллекцию?
Спасибо!
HashMap - это еще одна структура данных, наряду с List, Set, Queue, просто механизм работы другой, поэтому подходит для других случаев. Все коллекции имеют функционал по поиску/добавлению/удалению элементов из них
Внимательно вроде все посмотрел, но никак не пойму, что такое число 35. Вы сказали, что это как пример, но если это hash, то ведь он определяется по заданному Id, который у нас имеет значение 1 (заданное нами). И должен быть равен 1, так как так вычисляется. Вот у Светы вроде так и есть. Этот вопрос побудил проследить всю цепочку)
Я проследил следующую цепочку через дебаг. -> .put() вызывает .putVal(), который принимает 1 (Id оно же key) и применяет к нему .hash(). Он в свою очередь применяет hashCode(), который применяет Integer.hashCode() (уже из класса Integer) к переданному значению и возвращает 1, так как у Integer, как я понял, такой способ образования hashcode, то есть он просто такой же, как и переданное в качестве аргумента значение.
Попробовал, ради интереса, еще задать в качестве ключа имя Ivan и там уже с типом String более интересная история поиска hashcode через класc String и другие (StringLatin1). Как я понял, там он привязывает поиск hashcode (наше поле hash) к символам в слове Ivan.
Подскажите, пожалуйста,
1. Правильно ли я понимаю путь нахождения hashcode (поле hash) для типов Integer и String ?
3. Операция с делением hash на остаток от деления и последующим определением ячейки в таблице для хранения значения реализуется в putVal()? Я так понял из дебага.
2. Откуда это число 35 ?
Просто хочется детально понимать цепочку происходящего и откуда что появляется. Может я что-то проглядел или не так понял.
Число 35 - это я просто наугад взял, чтобы показать, что не надо завязываться на значение hashCode. Просто пример не такой хороший взял, ибо для класса Integer - hashCode равен самому значению Integer. Для остальных классов он рассчитывается динамически в зависимости от состояния объекта класса.
Более того, нет никакого пути нахождения hashCode - ибо просто вызывается этот метод у объекта, который ты помещаешь в Map в виде ключа. Ты в своих классах сам можешь его переопределить как хочешь. Для Java классов (как Integer, String и т.д.) он уже переопределен просто и мы используем готовый
@@dmdev спасибо за пояснение! Вроде понял. Да, нужно попробовать поработать с ним и его переопределением для своих классов, чтобы лучше это понять. Ты имеешь в виду, что переопределить могу именно встроенным способом Intelij (где вызывается через Objects, а потом через Arrays и там уже логика вычисления), как ты показывал в предыдущем видео или что я могу буквально сам определить логику его вычисления? Тут еще интересно как это реализуется в реальных проектах.
Да, ты можешь сам переопределить метод hashCode как захочешь (я показывал в видео по hashCode). Но то, как это генерирует тебе IntelliJ - это хорошее переопределение и в реальных приложениях его и используют (либо дальше на http servlets курсе я буду рассказывать про Lombok библиотечку, она будет генерировать hashCode).
@@dmdev понял, спасибо, буду дальше смотреть!)
@@alexcodeplace
Когда вы создавали такую строку
for (Map.Entry entry: personMap.entrySet())
то как написав только имя коллекции быстро создали то что до : ?
Подскажите, как называется или что происходит когда пишем
Map.Entry entry
Тут два интерфейса и создали объект интерфейсов?
1. Intellij сама тебе вставить то, что до : - ты главное напиши iter и введи коллекцию, по которой будешь итерироваться.
2. Map.Entry entry - это просто ссылка на объект типа Entry, который является вложенным классом в классе Map. И более того, он параметризован Integer (ключ) и Person (значение).
Просто заходи внутрь классов и смотри как/что реализовано. Поначалу сложно будет, зато потом не остановишь тебя!
@@dmdev спасибо за ответы, иногда сажусь за занятия и думаю, что есть такая вот дистанционная поддержка и легче становится, а то часто кажется что все хочется бросить и пользы никакой)
@@user-xh8gn4lh2k всегда обучение идет циклами - от "круто у меня получилось" и до "у меня ничего не получится, все слишком сложно и не понятно".
Добавляйся в телеграм чат dmdev - там всегда помогут.
@@dmdev спасибо )) номально ли бросить на месяц где то занятия? иногда кажется что все безпросветно) А я хочу включить андроид и сделать приложение, а пока только джава кор, страшно очень что вдруг ничего не получится)
@@user-xh8gn4lh2k В любом деле - главное постоянство. Бросаешь на месяц - значит придется потом наверстывать, ибо навыки улетучиваются без использования. Это как спортивная форма - нужно постоянно ее поддерживать)
Я думаю, что при возникновении коллизии, Света устанавливается перед Ваней. У Светы в поле next записывается ссылка на Ваню. Возможно я ошибаюсь.
Зачем сомневаться в чем-то, если можно просто зайти внутрь класса HashMap и посмотреть код?
java.util.HashMap#put - смотришь этот метод и видишь строку:
p.next = newNode(hash, key, value, null);
И понимаешь, что устанавливается следующий элемент (поле next) в уже существующем при коллизии, а не наоборот
@@dmdev четко аргументированно, молодец
@@user-tt3vu5ob7g спасибо
Вопросик:
Изначально размер мапы равен 16.
Есть ключ равный 3 и значение "hello"
хеш = 35
индекс = 35 % 16 = 3
по индексу 3 у нас будет hello
предположим что размер увеличился и теперь он равен 64
Теперь при получении нашей строки hello по ключу 3 у нас будет
35 % 64 = 35.
получается индекс равен 35.
Как так?))
Или я что-то не понял?)
а, все теперь понял. там в следующем видео говорится
@@progprog3690 рад, что разобрался
Почему у id=1 хэш=35?
Я просто в уме вызвал функцию хешкод и получил 35. Скорее всего цифра будет другая, если сделать это на самом деле. Для объяснения алгоритма это не играет роли
@@dmdev может кого-то запутать. У интеджера хэш по умолчанию равен его значению ведь
Я хотел показать, что хешкод - это совсем рандомное число и зависит от состояния объекта. Более того, нельзя заострять внимание на том, что хешкод равен значению объекта (в случае Integer - это просто совпадение, которое может в любой новой версии Java поменяться)
У вас звук плохое, плохо слышно
Спасибо. Буду стараться сделать погромче
Ждем студийный микрофон
А то, что звук и видео не синхронны никому не интересно?)
Наверное, я что-то не знаю про значение слова синхронизация, но сейчас проверил звук и видео еще раз - все четко.
P.S. устройство ассоциативного массива гораздо интереснее)
@@dmdev а, сорян. У меня походу браузер залагал, сейчас все нормально.
Отлично! Теперь можно пожелать приятного просмотра!
А то действительно неудобно смотреть, когда видео и звук не синхронизированы