Изменение размера таблицы массивов в реализации HashMap
Это простой вопрос для тех, кто знает внутреннюю реализацию HashMap :)
Исходный объем 16 ковшей, коэффициент загрузки 0,75. Это означает, что когда он получает (обратите внимание на это слово) 12, он изменяется до 32 ведер.
Мой вопрос: изменяется ли он с 16 до 32 сегментов, когда он получает 12 пар ключ-значение или когда он получает 12 «заполненных» сегментов? Я спрашиваю об этом, потому что может случиться так, что из этих 16 сегментов все 12 пар ключ-значение будут вставлены в один сегмент. В этом случае было бы странно изменять размер, поскольку остальные 15 полностью пусты.
Спасибо, любое мнение по этому поводу будет оценено :)
Ответы
Как упоминалось в этой ссылке .
Он представляет, что 12-я пара ключ-значение хэш-карты сохранит свой размер до 16. Как только 13-й элемент (пара ключ-значение) войдет в хэш-карту, он увеличит свой размер с 2 ^ 4 = 16 сегментов по умолчанию до 2 ^ 5 = 32 ведра.
Независимо от того, где был вставлен каждый ключ, при превышении произведения коэффициента нагрузки и текущей емкости размер таблицы будет изменен.
HashMap не заботится о том, сколько сегментов было использовано до достижения коэффициента загрузки, он знает, что вероятность возникновения коллизий становится слишком большой, и размер карты следует изменить. Хотя уже произошло много столкновений.
Из JavaDoc https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#put-K-V-
When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
Итак, HashMap изменяет размер, когда он имеет 12 пар ключ-значение. Это не странно, потому что после изменения размера записи изменят свое ведро.