equals() and hashCode() contract in Java

Question

The SCJP 6 Study Guide from Bert Bates and Kathy Sierra states on page 554 (among other requirements) that x.hashCode() != y.hashCode() requires that x.equals(y) == false.

But the Javadoc for Object doesn't mention such requirement explicitly. Quote:
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.

Should I take what Javadoc says as a material implication, such as eq -> hc? Then there would be no conflict between these two sources.

Answer 1

The fundamental idea behind hashCode is that an entity which knows that an object has reported a hashCode value different from what some other object is entitled to assume that the objects are unequal without having to examine them any further. Because the integers uphold various axioms related to equivalence, an entity may know that two hash codes differ without directly comparing them. For example, knowledge that one of them has reported an even number and the other an odd number would suffice to show that they can't match. Such assumptions often allow entities to quickly identify large portions of collections which cannot possibly contain an object being looked up, and thus not bother examining those areas.

Both of the cited "requirements" about hashCode and equals include an unstated premise: In cases where X.equals(Y) reports true, one won't want entities to incorrectly assume it to be false. In general, it's very bad for code to act upon false assumptions, so the premise that one wouldn't want entities to make incorrect assumptions about the equality of objects is reasonable. The Study Guide quote alludes to the fact that if two objects have unequal hashcodes, they'll be presumed unequal; making such presumption match reality requires that they be unequal. The JavaDoc essentially alludes to the fact that if two objects are equal, and one wants to avoid having entities assume they won't be and fail to notice that they are, one must ensure that a hashCode value returned by one will also be returned by the other.

Answer 2

The two statements are equivalent.

Put simply:

1. if two hashcodes differ, the objects are definitely different under equals.
2. if two hashcodes are the same, we don't know. (but in many practical cases the objects will be equal).

Answer 3

As z5h says, the statements are equivalent.

For logical conditions x and y, "x implies y" is the same as "!y implies !x".

"If something is a bus, it's red" is logically equivalent to "if something isn't red, it's not a bus."

This is contraposition.

Should I take what Javadoc says as a material implication, such as eq -> hc.

Yes, that's exactly what it's saying: two objects being equal under equals implies their hashcodes must be equal.

Answer 4

Basic Facts about HashMap.
1. HashMap will generate hashcode for each key irrespective of the object type.
2. To be specific - hashcode will be generated based on the key and value(i.e. entry)

Experiment: Consider a user-defined object(eg. SPObject) is the key for a hashmap; SPObject has only one parameter (name) in it. Refer: http://www.programcreek.com/2011/07/java-equals-and-hashcode-contract/

If hashCode() and equals() are not written properly in the SPObject class, the issues are below.
Put 2 entries - new SPObject("SP") & new SPObject("SP"). These are treated as different object and gets stored in Map successfully.

map.get(new SPObject("SP")) will return null.
map.contains(new SPObject("SP")) will return false.

This is the result, if the hashCode/equals contract is not handled properly.

hashCode()     |    equals()    | Treated as | Description

No             |      No        | Duplicate  | Stored in different buckets.
                                             | Treated as different object.

Yes            |      No        | Duplicate  | Stored in same bucket.
                                             | Treated as different object. 
                                             | Because, the default(Object) equals method will check only the reference of objects.     

No             |      Yes       | Duplicate  | Stored in different buckets.Treated as different object

Yes(hashlogic) |      Yes       | Unique     | Stored in same bucket.Treated as same object.Efficient.

Yes(constant)  |      Yes       | Unique     | Stored in same bucket.Treated as same object.
                                             | Inefficient, because it will iterate bucket elements for equality check.

Answer 5

There is no conflict between these statements, they are equivalent.

p: x.equals(y)
q: x.hashCode() == y.hashCode()
p implies q
not q implies not p