Vogulev Tech

HashMap и выбор ключей, один из самых частых вопросов на собеседовании

Когда работаешь с HashMap, выбор типа ключа кажется простым делом. Но на практике неправильный выбор может привести к неочевидным багам, которые сложно отследить.

Главное правило при работе с HashMap - ключи должны быть иммутабельными. Под иммутабельностью я имею в виду, что после создания объекта его состояние не должно меняться. Именно поэтому String, Integer, Long и другие обёртки примитивов так популярны в качестве ключей. Они по умолчанию иммутабельные.

Почему это важно? HashMap использует хеш-код объекта для определения, в какую корзину положить пару ключ-значение. Когда ты кладёшь элемент в мапу, вычисляется hashCode() ключа, и на основе этого значения элемент попадает в определённую ячейку внутреннего массива. Когда потом ищешь значение по ключу, снова вычисляется хеш-код и HashMap знает, в какой корзине искать.

Теперь представь, что ключ изменяемый. Ты положил объект в мапу, он попал в корзину номер 5, допустим. Потом изменил поля этого объекта. Его hashCode() изменился, теперь он должен быть в корзине номер 12. Но физически объект всё ещё лежит в корзине 5. Когда пытаешься получить значение по этому же ключу, HashMap вычисляет новый хеш-код, идёт искать в корзину 12, а там ничего нет. Получаешь null, хотя элемент в мапе есть.

Давай посмотрим на конкретный пример. Создаём класс Person с изменяемыми полями:


class Person {
    private String name;
    private int age;
    
    // конструктор, геттеры, сеттеры
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        // стандартная реализация
    }
}

Используем его как ключ:


Person person = new Person("Артём", 30);
Map<Person, String> map = new HashMap<>();
map.put(person, "Developer");

// Пока всё работает
System.out.println(map.get(person)); // "Developer"

// Меняем состояние ключа
person.setAge(31);

// Теперь проблема
System.out.println(map.get(person)); // null!

Элемент в мапе есть, но найти его не можем. Более того, если попробуешь итерироваться по всем ключам мапы, этот Person там будет, но достать его по ключу через get() невозможно. Это называется "потерянный элемент".

Ещё хуже, если в мапе уже есть другой объект с таким же хеш-кодом после изменения. Тогда получишь коллизию там, где её не ожидал, и можешь случайно перезаписать данные.

Что делать, если всё-таки нужно использовать сложный объект как ключ? Делай его иммутабельным. Все поля должны быть final, в конструкторе задаются один раз и больше не меняются. Если внутри есть коллекции или другие объекты, они тоже должны быть иммутабельными или защищёнными от изменений.

Пример правильного иммутабельного ключа:


final class ImmutablePerson {
    private final String name;
    private final int age;
    
    public ImmutablePerson(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    public String getName() {
        return name;
    }
    
    public int getAge() {
        return age;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof ImmutablePerson)) return false;
        ImmutablePerson other = (ImmutablePerson) obj;
        return age == other.age && Objects.equals(name, other.name);
    }
}

Класс final, все поля final, нет сеттеров. Такой объект можно безопасно использовать как ключ.

Ещё один момент про equals() и hashCode(). Эти методы должны быть переопределены корректно и согласованно. Если два объекта равны по equals(), их hashCode() должен быть одинаковым. Иначе HashMap не сможет найти элемент даже с правильным ключом. Обычно IDE генерирует эти методы автоматически, но стоит проверять, что они используют те же поля.

⚡4❤3🔥3

53 viewsedited 12:17