What is the time complexity for adding a String,String entry to a HashMap in Java?

Question

If we have a HashMap<String,String> H, and we use the code H.put("Hello","World"). Would the time complexity be the same as in the case where we use an integer key-value pair in a HashMap? I feel that the performance with String should be poorer, as hashing the String would be an O(String length) operation.

Yossi Vainshtein · Accepted Answer · 2017-03-18 20:47:31Z

2

Yes, It's performance will be poorer since hashing a string is indeed slower then hashing an integer.

In fact, Java uses a specific formula for hashCode() of String, which you can see here, and it does check all the charachters of the string, as you would expect.

In my Eclipse the code for 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;
}

But why are you comparing these two things? It doesn't make much sense to compare complexity of two algorithms which do different things.

edited Mar 18, 2017 at 20:47

answered Mar 18, 2017 at 20:42

Yossi Vainshtein

4,0455 gold badges26 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dhruv Mullick Over a year ago

I didn't mean to compare, I was wondering if there is any drop in performance due to the length of string.

Yossi Vainshtein Over a year ago

Yes. You can even see the code for String.hashCode() in your eclipse and see the loop. (see edit in my answer)

Collectives™ on Stack Overflow

What is the time complexity for adding a String,String entry to a HashMap in Java?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related