Зависимость работы HashSet от переопределения equals() и hashCode() у элементов множества

#java #hashcode #hashset #equals

Мне дали задание сделать два разных объекта класса User с одинаковыми полями и 4
варианта их добавления в HashSet:


Не переопределять ни equals(), ни hashCode() у класса User.
Переопределить только equals().
Переопределить только hashCode().
Переопределить и equals(), и hashCode().


Во всех случаях нужно сказать какой будет size и почему.

Класс User выглядит так:

public class User {
    public String name;
    public int children;
    public Calendar birthday;

    public User(String name, int children, Calendar birthday) {
        this.name = name;
        this.children = children;
        this.birthday = birthday;
    }
}


hashCode() я переопределяю так:

@Override
public int hashCode() {
    int hash = 31;
    hash = hash * 17 + name.hashCode();
    hash = hash * 17 + birthday.hashCode();
    hash = hash * 17 + children;
    return hash;
}


equals() я переопределяю так:

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (this.getClass() != obj.getClass())
        return false;
    UserEquals ue = (UserEquals) obj;
    return this.hashCode() == ue.hashCode() ||
            (this.birthday.getTimeInMillis() == ue.getBirthday().getTimeInMillis() &&
            this.children == ue.getChildren() &&
            this.name.equals(ue.getName()));
}


Если мои варианты переопределения методов некорректны, прошу меня поправить.

Тест в общем случае выглядит так:

@Test
public void whenThen() {
    Calendar calendar = new GregorianCalendar(1988, Calendar.JUNE, 19);
    User user1 = new User("Pavel", 0, calendar);
    User user2 = new User("Pavel", 0, calendar);
    Set set = new HashSet<>();
    set.add(user1);
    set.add(user2);
    int result = set.size();
    assertThat(result, is(2));
}


И вот вопрос:

Когда я не переопределяю ничего у класса User, то у меня size == 2, и когда я переопределяю
только equals() - тоже size == 2. И я подумал, что HashSet вообще не использует метод
equals(), а сразу использует hashCode() (то есть сравнение по содержанию полей в equals()
на ситуацию не влияет). 

Но когда я переопределил отдельно только hashCode(), ситуация также не изменилась:
size по-прежнему остался равен 2. И только когда я переопределил оба метода (и hashCode(),
и equals()), size стал равен 1.

Сколько ни блуждаю по исходникам HashSet, не могу до конца понять как же оно всё-таки
работает.

В чем идея класса HashSet при выявлении что считать дубликатом, а что - нет?
    

Ответы

Ответ 1

Чтобы понять почему получились такие результаты, нужно понять, как работает хэш таблица.

Для методов equals и hashCode установлен определенный контракт:


если элементы равны между собой, т.е. equals возвращает true, то значение hashCode
для этих объектов должно совпадать.
если значение hashCode для объектов совпадает, то это еще не значит, что equals для
них вернет true, т.е. объекты не обязаны быть равны между собой, т.е. возможны коллизии. 


И так, рассмотрим хэш таблицу с bucket'ами. Она состоит из массива, в каждой ячейке
которого хранится список элементов.

Когда мы добавляем элемент, для него вычисляется кэшкод, затем по определяется индекс
ячейки, где должен хранится список, содержащий данный элемент:

index = hashcode % table_size


где table_size - это размер таблицы.

По индексу достается список, методом equals проверяется, содержится ли данный элемент
в списке, если нет, то он добавляется.
Аналогично, выполняется операции remove, contains.

Теперь рассмотрим каждый случай по отдельности:


equals и hashCode не переопределены, это значит, что equals будет возвращать true
только в случае если ссылки равны, а hashCode может быть как равен так и нет. Размер,
не зависимо от значения hashCode, будет 2.  
equals и hashCode переопределены, тогда у нас будет одинаковое хэш значение, мы попадем
в одну и туже ячейку таблицы, equals определит, что объект в списке уже присутствует,
соответственно размер будет равен 1.
equals непереопределен, а hashCode переопределен. В этом случае, индекс ячейки будет
одним и тем же, но в списке не обнаружится одинакового элемента и по этому размер будет
равен 2.
equals переопределен, а hashCode непереопределен. Здесь зависит того как генерируется
значение для hashCode в классе Object. Если значения будут одинаковы, то список будет
один и тот же, и соответсвенно, количество элементов в таблице будет 1. Если разные,
то поиск будет происходить в разных списках, и дубликатов не обнаружится, тогда размер
будет равен 2.


Ответ 2

(обязательно прочитайте последний пункт, связанный с изменениями в JDK 8)

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

Рассмотрим исходный код метода boolean add(E e) класса HashSet:

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}


Отсюда видно, что при добавлении элемента в HashSet происходит добавление этого элемента
в map, который является объектом класса HashMap:

private transient HashMap map;


В качестве ключа здесь используется переданный в метод add(...) объект, а в качестве
значения – объект класса Object:

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();


Отсюда делаем вывод, что HashSet работает ровно так же, как и HashMap с поправкой
на то, что в качестве значения используется некоторая заглушка – один и тот же объект
класса Object.

Как работает HashMap

HashMap работает по принципам хэширования, за счет которого доступ к элементам по
ключу достигается в лучшем случае за константное время – O(1).

HashMap хранит элементы вида ключ-значение в массиве:

transient Node[] table;


где Node – вложенный класс со следующей структурой:

static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;

    ...

    }


Как видно, в Node хранится хэш, ключ, значение и ссылка не следующий элемент
(об этом поле расскажу далее).

В теории хэширования существует такое понятие как коллизия – это явление, когда для
разных объектов получается одинаковый хэш-код.

В Java хэш-код имеет тип int, следовательно, множество хэш-кодов ограничено множеством
значений типа int – [-2147483648;2147483647].

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

Вкратце, процесс добавления пары key-value в HashMap выглядит следующим образом:


Если key == null, то вызывается метод putForNullKey(...) в который передается value.
Этот метод добавляет key-value в нулевую позицию массива;
Если key != null, то вычисляется хэш-код объекта key, который передается в метод
hash(...):

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

По полученному из метода hash(...) хэш-коду вычисляется индекс массива, по которому
необходимо разместить данную пару key-value:

static int indexFor(int h, int length) {
    return h & (length-1);
}

Если по полученному индексу в массиве не содержится ничего, то данная пара размещается
по этому индексу.
Если по полученному индексу уже находится какая-либо пара (либо пары), то происходит
последовательный обход всех пар с проверкой равенства хэш-кода и ключа добавляемой
пары с соответствующими значениями уже находящихся в данной корзине пар. Для сравнения
хэш-кода используется ==, а для сравнения ключа == или key.equals(...). При совпадении
этих параметров, значение элемента перезаписывается.


Таким образом, каждый элемент массива (корзина, bucket) представляет собой связный
список (linked list), в котором последовательно хранятся элементы.

Отсюда становится понятно, что:


В лучшем случае (когда в одной корзине находится не более одного элемента) – значение
по ключу можно получить за O(1);
В худшем случае (когда все элементы находятся в одной корзине, а искомый элемент
– последний в списке) – значение по ключу можно получить за O(n) (так как придется
последовательно обойти все элементы списка).


Одно очень важное замечание


В JDK 7 и ниже, для хранения пар в одной корзине используется linked list;
В JDK 8 для этой цели используется balanced tree, следовательно, в худшем случае,
значение по ключу может быть получено уже за O(log n).


Возможно, в приведенном выше тексте есть некоторые неточности, но в целом алгоритм
работы HashMap именно такой.

Ответ на Вашу непосредственную задачу расписывать не буду, так как согласен с ответом
коллеги.