To understand this concept, you might have already read the bucket example given in K&B book. In that every bucket would have an id and that id is nothing but our hashcode. Now coming to the point of relation between equals and hashCode. Its absolutely not a mandatory to over hashCode if equals is overriden. But, imagine we have equals overriden , but not hashCode. Let the default hashCode be given to all the objects (hashCode implemention in Object class). Then all the objects we create would land into a same bucket. Now the problem comes while searching which is a two step process, that is first find out the right bucket and with in the bucket find the right object. This is one of the optimal solutions for searching. Nothing would stop us to implement our own algorithm.
Then while searching, for every object we search, we would be pointing to the same bucket (Due to same hashcode) and with in that bucket we need to search for the actual object using equals traversing all the un wanted objects. So if we implement hashCode in an optimal fashion such that objects are distributed evenly, then our search time drastically comes down. Hope I made a point here.
As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)