I recently had a phone interview with Google, and I wrote out a solution for a problem that uses dictionaries in Python. Something Like:

#disregard whatever the forloop does
for x in range(N):
	for y in range(N):
		dic[key] = 0

He asked me what the time complexity of this piece of code is, I told him it was O(N^2) since hashing is on average O(1), he corrected me saying making the hash for the key also takes time, which at worst if the key length == N, the runtime would be O(N); hence, the runtime is actually O(N^3).

I've been told hashing is generally a constant time operation, except during hash collisions where it could take up to O(N). But I've never heard about this runtime explanation, Can someone elaborate or confirm this analysis?