HashMap Iterative Complexity

Question

From java doc, I know that:

Iterating over collection views takes time proportional to the "capacity" of the HashMap instance (number of buckets) plus its size (number of key value mappings). Thus, it is very important not to set the initial power too high (or the load factor too low) if iterative performance is important.

Does this mean that the time complexity for iterating over a HashMap is O (n²)? This question may seem silly, but I'm actually a bit confused.

Answer 1

, , O (n ²).

c , O (n) , O (n ²) . , :

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

loadFactor - float, 0.75f.

, , . , - O (c), O (n), c - .

Answer 2

, , HashMap O (n + s), n - , s - . s n .

Answer 3

To search in a HashMap (or Hash function in general), you expect O (1) runtime and O (n) worst-case time (n is the size of the Hashmap) plus the linear coefficient that the speaker talked about. For efficiency, you do not want to be huge in size to reduce the worst time complexity.