The hashing mechanism

To demonstrate why both the hashCode() and equals() methods are so important, let's check out an example.

Consider the following Java code that creates a HashMap instance and adds a key/value pair:

    map = HashMap();
    map.put("key1", "value1");

The hashCode() method will be called on the passed key object, in this case, the String instance key1. This will result in an arbitrary number that can be used for hashing, in this example, 123. Internally, the HashMap instance stores the hash of the key in such a way that it will be able to quickly look it up, and it will link both the key and value objects to it.

A new key/value pair key2 and value2 are added to the map now. Assume that the hashCode() method of the key2 object would return 234. This hash code was not used earlier, so a new hash code key value is added and the specified key and value objects are associated with it.

Now, when you add the new key3 and value3 pairs, something unexpected happens. The hashCode() method of the key3 String instance returns 234. This hash code points to both the key2/value2 and key3/value3 pairs. This is called a collision.

The program requests the value object that corresponds to the key3 key object:

    Object o = map.get("key3");

The HashMap object will call the hashCode() method of the passed key, "key3", which will return 234 again. The HashMap object sees that this hash code is associated with two Key/Value pairs and will, therefore, call the equals() method of both the "key2" and "key3" String objects to determine which of the passed keys match with the "key3" String. In this case, "key3" matches and the "value3" object is returned.

What you learned from this example is that the hashCode() and equals() methods are really important. The fewer the number of collisions that occur when adding key/value pairs, the quicker the keys will be found. If the equals() method implementation is buggy, then the key lookup process will fail as well.