Java - do we need to implement equals and hash code methods in object used as key in TreeMap (or HashSet)

We don't need to implement equals and hashCode in key object used in TreeMap or HashSet.

It is good practice to implement equals and hashCode methods.

In case we use the key with hash map, we need to implement equals and hash code (without implementing it the hash map / hash set won't work correctly), list of hash maps implemntations in java:

• HashMap
• HashSet
• LinkedHashMap
• ConcurrentHashMap
• Hashtable

TreeMap and HashSet in java works by comparing objets (that's why we have sorted order). If the key is the same than the value is overrided by new value.

It is good to undetstand the difference between HashMap and TreeMap. HashMap works on hashCode and equals method (so called contract). TreeMap is backed by Red-black tree algorithm (self-balancing binary search tree) - implementations based on algorithm described in book: Cormen, Leiserson, and Rivest's Introduction to Algorithms.

We can read in TreeMap JDK docs about equals implementation:

Note that the ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

Object that we use as a Key in TreeMap or HashSet needs to:

• implement Comparable, see this question for more details: Java TreeMap Comparable vs Comparator
• or we need to pass Comparator implementations by constructor (example below).

See below example, we implemented Comparator interface for Point object. 

• String put1 = map.put(new Point(1, 2), "pt1");
• String put2 = map.put(new Point(1, 2), "pt1-override"); // override value for key: Point(1, 2)
• assertThat(put1).isNull(); // there was no previous value
• assertThat(put2).isEqualTo("pt1"); // pt1 was prev value for key: Point(1, 2)

Full code example:

import org.junit.Test;

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

import static org.assertj.core.api.Assertions.assertThat;

public class Example {
    @Test
    public void shouldTestComparator() {
        TreeMap<Point, String> map = new TreeMap<>(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                // asc order
                int compareX = Integer.compare(o1.getX(), o2.getX());
                if (compareX == 0) { // eq
                    return Integer.compare(o1.getY(), o2.getY());
                }
                return compareX; // -1 or 1 - if o1X < o2X ret -1, if o1X > o2X ret 1
            }
        });

        // Map.put returns:
        // the previous value associated with key, or null if there was no mapping for key.

        String put1 = map.put(new Point(1, 2), "pt1");
        String put2 = map.put(new Point(1, 2), "pt1-override"); // override value for key: Point(1, 2)
        String put3 = map.put(new Point(2, 1), "pt2");

        assertThat(put1).isNull(); // there was no previous value
        assertThat(put2).isEqualTo("pt1"); // pt1 was prev value for key: Point(1, 2)
        assertThat(put3).isNull(); // there was no previous value

        assertThat(map).hasSize(2);
        assertThat(map.get(new Point(1, 2))).isEqualTo("pt1-override");
        assertThat(map.get(new Point(2, 1))).isEqualTo("pt2");
        assertThat(map.toString())
                .isEqualTo("{Point{x=1, y=2}=pt1-override, Point{x=2, y=1}=pt2}");
    }

    private static class Point {
        private final int x;
        private final int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        @Override
        public String toString() {
            return "Point{" + "x=" + x + ", y=" + y + '}';
        }
    }
}