Java TreeSet Comparator — How It Silently Drops Duplicates

Every non-trivial Java application eventually needs sorted data — a leaderboard ranked by score, a task scheduler ordered by deadline, a word-frequency map listed alphabetically. You could dump everything into an ArrayList and call Collections.sort() every time, but that's like re-alphabetising your entire library every time a new book arrives. Java's TreeMap and TreeSet solve this permanently by keeping data sorted at all times, automatically, on every insert and delete.

The problem with HashMap and HashSet is that they trade order for raw speed. That's a great deal when you only need to answer 'does this key exist?' or 'give me this value'. But the moment a user asks 'show me the top 10 scores' or 'find everything between Tuesday and Friday', a HashMap forces you to scan the entire structure. A TreeMap answers those range and boundary questions in O(log n) time because it's backed by a Red-Black Tree — a self-balancing binary search tree that keeps everything sorted without you lifting a finger.

By the end of this article you'll know exactly when to reach for a TreeMap versus a HashMap, how to exploit the NavigableMap and NavigableSet APIs to slice your data in powerful ways, and which subtle mistakes cause ClassCastExceptions and incorrect ordering in production. You'll also have concrete, real-world patterns you can copy directly into your own codebase.

TreeSet — When Order Is Non-Negotiable

A TreeSet is a Set — so it never stores duplicates — but unlike HashSet it keeps every element in its natural sorted order at all times. 'Natural order' means whatever Comparable defines for that type: alphabetical for Strings, ascending for numbers, chronological for dates.

The real payoff isn't just iteration order. It's the NavigableSet API: methods like first(), last(), floor(), ceiling(), headSet(), and tailSet() let you slice and query your sorted data without loops. Want every username that comes after 'mike' alphabetically? One line. Want the five closest scores below a threshold? One line.

Internally, TreeSet wraps a TreeMap and stores your elements as keys. Every add(), remove(), and contains() runs in O(log n) — slower than HashSet's O(1) average, but a fair trade when you genuinely need sorted access. Don't use TreeSet by default; use it when the ordering itself is part of the feature you're building.

package io.thecodeforge.collections;

import java.util.TreeSet;
import java.util.NavigableSet;

public class LeaderboardTreeSet {
    public static void main(String[] args) {
        // io.thecodeforge: Scores are kept sorted (ascending) automatically
        TreeSet<Integer> scores = new TreeSet<>();

        scores.add(4200);
        scores.add(1500);
        scores.add(8750);
        scores.add(3300);
        scores.add(9100);
        scores.add(4200); // duplicate — silently ignored

        System.out.println("All scores (always sorted): " + scores);

        // Lowest and highest score in O(log n)
        System.out.println("Lowest score : " + scores.first());
        System.out.println("Highest score: " + scores.last());

        // floor() returns the greatest element <= 4000
        System.out.println("Highest score at or below 4000: " + scores.floor(4000));

        // subSet with booleans for inclusivity
        NavigableSet<Integer> mainBracket = scores.subSet(3000, true, 9000, false);
        System.out.println("Main bracket [3000, 9000): " + mainBracket);
    }
}

TreeMap — Sorted Keys With All the Power of a Map

TreeMap is to HashMap what TreeSet is to HashSet: it keeps all its keys in sorted order at all times, and it exposes a rich NavigableMap API for range queries, boundary lookups, and sliced views.

The classic use case is any kind of timeline, schedule, or rank-ordered dataset. Imagine you're building a task scheduler. Each task has a deadline (the key) and a description (the value). A TreeMap lets you instantly find the next task due, all tasks due before a certain date, or every task in a given window — without scanning the entire map.

TreeMap also implements SortedMap and NavigableMap, which means you get firstKey(), lastKey(), floorKey(), ceilingKey(), lowerKey(), higherKey(), headMap(), tailMap(), and subMap() — all backed by the same O(log n) Red-Black Tree. You can even get a descending view of the entire map with descendingMap(). These aren't convenience extras; they're the whole reason to choose TreeMap over HashMap.

package io.thecodeforge.collections;

import java.time.LocalDate;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

public class TaskSchedulerTreeMap {
    public static void main(String[] args) {
        // io.thecodeforge: Standardizing chronologically sorted task maps
        TreeMap<LocalDate, String> schedule = new TreeMap<>();

        schedule.put(LocalDate.of(2025, 7, 15), "Submit tax return");
        schedule.put(LocalDate.of(2025, 6, 30), "Renew software licences");
        schedule.put(LocalDate.of(2025, 8, 1),  "Team performance reviews");
        schedule.put(LocalDate.of(2025, 7, 4),  "Deploy v2.0 to production");

        LocalDate today = LocalDate.of(2025, 7, 1);

        // ceilingKey returns the smallest key >= today
        LocalDate nextDeadline = schedule.ceilingKey(today);
        System.out.println("Next task: " + nextDeadline + " - " + schedule.get(nextDeadline));

        // headMap(key, inclusive) provides an efficient view of past entries
        NavigableMap<LocalDate, String> overdue = schedule.headMap(today, false);
        System.out.println("Overdue count: " + overdue.size());
    }
}

NavigableMap and NavigableSet — The Real Reason to Choose Tree

The true power of TreeMap and TreeSet lies in their Navigable interfaces — not just sorted iteration, but the ability to slice, dice, and query your data in logarithmic time. These methods don't copy data; they return live views that reflect ongoing mutations.

• floorKey(k) / ceilingKey(k): Find the nearest key less than/equal or greater than/equal to a target.
• lowerKey(k) / higherKey(k): Strict versions of above (exclusive).
• headMap(k, inclusive): All keys less than (or ≤) k.
• tailMap(k, inclusive): All keys greater than (or ≥) k.
• subMap(from, fromInclusive, to, toInclusive): A contiguous slice.
• descendingMap() / descendingSet(): Reverse-order views without sorting copy.
• pollFirstEntry() / pollLastEntry(): Retrieve and remove boundary entries.

Use these when you need to answer 'what's the next available slot?', 'find all orders within a date range', or 'get the top 5 scores' without ever calling sort().

package io.thecodeforge.collections;

import java.util.NavigableMap;
import java.util.TreeMap;

public class NavigableApiDemo {
    public static void main(String[] args) {
        // io.thecodeforge: Using NavigableMap for real-time slicing
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "ten");
        map.put(20, "twenty");
        map.put(30, "thirty");
        map.put(40, "forty");
        map.put(50, "fifty");

        // Closest key >= 25
        System.out.println("Ceiling of 25: " + map.ceilingKey(25)); // 30

        // Closest key < 30
        System.out.println("Lower of 30: " + map.lowerKey(30)); // 20

        // Entries between 20 (inclusive) and 40 (exclusive)
        NavigableMap<Integer, String> slice = map.subMap(20, true, 40, false);
        System.out.println("Submap [20,40): " + slice);

        // Reverse order view
        System.out.println("Descending: " + map.descendingMap());
    }
}

Custom Ordering With Comparator — When Natural Order Isn't Enough

Natural order works great for Strings and numbers, but what about your own objects? And what if you want reverse order, or a case-insensitive sort? That's where a Comparator comes in.

Both TreeMap and TreeSet accept a Comparator in their constructor. Once you supply one, it completely overrides natural order — even if your objects implement Comparable. This is powerful, but there's a critical rule: the Comparator you use for ordering becomes the equality definition for the collection. Two elements are considered duplicates if comparator.compare(a, b) == 0, not if a.equals(b). This surprises many developers.

A practical pattern: pass Comparator.reverseOrder() to get a descending TreeMap, which is perfect for leaderboards where you want the highest value first. Or pass String.CASE_INSENSITIVE_ORDER to a TreeSet of strings so 'Apple' and 'apple' are treated as the same entry. The Comparator is your formatting rule for the entire collection.

package io.thecodeforge.collections;

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

public class CustomComparatorDemo {
    record Product(String name, double price) {}

    public static void main(String[] args) {
        // io.thecodeforge: Custom Comparator for secondary sorting
        Comparator<Product> byPriceThenName = Comparator
                .comparingDouble(Product::price)
                .thenComparing(Product::name);

        TreeMap<Product, Integer> inventory = new TreeMap<>(byPriceThenName);
        inventory.put(new Product("Mechanical Keyboard", 120.00), 15);
        inventory.put(new Product("Wireless Mouse", 45.00), 22);
        inventory.put(new Product("USB-C Cable", 15.00), 100);

        inventory.forEach((p, qty) -> System.out.println(p.name() + ": $" + p.price()));
    }
}

TreeMap vs HashMap vs TreeSet vs HashSet — Choosing the Right Tool

The most common mistake is defaulting to HashMap or HashSet out of habit and then discovering you need sorted access later — at which point you're either converting structures or adding sort calls everywhere. Choosing right from the start costs nothing.

The decision is straightforward: if you need to ask range questions ('everything between X and Y'), boundary questions ('what's the closest element to Z?'), or if iteration order must be predictable and sorted, use the Tree variant. If you only ever ask point questions ('does this key exist?', 'give me this value') and don't care about order, stick with the Hash variant for its faster O(1) average operations.

LinkedHashMap and LinkedHashSet are the middle ground — they maintain insertion order but don't sort. Use them when you want predictable iteration without the overhead of sorting. The table below captures the key trade-offs so you can settle this question in seconds during a code review.

package io.thecodeforge.collections;

import java.util.*;

public class ChoosingTheRightCollection {
    public static void main(String[] args) {
        List<String> rawData = List.of("cherry", "apple", "banana");

        // O(1) speed, random order
        Set<String> unordered = new HashSet<>(rawData);
        
        // O(1) speed, maintains "cherry", "apple", "banana" order
        Set<String> insertionOrdered = new LinkedHashSet<>(rawData);

        // O(log n) speed, maintains "apple", "banana", "cherry" order
        Set<String> sorted = new TreeSet<>(rawData);

        System.out.println("TreeSet Order: " + sorted);
    }
}

TreeMap vs HashMap — Detailed Comparison

While both implement Map, TreeMap and HashMap serve fundamentally different purposes. The table below highlights the key differences you need to consider when choosing.

This table is a quick reference for code reviews and design decisions. When in doubt, ask: "Do I need to answer 'what's between X and Y'?" If yes, TreeMap is the answer.

TreeSet vs HashSet — Detailed Comparison

The same trade-offs apply to the Set variants. Here's a direct comparison.

Like the Map counterparts, the decision hinges on whether you ever need ordered iteration or range queries. If you only need uniqueness and fast membership tests, HashSet is the better choice.

Advantages and Disadvantages of TreeMap and TreeSet

Both TreeMap and TreeSet share the same underlying data structure (Red-Black Tree), so their strengths and weaknesses are nearly identical.

Advantages

Disadvantages

These trade-offs are fundamental to the data structure. Use the advantages when you need sorted ordering; avoid the disadvantages by carefully designing keys and comparators.

Advanced NavigableMap Operations: descendingMap, pollFirstEntry, pollLastEntry

Beyond the basic floor/ceiling and sub-range views, NavigableMap offers three powerful methods for boundary manipulation: descendingMap(), pollFirstEntry(), and pollLastEntry(). These are especially useful for leaderboards, job queues, and any scenario where you need to process items in order while mutating the collection.

• descendingMap(): Returns a reverse-order view of the map. No new data is created; iteration over the descending map is just as fast and memory-cheap as iterating forward. Combined with subMap(), you can easily get slices in descending order.
• pollFirstEntry(): Retrieves and removes the entry with the smallest key. This is a single O(log n) operation that both reads and deletes the first entry. Equivalent to firstEntry() + remove(firstKey()) but atomic and more efficient.
• pollLastEntry(): Retrieves and removes the entry with the largest key. Same benefits as pollFirstEntry for the other end.

These methods are commonly used in priority queues where you want to serve items in order while draining the structure. They are also great for implementing round-robin or timeout processing without additional locking or iteration.

package io.thecodeforge.collections;

import java.util.TreeMap;
import java.util.NavigableMap;

public class AdvancedNavigableMap {
    public static void main(String[] args) {
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 2500);
        scores.put("Bob", 1800);
        scores.put("Charlie", 3200);
        scores.put("Diana", 1500);
        scores.put("Eve", 2900);

        // Descending order view
        NavigableMap<String, Integer> descending = scores.descendingMap();
        System.out.println("Descending order: " + descending);
        // Output: Descending order: {Eve=2900, Charlie=3200, Alice=2500, Bob=1800, Diana=1500}

        // Poll first (lowest) entry
        System.out.println("Poll first (lowest score): " + scores.pollFirstEntry());
        // Output: Poll first (lowest score): Diana=1500
        System.out.println("After pollFirstEntry: " + scores);
        // Output: After pollFirstEntry: {Alice=2500, Bob=1800, Charlie=3200, Eve=2900}

        // Poll last (highest) entry
        System.out.println("Poll last (highest score): " + scores.pollLastEntry());
        // Output: Poll last (highest score): Eve=2900
        System.out.println("After pollLastEntry: " + scores);
        // Output: After pollLastEntry: {Alice=2500, Bob=1800, Charlie=3200}
    }
}

Practice Problems: Interval Scheduling, Range Queries, Sliding Window

The best way to internalize the power of TreeMap and TreeSet is to solve problems that naturally require sorted order and range queries. Below are five practice problems you can implement to sharpen your skills.

1. Interval Scheduling with TreeSet Given a list of intervals (start, end), find the maximum number of non-overlapping intervals you can schedule. Use a TreeSet to store intervals sorted by end time. Iterate through sorted intervals, and when you find one that doesn't overlap with the last scheduled, add it. Demonstrates floor() or last() for boundary checks.

2. Range Sum Queries on a Dynamic Array Maintain a TreeMap of cumulative sums or directly a TreeMap<Integer, Integer> where keys are indices. Support operations: add value at index, query sum between indices. Use subMap() to get entries in the range and compute the sum. Simulates a Fenwick tree without the complexity.

3. Sliding Window Median Given a stream of integers and a window size k, find the median of each window. Use two TreeSets (or one TreeSet with order statistics) to maintain left and right halves. Use last() and first() to get the max of left and min of right. Demonstrates maintaining balance and using boundary methods.

4. Nearest Neighbor in 1D Given a set of points on a line (integers), support insert(x) and query(x) that returns the closest point to x. Use TreeSet and its floor() and ceiling() methods. Compare distances to find nearest. Classic example of why NavigableSet exists.

5. Task Scheduler with Deadline Constraints Given tasks with deadlines and durations, find if all tasks can be scheduled. Use a TreeMap to store tasks sorted by deadline. Iterate from earliest deadline, subtract duration from current time, and if you ever go negative, impossible. Uses firstKey() and pollFirstEntry() efficiently.

Each problem can be solved in < 50 lines of Java using TreeMap/TreeSet. Implement them to gain confidence with the APIs discussed in this article.