Why are keys immutable in Java?

Question

Apologies for the fairly naive question, but I believe my own answer to be naive. I think keys (in HashTables) are immutable because we wouldn't want to somehow accidentally alter a key and therefore mess with the sorting of the HashTable. Is this a correct explanation? If so, how can it be more correct?

Answer 1

During the HashTable.put the key is hashed and it an its value are stored in one of a number of buckets (which are lists of key value pairs) based on the hash, for example something like:

bucket[key.hashcode() % numberOfBuckets].add(key, value)

If the key's hashcode changes after insertion it could then be in the wrong bucket and you would then not be able to find it and the hashtable would incorrectly return null on any get for that key.

Aside: Understanding the inner workings of a hashtable helps you understand the importance of a good quality hashcode function for your keys. As a poor hashcode function could result in a poor distribution of keys in buckets. And as buckets are just lists, this results in a lot of linear searches which greatly reduces the effectiveness of the hashtable. e.g. this terrible hashcode function puts everything in one bucket, so it's effectively just one list.

public int hashcode { return 42; /*terrible hashcode example, don't use!*/ }

This is also one reason why prime numbers appear in good hashcode functions, e.g.:

public int hashcode {
    int hash = field1.hashcode();
    hash = hash*31 + field2.hashcode(); //note the prime 31
    hash = hash*31 + field3.hashcode();
    return hash;
}