What is the time complexity of obtaining a value by key in a HashMap?

In a HashMap data structure, retrieving a value by key on average has a time complexity of O(1). This is achieved through the use of a hash function that directly computes the index for storing the value.

However, in the worst case, when collisions occur (when multiple keys have the same hash), the complexity can degrade to O(n), where n is the number of elements in the bucket. Modern implementations of HashMap use balanced trees to store collisions, which reduces the worst case to O(log n).