HashSet look-up complexity?

java time-complexity
phoenix picture phoenix · Jul 4, 2011 · Viewed 35.3k times · Source

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

JB Nizet picture JB Nizet · Jul 4, 2011

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

Related questions

Is a Java hashmap search really O(1)?

I've seen some interesting claims on SO re Java hashmaps and their O(1) lookup time. Can someone explain why this is so? Unless these hashmaps are vastly different from any of the hashing algorithms I was bought up on, there …

Read More
What are the time complexities of various data structures?

I am trying to list time complexities of operations of common data structures like Arrays, Binary Search Tree, Heap, Linked List, etc. and especially I am referring to Java. They are very common, but I guess some of us are …

Read More
Time complexity for java ArrayList

Is ArrayList an array or a list in java? what is the time complexity for the get operation, is it O(n) or O(1)?

Read More