Какие элементы являются сравнимыми в HashMap

Какие элементы являются сравнимыми в HashMap?

Уточнение вопроса: в HashMap сравниваются только ключи, и по умолчанию HashMap использует hashCode() и equals(), а не методы сравнения (compareTo). HashMap не требует, чтобы ключи были Comparable.

1. HashMap использует hashCode() и equals()

HashMap не сравнивает ключи через Comparable или compareTo(). Вместо этого используется:

public class HashMap<K, V> extends AbstractMap<K, V> {
    
    @Override
    public V put(K key, V value) {
        // Шаг 1: Вычисляется hash ключа
        int hash = hash(key);  // hash(key.hashCode())
        
        // Шаг 2: Находится bucket по хешу
        int index = (hash) & (table.length - 1);  // Бинарная маска
        
        // Шаг 3: Если есть коллизия, используется equals() для проверки
        Node<K, V> node = table[index];
        while (node != null) {
            // Сравнение: сначала hash, потом equals
            if (node.hash == hash && 
                (key == node.key || key.equals(node.key))) {
                // Найден существующий ключ
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
            node = node.next;
        }
        // Добавление нового узла
        addNode(hash, key, value, table[index]);
        return null;
    }
}

2. Сравнимые типы (Comparable) НЕ требуются

public class CustomKey {
    private String name;
    
    public CustomKey(String name) {
        this.name = name;
    }
    
    // НЕ реализуем Comparable
    // НЕ реализуем Comparator
    
    @Override
    public int hashCode() {
        return name.hashCode();
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        CustomKey other = (CustomKey) obj;
        return name.equals(other.name);
    }
}

// Использование
public static void main(String[] args) {
    HashMap<CustomKey, String> map = new HashMap<>();
    
    CustomKey key1 = new CustomKey("john");
    CustomKey key2 = new CustomKey("john");
    
    map.put(key1, "value1");
    // key2.compareTo(key1) — НЕ вызывается!
    // Вместо этого используется: key2.equals(key1) и key2.hashCode()
    System.out.println(map.get(key2));  // "value1"
}

3. TreeMap vs HashMap — это разные структуры

Часто возникает путаница: TreeMap использует Comparable, HashMap — нет.

TreeMap — требует сравнения:

public class Person implements Comparable<Person> {
    private String name;
    private int age;
    
    @Override
    public int compareTo(Person other) {
        // TreeMap будет использовать это для сортировки
        return this.age - other.age;
    }
}

// TreeMap
TreeMap<Person, String> treeMap = new TreeMap<>();  // Требует Comparable
treeMap.put(new Person("Alice", 30), "value1");
treeMap.put(new Person("Bob", 25), "value2");  // Сортируется по возрасту

HashMap — не требует сравнения:

public class Person {  // НЕ реализуем Comparable
    private String name;
    private int age;
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person other = (Person) obj;
        return name.equals(other.name) && age == other.age;
    }
}

// HashMap
HashMap<Person, String> hashMap = new HashMap<>();  // Не требует Comparable
hashMap.put(new Person("Alice", 30), "value1");
hashMap.put(new Person("Bob", 25), "value2");  // Порядок не определен

4. Процесс поиска в HashMap (детально)

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 10);
map.put("banana", 20);
map.put("cherry", 30);

Integer value = map.get("apple");

// Шаг за шагом:
// 1. Вычисляется hash("apple")
//    Внутри: int h = "apple".hashCode();
//           return h ^ (h >>> 16);  // Высокие биты в низкие

// 2. Индекс в массиве: index = hash & (capacity - 1)
//    Если capacity = 16, то маска = 0xF (1111 в двоичной)

// 3. Проверяется bucket[index]
//    Если там цепочка узлов (chain) из-за коллизий:
//    for (Node node = bucket[index]; node != null; node = node.next) {
//        if (node.hash == hash && node.key.equals("apple")) {
//            return node.value;  // Найдено!
//        }
//    }

// 4. Результат: Integer 10

5. Важность правильного equals() и hashCode()

// ❌ ПЛОХО — нарушает контракт
public class BadKey {
    private int id;
    
    @Override
    public int hashCode() {
        return id;  // OK
    }
    
    @Override
    public boolean equals(Object obj) {
        // БУГ: equals и hashCode не согласованы!
        return true;  // Все объекты "равны"
    }
}

// Результат: HashMap будет неправильно работать
HashMap<BadKey, String> map = new HashMap<>();
BadKey k1 = new BadKey(1);
BadKey k2 = new BadKey(2);
map.put(k1, "value1");
map.put(k2, "value2");  // Перезапишет value1!
System.out.println(map.size());  // 1 вместо 2

// ✅ ПРАВИЛЬНО — контракт соблюдается
public class GoodKey {
    private int id;
    private String name;
    
    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        GoodKey other = (GoodKey) obj;
        return id == other.id && name.equals(other.name);
    }
}

6. Контракт между hashCode() и equals()

Правило:

Если a.equals(b) == true,  то a.hashCode() == b.hashCode()
Если a.hashCode() == b.hashCode(), то a.equals(b) может быть true или false (коллизия)

Примеры соблюдения контракта:

// Пример 1: String
String s1 = "hello";
String s2 = new String("hello");
System.out.println(s1.equals(s2));      // true
System.out.println(s1.hashCode() == s2.hashCode());  // true ✓

// HashMap
HashMap<String, Integer> map = new HashMap<>();
map.put(s1, 1);
System.out.println(map.get(s2));  // 1 (работает, потому что контракт соблюдается)

// Пример 2: Integer
Integer i1 = 100;
Integer i2 = 100;
System.out.println(i1.equals(i2));      // true
System.out.println(i1.hashCode() == i2.hashCode());  // true ✓

// HashMap
HashMap<Integer, String> map2 = new HashMap<>();
map2.put(i1, "value");
System.out.println(map2.get(i2));  // "value"

7. Содержимое цепочки при коллизиях (JDK 8+)

Если несколько ключей имеют одинаковый hash (коллизия):

HashMap<String, Integer> map = new HashMap<>();
map.put("ab", 1);   // hash = некоторое значение
map.put("ba", 2);   // случайно, может быть тот же hash

// Внутренняя структура при коллизии:
Node<String, Integer>[] table = new Node[16];

// table[index] → Node("ab", 1) → Node("ba", 2) → null
//                  (связный список)

// При поиске:
Integer value = map.get("ba");
// 1. Вычислить hash("ba")
// 2. Найти индекс
// 3. Пройти по цепочке (linked list)
//    - Проверить: node.hash == hash && node.key.equals("ba")
//    - Для "ab": hash совпадает, но "ab".equals("ba") == false
//    - Для "ba": hash совпадает, и "ba".equals("ba") == true → Найдено!

8. Сравнение структур данных

9. Когда нужна Comparable?

// Если нужна СОРТИРОВКА по ключам
TreeSet<Person> sortedByAge = new TreeSet<>();
// TreeSet требует Comparable (или Comparator)

// Если нужны отсортированные ключи в Map
SortedMap<Person, String> sortedMap = new TreeMap<>();
// TreeMap требует Comparable (или Comparator)

// Если нужна сортировка значений
List<Person> people = personMap.values().stream()
    .sorted(Comparator.comparingInt(p -> p.getAge()))
    .collect(Collectors.toList());
// Сортировка не требует Comparable ключей

10. Best Practices

public class EmployeeKey {
    private final long id;
    private final String department;
    
    public EmployeeKey(long id, String department) {
        this.id = id;
        this.department = department;
    }
    
    // Всегда переопредели hashCode() для HashMap ключей
    @Override
    public int hashCode() {
        return Objects.hash(id, department);
    }
    
    // Всегда переопредели equals() для HashMap ключей
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        EmployeeKey other = (EmployeeKey) obj;
        return id == other.id && 
               Objects.equals(department, other.department);
    }
    
    // Не реализуй Comparable, если не нужна сортировка
    // Это добавит ненужную сложность
}

// Использование
public static void main(String[] args) {
    HashMap<EmployeeKey, String> employees = new HashMap<>();
    EmployeeKey emp1 = new EmployeeKey(1, "Engineering");
    EmployeeKey emp2 = new EmployeeKey(1, "Engineering");  // Эквивалентен emp1
    
    employees.put(emp1, "John");
    employees.put(emp2, "Jane");  // Перезапишет значение
    
    System.out.println(employees.size());  // 1
    System.out.println(employees.get(emp2));  // "Jane"
}

Итоги

В HashMap сравниваются только ключи, и сравнение использует:

1. hashCode() — для определения позиции (bucket index)
2. equals() — для проверки совпадения при коллизиях

Ключи НЕ требуют быть Comparable. Comparable нужна только для:

• TreeMap — для сортировки ключей
• TreeSet — для сортировки элементов
• Collections.sort() — для сортировки списков

DEFAULT HashMap просто хранит пары ключ-значение без какой-либо сортировки, используя только hashCode() и equals().