How does it affect the performance of HashMap if all keys receive the same hash code?

If all keys in a HashMap have the same hash code, the efficiency of the data structure sharply decreases. Instead of fast access in amortized O(1) time, it degrades to O(n) time, where n is the number of elements.

Why does this happen:

• HashMap uses the hash code to distribute keys across buckets.
• If all keys land in the same bucket due to the same hash code, then within this bucket, keys are stored in a linked list or a tree.
• When searching, inserting, or deleting, it is necessary to sequentially iterate over all elements in this bucket.

In Java 8 and above, if a bucket contains many elements, HashMap converts the linked list into a balanced tree (TreeNode), which improves search time to O(log n), but it is still worse than O(1) with a uniform distribution.

Example:

Map<Key, String> map = new HashMap<>() {
    @Override
    public int hashCode() {
        return 42; // All keys have the same hash code
    }
};

// When adding many such keys, performance drops

Conclusion: for good performance, it is important that the hash function distributes keys evenly across buckets.