HashMap Java собеседование
Вставка
- Опубліковано 6 жов 2024
- Текст сюжета тут - it-channel.ru/2...
HashMap Java собеседование
00:42 Устройство HashMap
02:10 Начальное количество корзин в HashMap
02:25 Коллизии в HashMap
04:01 Как происходит увеличение корзин в HashMap.loadFactor
04:50 Временная оценка операций HashMap.
06:40 ВРеменная оценка сложности алгоритмов
07:09 Ответ за задание из прошлого выпуска
07:44 Задание. Разминка для ума
Хотите повлиять на темы сюжетов? Вам сюда
itspher...
Я в ВК id26420520
Группа в ВК itspher...
Опрос в группе itspher...
Всем привет. Меня зовут Александр. Я по прежнему снимаю видео ролики посвященные прохождению собеседования на позицию java developera. Если хотите посмотреть первый ролик посвященный ArrayList-ам и LinkedList-ам, то вам сюда. Напомню что сейчас я разбираю коллекции в java. Сегодняшняя тема будет HashMap. Почему я выбрал эту тему? Да все по той же причине. Ее нужно знать обязательно если вы пришли на собеседование. Не знаете = не готовы!
Также если помните в прошлом видео ролике я задал вопрос для того чтобы вы дома размяли мозг. Ответ на него ищите в конце этого ролика.
Пожалуй начнем.
Расскажите про устройство HashMap?
Во-первых что такое HashMap?
HashMap - это ассоциативный массив. Если вкратце, то ассоциативный массив это структура данных которая хранит пары ключ-значения.
Чтобы было проще понять что это такое можно представлять HashMap как пронумерованные корзинки в которых хранятся какие-то данные. При добавлении нового объекта в HashMap мы также передаем помимо самого объекта еще и ключ по которому в дальнейшем его можно будет отыскать. Как по ключу можно определить положение искомого объекта? Для этого нам нужно знать hashCode ключа. Где же его взять? Да это очень просто если понимать что в качестве ключа может выступать любой объект в java. Все знают что класс Object реализует метод hashCode() это означает что он будет унаследован или переопределен самим “ключом”. Т.к. все в java наследуются от класса Object. Теперь понятно откуда у ключа берется hashCode!
После того как в hashMap, был передан ключ + сохраняемый объект специальная hash функция вычисляет то в какую корзину отнести наши данные.
Как вы понимаете никаких корзинок в HashMap-е нет. Вместо их есть массив. который хранит ссылки на связанные списки в которыхэ хранятся наши данные. Каждому элементу массива соответствует один список.
Какое начальное количество корзин в HashMap?
Данный вопрос мне ни разу не задавали я его нашел на хабре. Ответ 16. Но как и с ArrayList-ом в конструкторе можно задать другое количество.
Что такое коллизия? Способ решения коллизий.
Этот вопрос так же часто встречается
2:40
Коллизии возможны не только когда хэшкоды одинаковы, но и когда алгоритм расчёта индекса в массиве (&) даст одинаковые результаты.
5:17
Задать количество bucket'ов равное количеству объектов с которыми будем работать не всегда удастся, т.к. количество bucket'ов должно быть степенью двойки (заданный руками initialCapacity округляется до ближайшей степени двойки).
Если хотим затюнить время (снизить количество возможных коллизий) лучше подсчитать initialCapacity, если память то да, можно поставить loadFactor = 1.
6:28
Односвязанный список =)
Andrei Petrov Спасибо огромное я если не забуду добавлю правки в виде аннотаций.
в Джава 8 когда в LinkedList-е к-во элементов превышает определенный порог, объекты переносятся в balance trees что сменит скорость с O(n) до O(log(n))
линкедлист - двусвязный список. В хешмапе односвязный список, тк не имеет смысла хранить ссылку на предыдущий узел.
Что такое О() ?
@@Judosaper с помощью О большое описывают сложность алгоритма, big O - поищи
В примере на первой минуте, где корзинки, ошибка. Последующие элементы вставляются не в конец корзинки, а в начало и указывают на элемент, который до этого был первым. Элементы 1 и 5 должны поменяться местами.
в Java 8, если класс ключа реализует Comparable, для бакетов с большим числом коллизий, внутри будут не связные списки, а сбалансированные деревья
Вообще-то не так. Связанные списки в HashMap разворачиваются в деревья независимо от того, какие интерфейсы реализует класс ключа. По умолчанию в таком дереве элементы сортируются на основе хэшкода, но если класс ключа реализует Comparable, то сортировка выполняется на основе метода compareTo
@@aljesco8338 и это тоже не так. Там сначала добавляется в список, а если элементов в бакете больше 8, они образуют дерево. в джава 8+
@@ВиталийСергеев-б2м и это тоже не совсем верно. Преобразование в дерево произойдёт только если capacity >= 64! :)
@@MrSBFI и это тоже еще не все. Если количество элементов в одном бакете уменьшится до 6, то произойдет обратный переход от дерева к односвязному списку. Кто следующий? =D
@@МистерВиктор-х9р ребята, мне кажется это наконец-то все
6:27 там список, кажется, не двусвязный, а односвязный. Оно и логично - проход осуществляется в одну же сторону.
весьма популярный вопрос на собеседовании в довольно крупные компании, недавно ходил по разным и сталкивался. Спрашивают, как реализован dict в python, hashmap в Java, Map в C++, временную сложность и про разрешение коллизий. Спасибо автору ролика, для закрепления самое то. Лучше все-таки дополнительно поштудировать книги по алгоритмам.
Спасибо, отличное видео, за 5 минут все понял.
Основные условия, при которых могут возникать коллизии в HashMap:
Разные ключи, но одинаковые хеш-коды: Если два различных ключа возвращают одно и то же значение хеша, они будут храниться в одной и той же ячейке (bucket).
Ограниченное количество возможных хеш-кодов: Поскольку хеш-коды представлены 32-битными числами, пространство хеш-кодов ограничено. Это значит, что различные ключи могут иметь одинаковые хеш-коды.
Недостаточный размер хэш-таблицы: Если размер хэш-таблицы недостаточно велик, чтобы вместить все ключи, возрастает вероятность коллизий.
4:30 ошибочка.условие роста внутреннего массива - заполненность "корзин", т.е. если добавить 12 элементов не обязательно будут заполнены 12 "корзин"
threshold - Предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
Хорошие уроки! Стоило добавить как hash функция определяет индекс корзинки - hashcode % текущее n корзинок
Это видео поставлено намного, намного приятнее, чем про ArrayList. сначала негативно подумал об авторе, но вижу, что он молодцом)))))
звук конечно ужасный
Новый объект добавляется в начало списка а не в конец
Если посмотреть исходники метода putVal в java 8, то видно - вставка идёт в конец, а не в начало списка
Сам научись, потом других учи
круто, узнал много нового
Такое ощущение что ты не научил, а ещё больше запутал своим видео
Интиресненько!
спасибо за труд и за желание поделиться опытом.!
И количество корзинок не увеличивается вдвое, а увеличивается по правилу (currentCount*3)/2 + 1
спасибо!
Спасибо за видео! Вопрос про добавление. В некоторых источниках я видел добавление в начало?( у тебя в конец добавление) Внесёшь ясность?
что-то не понял, если есть уже под таким хешключем обьект который equals с добавляемым - то зачем производить замену ?
видимо по принципу - обновления данных? типа если объект имеет тот же хэшкод, но однако он появился на входе, вероятно это его update. а иначе, программист не следит за правильным расчётом HashCode, которые у него пересекаются постоянно между объектами...а это не правильно.
PS
я не претендую на правильность ответа, учусь только. поправьте меня, если что )))
loadFactor
звук плохой
ты что лук режешь перед каждой трансляцией?
он долго смотрел в монитор, вот глаза и покраснели.
Load Factory... )))
Don't teach when you're not skilled at all...
Andrii Andriichuk правильно просто Factory?
@@СашаНемо-з2ы правильно load factor, фактор а не фабрика))
docs.oracle.com/javase/8/docs/api/java/util/HashMap.html
Don't speak if you cant properly
Дольф Лундгрен. Начало.
на счет решения n + m - смещать влево точно на *n* или все же на *m*?
Много ошибок.
7:09 о чем это он говорить вообще не понял (
Примеров не хватает.
у вас уроки про JAVA только core?
А про Сет и очереди будет?
Херово он рассказывает, честно говоря. Прекрасно зная как работает хешмап, его инфу я вообще не понял
Yevhen Rudenko такая же проблема))
смешной комментарий, конечно +. Но поему все он понятно объясняет!
Так заходите ко мне на канал)
да по моему норм рассказывает
с каких пор начальная емкость ArrayList == 16?
Vlad вроде как 10. А потом идут расширения до 15, 22, 33, ... элементов
Спасибо, я уже посмотрел и проверил. В начале 0, когда добавляем хоть один элемент, то 10, а потом на 50% увеличивается.
@@spoker3L В начале 0, когда добавляем хоть один элемент, новая ёмкость:
newCap = DEFAULT_INITIAL_CAPACITY;
Которая равна:
static final int DEFAULT_INITIAL_CAPACITY = 1
Увеличивается х1.5 + 1
Поначалу хорошо, а потом как-то еще больше путать начало. Вот тут доступнее ua-cam.com/video/xXaqBe78AfI/v-deo.html
ммда парниша ты ппц по по листку рассказываешь )) ещё и запутать пытаешься вот прям видно что ты сам не понимаешь о чём рассказываешь))
Посмотрите лучше Заура Трегулова или Алишева, чем этого самоучку, который толком в теме не разобрался даже.
Рипни плиз канал и не вводи людей в заблуждение
Ппц, очередное видео с грубыми ошибками.
Как можно рассказывать устройство HashMap без единой схемы? от меня -