Я так понимаю, что если вдруг есть поля, которые по ходу "жизни" объекта нужно изменять(тот же курс, на котором студент учится), можно просто написать реализацию хешкода, которая от этого динамически изменяемого(не final) поля не будет зависеть? тем самым, с изменением данного поля, объект для хешмапы будет оставаться immutable т.к. хэшкод не изменился? это нормальная практика же?
Здравствуйте, спасибо за уроки, но хотелось бы уточнить: в массиве хранятся же не LinkedList, а ноды в виде односвязного списка? Просто непонятно, ячейка массива - это экземпляр класса LinkedList или Node
Спасибо) Только вместо "несложного алгоритма" можно было просто уточнить, что хэш делится на кол-во бакетов :) Потому что это могут и спросить на интервью )
@@programaniya Я имел ввиду, что если у нас 100 бакетов а итоговый хэш объекта например 11005, то остаток от деления 11005/100 = 5 и будет номером бакета) Я уже не помню, говорили ли вы это или нет, я пожалуй не буду пересматривать )
In Java, hash tables are implemented as arrays of linked lists. Each list is called a bucket (see Figure 9.10). To find the place of an object in the table, compute its hash code and reduce it modulo the total number of buckets. The resulting number is the index of the bucket that holds the element. For example, if an object has hash code 76268 and there are 128 buckets, then the object is placed in bucket 108 (because the remainder 76268 % 128 is 108). Perhaps you are lucky and there is no other element in that bucket. Then, you simply insert the element into that bucket. Of course, sometimes you will hit a bucket that is already filled. This is called a hash collision. Then, compare the new object with all objects in that bucket to see if it is already present. If the hash codes are reasonably randomly distributed and the number of buckets is large enough, only a few comparisons should be necessary.@@programaniya
На самом деле там не "честная" сложность О(1), а "округленная" до константного значения. Это используется для упрощения. В HashMap по определению не может быть О(1) т.к. используется LinkedList доступ к элементам которого О(n). Среднее же время работы будет О(1 + α), где α - коэффициент загрузки LinkedList, т.е. чем больше элементов в конкретном LInkedList'е тем дольше будет происходить доступ к последнему элементу.
Зравствуйте! Отличное видео. Но у меня возник вопрос. В уроке про LinkedList Вы говорил что put() и remove() это быстрые операции т.к только переписываются ссылки на элементы. А здесь вы говорите что добавление и удаление в LinkedList это всегда O(n), а не константное...где ошибка?)
@@u_n_d_e_r_s_c_o_r_e_d Я правильно понимаю, что добавление и удаление в LinkedList это всегда O(1) т.к просто нужно перезаписать ссылки на элементы коллекции ?
Нигде ошибки нет. Всё зависит от того, куда вы вставляете элемент или откуда его удаляете. Если начало/конец списка, то это быстро. Если операция происходит ближе к середине листа, то это O(n). Учитывая, что всегда в расчёт берётся не частный, а общий случай, то добавление и удаление элемента в LinkedList происходит за O(n).
Здравствуйте. Вы показали для чего использовать final поля , но я не понял, что нам даст запрет наследования от класса Student? Каким образом он влияет на hashCode()?
Здравствуйте. Это делается для того, чтобы никто не смог наследовать ваш класс, используемый в качестве ключа и не "испортить" метод hashCode. Ведь классы наследники также смогут выступать в роли ключей, а плохо написанный hashCode обеспечит вам большое колличество коллизий.
Определение сбалансированного дерева строится на том, что высота любых двух поддеревьев от одного узла, отличается не более чем на 1. Из этого и следует, что поиск будет логарифмический. Ваше определение это определение это не определение сбалансированного дерева.
Так в уроке не было определения сбалансированного дерева. Я просто озвучил одну из характеристик такого дерева, которую посчитал необходимой для данного урока.
Есть мнение, что Заур красавчик. Очень хорошо объясняешь! 👍
Благодаря вашей подаче, темы которые кажутся на первый взгляд сложными, превращаются в простые
Просто лучший урок! Прекрасная работа, спасибо
очень хорошо объяснена тема, меня немного на ней потопили на собесе, но с помощью твоих видосов я преисполнился, спасибо, здоровья!
Очень хорошее объяснение про работу HashMap! Спасибо!
Заур, шикарно объясняешь, спасибо!
Спасибо, очень грамотное объяснение, приятно слушать
Спасибо большое! Все понятно!
while(true){
System.out.println("Заур спасибо!");
}
Очень полезное видео. Большое спасибо.
Спасибо тебе огромное. Очень помог разобратся с hashMap.
Спасибо !!!Круто объяснил)))
Лучшее объяснение!
Заур спасибо!
Курс купил ;)
Отличное видео
Благодарю!
спасибо за урок!
Ну это очень круто
Лучше было бы просто исключить курс из расчета equals и hashcode потому что люди могут менять курс, но при этом они остаются теми же людьми)
Отличный комментарий!
спасибо!
чему должно быть равно числ коллизий чтобы hashmap перестроился в красночерное дерево?
Попробуйте, пожалуйста, загуглить. Я не стремлюсь запоминать такого рода информацию, и вам не советую ))
Подскажите есль есть в Вашем уроке, то в каком, примеры с одинаковыми ключами в Map.
И спасибо за Ваши уроки!
Здравствуйте. Вы не нашли такого примера в этом уроке?
@@programaniya возможно есть. Я ещё в пути, на других видео. Если есть в этом, то под нужным видео оказался
Так и есть :)
Я так понимаю, что если вдруг есть поля, которые по ходу "жизни" объекта нужно изменять(тот же курс, на котором студент учится), можно просто написать реализацию хешкода, которая от этого динамически изменяемого(не final) поля не будет зависеть? тем самым, с изменением данного поля, объект для хешмапы будет оставаться immutable т.к. хэшкод не изменился? это нормальная практика же?
Да, всё верно. Хороший комментарий!
Здравствуйте, спасибо за уроки, но хотелось бы уточнить: в массиве хранятся же не LinkedList, а ноды в виде односвязного списка? Просто непонятно, ячейка массива - это экземпляр класса LinkedList или Node
Здравствуйте. Благодарю за вопрос. В данном контексте воспринимайте оба понятия, как взаимозаменяемые. Нода - это тоже список.
Спасибо) Только вместо "несложного алгоритма" можно было просто уточнить, что хэш делится на кол-во бакетов :) Потому что это могут и спросить на интервью )
Не очень понял, что значит "хэш делится на кол-во бакетов"? А так, про бакеты в уроке даётся полная информация ;)
@@programaniya Я имел ввиду, что если у нас 100 бакетов а итоговый хэш объекта например 11005, то остаток от деления 11005/100 = 5 и будет номером бакета) Я уже не помню, говорили ли вы это или нет, я пожалуй не буду пересматривать )
In Java, hash tables are implemented as arrays of linked lists. Each list is
called a bucket (see Figure 9.10). To find the place of an object in the table,
compute its hash code and reduce it modulo the total number of buckets. The
resulting number is the index of the bucket that holds the element. For
example, if an object has hash code 76268 and there are 128 buckets, then
the object is placed in bucket 108 (because the remainder 76268 % 128 is
108). Perhaps you are lucky and there is no other element in that bucket.
Then, you simply insert the element into that bucket. Of course, sometimes
you will hit a bucket that is already filled. This is called a hash collision.
Then, compare the new object with all objects in that bucket to see if it is
already present. If the hash codes are reasonably randomly distributed and
the number of buckets is large enough, only a few comparisons should be
necessary.@@programaniya
нет, для расчета индекса используются операции сдвига (>>>) и побитовые операции (^) обработки хэш-кода @@VoidObj
вваааууууу. Спасибо !
На самом деле там не "честная" сложность О(1), а "округленная" до константного значения. Это используется для упрощения. В HashMap по определению не может быть О(1) т.к. используется LinkedList доступ к элементам которого О(n). Среднее же время работы будет О(1 + α), где α - коэффициент загрузки LinkedList, т.е. чем больше элементов в конкретном LInkedList'е тем дольше будет происходить доступ к последнему элементу.
Совершенно верно. Рассматривается случай идеальной мапы, конда каждый LinkedList содержит лишь 1 элемент.
Ну это очевидно
А load factor разве может быть > 1?
Ваш вопрос легко проверить.
Почему тогда вместо LinkedList не юзать сбалансированные деревья с самого начала? Ведь же O(logN) быстрее O(n)
Вопрос скорее к разработчикам.
Разве изначально массив не заполнится null? Не понял почему при большом капасити, сразу будет много памяти занимать
Без разницы чем заполнен массив. Всё равно при его создании выделяется память, соответствующая его длине.
Это тоже самое что там long , неважно как-то там число хранится, он все равно занимает 8 байт
Зравствуйте! Отличное видео. Но у меня возник вопрос. В уроке про LinkedList Вы говорил что put() и remove() это быстрые операции т.к только переписываются ссылки на элементы. А здесь вы говорите что добавление и удаление в LinkedList это всегда O(n), а не константное...где ошибка?)
В этом видео ошибка
@@u_n_d_e_r_s_c_o_r_e_d Я правильно понимаю, что добавление и удаление в LinkedList это всегда O(1) т.к просто нужно перезаписать ссылки на элементы коллекции ?
@@artaqa да
Нигде ошибки нет. Всё зависит от того, куда вы вставляете элемент или откуда его удаляете. Если начало/конец списка, то это быстро. Если операция происходит ближе к середине листа, то это O(n). Учитывая, что всегда в расчёт берётся не частный, а общий случай, то добавление и удаление элемента в LinkedList происходит за O(n).
Здравствуйте. Вы показали для чего использовать final поля , но я не понял, что нам даст запрет наследования от класса Student? Каким образом он влияет на hashCode()?
Здравствуйте. Это делается для того, чтобы никто не смог наследовать ваш класс, используемый в качестве ключа и не "испортить" метод hashCode. Ведь классы наследники также смогут выступать в роли ключей, а плохо написанный hashCode обеспечит вам большое колличество коллизий.
А если не final делать поля свойств и класс, а для вычисления хэш кода использовать только значение ключа?
Можете привести пример?
🧠
Определение сбалансированного дерева строится на том, что высота любых двух поддеревьев от одного узла, отличается не более чем на 1. Из этого и следует, что поиск будет логарифмический. Ваше определение это определение это не определение сбалансированного дерева.
да, конечно, условие из видео также необходимо для доказательства асимптотики, но всё же это не определение сбалансированного дерева
Так в уроке не было определения сбалансированного дерева. Я просто озвучил одну из характеристик такого дерева, которую посчитал необходимой для данного урока.
в худшем случае с O(n) до O(log n)*