Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Map Doubt

Abhi vijay
Ranch Hand
Posts: 509

Can anyone explain me the working of this program? I know its a very basic question but still I am not able to understand when the equals method will be called why the size=2?

Ankit Garg
Sheriff
Posts: 9542
33
When you add the third element to the map, the compareTo method is used to check if there is already a same key in the map.

t.put(d3,"CLOVER");

It will find that there is already a key in the map based on the result of the compareTo method. So the new value will replace the old value i.e. the value inserted using d2.

t.put(d2,"CLOVER");

The problem here is that the new and old value are the same. So you are not able to see any differences. Change the program like this to see the difference

Punit Singh
Ranch Hand
Posts: 952
t.put(d1,"AIKO");

When this element will be put in TreeMap, equals() will not be called as TreeMap has no element at this time.

t.put(d2,"CLOVER");

When this line called, TreeMap will call
1) d1.hashCode()==d2.hashCode(), this will return true as 7==7 is true, so it will call equals().
2) d1.equals(d2) will be called, this will return false as "AIKO"!="CLOVER".
equals() returns false so it will add d2 in the TreeMap

t.put(d3,"CLOVER");

When this line called, TreeMap will call
1) d1.hashCode()==d2.hashCode(), this will return true as 7==7 is true, so it will call equals().
2) d1.equals(d2) will be called, this will return false as "AIKO"!="CLOVER".
Now again
3) d2.hashCode()==d3.hashCode(), this will return true as 7==7 is true, so it will call equals().
4) d2.equals(d3) will be called, this will return true as "CLOVER"!="CLOVER".
here d2.equals(d3) returns true, so it will not add d3 in the map.
[ January 03, 2009: Message edited by: Punit Singh ]

Ankit Garg
Sheriff
Posts: 9542
33
Originally posted by Punit Singh:
When this line called, TreeMap will call
1) d1.hashCode()==d2.hashCode(), this will return true as 7==7 is true, so it will call equals().
2) d1.equals(d2) will be called, this will return false as "AIKO"!="CLOVER".
equals() returns false so it will add d2 in the TreeMap

Punit equals will never be called. This is TreeMap not HashMap. TreeMap uses compareTo method to check if key already exists...

Punit Singh
Ranch Hand
Posts: 952
Okay means first compareTo() will be called, and if compareTo() does not return 0, then only hashCode() will be called to store it in proper bucket.
Is it right Ankit?
Or
hashCode() will not be used, may be TreeMap is not a collection that uses Hashing for storage purpose. It may be using binary search tree for storing.

Ankit Garg
Sheriff
Posts: 9542
33
Originally posted by Punit Singh:
hashCode() will not be used, may be TreeMap is not a collection that uses Hashing for storage purpose.

Yes! TreeNode will never use hashCode or equals methods. Try this code without hashCode and equals, it will give the same result-

Punit Singh
Ranch Hand
Posts: 952
I got it Ankit, it use RED-BLACK Tree for storage purpose and this tree's name is Entry<K,V> and it is static final inner class of TreeMap.
Here it is in brief:

// Red-black mechanics

private static final boolean RED = false;
private static final boolean BLACK = true;

/**
* Node in the Tree. Doubles as a means to pass key-value pairs back to
* user (see Map.Entry).
*/

static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;

boolean color = BLACK;

Abhi vijay
Ranch Hand
Posts: 509
Punit,

That means the compareTo() compares aiko,clover1,clover2.
Dog d1= new Dog("aiko");
Dog d2 = new Dog("clover1");
Dog d3= new Dog("clover2");

It does not compare AIKO, CLOVER1,CLOVER2.
t.put(d1,"AIKO");
t.put(d2,"CLOVER1");
t.put(d3,"CLOVER2");

Am i right?

Ankit Garg
Sheriff
Posts: 9542
33
Yes abhi it compares d1, d2 and d3 as these are the keys i.e. the unique part in a map...

Punit Singh
Ranch Hand
Posts: 952
Yes you are right Abhi.

Abhi vijay
Ranch Hand
Posts: 509
Thanks Ankit and Punit.
I have one more doubt the implementation of HashMap and TrreMap is the same, except that in TreeMap, comparison is done by the compareTo() and in case og Hashmap it is done by hashCode() and equals(). Am I right?

Ankit Garg
Sheriff
Posts: 9542
33
If you don't go into the implementation, then you can say that this is the only difference between HashMap and TreeMap...

Ruben Soto
Ranch Hand
Posts: 1032
I was unaware of this. I also thought that hashCode() and equals() were being used for a TreeMap. Thank you for explaining that, Ankit!