File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes TreeMap containsKey issue Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "TreeMap containsKey issue" Watch "TreeMap containsKey issue" New topic
Author

TreeMap containsKey issue

Doug Morand
Greenhorn

Joined: Jan 31, 2012
Posts: 19
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.



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
Greenhorn

Joined: Dec 16, 2011
Posts: 16
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
Greenhorn

Joined: Jan 31, 2012
Posts: 19
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
Bartender

Joined: Oct 14, 2005
Posts: 18570
    
    8

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

Joined: Jan 31, 2012
Posts: 19
Yeah I put a breakpoint on the compare method and I can see it being called when containsKey(Oject) is being called
Doug Morand
Greenhorn

Joined: Jan 31, 2012
Posts: 19
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
Bartender

Joined: Oct 14, 2005
Posts: 18570
    
    8

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
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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
Greenhorn

Joined: Dec 16, 2011
Posts: 16
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
Greenhorn

Joined: Jan 31, 2012
Posts: 19
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
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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
Greenhorn

Joined: Jan 31, 2012
Posts: 19
Alright here is an updated class I'm using to test now:



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
Greenhorn

Joined: Jan 31, 2012
Posts: 19
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
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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
Greenhorn

Joined: Jan 31, 2012
Posts: 19
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
Greenhorn

Joined: Jan 31, 2012
Posts: 19
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
Rancher

Joined: Aug 11, 2007
Posts: 4655
    
    5

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
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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
Greenhorn

Joined: Jan 31, 2012
Posts: 19
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
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

You're welcome!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: TreeMap containsKey issue