Which explains what it says in the API documentation for Object:
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
Since you are implicitly using the hashCode method by putting your objects into a HashMap, you should follow this rule. And since you are getting unexpected results, perhaps you didn't follow this rule. That would mean that you have created two objects which are "equal" but have different hashCode values; you could check that with a little debugging.
And your second (correct) example has a hashCode method which does follow that rule, and so you get correct-looking results.
HashSet, HashMap etc first use the return value of hashCode() to find the "bucket" the object is in. After that it uses equals to check all elements inside the bucket. If hashCode() does not follow the contract then the HashSet / HashMap will look in the wrong bucket.