• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

TreeMap containsKey issue

 
Doug Morand
Greenhorn
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 16
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 20203
26
MySQL Database
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And have you done any debugging to see if your comparator is actually being called when you try the "containsKey" method?
 
Doug Morand
Greenhorn
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 20203
26
MySQL Database
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 16
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4660
5
Linux Mac OS X VI Editor
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 19
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome!
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic