Why are immutable objects in hashmaps so effective?

caching, hashmap, immutability, java, performance

Solution

`String#hashCode`:

private int hash;

...

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        int off = offset;
        char val[] = value;
        int len = count;

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

Since the contents of a `String` never change, the makers of the class chose to cache the hash after it had been calculated once. This way, time is not wasted recalculating the same value.

Problem

So I read about HashMap. At one point it was noted: "Immutability also allows caching the hashcode of different keys which makes the overall retrieval process very fast and suggest that String and various wrapper classes (e.g., `Integer`) provided by Java Collection API are very good `HashMap` keys." I don't quite understand... why?

Original source