Comparators and Sorting Keys

A TreeMap stores associations in a sorted tree, so its keys must be comparable, either through the Comparable interface or through a Comparator passed to the constructor

Programming

Two Maps That Look Alike

Java provides more than one class that implements the Map interface, so a program that needs key/value associations has to pick one. Two of these classes, TreeMap and HashMap, look almost the same from the outside. You create one, store associations in it, and look values up by key. Because their public use looks so similar, it is easy to assume that the two classes also agree on what makes two keys equal, what kinds of keys they accept, and what order they keep their entries in. They do not agree on these things, and the differences matter as soon as you use either class with your own key types.

What do you think happens?

Suppose a TreeMap's keys are ordered by a comparison method that looks only at the length of a string, so any two strings of the same length compare as equal even when their characters differ. You store a value under the key cat and then store a value under the key dog. Both keys are three letters long. Will the map hold two separate entries, or treat them as one?

Two separate entries, one for cat and one for dog
One entry, because the comparison ranks the two keys as tied

Reveal answer

Answer:

One entry, because the comparison ranks the two keys as tied

A TreeMap does not ask whether two keys are equal. It asks whether comparing them gives a result that counts as a tie. Here the length-based comparison returns a tie for cat and dog, so the TreeMap treats them as the same key. The second value is stored under the key the map already holds, rather than creating a new entry.

Keys Placed in a Sorted Tree

A TreeMap stores its key/value associations in a sorted tree, sorted according to their keys. The mental picture to build is a tree of keys in which each association sits at a place determined by its key. Each new key is placed by comparing it with keys already in the tree. That comparison is exactly where the comparison method does its work. The source does not describe the internal balancing or traversal details, so the picture here is limited to what the source states: the associations are kept in a sorted tree, ordered by their keys.

When the keys mango, apple, peach, and banana are inserted in that order, where does each one sit so that the tree stays sorted?

Read the diagram as a record of comparisons. The key mango sits at the top. Apple is compared with mango and found smaller, so it goes to the left. Peach is larger, so it goes to the right. Banana is then compared with mango, found smaller, and so it moves to the left branch. There it is compared with apple, found larger, so it sits to the right of apple. The same process places every key, which is why the associations can be described as sorted according to their keys.

Worked example

Placing banana in the tree

The tree already holds mango at the top, with apple to its left and peach to its right. Where does banana go?

1
Start at the root
Compare banana with mango, the key at the top of the tree.
2
Take the left branch
Banana is smaller than mango, so the search moves to the left, where apple is.
3
Compare with apple
Banana is larger than apple, so it goes to the right of apple.
4
Place the key
There is no further node on that branch, so banana is inserted there and the tree stays sorted.

Result

Banana sits to the right of apple, as the sorted order requires.

Where the Ordering Rule Comes From

The sorted tree only works if it is possible to compare the keys to one another. The source gives two ways to satisfy this requirement. Either the key class supplies the comparison itself, or the program supplies a separate comparison object. Each route has a different owner of the ordering rule, and that difference determines how flexible the design is.

Comparable Versus Comparator Side by Side

Question	Comparable on the key class	Comparator passed to the constructor
Where is the ordering rule defined?	Inside the key class, through compareTo()	Outside the key class, in a separate comparison object
Which method decides ordering and sameness?	compareTo()	compare()
Can the same key class be ordered differently in different maps?	Not through this route alone, because the rule travels with the key	Yes, because each map can be given its own Comparator
How is it supplied?	The key class implements Comparable	Passed as a parameter to the TreeMap constructor

Two routes to the comparison a TreeMap needs, as described in the source.

When Two Keys Count as the Same

The belief to examine is this: two keys are the same key in a map when they are equal in the usual sense, meaning that equals() reports true for them. That belief is reasonable for many maps, and it is the belief most programmers bring to a TreeMap without thinking about it. The source warns against it directly. In a TreeMap, as in a TreeSet, the compareTo() method, or the compare() method when a Comparator is supplied, is the thing used to decide whether two keys are considered the same. Equality in a TreeMap is therefore whatever the comparison method says it is, and that may or may not match equals().

The rule is the same one that places keys in order. The comparison that decides where a key goes is also the comparison that decides when two keys occupy the same position. When the comparison ranks two keys as equivalent, the TreeMap treats them as one key. The map is not broken in that case. It is following the rule it was given.

When put is called on a TreeMap, which result of the comparison makes the new key count as the same key as one already stored?

Worked example

Storing cat and then dog in a length-ordered TreeMap

The keys are ordered by a comparison that looks only at string length. What happens when cat and then dog are stored?

1
Store cat
The map has no keys yet, so cat is inserted with its value.
2
Store dog
The map compares dog with cat. Both strings have three letters, so the comparison returns a tie.
3
Apply the tie rule
A tie means the two keys count as the same key, so the map does not create a second entry.
4
Read the result
Looking up cat or dog now finds the one entry, because the two keys occupy the same position.

Result

The TreeMap holds one entry for these two keys, even though the strings differ and equals() would report false for them.

Mistakes With Key Sameness and Key Types

Common mistake
Assuming a TreeMap uses equals() to decide whether two keys are the same
What it looks like
Keys cat and dog are stored in a TreeMap ordered by string length, and the programmer expects two entries because the strings are not equal.
Why it fails
In a TreeMap the compareTo() or compare() method decides sameness, and a tie in that comparison makes the keys count as one key.
Do this instead
Check what the comparison method treats as a tie, and make sure that result matches the meaning of sameness the program needs.
Common mistake
Using a key class in a TreeMap without giving it any ordering
What it looks like
A custom key class implements neither Comparable nor a Comparator, and it is placed in a TreeMap.
Why it fails
The sorted tree needs its keys to be comparable, and a TreeMap built this way has no way to order them.
Do this instead
Either make the key class implement Comparable, or pass a Comparator to the TreeMap constructor.
Common mistake
Assuming a HashMap needs comparable keys
What it looks like
A custom key class with no ordering is used as a HashMap key, and the programmer adds Comparable just in case.
Why it fails
A HashMap stores associations in no particular order, so its keys do not need to be comparable.
Do this instead
Focus on equals() and hashCode() instead. The source says the key class should define these sensibly.
Common mistake
Mixing up the two classes because their public use looks the same

HashMap Versus TreeMap

Aspect	HashMap	TreeMap
Order of entries	No particular order	Sorted according to the keys, in a sorted tree
Requirement on keys	Should define equals() and hashCode() sensibly; no ordering needed	Must be comparable, through Comparable or a Comparator
What decides sameness	Equality and hashing defined by the key class	The compareTo() or compare() result; a tie means the same key
Speed	Most operations are a little faster	Slightly slower, because of the sorted structure
When to choose it	Default choice, and enough when only put and get are used	When there is a real need for sorted keys

Differences between the two Map classes, as stated in the source.

Comparability is not the same as having no requirements. A HashMap key class is still expected to define equality and hashing sensibly, and most of Java's standard classes define these methods correctly. For a HashMap, ordering is not part of the bargain. This is the opposite emphasis from a TreeMap, where the comparison method carries both the ordering and the sameness rule.

Choosing a Map for a Task

The source gives a clear default. In general, use a HashMap unless you have some particular need for the ordering property of a TreeMap. If you are only using the put and get operations, you can safely use a HashMap. The reason to reach for a TreeMap is a real need for sorted keys, not a general preference for tidiness.

EASY

A program stores student names as keys and test scores as values. It only needs to look up a score when a student's name is given. Which map should it use, and why? Then consider a second program that must print every student name in alphabetical order.

Hints

Ask whether the task needs the entries in sorted order, or only needs lookups by key.
If the task needs both lookup and sorted printing, consider what the TreeMap needs from its keys.

Your attempt (not saved)

MEDIUM

Suppose a TreeMap orders its keys by a comparison that looks only at the first letter of a word. Store a value under apple and then under avocado. Will the map hold one entry or two, and what rule decided your answer?