HashSet look-up complexity?

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *