Menu
I need to know: What is the time complexity of HashMap.containsKey() in java?
904
From the API doc of HashMap: This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.
The Java HashMap containsKey() method checks if the mapping for the specified key is present in the hashmap. The syntax of the containsKey() method is: hashmap.containsKey(Object key) Here, hashmap is an object of the HashMap class.
It takes approximately the same amount of time to call get and containsKey, and it's virtually guaranteed that after you call containsKey, you're going to call get anyways, so you may as well cut out the middle man.
With HashMap, we can achieve an average time complexity of O(1) for the put and get operations and space complexity of O(n).
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).
157
Generally O(1), but if we're using a bad hashCode function, we need to add multiple elements to one bucket so it can be O(n) in worst case.
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
