What is the time complexity of HashMap.containsKey() in java?

java performance hashmap time-complexity
Hossein picture Hossein · Jan 19, 2012 · Viewed 62.1k times · Source

I need to know: What is the time complexity of HashMap.containsKey() in java?

Answer

Michael Borgwardt picture Michael Borgwardt · Jan 19, 2012

From the API doc ofHashMap:

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

Since containsKey() is just a get() that throws away the retrieved value, it's O(1) (assuming the hash function works properly, again).

Related questions

Java HashMap performance optimization / alternative

I want to create a large HashMap but the put() performance is not good enough. Any ideas? Other data structure suggestions are welcome but I need the lookup feature of a Java Map: map.get(key) In my case I …

Read More
Java : Iteration through a HashMap, which is more efficient?

Given the following code, with two alternative ways to iterate through it, is there any performance difference between these two methods? Map<String, Integer> map = new HashMap<String, Integer>(); //populate map //alt. #1 for (String key : map.…

Read More
Why is HashMap faster than HashSet?

I have been reading/researching the reason why HashMapis faster than HashSet. I am not quite understanding the following statements: HashMap is faster than HashSet because the values are associated to a unique key. In HashSet, member object is used …

Read More