TreeMap containsKey issue

[Doug Morand]

I'm trying to test out the containsKey() function of the TreeMap class, but I'm getting some strange results when calling that method. When I call the containsKey() method, it's returning false when I'm expecting it to be true

Below is a test class I wrote to try this out.

public class TreeMapTesting {

	class TestClass{
		private long id;
		private String name;

		TestClass(long id){
			this.id=id;
			this.name = "";
		}
		
		TestClass(long id,String name){
			this.id = id;
			this.name = name;
		}
		
		public String getName(){
			return this.name;
		}
       
        @Override
        public String toString(){
        	return "id: " + id 
        	+ ",name: " + name;
        }

	}
	
	//Sort by the name ascending
	Comparator lastNameAscendingSortComparator = new Comparator(){
		public int compare(Object pers1,Object pers2){
			TestClass tc1 = ((TestClass) pers1);
			TestClass tc2 = ((TestClass) pers2);
			String pers1LN = tc1.getName();
			String pers2LN = tc2.getName();

			if(pers1LN == null) pers1LN = "";
			if(pers2LN == null) pers2LN = "";
			
			//System.out.println("Comparing " + pers1LN + " and " + pers2LN);
			if(tc1.id == tc2.id) return 0;
			
			return pers1LN.compareTo(pers2LN);
		}};
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeMapTesting tmt = new TreeMapTesting();
		tmt.testMap();
	}
	
	private void testMap(){
		Map<TestClass,String> testMap = new TreeMap<TestClass,String>(lastNameAscendingSortComparator);
		
		TestClass tc1 = new TestClass(1,"Test1");
		TestClass tc2 = new TestClass(1,"Test2");
		TestClass tc3 = new TestClass(2,"Test2");
		
		testMap.put(tc1, "One");
		testMap.put(tc2, "Two");
		testMap.put(tc3, "Three");
	
		Set<TestClass> testMapKeys = testMap.keySet();
		System.out.println("Entries: " + testMap.size());
		for(TestClass tc : testMapKeys){
			System.out.println("Name: " + tc.getName() + ", id=" + tc.id
					+ ", Entries: " + testMap.get(tc));
		}
		
		TestClass tcTest = new TestClass(2);
		if(testMap.containsKey(tcTest)){
			System.out.println("Yes");
		} else{
			System.out.println("No");
		}
	}

}

Here is the output I'm getting"

Entries: 2
Name: Test1, id=1, Entries: Two
Name: Test2, id=2, Entries: Three
No

I was expecting it to be this:
Entries: 2
Name: Test1, id=1, Entries: One
Name: Test2, id=2, Entries: Three
Yes

Why isn't the containsKey() method returning true? My comparator is comparing the id which 2 is a valid Id so it should be returning true.

Also, why is the value in the map for id 1 being updated to "Two"? I thought it would check the comparator and see that the id of 1 already exists and return 0 therefore not adding tc2 to the Map

What am I missing here?

[Mori Gad]

You seem want it to find the Objects based on object id for your test, but in the comparator you return comparisons based on the name.

Remember, treemap is a tree, so it will search through it that way.

[Doug Morand]

I want the Comparator to order the list by the name, but I don't want items placed in the map if the id is the same. Does that mean my Comparator is built wrong?

[Paul Clapham]

And have you done any debugging to see if your comparator is actually being called when you try the "containsKey" method?

[Doug Morand]

Yeah I put a breakpoint on the compare method and I can see it being called when containsKey(Oject) is being called

[Doug Morand]

I guess i'm confused then because I have to have my compare method make sure to not insert a new entry in the map if the ID is the same, but then I need it to sort the map keys based on name. Is this possible?

[Paul Clapham]

And you can see it returning zero?

Assuming your answer is yes, I'm going to suggest that you should override the equals() method of TestClass to return true if the two TestClass objects are "equal", following the same rules you put into your comparator.

[Jeff Verdegan]

Paul Clapham wrote:And you can see it returning zero?

Assuming your answer is yes, I'm going to suggest that you should override the equals() method of TestClass to return true if the two TestClass objects are "equal", following the same rules you put into your comparator.

If I'm not mistaken, TreeMap's docs even have some comments about the consistency of compare(To)() and equals().

[Mori Gad]

The trouble in containsKey is that it uses the ordering of the tree, and the id is not necessarily on the ordering.

In this case, you have it ordered with "Test1" id1 as the root and "Test2" id2 as the greater than. "" id2 is tested as a contains, it goes to root, id is not the same, "" is less than "Test1" therefore go to the less than side of the tree where it terminates and returns false.

[Doug Morand]

Seems that the TreeMap is a bit tricky to implement. Seems like it might just be easier to use a HashMap and then a Comparator to sort it after the fact. Is this how it's done normally?

[Jeff Verdegan]

Doug Morand wrote:Seems that the TreeMap is a bit tricky to implement.

I doubt you're implementing TreeMap. More likely you're using it. And it's not hard to use at all. But you have to use it consistently. For instance, checking for something being contained should be consistent with it being equal to something else in your tree as per the comparator.

[Doug Morand]

Alright here is an updated class I'm using to test now:

public class TreeMapTestingv2{

	class TestClass implements Comparable{
		private long id;
		private String name;

		TestClass(long id){
			this.id=id;
			this.name = "";
		}
		
		TestClass(long id,String name){
			this.id = id;
			this.name = name;
		}
		
		public String getName(){
			return this.name;
		}
		
		@Override
        public boolean equals(Object o) {
            System.out.println("Overridding equals"); //NOT BEING CALLED
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            TestClass p = (TestClass) o;
            if (this.id != p.id) return false;
            
            return true;
        }

        @Override
        public int hashCode() {
        	System.out.println("Overridding hashCode"); //NOT BEING CALLED
            return (int) id;
        }
        
        @Override
        public String toString(){
        	return "id: " + id 
        	+ ",name: " + name;
        }

		@Override
		public int compareTo(Object o) {
			// TODO Auto-generated method stub
			TestClass tc1 = ((TestClass) o);
			int returnValue;
			if(tc1.id == this.id){
				return 0;
			} else{
				return Long.valueOf(tc1.id).compareTo(this.id);
			}
		}

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeMapTestingv2 tmt = new TreeMapTestingv2();
		tmt.testTwo();
	}

	private void testTwo(){
		Map<TestClass,String> map = new TreeMap<TestClass,String>();
		map.put(new TestClass(1,"One"), "Test1");
		map.put(new TestClass(2,"Eleven"), "Test2");
		map.put(new TestClass(4,"Three"), "Test3");
		
		Set<TestClass> testMapKeys = map.keySet();
		System.out.println("Entries: " + map.size());
		for(TestClass tc : testMapKeys){
			System.out.println("Name: " + tc.getName() + ", id=" + tc.id
					+ ", Entries: " + map.get(tc));
		}
		
		System.out.println("Map contains 1: " + map.containsKey(new TestClass(1,"")));
		System.out.println("Map contains 2: " + map.containsKey(new TestClass(2,"T")));
		System.out.println("Map contains 4: " + map.containsKey(new TestClass(4)));
	}
}

Output:

Entries: 3
Name: Three, id=4, Entries: Test3
Name: Eleven, id=2, Entries: Test2
Name: One, id=1, Entries: Test1
Map contains 1: true
Map contains 2: true
Map contains 4: true

The output looks good, other than the sorting which is now not working

Expected:

Entries: 3
Name: Eleven, id=2, Entries: Test2
Name: One, id=1, Entries: Test1
Name: Three, id=4, Entries: Test3
Map contains 1: true
Map contains 2: true
Map contains 4: true

[Doug Morand]

Jeff Verdegan wrote:

Doug Morand wrote:Seems that the TreeMap is a bit tricky to implement.

I doubt you're implementing TreeMap. More likely you're using it. And it's not hard to use at all. But you have to use it consistently. For instance, checking for something being contained should be consistent with it being equal to something else in your tree as per the comparator.

The new class I just posted now has the compareTo and the equals being consistent, but now everything is based off the ID. I was under the impression that I would use the Comparator to sort the list properly, but now I'm seeing that it's being used to determine if the key is contained within the Set

[Jeff Verdegan]

It seems to me you're using two mutually incompatible approaches to finding objects in this data structure. So, depending on your specific use cases and usage profiles, you probably want either two separate data structures (which may or may not be kept in sync automatically by some wrapping class) or two different Comparators (or one Comparator and a natural sorting order).

[Jeff Verdegan]

Doug Morand wrote:I was under the impression that I would use the Comparator to sort the list properly, but now I'm seeing that it's being used to determine if the key is contained within the Set

It's used for both. Sorting includes testing for equality, and your Comparator defines the conditions under which two nodes are equal. Searching for the key being present is a test for equality. You're saying that for sorting you want one definition of equality, and for searching you want a different definition of equality.

[Doug Morand]

Thanks that makes sense.

Seems that in this case where I don't want duplicate IDs inserted, but then also sort by the Name then I should just use a HashMap and then pass the keySet to a TreeSet with a name comparator

[Doug Morand]

Does someone have an example of how to use a TreeMap to not insert duplicates, but sort on a different value from the key?

[Pat Farrell]

I can't see why you would expect the TreeMap (or TreeSet) to sort on another Comparitor than the key.

If you want to do a sort, just use the Collections.sort() that takes a Comparitor, and pass in another Comparitor that does it the second way. You may have to copy the values of the of Tree and into a normal List, but that's cheap most of the time.

[Jeff Verdegan]

Doug Morand wrote:Does someone have an example of how to use a TreeMap to not insert duplicates, but sort on a different value from the key?

I thought it was clear by now that that's not really possible. "Duplicate" is by definition of TreeMap, "equal according to my sorting rules." It says so right in the java.util.TreeMap docs:

...a map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal.

[Doug Morand]

Thanks for the info. I was just confused on how the TreeMap worked. I'm going to just use a HashMap instead, and just sort the keys once I'm ready to access it. Thanks!

[Jeff Verdegan]

You're welcome!