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

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

Набор

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

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

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

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

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

Интерфейс Set фото

2. Класс HashSet

Класс HashSet реализует интерфейс Set и создает коллекцию, которая хранит элементы в хеш-таблице.

Хеш-таблица

Что же такое хеш-таблица? Элементы хеш-таблицы хранятся в виде пар ключ-значение. Ключ определяет ячейку (или бакет) для хранения значения. Содержимое ключа служит для определения однозначного значения, называемого хеш-кодом.
Мы можем считать, что хеш-код это ID объекта, хотя он необязательно должен быть уникальным. Этот хеш-код служит далее в качестве индекса, по которому сохраняются данные, связанные с ключом.

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

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

Ключ Алгоритм хеш-кода Хеш-код
Alex
A(1) + l(12) + e(5) + x(24)
42
Bob
B(2) + o(15) + b(2)
19
Dirk
D(4) + i(9) + r(18) + k(11)
42
Fred
F(6) + r(18) + e(5) + d(4)
33

Использование hashCode() - фото

Допустим, чтобы получить хеш-код, я сопоставляю каждый символ из ключа с номером этого символа в алфавите и получаю их сумму. Таким образом "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()

Эффективным алгоритмом для определения хеш-кода объекта является такой алгоритм, который ровным слоем распределяет объекты по хеш-таблице. Вообще создание такого алгоритма, это достаточно сложный процесс, на котором защищают докторские диссертации. Но хорошей новостью является то, что на самом деле Вам не нужно придумывать свой алгоритм.
В средствах разработки, в частности в IntelliJ IDEA, существует генератор, который сгенерирует Вам метод 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

Выгода от хеширования состоит в том, что оно обеспечивает постоянство время выполнения операций add(), contains(), remove() и size(), даже для больших наборов. Сложность выполнения операций будет О(1). В худшем случае (если в хэш-таблице только один bucket) сложность выполнения будет O(n) для Java 7 и О(log n) для Java 8.
Недостаток класса 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);
    }
}
Read also:
Trustpilot
Trustpilot
Comments