HashMap итерация сложность

Question

С JAVA документа Я знаю, что:

Итерация над видом сбора требует времени, пропорционального «мощности» экземпляр HashMap (число ковшей) плюс его размера (количество сопоставления ключевых значений). Таким образом, очень важно не устанавливать слишком высокую начальную мощность (или слишком низкий коэффициент нагрузки), если значение производительности итерации очень важно.

Означает ли сложность времени для итерации над HashMap является O (n²)? Этот вопрос может показаться глупым, но на самом деле я немного смущен.

Answer 1

Нет, это значит, что сложность для итерации над HashMap представляет собой О (N + S), где п это число отображений и с является размер. Он должен итерировать линейно по всем s ковши и линейно по всем n записей.

Answer 2

Нет, это не означает, что сложность итерации равна O (n).

Когда емкость c установлена ​​автоматически, она растет как O (n) с количеством элементов, а не как O (n). В соответствии с исходным кодом, выходная мощность вычисляется следующим образом:

int targetCapacity = (int)(numKeysToBeAdded/loadFactor + 1); 

где loadFactor является float значение, установленное в 0.75f по умолчанию.

Этот пункт, который вы указываете, становится актуальным только при установке емкости вручную. Он говорит вам, что производительность - это O (c), а не O (n), где c - это емкость, которую вы установили, или мощность, вычисленная автоматически.

Answer 3

Для поиска в HashMap (или Hash-функции вообще) вы ожидаете время выполнения O (1) и наихудшего времени O (n) (n - размер Hashmap) плюс линейный фактор, о котором говорил яросик. Для эффективности вы не хотите иметь огромный размер, чтобы снизить худшую временную сложность.