I have a question about time complexity for hash maps. What is considered the complexity of inserting an initially unknown number n of items into the map?

My longstanding belief was that this complexity should be O(n log n) because a particular hash size will be chosen and then have to be repeatedly grown as the density of the map's population overwhelms the current size of the structure. An exponentially increasing size gives growth steps every log n items, and the growth step will require O(n) time.

Now everyone seems to believe that hash maps insertion is O(1) time with the only exception being degenerate coincidence between hash function and hashed data that puts large number of items into the same bucket.

Do current hash maps avoid O(n) complexity when growth is required? How?