K&B chapter 7 Q7 question HashMap vs TreeMap

[Jia Tan]

I modify the original code a little bit to add Comparable interface:

 import java.util.*;

public class MapEQ2 {
    public static void main (String[] args) {
        Map<ToDo, String> m = new HashMap<ToDo, String> ();
        ToDo td1 = new ToDo("Monday");
        ToDo td2 = new ToDo("Monday");
        ToDo td3 = new ToDo("Tuesday");
        m.put(td1, "doLaundry");
        m.put(td2, "payBills");
        m.put(td3, "cleanAttic");
        System.out.println(m.size());
    }
}
class ToDo implements Comparable<ToDo> {
    String day;
    ToDo (String d) { day = d; }
    public boolean equals (Object o) {
        return (((ToDo)o).day == this.day);
    }
//  public int hashCode () { return 9; }
    public int compareTo(ToDo td) {
        return day.compareTo(td.day);
    }
}

The output is 3.
If I change line 5 to:

         Map<ToDo, String> m = new TreeMap<ToDo, String> ();

The output becomes 2.
Why the difference?

[Ruben Soto]

Hi Jia,

The problem in your code is that hashCode() shouldn't be commented, because if it is, you are violating the equals/hashCode() contract. Also notice that TreeMap doesn't use equals/hashCode, but the compareTo() method.
In your case, TreeMap works as expected, but since you are using the default hashCode() from Object, you are able to add all 3 mappings to your map. If you uncomment hashCode you will find that only 2 mappings get added.

[Stephen Davies]

Ruben, you are almost correct, though your statement is incorrect. If you do not override Object method, hashCode() you are NOT violating the hashCode contract, as the contract can only be honored if you override the method. It certainly will produce erroneous results, if you don't override or if you use the default implementation, and then attempt to use the equals() method in a collection as such. There is no rule to actually implement hashCode, as there is no rule with other Object methods such as toString(), wailt(), notify() etc.

A contract comes into play, Only when overriding, but it is not a contractual requirement to Override. Finally there is no contract between hashCode and equals().
However, the contract for overriding the hashCode() method does contain rules in relation to the equals method, but this does not mean if you override equals() that you must also override hashCode() (although you should). If you do override hashCode(), you must ensure it operates within the bounds of the equals operation as stipulated in the hashCode() contract, thus in this sense there is an operational relationship, but not a dependent relationship., and certainly not a contract in the API sense of the word.

Don't forget the compareTo() is the only method of the Comparable interface, and must be Implemented if the class implements Comparable. However, equals() and hashCode are methods of java.lang.Object class, and do not have to be implemented. As Jia's class implements Comparable, then he must override compareTo() but he does not have to override hashCode();

Jia, just as an added snippet I have learnt, if you are overriding the equals() method, and your method included a Class cast, its good practice to put an object type check in before casting, to avoid class cast errors. The way that this is reccomended by Sierra & Bates, is to use the instanceof operator, as a condition before comparisson:

for example;

@Override
	public boolean equals(Object o){
		if((o instanceof Car) && ((Car)o).getReg()==this.reg){
			return true;
		} else {
		
		return false;
		}
	
	}

From this the conditional test requires that Object reference o, fulfill the is-a for type Car, before being cast, and thus ensuring a successful comparison .

[Jia Tan]

Thank you all for the explaination. I guess I forgot that TreeMap does not allow duplacate keys. That's why the result is different.

[Henry Wong]

Ruben, you are almost correct, though your statement is incorrect. If you do not override Object method, hashCode() you are NOT violating the hashCode contract, as the contract can only be honored if you override the method. It certainly will produce erroneous results, if you don't override or if you use the default implementation, and then attempt to use the equals() method in a collection as such.

Ruben was referring to the equals/hashcode contract that is specified in the JavaDoc. This contract not only specified how these two method should behave themselves -- but how they should behave with each other. So, if you override one that breaks the contract, isn't the contract violated? I am not sure why you need to override both methods before you consider the contract is violated.

Henry

[Henry Wong]

BTW, here is the relevant quote from the JavaDoc...

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 hashtables.

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.)

[Stephen Davies]

I am not sure why you need to override both methods before you consider the contract is violated.

Henry, I am unclear or what you mean here. My point is that I was of the opinion, the API did not exclusively provide a contract between hashCode and equals. They each contain a contract for their own implementations, if you choose to implement and override them, and yes if you override them both they must fulfill requirements in respect of each other. However, are you suggesting that if you implement and override equals() that you MUST implement / override hashcode? This is the point I am referring to.

To quote Sierra & Bates SCJP 5 P.529

equals() and hashCode are bound together by a joint contract that specifies if two objects are considered equal using the equals() method, then they must have identical hashcode values. So to be truly safe, your rule of thumb [emphasis added]should be, if you override equals(), override hashcode as well

So, in my reading of this, it is good practice to override both, but it is not a contract that you must override hashCode() if you choose to override equals(). However inversely it makes no sense and it IS a contractual error not to override equals() if you override hashCode(), as the hasCode() contract specifies operability with the equals method.

As I was writing this post you managed to post the API contract for hashCode(), which supports my inverse point above, however, within the contract for equals() I believe there is no mention of the hashCode() implementation?

In the code originally provided, the implementation was for compareTo() which is a method of the Comparable interface, so by commenting out the hashCode() implementation, there is indeed no contract broken is there not?

I hope this clears matters up

[Henry Wong]

So, in my reading of this, it is good practice to override both, but it is not a contract that you must override hashCode() if you choose to override equals(). However inversely it makes no sense and it IS a contractual error not to override equals() if you override hashCode(), as the hasCode() contract specifies operability with the equals method.

Well, yea, I agree. It's not a "contract", in that an error will be flagged by the compiler (or something else). IMO, the word "contract" is way too strong to be used here. But unfortunately, the JavaDoc does use the word, so.... when Ruben mentioned the "contract", he is merely using the official wording -- and not implying anything more than that.

so by commenting out the hashCode() implementation, there is indeed no contract broken is there not?

Now we are debating over semantics. "contract" arguments aside, whatever it is... it is no long as specified, hence, it is broken.

Henry

[Stephen Davies]

The brokeness, I certainly agree on, but as for commenting out hasCode() resulting in a broken contract with a compareTo() I will kindly agree that perhaps it is simply a matter of semantics and nothing else, and thus move on.

Though such as discussion as we have had is one of the great things about the Ranch, sharing ideas opinions and perspectives, is certainly invaluable input, keep it up!

[Ruben Soto]

Stephen Davies wrote:The brokeness, I certainly agree on, but as for commenting out hasCode() resulting in a broken contract with a compareTo() I will kindly agree that perhaps it is simply a matter of semantics and nothing else, and thus move on.

Though such as discussion as we have had is one of the great things about the Ranch, sharing ideas opinions and perspectives, is certainly invaluable input, keep it up!

Hi Stephen,

I welcome this discussion, but I think you are confusing things unnecessarily and it might be hard for some people to distinguish what is going on. Commenting hashCode() doesn't result in a broken contract with compareTo(), it is equals() and hashCode() that must be consistent with each other.

This is from the Map interface API documentation:

Implementations are free to implement optimizations whereby the equals invocation is avoided, for example, by first comparing the hash codes of the two keys. (The Object.hashCode() specification guarantees that two objects with unequal hash codes cannot be equal.)

What that means is that it is possible that when you use put() to add a mapping to a HashMap, if the hashCode() value for the key of the mapping you are trying to add is different than the hashCode() of any of the keys already present, the mapping will be added. This is despite the fact that the key might be equal (as per equals()) to some existing key. That's why you need to respect the hashCode()/equals() contract, because if you don't you will possibly get erroneous behavior, as you do in Jia's example.

In contrast, when Jia used a TreeMap, the behavior is correct. The reason is that TreeMap doesn't use equals() and hashCode() like HashMap does, but compareTo(). By the way, compareTo() is also expected to be consistent with equals(), but that fact does not directly apply to this case.

I hope that clarified things.

[Stephen Davies]

Ruben,

You stated

The problem in your code is that hashCode() shouldn't be commented, because if it is, you are violating the equals/hashCode() contract.

It is here, from which my understanding arose, I apologize if I have caused unnecessary confusion, though I am grateful we could go through it on this post to help. However, as I said before I would agree to put down the discussion now and admit it is probably a moot point now as its simply a misunderstanding on my part based on semantics and nothing, else. I gratefully request we move on.

Thanks

[Ruben Soto]

Stephen Davies wrote:Ruben,

You stated

The problem in your code is that hashCode() shouldn't be commented, because if it is, you are violating the equals/hashCode() contract.

It is here, from which my understanding arose, I apologize if I have caused unnecessary confusion, though I am grateful we could go through it on this post to help. However, as I said before I would agree to put down the discussion now and admit it is probably a moot point now as its simply a misunderstanding on my part based on semantics and nothing, else. I gratefully request we move on.

Thanks

Sounds good, Stephen. But my quote (that you are quoting) is correct. Because Jia didn't override hashCode(), the hashCode()/equals() contract was violated, and that's why the code was not working correctly. If you don't ensure that the contract is respected (and yes, it is a contract, as in "a set of rules that should be respected in order to ensure everything is alright") then your code can malfunction, and nobody wants their code to malfunction.

There is nothing wrong about discussing things in detail, as I am sure it will help people that are confused by this. So if there are any other questions, I say we continue discussing it until everything is clear.