Java TreeMap Tutorial with Examples

Objects comparing in TreeMap

• Internally, TreeMap basic operations such as

  • containsKey, put, putIfAbsent, replace(key, value) and remove(key) work based on comparing key objects which ground on their Comparable or Comparator, regardless of their equals and hashCode, depending on which TreeMap constructor is used at the creation time

  • containsValue, replace(key, oldValue, newValue), remove(key, value) work based on comparing value objects which ground on their equals method implementation

  In the following example, the expected results don't happen due to the incorrectly implementation of equals on Book, compareTo on Category and Book objects

  • treeMap.containsKey(new Category(2, "c1")) and treeMap.containsValue(new Book(2, "b1")) should return false but true

  • treeMap.put(new Category(2, "c1"), new Book(2, "b1")) should success but not

  • treeMap.replace(new Category(2, "c1"), new Book(2, "b1")) and treeMap.remove(new Category(2, "c1")) should not but success

@Test
public void objectsComparingProblem(){  
    NavigableMap<Category, Book> treeMap = new TreeMap<>();

    treeMap.put(new Category(1, "c1"), new Book(1, "b1"));

    boolean containedKey = treeMap.containsKey(new Category(2, "c1"));
    assertThat(containedKey).isTrue();

    boolean containedValue = treeMap.containsValue(new Book(2, "b1"));
    assertThat(containedValue).isTrue();

    treeMap.put(new Category(2, "c1"), new Book(2, "b1"));
    assertThat(treeMap).hasSize(1);

    Book previousValue = treeMap.replace(new Category(2, "c1"), new Book(2, "b1"));
    assertThat(previousValue).isNotNull();

    treeMap.remove(new Category(2, "c1"));
    assertThat(treeMap).hasSize(0);
}

static class Category implements Comparable<Category> {  
    int id;
    String name;

    Category(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public int compareTo(Category o) {
        return CharSequence.compare(this.name, o.name);
    }
}

static class Book  implements Comparable<Book> {  
    int id;
    String title;

    Book(int id, String title) {
        this.id = id;
        this.title = title;
    }

    int getId() {
        return id;
    }

    String getTitle() {
        return title;
    }

    @Override
    public int compareTo(Book o) {
        return CharSequence.compare(this.title, o.title);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Book book = (Book) o;
        return Objects.equals(title, book.title);
    }
}

• You can fix the above problem by overriding equals and hashCode as the below example

@Test
public void objectsComparingFixed(){  
    NavigableMap<CategoryFixed, BookFixed> treeMap = new TreeMap<>();

    treeMap.put(new CategoryFixed(1, "c1"), new BookFixed(1, "b1"));

    boolean containedKey = treeMap.containsKey(new CategoryFixed(2, "c1"));
    assertThat(containedKey).isFalse();

    boolean containedValue = treeMap.containsValue(new BookFixed(2, "b1"));
    assertThat(containedValue).isFalse();

    treeMap.put(new CategoryFixed(2, "c1"), new BookFixed(2, "b1"));
    assertThat(treeMap).hasSize(2);

    BookFixed previousValue = treeMap.replace(new CategoryFixed(2, "c1"), new BookFixed(2, "b1"));
    assertThat(previousValue).isNotNull();

    treeMap.remove(new CategoryFixed(2, "c1"));
    assertThat(treeMap).hasSize(1);
}

static class CategoryFixed implements Comparable<CategoryFixed>{  
    int id;
    String name;

    CategoryFixed(int id, String name) {
        this.id = id;
        this.name = name;
    }

    int getId() {
        return id;
    }

    String getName() {
        return name;
    }

    @Override
    public int compareTo(CategoryFixed o) {
        return Comparator.comparing(CategoryFixed::getName)
            .thenComparing(CategoryFixed::getId)
            .compare(this, o);
    }
}

static class BookFixed implements Comparable<BookFixed> {  
    int id;
    String title;

    BookFixed(int id, String title) {
        this.id = id;
        this.title = title;
    }

    int getId() {
        return id;
    }

    String getTitle() {
        return title;
    }


    @Override
    public int compareTo(BookFixed o) {
        return Comparator.comparing(BookFixed::getTitle)
            .thenComparing(BookFixed::getId)
            .compare(this, o);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        BookFixed bookFixed = (BookFixed) o;
        return id == bookFixed.id &&
            Objects.equals(title, bookFixed.title);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, title);
    }
}

• In practice, consider to override hashCode when overriding equals and keep equals consistent with compareTo since your defined classes may be used elsewhere either as a key or value objects in a hash table based collection such as HashMap and HashSet or in a red-black tree collection such as TreeMap and TreeSet

  Learn more about equals and hashCode

Conclusion

In this tutorial, we had a quick overview of the TreeMap hierarchy, features, and operations. You can find below the full example source code