Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Need explanation for hashcode example in Effective Java textbook

Here's the sample code from Item 9:

public final class PhoneNumber {
  private final short areaCode;
  private final short prefix;
  private final short lineNumber;

  @Override
  public int hashCode() {
    int result = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    return result;
  }
}

Pg 48 states: "the value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as muiltiplication by 2 is equivalent to shifting."

I understand the concept of multiplication by 2 being equivalent to bit shifting. I also know that we'll still get an overflow (hence information loss) when we multiply a large number by a large odd prime number. What I don't get is why information loss arising from multiplication by large odd primes is preferable to information loss arising from multiplication by large even numbers.

like image 616
Kes115 Avatar asked Jun 06 '12 13:06

Kes115


People also ask

What is hashCode in Java with example?

hashCode() Method ADVERTISEMENT. ADVERTISEMENT. The hashCode() is a method of Java Integer Class which determines the hash code for a given Integer. It overrides hashCode in class Object. By default, this method returns a random integer that is unique for each instance.

Why do we need hashCode in Java?

HashMap and HashSet use hashing to manipulate data. They use hashCode() method to check hash values. The default implementation of hashCode() in Object class returns distinct integers for different objects.

How does hashCode () method work in Java?

The Java hashCode() MethodIt returns an integer whose value represents the hash value of the input object. The hashCode() method is used to generate the hash values of objects. Using these hash values, these objects are stored in Java collections such as HashMap, HashSet and HashTable.

What is hashCode of an object?

Java Object hashCode() is a native method and returns the integer hash code value of the object. The general contract of hashCode() method is: Multiple invocations of hashCode() should return the same integer value, unless the object property is modified that is being used in the equals() method.


2 Answers

There is no such thing as a large even prime - the only even prime is 2.

That aside - the general point of using a medium-sized prime # rather than a small one like 3 or 5 is to minimize the chance that two objects will end up with the same hash value, overflow or not.

The risk of overflow is not the issue per se; the real issue is how distributed the hashcode values will be for the set of objects being hashed. Because hashcodes are used in data structures like HashSet, HashMap etc., you want to minimize the # of objects that could potentially share the same hash code to optimize lookup times on those collections.

like image 40
wrschneider Avatar answered Sep 28 '22 01:09

wrschneider


With an even multiplier the least significant bit, after multiplication, is always zero. With an odd multiplier the least significant bit is either one or zero depending on what the previous value of result was. Hence the even multiplier is losing uncertainty about the low bit, while the odd multiplier is preserving it.

like image 71
rossum Avatar answered Sep 28 '22 02:09

rossum