What is the worst-case scenario for HashMap in terms of computational complexity?

The worst-case scenario for HashMap in terms of computational complexity is when all keys hash to the same bucket, causing collisions for all elements. In this case, the data structure degrades from a hash table to a linked list or a tree (starting from Java 8), and search, insert, and delete operations become linear in the number of elements in the bucket.

Before Java 8, the worst case was O(n), as all elements in the bucket were stored in a linked list. Starting from Java 8, with a large number of collisions, the bucket is converted into a balanced tree (TreeMap), reducing the worst case to O(log n).

Example:

Map<Integer, String> map = new HashMap<>();
// If all keys have the same hashCode, for example, objects with overridden hashCode
class BadKey {
    int value;
    BadKey(int v) { value = v; }
    @Override
    public int hashCode() { return 1; } // all keys go into one bucket
    @Override
    public boolean equals(Object o) { return o instanceof BadKey && ((BadKey)o).value == this.value; }
}

for (int i = 0; i < 1000; i++) {
    map.put(new BadKey(i), "Value" + i);
}
// Search will be slow because all elements are in one bucket

Therefore, it is important to choose a good hash function and avoid collisions.