General Contract of the hashCode() Method- Object Comparison
General Contract of the hashCode() Method
The general contract of the hashCode() method stipulates the following:
- Consistency during execution is a necessary prerequisite: Multiple invocations of the hashCode() method on an object must consistently return the same hash code during the execution of an application, provided the object is not modified to affect the result returned by the equals() method. The hash code need not remain consistent across different executions of the application. This means that using a pseudorandom number generator to produce hash codes is not a valid strategy.
- Object value equality implies hash code equality: If two objects are equal according to the equals() method, then the hashCode() method must produce the same hash code for these objects. This tenet ties in with the general contract of the equals() method.
- Object value inequality places no restrictions on the hash code: If two objects are unequal according to the equals() method, then the hashCode() method need not produce distinct hash codes for these objects. However, it is strongly recommended that the hashCode() method produce unequal hash codes for unequal objects.
Note that the hash code contract does not imply that objects with equal hash codes are equal. Not producing unequal hash codes for unequal objects can have an adverse effect on performance, as unequal objects with the same hash code will hash to the same bucket.
Heuristics for Implementing the hashCode() Method
In Example 14.6, the computation of the hash code in the hashCode() method of the ReliableVNO class embodies heuristics that can produce fairly reasonable hash functions. The hash code is computed according to the following formula:
hashValue = 11 * 31
3
+ release * 31
2
+ revision * 31
1
+ patch
Only the significant fields that have bearing on the equals() method are included. This ensures that objects that are equal according to the equals() method also have equal hash codes according to the hashCode() method.
Example 14.6 Implementing the hashCode() Method
import java.util.Objects;
// Overrides both equals() and hashCode().
public class ReliableVNO {
private int release;
private int revision;
private int patch;
public ReliableVNO(int release, int revision, int patch) {
this.release = release;
this.revision = revision;
this.patch = patch;
}
public int getRelease() { return this.release; }
public int getRevision() { return this.revision; }
public int getPatch() { return this.patch; }
@Override public String toString() {
return “(” + release + “.” + revision + “.” + patch + “)”;
}
@Override public boolean equals(Object obj) { // (1)
return (this == obj) // (2)
|| (obj instanceof ReliableVNO vno // (3)
&& this.patch == vno.patch // (4)
&& this.revision == vno.revision
&& this.release == vno.release);
}
@Override public int hashCode() { // (5)
int hashValue = 11;
hashValue = 31 * hashValue + release;
hashValue = 31 * hashValue + revision;
hashValue = 31 * hashValue + patch;
return hashValue;
// return Objects.hash(this.release, this.revision, this.patch); // (6)
}
}
The basic idea is to compute an int hash code sfVal for each significant field sf, and include an assignment of the form shown at (1) in the computation below:
public int hashCode() {
int sfVal;
int hashValue = 11;
…
sfVal = … // Compute hash code for each significant field sf. See below.
hashValue = 31 * hashValue + sfVal; // (1)
…
return hashValue;
}
This setup ensures that the result from incorporating a field value is used to calculate the contribution from the next field value.
Calculating the hash code sfVal for a significant field sf depends on the type of the field:
- Field sf is a boolean:
sfVal = sf ? 0 : 1;
- Field sf is a byte, char, short, or int:
sfVal = (int)sf;
- Field sf is a long:
sfVal = (int) (sf ^ (sf >>> 32));
- Field sf is a float:
sfVal = Float.floatToInt(sf);
- Field sf is a double:
long sfValTemp = Double.doubleToLong(sf);
sfVal = (int) (sfValTemp ^ (sfValTemp >>> 32));
- Field sf is a reference that denotes an object. Typically, the hashCode() method is invoked recursively if the equals() method is invoked recursively:
sfVal = (sf == null ? 0 : sf.hashCode());
- Field sf is an array. The contribution from each element is calculated similarly to a field.
The order in which the fields are incorporated into the hash code computation will influence the hash code. Fields whose values are derived from other fields can be excluded. There is no point in feeding the hash function with redundant information, since this is unlikely to improve the value distribution. Fields that are not significant for the equals() method must be excluded; otherwise, the hashCode()
method might end up contradicting the equals() method. As with the equals() method, data from unreliable resources (e.g., network access) should not be used, and inclusion of transient fields should be avoided.
A legal or correct hash function does not necessarily mean it is appropriate or efficient. The classic example of a legal but inefficient hash function is
public int hashCode() {
return 1949;
}
All objects using this method are assigned to the same bucket. The hash table is then no better than a list. For the sake of efficiency, a hash function should strive to produce unequal hash codes for unequal objects.
For numeric wrapper types, the hashCode() implementation returns an int representation of the primitive value, converting the primitive value to an int, if necessary. The Boolean objects for the boolean literals true and false have specific hash codes, which are returned by the hashCode() method.
The hashCode() method of the String class returns a hash code that is the value of a polynomial whose variable has the value 31; the coefficients are the characters in the string, and the degree is the string length minus 1. For example, the hash code of the string “abc” is computed as follows:
hashValue = ‘a’ * 31
2
+ ‘b’ * 31
1
+ ‘c’ * 31
0
= 97 * 31 * 31 + 98 * 31 + 99 = 96354
For immutable objects, the hash code can be cached—that is, calculated once and returned whenever the hashCode() method is called.
However, the hash() method of the Objects class makes it very convenient to compute the hash code for an object with multiple fields. The procedure outlined above for calculating the hash code for a version number can be replaced by a single statement, as shown at (6) in Example 14.6. Each int field value is autoboxed in an Integer and passed in the call to the Objects.hash() method which returns a hash code based on the field values of the version number.
return Objects.hash(this.release, this.revision, this.patch); // (6)
The client in Example 14.7 demonstrates searching for objects of the class ReliableVNO in a set and in a map. The ReliableVNO objects in the array versions are used as elements in the set and as keys in the map.
Output from the program in Example 14.7 shows that the search key (9.1.1) and the element (9.1.1) in the set vnoSet have the same hash code. The search is successful. These objects hash to the same bucket. Therefore, the search for the element takes place in the right bucket. It finds the element (9.1.1) using the equals() method by successfully checking for equality between the search key (9.1.1) and the element (9.1.1) of the set.
Each entry in the map versionStatistics represents a version number (the key) and the number of downloads (the value) for that version number. Output from the program also shows that the key (9.1.1) of the entry (9.1.1)=6000 in the map has the same hash code as the search key (9.1.1). The search is successful.
However, we still cannot use objects of the class ReliableVNO in sorted sets and maps, as no criteria for comparing the version numbers have been defined.
Example 14.7 Implications of Implementing the hashCode() Method
import static java.lang.System.out;
import java.util.*;
public class TestReliableVNO {
public static void main(String[] args) {
// Print name of version number class:
out.println(ReliableVNO.class);
// An array of version numbers.
ReliableVNO[] versions = new ReliableVNO[] { // (1)
new ReliableVNO( 3,49, 1), new ReliableVNO( 8,19,81),
new ReliableVNO( 2,48,28), new ReliableVNO(10,23,78),
new ReliableVNO( 9, 1, 1)};
// Search key and its hash code:
ReliableVNO searchKey = new ReliableVNO( 9, 1, 1); // (2)
out.printf(“Search key %s has hash code: %d%n”, searchKey,
searchKey.hashCode()); // (3)
// Print hash values:
out.println(“Hash codes:”);
for (ReliableVNO element : versions) { // (4)
out.printf(” %10s: %s%n”, element, element.hashCode());
}
out.println();
// Searching in a set:
Set<ReliableVNO> vnoSet = new HashSet<>(Arrays.asList(versions)); // (5)
out.println(“Set: ” + vnoSet);
out.printf(“Search key %s contained in set: %s%n%n”, searchKey,
vnoSet.contains(searchKey)); // (6)
// Searching in a map:
Map<ReliableVNO, Integer> versionStatistics = new HashMap<>(); // (7)
versionStatistics.put(versions[0], 2000);
versionStatistics.put(versions[1], 3000);
versionStatistics.put(versions[2], 4000);
versionStatistics.put(versions[3], 5000);
versionStatistics.put(versions[4], 6000);
out.println(“Map: ” + versionStatistics); // (8)
out.printf(“Search key %s contained in map: %s%n”, searchKey,
versionStatistics.containsKey(searchKey)); // (9)
}
}
Output from the program:
Click here to view code image class ReliableVNO
Search key (9.1.1) has hash code: 336382
Hash codes:
(3.49.1): 332104
(8.19.81): 336059
(2.48.28): 331139
(10.23.78): 338102
(9.1.1): 336382
Set: [(10.23.78), (2.48.28), (9.1.1), (3.49.1), (8.19.81)]
Search key (9.1.1) contained in set: true
Map: {(10.23.78)=5000, (2.48.28)=4000, (9.1.1)=6000, (3.49.1)=2000,
(8.19.81)=3000}
Search key (9.1.1) contained in map: true