, если Hashmap использует связанный список внутри, почему это необходимо для увеличения емкости. Также, если мы постоянно увеличиваем количество ведер, тогда многие ведра останутся пустыми с коэффициентом загрузки как 0,75?, если Hashmap использует связанный список внутри, почему необходимо увеличить емкость
HashMap не использует LinedList всегда, он использует массив. Напр. если создается новый объект hashmap, тогда создается массив размером 16. Каждый индекс содержит 4 части, содержащие ключ, значение, hashcode, next.
LinedList формируется в индексе, когда происходит столкновение (тот же хэш-код), и эта концепция называется отдельной цепью. . если вы поместите 2 объекта в объект карты с одним и тем же хэш-кодом, тогда будет происходить раздельная цепочка, иначе будут созданы 2 ведра.
Когда несколько объектов попадают в одно и то же ведро, время поиска увеличивается это худший сценарий O (n). –
Скажите, что у вас 10 ведер, 1_000_000 элементов и отличное распределение, сколько элементов будет содержать каждый ведро (связанный список)? Какую худшую производительность вы ожидаете от поиска? Что, если у вас было 100_000 ведер? –
linkedlists - один из способов борьбы с столкновениями. В связанном случае, когда у вас есть столкновение, вы просто храните оба объекта в одном месте, и при поиске вы должны проверить, какой из них нужно вернуть, в то время как открытая адресация, когда находит найденный слот, уже вычисляет другой хэш для одного и того же объекта чтобы найти пустой слот, это означает, что у вас больше полных слотов и поиск может потребовать вычисления различных хэшей. Если у вас 1 миллион столкновений, без изменения размера хэш-карты, вы получите 1 миллион связанных списков (открытая адресация просто завершится неудачно в определенный момент, когда таблица заполнена) – Bakuriu