Как используется hashCode в HashSet/HashMap?

Давайте рассмотрим пример плохой реализации hashCode:

import java.util.*;
class Main {
    public static void main (String[] args) {
        BadHash one = new BadHash();
        one.hash = 1;
        HashSet<BadHash> s = new HashSet<>();
        s.add(one);
        one.hash = 2;
        System.out.println(s.contains(one)); //false
        System.out.println(s); //2
        s.add(one);
        System.out.println(s.size()); //2
    }
}
class BadHash {
    public int hash;
    @Override
    public int hashCode() {
        return hash;
    }
    @Override
    public String toString() {
        return hash+"";
    }
}

Мы создали класс (BadHash) хеш которого можно изменять. В результате, после того как хеш изменился объект, ранее добавленный в HashSet, не удалось найти.

Что произошло по шагам:

• при добавлении элемента HashSet рассчитал его хеш (на тот момент 1) и поместил его в соответствующую хешу ячейку;
• при вызове contains HashSet рассчитал хеш переданного элемента (теперь 2), попытался найти его в ячейке, соответствующей 2 и не нашел;
• при выводе множества в строку он вывел то, что вернул toString() (2), т.е. объект все еще лежит в ячейке 1, но его хеш и строковое представление изменились;
• более того, если снова добавить тот же объект в множество, то он будет добавлен и в разных ячейках (с хешем 1 и 2) лежат ссылки на один и тот же объект.

Теперь по вопросам:

1. Как понять использование hash-кодов позволяет быстро искать, добавлять и тд. Мы если помещаем в реализацию HashSet несколько значений и выводим мы видим их текстовое представление, а не hash-коды поэтому не понятно, объясните.

Когда Вы выводите объекты, Вы выводите их текстовое представление. Но HashSet текстовое представление в расчет не берет. Множество использует hashcode для определения ячейки (скорости) и equals для проверки на совпадение.

2. Если ты забудешь реализовать метод hashCode(), то рискуешь, что твой объект в коллекции Set не будет найден, даже если он там есть.

Вот здесь мне не совсем понятно, что имено люди на JavaRush имели ввиду, поэтому объясню поподробнее что происходит.

Если в классе не переопределить («реализовать», имхо, не очень подходит) метод hashCode, то он унаследует hashCode от ближайшего класса-родителя в котором метод переопределен. Если ни один из классов в иерархии не переопределит hashCode, то будет использоваться метод класса Object.

Проблемы могут возникнуть если логика хеша класса-родителя не подходит к Вашему классу.

Давайте снова рассмотрим пример. Объявим класс Point который будет обозначать точку в декартовой системе координат. Переопределим для него метод equals, чтобы точки с одинаковыми координатами считались одинаковыми, но не будем переопределять hashCode:

class Point {
    int X;
    int Y;
    Point(int x, int y) {
        X = x;
        Y = y;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point other = (Point) o;
        return X==other.X && Y ==other.Y;
    }
}

Проверим, что equals работает корректно:

Point one = new Point(1, 1);
Point anotherOne = new Point(1, 1);
System.out.println("Are points equals to each other: "+one.equals(anotherOne)); //true

Все нормально. А теперь проверим, будет ли HashSet работать с Point без переопределения hashCode:

HashSet<Point> s = new HashSet<>();
s.add(one);
System.out.println("Can you find the point without hashCode: "+s.contains(anotherOne)); //false

Из-за того что hashCode не переопределен используется метод Object.hashCode. Этот метод возвращает (по крайней мере пытается) разные хеши для разных объектов. В результате HashSet не может найти вторую точку по хешу, хотя равная ей точка уже есть в множестве.

Для того, чтобы точки корректно находились в множестве нужно:

• рассчитывать hashCode на основе значимых полей — так он будет совпадать для одинаковых объектов и отличаться для большинства разных;
• сделать поля неизменяемыми — так мы не пострадаем от изменений хеша.

class Point {
    private int x;
    private int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point other = (Point) o;
        return x==other.x && y ==other.y;
    }
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

Такой класс уже будет хорошо работать с HashSet и HashMap