What is the time complexity of HashMap.containsKey() in java?
Solution 1:
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).
Solution 2:
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.