Using Comparators with TreeMap

A TreeMap or TreeSet tests keys for equality using a Comparator object or a compareTo method, and never uses the equals() method for this purpose.

Programming

A Word Index with Two Spellings

Imagine you are building a word index for a document. Each time a word appears, you want to record the page on which it occurs. A TreeMap is a natural choice for this job, because it keeps its entries in sorted order and lets you look up each term quickly. The trouble starts when two different spellings seem to refer to the same word. Suppose the program records the term 'aardvark' on one page and later meets the term 'Aardvark' with a capital letter. Should the TreeMap store these as two separate terms, or as one?

Many programmers answer this question by reaching for the method they already associate with sameness in Java: equals(). That instinct is understandable, but it points toward the wrong mechanism for this collection. This article explains why the instinct misleads you, and what a TreeMap actually consults when it decides that two keys are the same.

Predicting the Index Result

What do you think happens?

The index program stores 'aardvark' with one page number, then stores 'Aardvark' with another page number. Does the TreeMap end up with one entry or two?

One entry, with both page references merged
Two entries, one for each spelling

Reveal answer

Answer:

One entry, with both page references merged

The Comparator returns zero for the two strings, so the TreeMap treats them as the same key and combines their associated values. Commit to your answer before reading the explanation that follows.

The Belief About equals()

The misconception this article targets is the belief that a TreeMap tests its keys for equality by calling the equals() method on them. It is easy to hold this belief because equals() is the usual way Java code asks whether two objects are equivalent. Within a TreeMap, however, that assumption does not hold.

What Sameness Means Inside a TreeMap

Definition

A Comparator object is an object whose job is to compare two items and report the result. In a TreeMap, equality is defined by ordering: two keys are considered the same when the comparison used for ordering reports that they are equal, which the source describes as returning the value zero.

The source states the rule directly: TreeMaps and TreeSets always use a Comparator object or a compareTo method to test for equality, and they do not use the equals() method for this purpose. The Comparator is the object that determines equality for the map. When it looks at 'aardvark' and 'Aardvark' under a case-insensitive rule, it returns zero, which signals that the two strings are equal for the purposes of this comparison. The TreeMap accepts that signal and therefore treats the two strings as one key.

Equals Versus Comparator Sameness

Placing the two mechanisms side by side makes the difference easier to remember. Both are ways of deciding whether two objects should be treated as one, but they are driven by different methods, and they can disagree about the same pair of strings. The equals() method does not appear anywhere in the chain that a TreeMap follows when it decides that two keys match.

Why does the map treat two keys as identical when the Comparator returns 0, even though equals() returns false for them?

Tracing a Put with an Equivalent Key

Now trace what happens when a key arrives that the Comparator considers equivalent to a key already stored. Suppose the map holds 'apple' with a value v1, and the program then calls put with 'Apple' and a value v2. The TreeMap compares the new key against stored keys using the Comparator. Because the Comparator returns zero, the TreeMap finds the existing entry rather than creating a new one.

After put('Apple', v2) on a map that already holds 'apple' with v1, what are the stored key and value now?

The stored key stays as the original spelling, 'apple', and only the value changes to v2. The map still holds one entry. This follows from the rule that the TreeMap treats the two keys as the same key, so the new key does not take the place of the old one.

A Case-Insensitive Comparator in Code

The following sketch builds a TreeMap whose Comparator ignores capitalization. The comparison String.CASE_INSENSITIVE_ORDER is a standard Java Comparator, so the map uses it instead of equals() to decide sameness. The code is an illustrative example written for this lesson, not a listing from the source.

Code walkthrough

Map<String, Integer> index = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
index.put("aardvark", 3);
index.put("Aardvark", 7);
System.out.println(index.size());
System.out.println(index.keySet());

1
Create a TreeMap that uses a case-insensitive Comparator to order and identify keys.
2
Store 'aardvark' with the value 3. The map now has one entry.
3
Store 'Aardvark' with the value 7. The Comparator reports zero, so the map treats this as the same key and replaces the value.
4
The size is 1, and the printed key is the original spelling, 'aardvark'.

The Comparator is passed to the TreeMap constructor, so it governs ordering and equality.
The second put finds the existing entry because the Comparator returns zero for the two spellings.
The stored key is the first spelling encountered, and the value becomes 7.

Output

1
[aardvark]

Judging the Consequences of Merging

The behavior in the worked example is a direct consequence of the Comparator's rule, and the source notes that this is probably acceptable in that particular example. For an index whose purpose is to tell a reader which pages mention a word, folding capitalization differences into one entry is often what the reader wants. The source does not treat this as a universal answer.

Mistakes When Reasoning About Keys

Common mistake
Assuming a TreeMap calls equals() to decide whether two keys match
What it looks like
Expecting 'aardvark' and 'Aardvark' to stay separate because equals() reports them as different strings.
Why it fails
The source states that TreeMaps and TreeSets use a Comparator object or a compareTo method for equality testing and never use equals() for this purpose.
Do this instead
Ask what the Comparator returns for the two keys. A zero means the TreeMap treats them as the same key.
Common mistake
Expecting a new key to replace the stored key object
What it looks like
After put('Apple', v2) on a map holding 'apple', assuming the stored key is now 'Apple'.
Why it fails
The TreeMap treats the keys as one, so the existing entry is kept and its value is updated.
Do this instead
Expect the original key, 'apple', to remain and only the value to change to v2.
Common mistake
Forgetting that the Comparator defines the map's notion of sameness, so changing the Comparator can change how many entries the map holds

Practice: Predict the Entry Count

EASY

A TreeMap uses a case-insensitive Comparator. The program calls put with 'Zebra', then put with 'zebra', then put with 'ZEBRA'. How many entries does the map hold afterward, and which spelling does the key keep? Explain your answer by naming the method that decides sameness.

Hints

Ask what the Comparator returns when it compares each new key with the stored key.
Remember that equals() plays no part in deciding sameness inside a TreeMap.

Your attempt (not saved)

Key Takeaways

A TreeMap or TreeSet decides whether two keys are the same using a Comparator object or a compareTo method, never equals().
When the Comparator returns zero for two keys, the TreeMap treats them as one key and combines their associated values.
A case-insensitive Comparator makes 'aardvark' and 'Aardvark' one entry, and the first spelling encountered is the one kept.
Whether this merging is acceptable depends on the application; if it is not, a different technique is needed to sort terms alphabetically.