How is access time to an element in a HashMap data structure determined?

Access time to an element in a HashMap data structure in Java is usually considered constant — O(1). This is achieved by using a hash function that converts the key into an index in the array where the value is stored.

However, in practice, access time can increase to O(n) in the worst case if many collisions occur (different keys with the same hash), and elements are stored in a linked list or tree within a single bucket.

Since Java 8, to reduce access time during collisions, a linked list is converted into a balanced tree (TreeMap), which reduces search time to O(log n) in such cases.

Thus, the average access time is close to O(1), but in worst cases, it can be O(log n) or O(n).