Missing Key value pair in Tree Map

Question

I'm trying to solve a programming problem using TreeMap, which led me to post this question.

I have a defined a treeMap with (Int,Int) as my key and String as the value, defined the treeMap ordering on the basis of the first element of the tuple. and I have inserted two elements different Key, but the final treeMap contains only one element.Is this the defined behaviour of treeMap

Scala Code: (Version: 2.12.3)

val a = scala.collection.mutable.TreeMap[(Int, Int), String]()(Ordering.by(x => x._1))
a.put((9, 21), "value-1")
a.put((9, 10), "value-2")
println(a.size) // 1

I have tried the Same implementation in java, but it reports the Map Size as 2 here is my java code:

Can Some one suggest if i'm missing some thing

import java.util.Comparator;
import java.util.TreeMap;

public class JavaTreeMapTest {

    public static void main(String[] args) {

        class Tuple {
            Integer a;
            Integer b;

            public Tuple(Integer a, Integer b) {
                this.a = a;
                this.b = b;
            }

        }
        Comparator<Tuple> testComparator = new Comparator<Tuple>() {

            @Override
            public int compare(Tuple arg0, Tuple arg1) {
                if (arg0.a > arg1.a) {
                    return arg0.a;
                } else
                    return arg1.a;
            }

        };

        TreeMap<Tuple, String> tm = new TreeMap<Tuple, String>(testComparator);
        tm.put(new Tuple(100, 100), "value-1");
        tm.put(new Tuple(100, 101), "value-2");

        System.out.println(tm.size()); //2

    }
}

Answer 1

The problem is with your ordering. If you use it like this: Ordering.by(x => x._1), TreeMap will consider only first element for calculating equality. So, both (9, 21) and (9, 21) would be considered equal.

One solution would be to order first by first element and then by second. You can do this by returning a tuple: Ordering.by(x => (x._1, x._2)).

But since you're already using tuples, you can simplify it to:

Ordering.by(x => x)

or

Ordering.by(identity)

or

You can omit it because ordering by identity is a default.

To wrap up:

val a = scala.collection.mutable.TreeMap[(Int, Int), String]()
a.put((9, 21), "value-1")
a.put((9, 10), "value-2")
println(a.size) // 2

Answer 2

To give a precise answer, I would say that, unlike Java's TreeMap, scala.collection.mutable.TreeMap uses the provided Ordering to determine equality rather than using ==. This has some other interesting consequences. Using the a from your question:

a.contains((9, 0)) // true
a((9, -1000)) // "value-2"

Indeed, Ordering has a method equiv for determining whether two things are equal in an ordering. While this method is not used in the TreeMap implementation, it shows the philosophy of relying on the Ordering as the source of truth rather than the less flexible ==.