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

Question

I survived a Java implementation of the put method for a hash table 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; } } 

Although I understand that a key is required to check for conflicts, why does Java store the hash value of the key and also check it?

Answer 1

Since the same bucket ( tab ) can contain elements that have different hashes due to the % tab.length operation. Hash checking first is probably some performance optimization to avoid calling equals() if the hashes are different.

To give this as an example: let's say you have two complex objects with the expensive equals() method. One object has a hash equal to 1, while the other object has a hash 32. If you put both objects in a hash table that has 31 buckets, they will fall into the same bucket ( tab ). When adding a second (another object), you must make sure that it is not already in the table. You can use equals() right away, but it can be slower. Instead, you first compare hashes, avoiding costly equals() if it is not necessary. In this example, the hashes are different (even though they are in the same bucket), so equals() not required.

Answer 2

It makes access faster because the hash value does not need to be recalculated for each access. This is important not only for explicit searches (where the hash is checked before doing equals ), but also for rephrasing.