Как работает HashSet?

#java

  HashSet hs = new HashSet<>();
        hs.add("Sts");
        hs.add("Str");
        hs.add("Vbs");
        hs.add("Sts");
        System.out.println(hs);


Всё отработало и показало 1 - Sts, то есть исключило дубликат. Объясните почему везде
пишется что нужно переопределить hashCode()иequals() чтобы это заработало или я в чем-то
ошибаюсь.

2 вопрос: Порядок добавления элементов вычисляется с помощью хэш-кода.
Как понять это? То есть прежде чем добавлять у элементов вычисляется хэш код и они
ставятся по порядку своих хэш кодов?
    

Ответы

Ответ 1

Объясните почему везде пишется что нужно переопределить hashCode() и equals() чтобы
это заработало или я в чем-то ошибаюсь.


Хеш используется для быстрого поиска нужного объекта. Согласитесь, что быстрее сравнить
два целочисленных значения (особенно, если они еще и как-то отсортированы), чем сравнивать
все поля объекта.

Но т.к. разные объекты могут дать один и тот же хеш, то при нахождении объекта с
нужным хешем затем еще и проводится проверка на равенство этих объектов.

Например, для двух строк

String str1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaa";
String str2 = "aaaaaaaaaaaaaaaaaaaaaaaaaab";


чтобы  узнать равны они или нет, придется сравнить каждый символ. И только при сравнении
последнего, узнать, что строки не равны.

Или же сравнить хеши

int hash1 = str1.hashCode();
int hash2 = str2.hashCode();
if (hash1 != hash2) {
  // Строки не равны
} else {
  // хеши равны, но строки все равно могут быть не равны,
  // поэтому сравниваем еще и сами строки
  if (!str1.equals(str2)) {
    // Строки не равны
  } else {
    // Строки равны
  }
}


когда нужно сравнить два объекта, то сравнение быстрее, т.к. вычисление хеша операция
не быстрая. Но если нужно проводить регулярный поиск по списку, то хеши можно подсчитать
лишь единожды.

Вы используете стандартный класс String. Для него методы hashCode() и equals() уже
переопределены


  То есть прежде чем добавлять у элементов вычисляется хэш код 


Да. Смотри ответ выше


  и они ставятся по порядку своих хэш кодов?


Не обязательно. Сортировка по хешу - это особенность реализации. Ее может не быть
вообще, она может быть довольно хитрой. Могут использоваться деревья...

В целом, когда мы говорим о Set<> понятие сортировки не определено


Ответ 2

Как устроен HashSet, Anton Shchyrov достаточно подробно рассказал. Я расскажу, в
каких случаях надо переопределять методы hashCode и equals.

Представим, что у вас есть класс:

public class WrappedString {
    private String s;
    public WrappedString (String s) { this.s = s; }
}


Изменим немного main, чтобы использовать наш класс вместо строки.

public static void main (String[] args) {
    HashSet hs = new HashSet<> ();
    hs.add (new WrappedString ("Sts"));
    hs.add (new WrappedString ("Str"));
    hs.add (new WrappedString ("Vbs"));
    hs.add (new WrappedString ("Sts"));
    System.out.println (hs);
}


Вывод:

[WrappedString@74a14482, WrappedString@677327b6, WrappedString@1540e19d, WrappedString@14ae5a5]


Все 4 элемента добавились, и вы наверно уже поняли почему. По умолчанию для получения
хеш-кода используется адрес объекта, он же и используется для сравнения. То есть вам
не нужно переопределять в своем классе эти методы, если вы проверяете объекты на идентичность.
Переопределять их нужно, если у вас разные объекты могут быть равны.

Изменим наш класс обертки для строки:

public class WrappedString {

    public String s;


    public WrappedString (String s) {
        this.s = s;
    }


    @Override
    public int hashCode () {
        return s.hashCode ();
    }


    @Override
    public boolean equals (Object obj) {
        if (!(obj instanceof WrappedString)) return false;
        WrappedString ws = (WrappedString) obj;
        if (s == null) return ws.s == null;
        return s.equals (ws.s);
    }


    @Override
    public String toString () {
        return s;
    }

}


Вывод:

[Str, Sts, Vbs]


Но внимание!

При изменении поля, по которому считается хеш, HashSet не сможет заметить это изменение,
и контейнер станет для экземпляра неправильным!

Пример:

public static void main (String[] args) {
    HashSet hs = new HashSet<> ();
    WrappedString ws = new WrappedString ("Sts");
    hs.add (ws); // Sts
    ws.s = "Kek"; // но хранится он в контейнере для Sts, не Kek
    hs.add (new WrappedString ("Str"));
    hs.add (new WrappedString ("Vbs"));
    hs.add (new WrappedString ("Kek")); // добавляем дубликат
    System.out.println (hs);
}


Вывод:

[Str, Kek, Kek, Vbs]


Поэтому нужно либо объявлять поля от которых считается хеш как final, либо быть внимательным
и не менять их, когда экземпляр может находиться в хеш-таблице.