Why does a HashTable store the hash value of the key in the table in java

Question

I was going through Java's implementation of the put method for a hashtable and came across this :

// Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

While I understand that a key is required to check for collisions, why is Java storing the hash value of the key and also checking it ?

Darling

Answer 1

Because the same bucket (tab) can hold items having different hashes due to % tab.length operation. Checking hash first is probably some performance optimization to avoid calling equals() if hashes are different.

To put this in an example: Say you have two complex objects with costly equals() method. One object has hash equal to 1 while the other object has hash of 32. If you put both objects in a hash table having 31 buckets, they'll end up in the same bucket (tab). When adding a second (different object) you must make sure it's not yet in the table. You can use equals() immediately, but this might be slower. Instead you first compare hashes, avoiding costly equals() if not necessary. In this example hashes are different (despite being in the same bucket) so equals() is not necessary.

Glossectomy

Answer 2

It makes access faster, since the hash value does not need to be recomputed for every access. This is important not just for explicit searches (where the hash is checked before doing equals) but also for rehash.

Wardle