Путаница с «итерацией является линейной в сумме количества записей и количества сегментов»

Question

Java Tutorials (Set реализаций) :

Одна вещь, о которой стоит помнить о HashSet, это то, что итерация является линейной по сумме количества записей и количестваведра (вместимость).

Я нахожу это утверждение запутанным и спрашиваю себя, может ли кто-нибудь прояснить смысл этого утверждения.Из того, что я понимаю, лучшая производительность итерации достигается, если у нас есть x блоков и ровно 1 элемент в каждом сегменте.

Давайте подпишем x = 200k.Это дает нам 200 000 записей и 200 000 корзин.

И наоборот, если все элементы находятся в 1 корзине (что, как я прочитал, действительно ужасно), у нас будет 200 000записей и 1 сегмент.

Поскольку 200k + 200k> 200k + 1, не означает ли это, что если мы применим вышеупомянутое утверждение, производительность 1 сегмента больше, чем производительность 200k сегментов?

Answer 1

Поскольку 200k + 200k > 200k + 1, не означает ли это, что если мы применим вышеупомянутое утверждение, производительность 1 сегмента больше, чем производительность 200k сегментов?

Да , при итерации по всем элементам в HashSet тот факт, что они распределены по нескольким сегментам, плох.

Когда говорят, что итерация линейна в сумме количества записей иколичество сегментов, они означают, что итерация находится в O (n + m) , где n - это количество сегментов, а m - количество записей.Константы не раскрываются.Это может быть, например, случай, когда это занимает 0,0001 * n + m , т. Е. Что влияние количества ведер действительно очень мало по сравнению с воздействиемколичество элементов.

(Кстати, существует другая структура данных, называемая LinkedHashSet, с характеристиками, аналогичными HashSet, но с временем итерации, пропорциональным только количеству элементов.)