java - HashSet look-up complexity?

Question

A look-up operation OR contains for single can be O(n) in worst-case right ? So, for n elements look up in hashSet will be O(n^2)?

Answer 1

Yes, but it's really the worst case: if all the elements in the HashSet have the same hash code (or a hash code leading to the same bucket). With a correctly written hashCode and a normally distributed key sample, a lookup is O(1).