Mis on võtme järgi elemendi otsimise keerukus HashMap-is?

Average complexity is O(1), in the worst case — O(n).

• Average case (O(1)): With a good hash function and uniform distribution of elements across buckets, search reduces to computing the hash of the key and directly accessing the corresponding bucket in the array. Inside the bucket, if there are no collisions, the element is found in constant time.
• Worst case (O(n)): Occurs when all elements hash to the same bucket. In this case, search becomes a linear search in a linked list (or in a balanced tree in Java 8+ for buckets with many elements, but even traversing the tree can take O(log n), which in case of many collisions in one bucket still approaches O(n)).

Since Java 8, for buckets containing more than a certain threshold (TREEIFY_THRESHOLD, default 8) elements, the linked list is transformed into a balanced tree (Red-Black Tree). This improves the worst-case search within a single bucket to O(log n), but if all keys have the same hash, the overall search can still be close to O(n).