Collisions

The hash code for an object should be as unique as possible. If two unequal objects return the same hash code, they will resolve to the same slot in the hash table. This is known as a collision. The implication of a collision is extra logic and extra time to maintain a list of collided objects. A few solutions for resolving collisions exist. The simplest is manage a list of collided objects for each slot. Figure 9.4 shows a pictorial representation.

Figure 9.4. Hash Table Collisions

Since the possibility of collisions exists, when retrieving an object, the hash table code must also compare the object retrieved from a slot to ensure that it is the one expected. If not, the code must traverse the list of collided objects to find the match.

If all objects were to return the same hashCode, such as 1, then all objects will collide to the same slot in a HashMap. The end result would be that every insertion and deletion would require serially traversing the list of collided objects. This list would include every object inserted. In this degenerate case, you might as well use an ArrayList.

If the hash codes of all objects generate different slots, you have an optimally mapped hash table. Performance is the best possible: All insertions to and retrievals from the table execute in constant time. There is no need to serially traverse a collision list.