CODEWITHSUNDEEP
javaalgorithmbinary-search-treetreemap
Nitin Singhal
Nitin Singhal

Reputation: 223

How treemap handles case of putting key on same index?

I tried out following code:

public static void main (String[] args) throws java.lang.Exception
{
   // sorting based on number of dots
    Map<String, String> map =new TreeMap<>((o1, o2) -> {
        int noOfDots1 = o1.length() - o1.replaceAll("\\.", "").length() ;
        int noOfDots2 = o2.length() - o2.replaceAll("\\.", "").length() ;
        return noOfDots1 - noOfDots2;
    });
    map.put("ty.r.r.r", "a");
    map.put("t.i.o", "b");
    map.put("i.o.y.y", "c");
    map.put("p.u.r.w.e", "d");
    map.put("j.k.i", "e");
    System.out.println(map);
}

But output is coming as :

{t.i.o=e, ty.r.r.r=c, p.u.r.w.e=d}

Why we are not getting all the five keys in output?

EDIT :

Thank you all, I understood why I'm not getting all 5 keys in output, but I just wondering what would be best way to get all keys in sorted order of dots.

One idea, came to my mind is extract all keys, store them in list and sort that list based on no of dots, then use the same list to reorder the map? Any better ways

Upvotes: 1

Views: 64

Answers (3)

rzwitserloot
rzwitserloot

Reputation: 103283

.replace(".", "") is strictly superior (replace also replaces all occurrences; it is simply not also using regular expressions. You should fix this part of your code).

The easy solution is to have a secondary sorting order. How should t.i.o and j.k.y sort relatively to each other? For example, if you want alphabetical:

Comparator<String> a = (o1, o2) -> 
  o1.length() - o1.replace(".", "").length() -
  (o2.length() - o2.replace(".", "").length());

Comparator<String> b = Comparator.naturalOrder();

var map = new TreeMap<String, String>(a.thenComparing(b));

Note the use of 'thenComparing' to establish a secondary sorting order, to be used when the first would otherwise result in equality.

Upvotes: 0

Jeroen Steenbeeke
Jeroen Steenbeeke

Reputation: 4048

The put method in TreeMap uses the comparator you specified to check for equality. If your comparator returns 0 on two keys, it considers them identical.

For your data, this means that all Strings with an equal number of dots are considered identical keys.

Relevant source: https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/TreeMap.java#L795

Upvotes: 0

Saurav Sahu
Saurav Sahu

Reputation: 13974

Because numbers of dots in the keys are :

3
2
3
4
2

Unique counts are : 2, 3 and 4

Upvotes: 3

Related Questions