How is the search time for an element by key in a HashMap data structure determined?

In the HashMap data structure, the average time to search for an element by key is O(1) — constant time. This is achieved through the use of a hash function, which converts the key into an array index (bucket).

However, in the worst case, if many keys fall into the same bucket (collisions), the search can degrade to O(n), where n is the number of elements in that bucket. In modern Java implementations (starting from Java 8), when there are many collisions within a bucket, a balanced tree (e.g., red-black tree) is used, which reduces the search time in the bucket to O(log n).

Thus, the search time depends on the quality of the hash function and the distribution of keys, but it is generally considered to be close to constant.