Objects, equals() and hash-values -

Objects, equals() and hash-values

Figure 423. Hashing principle

“I want the 12p one”

Figure 424. Quickly identify by “simple” value

Where is the blond haired guy?
I take the pink flower.
The 334.50$ cellular phone.

Figure 425. Hashing in Java and equals()

Method hashCode(): Instance 0 ⇨ o.hashCode(), of type int.

Same value on repeated invocation
Objects with identical value with respect to equals() must have identical hash values:

true == a.equals(b) ⟹ a.hashCode() == b.hashCode().
Conversely: Two instances differing with respect to equals() may have identical hash values.

Consequence: equals() and hashCode() must be redefined simultaneously!

Figure 426. Rectangle equals(...) and hashCode()

public class Rectangle {
    int width, height;
    @Override public boolean equals(Object o) {
        if (o instanceof  Rectangle r) {
            return width == r.width && height == r.height;
        } else {
            return false;
        }
    }
    @Override public int hashCode() {
        return width + height;
    }
}

Figure 427. Rectangle hash values

public class Rectangle { int width, height; ... @Override public int hashCode() { return width + height; } }	width	height	hash value
	1	3	4
	2	2	4
	5	5	10
	2	7	9
	4	9	13

Figure 428.

Improved

hashCode() method

public class Rectangle { int width, height; ... @Override public int hashCode() { return width + 13 * height; } }	width	height	hash value
	1	3	40
	2	2	28
	5	5	70
	2	7	93
	4	9	121

exercise No. 132

Choosing a “good” `hashCode()` method

We consider:

public class TimePeriod {
  private final int hours, minutes, seconds;
  /**
   * A time period within a day e.g. 4 hours, 23 minutes and 11 seconds.
   *
   * @param hours Hours ranging from 0 to 23
   * @param minutes Minutes ranging from 0 to 59
   * @param seconds Seconds ranging from 0 to 59
   */
  public TimePeriod(final int hours, final int minutes, final int seconds) {
    this.hours = hours;
    this.minutes = minutes;
    this.seconds = seconds;
  }

  @Override
  public boolean equals(final Object o) {
    if (o instanceof TimePeriod t) {
      return hours == t.hours &&
          minutes == t.minutes &&
          seconds == t.seconds;
    } else {
      return false;
    }
  }
}

Which of the two hashCode() implementations is better with respect to quickly telling whether two TimePeriod instances are having the same value or not?

Method 1 Method 2

public class TimePeriod {
...
  @Override
  public int hashCode() {
    return seconds + 60 * (minutes + 60 * hours);
  }
}

public class TimePeriod {
...
  @Override 
  public int hashCode() {
    return seconds + minutes + hours;
  }
}

Tip

Excerpt from Object.hashCode():

However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

According to Figure 425, “Hashing in Java and equals() ” part of a hashCode() methods contract is:

true == a.equals(b) ⟹ a.hashCode() == b.hashCode().

A so called perfect hashCode() method in addition will return different values whenever two instances a and b differ in value with respect to the underlying equals() method:

false == a.equals(b) ⟺ a.hashCode() != b.hashCode().

Combining these two statements a perfect hashCode() method will have the following property:

a.equals(b) == (a.hashCode() == b.hashCode())

Method 1 serves this purpose: Its returns a given TimePeriod instance into its total amount of seconds equivalent. Example: (1 hour, 2 minutes, 5 seconds) amounts to (1 * 60 + 2) * 60 + 5 = 3725 seconds. Due to its specification an instance of TimePeriod cannot exceed 24 hours being equivalent to 24 * 60 * 60 = 86400 seconds. Thus a 4-byte int is safe with respect to overflow issues.

Conclusion: Whenever two instances of TimePeriod differ their method 1 hashCode() values will differ as well.

This does not hold with respect to method 2. Consider two instances (1 hour, 2 minutes, 3 seconds) vs. (3 hours, 2 minutes, 1 second) returning an identical hashCode() of 1 + 2 + 3 = 3 + 2 + 1 = 6. So method 2 requiring just two additions offers (slightly) better runtime performance at the expense of a higher hash value collision rate.

Note

Perfect hash functions are rare with respect to real world modeling problems. In the current example Timeperiod instances are limited by 24 hours, 59 minutes and 59 seconds. This limit is equal to 89999 seconds fitting well into the count of $2^{32}$ different int values.

exercise No. 133

`String` and good hashCode() implementations.

In the previous exercise we found a perfect hashCode() implementation:

public class TimePeriod {
...
  @Override
  public int hashCode() {
    return seconds + 60 * (minutes + 60 * hours);
  }
}

Does a perfect hash function exist for String instances as well?

Tip

Consider the possible number of different strings.

It is not possible to construct a perfect hashCode() method acting on strings. A Java String consists of individual char elements each requiring two bytes representing $2^{16}$ different characters. Depending on a string's length we have:

String length (number of characters)	Number of different strings
1	$2^{16}$
2	$2^{2 \times 16}$
3	$2^{3 \times 16}$

Thus considering just the union of zero (empty), one- and two character strings we have $1 + 2^{16} + 2^{32}$ possibilities exceeding the $2^{32}$ count of different int values. Thus hash value clashes are inevitable.

The JDK™'s String.hashCode() implementation already reveals conflicts for ASCII strings of length 2:

Code	Execution result
`System.out.println("hashcode of Aa: " + "Aa".hashCode()); System.out.println("hashcode of BB: " + "BB".hashCode());`	hashcode of Aa: 2112 hashcode of BB: 2112

Prev	Up	Next
Core Classes	Home	Using class `Math`

Core Classes