LinkedList and TreeMap: compareTo or equals?

Question

I need a clarification regarding the use of TreeMap and LinkedList. Do these two structures use compareTo or equals?

In particular, TreeMap keeps the order in the keys, I suppose using the compareTo method of the class defined for the keys. However, when using get, do they use compareTo or equals to see if the key you pass is contained?

I have the same doubt for contains and getIndex inside LinkedList.

Answer 1

TreeMap uses compareTo, and the documentation warns you of problems if compareTo is not consistent with equals (i.e. that a.compareTo(b) == 0 <=> a.equals(b) should be true).

Note that the ordering maintained by a tree map ... must be consistent with equals if this sorted map is to correctly implement the Map interface.

LinkedList uses equals.

---

The reason why TreeMap has to use an ordering consistent with equals is that the contract of Map defines the behavior in terms of equals. For example, containsKey is defined as:

returns true if and only if this map contains a mapping for a key k such that (key==null ? k==null : key.equals(k))

Let's say you define a class like this:

class Bad implements Comparable<Bad> {
  @Override public int compareTo(Bad other) { return 0; }
}

If you were to write:

Bad b1 = new Bad();
Bad b2 = new Bad();

Then:

Map<Bad, String> hm = new HashMap<>();
hm.put(b1, "");
System.out.println(hm.containsKey(b2));  // false

whereas

Map<Bad, String> tm = new TreeMap<>();
tm.put(b1, "");
System.out.println(tm.containsKey(b2));  // true

despite the fact that

System.out.println(tm.keySet().stream().anyMatch(k -> k.equals(b2))); // false

Thus, TreeMap violates the contract of Map, because Bad does not implement Comparable consistently with equals.