Override hashCode

Question

Can someone explain why we used both equals and hashcode and not just equals?

I don't really get how the hashcode works.. and documentation is really vague about that.

i.e

 @Override
    public int hashCode() {
        int result = mArtist != null ? mArtist.hashCode() : 0;
        result = 31 * result + (mTitle != null ? mTitle.hashCode() : 0);
        result = 31 * result + (mVideoUrl != null ? mVideoUrl.hashCode() : 0);
        return result;
    }

Answer 1 · 2015-08-08T20:16:02Z

August 8, 2015 8:16pm

Hello Jonathan,

Could it be any integer?

Yes, any positive or negative integer. This accounts for overflow.

Does it have a meaning of what integer it is for its place in the hashMap and that's all or it affects the comparing\equals methods too?

Quoted from the link I provided earlier:

The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

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.

It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

What is the meaning of the 31 I keep seeing in all the generated code \ when evaluating objects?

Efficiency through the prevention of as many collisions as possible. A collision is when we attempt to place an object in a hash table and the bucket already has an object. Now we would have to use a different methodology to account for the collision and ultimately loose efficiency. For example, we might have a linked list in which all Objects that attempt to be placed in a bucket get inserted for storage. We now have to traverse the list in linear time instead of being able to accomplish hashing in constant time. There are other methods as well but for the sake of brevity within these forums, I will just provide some links from college at the end of this post.

The number 31 is a Mersenne prime. A good explanation can be found at the following website:

http://mathworld.wolfram.com/MersennePrime.html

One of the important things that It states, "Mersenne primes were first studied because of the remarkable properties that every Mersenne prime corresponds to exactly one perfect number"

Using a Mersenne prime of 31 allows our algorithm to produce many more distinct integers than not using 31. Thus, less collisions that give us a more efficient hash table. Although, there has been a lot of advancement in regards to even better hashing algorithms lately and you can find many that cover them online today. Of course, for the purposes of the courses here on TreeHouse, we have already went well beyond anything you will need here. The auto generated code is good for now.

Please check out the following for further study:

https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-01/11-hashcode-map.pdf

https://courses.cs.washington.edu/courses/cse331/11wi/lectures/lect10-equality.pdf

Definitely check out MIT open courseware on time complexity of algorithms for more about algorithms and efficiency.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/

Regards,

Chris

Answer 2 · 2015-08-08T06:40:35Z

August 8, 2015 6:40am

Jonathan,

Now that is a great question. The answer stems from the fact that the equals method and the hashCode method share some important relationships. As you likely know, the Object class is the superclass to all other classes and it has the implementation of these methods in which includes a contract between them. You can look over the documentation to see these relationships at the following website:

http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html

Basically, we need a way to keep Object identity when using Objects within collections like hashMaps and hashTables because we could cause problems by placing Objects where they were not intended to go. The relationships/rules typically require us to use these methods together to meet these requirements.

For example, if you wanted to use a HashMap to store key value pairs consisting of a Vehicle Object and a Integer Object in order to keep how many of each vehicle in the lot is the same type of vehicle (i.e BMW, M6, Blue):

       HashMap<Vehicle, Integer> amountOfEachVehicleInLot = new HashMap<Vehicle, Integer>();

You could not just use the equals method. The issue that would arise is from the fact that since the Vehicle object is not overriding the hashCode() method, they would return a hashCode() based on their reference that is different. Therefore, if we place a Vehicle in the hashMap with make: BMW, model: M6, color: blue and then attempt to use the HashMap's get method to retrieve an amount via making a new vehicle with the same make, model, and color, we would just get NULL in return. Why?

Realistically, they are not the same car. They are two different cars with the same make, model, and color. However, we want to be able to retrieve the amount of cars in the lot that have the same make, model, and color. While there may be different ways to accomplish this goal, this example shows how overriding both the equals method and the hashCode method will allow us to do so. We would simply override the hashCode method to return an int based on something like the length of the color String.

       @Override
    public int hashCode() {
        return mColor.length();
    }

I hope this helps.

Regards,

Chris

Answer 3 · 2015-08-08T13:49:09Z

August 8, 2015 1:49pm

Thank you for your informative answer! :)

So basically same as with overriding equals, and defining how it would evaluate equality, we define for an object how to check the HashCode for -this- type of object, and it returns an integer?

Could it be any integer?
Does it have a meaning of what integer it is for its place in the hashMap and that's all or it affects the comparing\equals methods too?
What is the meaning of the 31 I keep seeing in all the generated code \ when evaluating objects?

Thanks in advance :)

Welcome to the Treehouse Community

Looking to learn something new?

Jonathan Leon

Jonathan Leon

Override hashCode

3 Answers

Christopher Augg

Christopher Augg

Christopher Augg

Christopher Augg

Jonathan Leon

Jonathan Leon