Why must equal objects have equal hash codes, and what breaks if they don't?

The contract is: if a.equals(b) then a.hashCode() == b.hashCode().

A HashMap first uses the hash code to pick a bucket, then equals() within it. If two equal keys produce different hash codes, they can land in different buckets, so after putting with one you may fail to get with the other -- the map appears to 'lose' the entry. That is why whenever you override equals() you must also override hashCode(), and why you must never mutate a field used in hashCode() after using the object as a key.