Почему увеличение load factor в хэш-таблице увеличивает время поиска элементов?

Вот цитата из описания HashMap с сайта оракла:

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).

Про уменьшение space overhead'а понимаю - если у нас, допустим, емкость таблицы 10 элементов, то при добавлении 8 элементов начнется рехэширование и размер станет, пусть, 20 элементов. Но если в итоге фактически у нас окажется только 9 элементов, то значит зря мы выделяли это дополнительное место. Оверхед в 11 элементов получится. Если же мы поставим load factor 1, то рехэширование и выделение дополнительного места начнется только когда таблица фактически забьется. Т.е. 0 оверхеда по памяти, но зато операция добавления может подвиснуть, т.к. по сути ей придется ждать, пока там все реорганизуется и появятся слоты.

А про увеличение времени добавления\поиска при увеличении фактора загрузки не понимаю вообще. Единственное предположение - это если load factor высокий, то это как-то увеличивает вероятность коллизий. Ну вроде того что мы до последнего не разрешаем расширяться, от этого слотов под новые элементы все меньше и меньше и как следствие увеличиваются коллизии, а значит в каждом слоте больше элементов и значит при поиске, грубо говоря, придется не сразу брать значение из слота, а сперва пройтись по "цепочке" в этом слоте.

С другой стороны, пока писал, подумал - а что если получится так, что рехэширование вообще не произойдет? Ну то есть из-за коллизий элементы будут распределяться по слотам так, что из наших условных 10 слотов всегда будут заполнены только 7, но фактически будет, пусть, 28 элементов? По 4 в каждом слоте. Или размер (capacity) таблицы это как раз количество фактических элементов, а не слотов?


Ответы (0 шт):