Что будет с повторяющимся элементом при передаче в TreeMap?

Что будет с повторяющимся элементом при передаче в TreeMap?

TreeMap — это отсортированная реализация Map, основанная на красно-чёрных деревьях. При попытке добавить дубликат ключа происходит перезапись значения (как и в обычных Maps), но механизм их удаления требует понимания контракта compareTo().

Поведение дубликатов ключей

Так как TreeMap использует красно-чёрное дерево с сортировкой, оно определяет уникальность ключей не через equals(), а через метод compareTo() (или Comparator).

import java.util.*;

public class TreeMapDuplicates {
    public static void main(String[] args) {
        // Пример 1: Integer как ключи
        Map<Integer, String> map = new TreeMap<>();
        
        map.put(1, "Один");
        map.put(2, "Два");
        map.put(1, "Один (обновлён)");  // Тот же ключ
        
        System.out.println(map.size());     // 2, не 3!
        System.out.println(map.get(1));    // "Один (обновлён)"
        
        // Вывод:
        // {1=Один (обновлённый), 2=Два}
    }
}

Ключевой момент: TreeMap видит два элемента как идентичные, потому что 1.compareTo(1) == 0.

Когда compareTo() возвращает 0

public class ComparableExample {
    static class Person implements Comparable<Person> {
        int id;
        String name;
        
        public Person(int id, String name) {
            this.id = id;
            this.name = name;
        }
        
        @Override
        public int compareTo(Person other) {
            return Integer.compare(this.id, other.id);  // Только по id!
        }
    }
    
    public static void main(String[] args) {
        Map<Person, String> map = new TreeMap<>();
        
        Person p1 = new Person(1, "John");
        Person p2 = new Person(2, "Jane");
        Person p3 = new Person(1, "Johnny");  // Тот же id
        
        map.put(p1, "First");
        map.put(p2, "Second");
        map.put(p3, "Third");  // Перезапишет первого!
        
        System.out.println(map.size());  // 2
        System.out.println(map.get(p1)); // "Third"
        // p1.compareTo(p3) == 0, поэтому они считаются одним ключом
    }
}

Отличие от HashMap

public class HashMapVsTreeMap {
    static class CustomKey {
        int value;
        String name;
        
        public CustomKey(int value, String name) {
            this.value = value;
            this.name = name;
        }
        
        @Override
        public int hashCode() {
            return value;  // Только по value
        }
        
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof CustomKey)) return false;
            return this.value == ((CustomKey) obj).value;
        }
        
        @Override
        public String toString() {
            return "[" + value + "," + name + "]";
        }
    }
    
    public static void main(String[] args) {
        Map<CustomKey, String> hashMap = new HashMap<>();
        Map<CustomKey, String> treeMap = new TreeMap<>((k1, k2) -> 
            Integer.compare(k1.value, k2.value));
        
        CustomKey k1 = new CustomKey(1, "First");
        CustomKey k2 = new CustomKey(1, "Second");
        
        hashMap.put(k1, "V1");
        hashMap.put(k2, "V2");
        System.out.println("HashMap size: " + hashMap.size());  // 1 (equals вернул true)
        
        treeMap.put(k1, "V1");
        treeMap.put(k2, "V2");
        System.out.println("TreeMap size: " + treeMap.size());  // 1 (compareTo вернул 0)
    }
}

Важная ошибка: несогласованность compareTo() и equals()

Это одна из самых подводных ошибок в Java!

public class InconsistentComparator {
    static class Student implements Comparable<Student> {
        int id;
        String name;
        
        public Student(int id, String name) {
            this.id = id;
            this.name = name;
        }
        
        // compareTo сравнивает только по id
        @Override
        public int compareTo(Student other) {
            return Integer.compare(this.id, other.id);
        }
        
        // Но equals сравнивает по id И name
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Student)) return false;
            Student other = (Student) obj;
            return this.id == other.id && this.name.equals(other.name);
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(id, name);
        }
    }
    
    public static void main(String[] args) {
        TreeMap<Student, String> map = new TreeMap<>();
        
        Student s1 = new Student(1, "John");
        Student s2 = new Student(1, "Johnny");  // Тот же id, но другое имя
        
        map.put(s1, "Value1");
        map.put(s2, "Value2");  // compareTo вернёт 0, перезапишет!
        
        System.out.println(map.size());  // 1
        
        // Но если проверить equals:
        System.out.println(s1.equals(s2));  // false!
        // ВНИМАНИЕ: s1 не equals s2, но TreeMap их считает одинаковыми!
        // Это нарушение контракта Comparable и может вызвать ошибки
    }
}

Правильная реализация

public class CorrectTreeMapUsage {
    static class Product implements Comparable<Product> {
        int id;
        String name;
        
        public Product(int id, String name) {
            this.id = id;
            this.name = name;
        }
        
        // compareTo и equals проверяют одни и те же поля!
        @Override
        public int compareTo(Product other) {
            int idCompare = Integer.compare(this.id, other.id);
            if (idCompare != 0) return idCompare;
            return this.name.compareTo(other.name);
        }
        
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Product)) return false;
            Product other = (Product) obj;
            return this.id == other.id && this.name.equals(other.name);
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(id, name);
        }
    }
    
    public static void main(String[] args) {
        TreeMap<Product, String> map = new TreeMap<>();
        
        Product p1 = new Product(1, "John");
        Product p2 = new Product(1, "Johnny");
        
        map.put(p1, "Value1");
        map.put(p2, "Value2");
        
        System.out.println(map.size());  // 2 — разные элементы!
        // p1.compareTo(p2) != 0, так что они разные
    }
}

Резюме

1. TreeMap использует compareTo(), не equals() — для определения уникальности ключей
2. compareTo() == 0 означает дубликат — значение будет перезаписано
3. Согласованность критична — (a.compareTo(b) == 0) должно быть эквивалентно a.equals(b)
4. Нарушение контракта вызывает баги — TreeMap и Collections.binarySearch() могут работать неправильно
5. Если compareTo() возвращает != 0 — то элементы считаются разными и оба сохраняются