Интерфейс Set и классы HashSet, LinkedHashSet

1. Интерфейс Set

Интерфейс Set определяет множество (набор).

Он расширяет Collection и определяет поведение коллекций, не допускающих дублирования элементов. Таким образом, метод add() возвращает false, если делается попытка добавить дублированный элемент в набор. 

Интерфейс не определяет никаких собственных дополнительных методов. 

Интерфейс Set заботится об уникальности хранимых объектов, уникальность определятся реализацией метода equals(). Поэтому если объекты создаваемого класса будут добавляться в Set, желательно переопределить метод equals().

Ниже представлена ветка иерархии интерфейса Set:

2. Класс HashSet

Хеш-таблица

Вычисление хеш-кода

Рассмотрим пример вычисления хеш-кодов:

Допустим, чтобы получить хеш-код, я сопоставляю каждый символ из ключа с номером этого символа в алфавите и получаю их сумму. Таким образом "Bob" попадает в бакет 19, "Fred" в бакет 33. Как видно из примера, для ключей "Alex" и "Dirk" получается одинаковый хеш-код, что тоже допустимо. Такая ситуация называется коллизией, два значения попадают в один бакет с номером 42. 

Каким образом происходит обратный процесс - поиск элемента в хеш-таблице? У нас есть ключ объекта, по которому мы вычисляем хеш-код и определяем бакет, в котором находится наш объект. Но что делать если в бакете находится не один, а несколько элементов? Конечно, же это не значит, что хеш-таблица вернет любой объект из бакета. Если объектов в бакете несколько, далее с помощью метода equals() определяется нужный объект.

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

Как Вы уже поняли, методы hashCode() и equals() тесно связаны между собой. Поэтому существуют специальный контракт написания методов hashCode() и equals():

1. Для одного и того же объекта, хеш-код всегда будет одинаковым.
2. Если объекты одинаковые, то и хеш-коды одинаковые (но не наоборот).
3. Если хеш-коды равны, то входные объекты не всегда равны.
4. Если хеш-коды разные, то и объекты гарантированно будут разные.

На самом деле, корректным, но не эффективным может быть такое определение хеш-кода:

@Override
public int hashCode() {
     return 1;
}

Это определение метода hashCode() соответствует контракту, но он разместит все объекты класса в один бакет, что нивелирует все достоинства хеш-таблицы. 

Создание метода hashCode()

Конструкторы класса HashSet

Давайте рассмотрим конструкторы класса HashSet:

• HashSet() - начальная емкость по умолчанию (initialCapacity) – 16, коэффициент загрузки по умолчанию (loadFactor) – 0,75.
• HashSet(int initialCapacity) - коэффициент загрузки – 0,75.
• HashSet(int initialCapacity, float loadFactor)
• HashSet(Collection collection) – конструктор, добавляющий элементы из другой коллекции.

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

Начальная емкость (initial capacity) – это изначальное количество ячеек (buckets) в хэш-таблице. Если все ячейки будут заполнены, их количество увеличится автоматически.

Коэффициент загрузки (load factor) – это показатель того, насколько заполненным может быть HashSet до того момента, когда его емкость автоматически увеличится. Когда количество элементов в HashSet становится больше, чем capacity * loadfactor, хэш-таблица ре-хэшируется (заново вычисляются хэшкоды элементов, и таблица перестраивается согласно полученным значениям) и количество buckets в ней увеличивается в два раза.

Коэффициент загрузки, равный 0,75, в среднем обеспечивает хорошую производительность. Если этот параметр увеличить, тогда уменьшится нагрузка на память (так как это уменьшит количество операций ре-хэширования и перестраивания), но это повлияет на операции добавления и поиска. Чтобы минимизировать время, затрачиваемое на ре-хэширование, нужно правильно подобрать параметр начальной емкости. 

Достоинства и недостатки класса HashSet

Пример использования класса HashSet

Рассмотрим пример использования класса HashSet:

import java.util.HashSet;
import java.util.Set;

public class HashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();

        set.add("Харьков");
        set.add("Киев");
        set.add("Львов");
        set.add("Кременчуг");
        set.add("Харьков");

        System.out.println(set);
    }
}

3. Класс LinkedHashSet

Класс LinkedHashSet языка Java расширяет HashSet, не добавляя никаких новых методов.

LinkedHashSet поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор. Но это приводит к тому что класс LinkedHashSet выполняет операции дольше чем класс HashSet.

Рассмотрим пример использования класса LinkedHashSet:

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<>();

        set.add("Бета");
        set.add("Aльфa");
        set.add("Этa");
        set.add("Гaммa");
        set.add("Эпсилон");
        set.add("Oмeгa");

        System.out.println(set);
    }
}