Why is the complexity of the hash function not considered in the complexity of HashMap's operations? [duplicate]

Question

For a HashMap<String, String> map each time a key-value pair is inserted into the map a hash is calculated -

java.lang.String#hashCode

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

As it's pretty self-explanatory, the complexity of put operation is basically the complexity of the hash calculation.

So what should be the appropriate way to define hashmap worst-case time complexity for put/get operation?

If you have the same question from hash collision perspective, here you can find the answer: Is a Java hashmap really O(1)?

Answer 1

When you calculate time complexity as a function of N, you must first decide what N represents. When we talk about the complexity of HashMap operations, N represents the size of the HashMap (i.e. the number of key-value pairs stored in the HashMap).

The time complexity of hashCode() of a given key does not depend on the number of entries in the HashMap. Therefore it takes O(1) time to compute the hashCode() (assuming the length of the String key in your example is not a function of the size of the Map - we can construct a strange HashMap<String,String> where the ith key put in the Map has i characters - in that edge case, hashCode() calculation would take O(N) time, and as a result, all the HashMap operations will require O(N) time instead of O(1)).

Once you compute the hashCode(), it takes O(1) time to find out whether the key is already present in the Map (since the average number of entries in each bucket of the HashMap is bound by a constant).