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).

Answer 2

lookp takes O(c)

c = constant value

Answer 3

Yes, but the whole reason we have HashSets is that we encounter this worst case with very, very low probability, and it's usually much faster than the guaranteed nlogn for a heap or a (self-balancing) TreeSet, or the guaranteed n^2 for an unsorted list.