Data Structures Complexities

Question 1

HashMap Search

hashmap.get(key);

Answer 1

O(1) - Lookup complexity is O(1) when there is a decent implementation of hashcode() function available. With decent implementation of hashcode(), we have only 1 value belonging to any bucket, and hence once the bucket is identified using hashcode(), the retrieval is a constant time operation.

Technically, the lookup complexity is O(1) + complexity of hashcode() method.

Worst Case - Up to Java 7
O(n) - This can happen when the hashcode() function returns a constant value for every key. This causes hashing-collision for every key, and hash collisions have disastrous impact on HashMap performance. In case of hash collision, many or all the keys are mapped to a single bucket. Until Java 7, this structure mapped with the bucked used to be a LinkedList, and hence, the retrieval runtime is nothing but the retrieval runtime of the LinkedList, which is O(n).

Worst Case - Java 8 Onwards
O(log n) Worst Case - In Java 8, when the bucket becomes too big in case of hash collisions (currently: TREEIFY_THRESHOLD = 8), HashMap dynamically replaces it with an ad-hoc implementation of tree map. This way rather than having pessimistic O(n) we get much better O(log n).