«1. Обзор

В этой статье мы углубимся в HashSet. Это одна из самых популярных реализаций Set, а также неотъемлемая часть Java Collections Framework.

2. Знакомство с HashSet

HashSet — одна из основных структур данных в Java Collections API.

Давайте вспомним наиболее важные аспекты этой реализации:

    Он хранит уникальные элементы и допускает пустые значения. Он поддерживается HashMap. Не поддерживает порядок вставки. при создании экземпляра HashSet:

Если вы хотите глубже понять, как работает HashMap, вы можете прочитать статью, посвященную этому, здесь. 

public HashSet() {
    map = new HashMap<>();
}

3. API

В этом разделе мы рассмотрим наиболее часто используемые методы и рассмотрим несколько простых примеров.

3.1. add()

Метод add() можно использовать для добавления элементов в набор. В контракте метода указано, что элемент будет добавлен только в том случае, если его еще нет в наборе. Если элемент был добавлен, метод возвращает true, иначе — false.

Мы можем добавить элемент в HashSet следующим образом:

С точки зрения реализации, метод add чрезвычайно важен. Детали реализации иллюстрируют, как HashSet работает внутри и использует метод put HashMap: 

@Test
public void whenAddingElement_shouldAddElement() {
    Set<String> hashset = new HashSet<>();
 
    assertTrue(hashset.add("String Added"));
}

Переменная map является ссылкой на внутренний поддерживающий HashMap: сначала с хэш-кодом, чтобы получить подробное представление о том, как элементы организованы в структурах данных на основе хэшей. 

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

Резюмируя: 

private transient HashMap<E, Object> map;

HashMap — это массив сегментов с емкостью по умолчанию 16 элементов — каждому сегменту соответствует разное значение хэш-кода. Если разные объекты имеют одинаковое значение хэш-кода, они сохраняются в одном сегменте. Если достигается коэффициент загрузки, создается новый массив, вдвое превышающий размер предыдущего, и все элементы повторно хешируются и перераспределяются между новыми соответствующими сегментами. Чтобы получить значение, мы хэшируем ключ, модифицируем его, а затем переходим к соответствующему сегменту и поиск по потенциально связанному списку в случае наличия более одного объекта

3.2. contains()

    Целью метода contains является проверка наличия элемента в заданном HashSet. Возвращает true, если элемент найден, иначе false.

Мы можем проверить наличие элемента в HashSet:

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

3.3. remove() 

@Test
public void whenCheckingForElement_shouldSearchForElement() {
    Set<String> hashsetContains = new HashSet<>();
    hashsetContains.add("String Added");
 
    assertTrue(hashsetContains.contains("String Added"));
}

Метод удаляет указанный элемент из набора, если он присутствует. Этот метод возвращает true, если набор содержит указанный элемент.

Давайте посмотрим на рабочий пример:

3.4. clear()

Мы используем этот метод, когда собираемся удалить все элементы из набора. Базовая реализация просто удаляет все элементы из базового HashMap. 

@Test
public void whenRemovingElement_shouldRemoveElement() {
    Set<String> removeFromHashSet = new HashSet<>();
    removeFromHashSet.add("String Added");
 
    assertTrue(removeFromHashSet.remove("String Added"));
}

Давайте посмотрим, что в действии:

3.5. size()

Это один из основных методов API. Он широко используется, поскольку помогает определить количество элементов, присутствующих в HashSet. Базовая реализация просто делегирует вычисление методу size() HashMap. 

@Test
public void whenClearingHashSet_shouldClearHashSet() {
    Set<String> clearHashSet = new HashSet<>();
    clearHashSet.add("String Added");
    clearHashSet.clear();
    
    assertTrue(clearHashSet.isEmpty());
}

Давайте посмотрим, что в действии:

3.6. isEmpty()

Мы можем использовать этот метод, чтобы выяснить, является ли данный экземпляр HashSet пустым или нет. Этот метод возвращает true, если набор не содержит элементов: 

@Test
public void whenCheckingTheSizeOfHashSet_shouldReturnThesize() {
    Set<String> hashSetSize = new HashSet<>();
    hashSetSize.add("String Added");
    
    assertEquals(1, hashSetSize.size());
}

3.7. iterator()

Метод возвращает итератор для элементов в наборе. Элементы посещаются в произвольном порядке, а итераторы работают безотказно. 

@Test
public void whenCheckingForEmptyHashSet_shouldCheckForEmpty() {
    Set<String> emptyHashSet = new HashSet<>();
    
    assertTrue(emptyHashSet.isEmpty());
}

Мы можем наблюдать случайный порядок итерации здесь:

Если набор изменяется в любое время после создания итератора любым способом, кроме как с помощью собственного метода удаления итератора, итератор выдает исключение ConcurrentModificationException.

Давайте посмотрим, что в действии: 

@Test
public void whenIteratingHashSet_shouldIterateHashSet() {
    Set<String> hashset = new HashSet<>();
    hashset.add("First");
    hashset.add("Second");
    hashset.add("Third");
    Iterator<String> itr = hashset.iterator();
    while(itr.hasNext()){
        System.out.println(itr.next());
    }
}

В качестве альтернативы, если бы мы использовали метод удаления итератора, мы бы не столкнулись с исключением:

«

@Test(expected = ConcurrentModificationException.class)
public void whenModifyingHashSetWhileIterating_shouldThrowException() {
 
    Set<String> hashset = new HashSet<>();
    hashset.add("First");
    hashset.add("Second");
    hashset.add("Third");
    Iterator<String> itr = hashset.iterator();
    while (itr.hasNext()) {
        itr.next();
        hashset.remove("Second");
    }
}

«Безотказное поведение итератора не может быть гарантировано, поскольку невозможно дать какие-либо жесткие гарантии при наличии несинхронизированной параллельной модификации. 

@Test
public void whenRemovingElementUsingIterator_shouldRemoveElement() {
 
    Set<String> hashset = new HashSet<>();
    hashset.add("First");
    hashset.add("Second");
    hashset.add("Third");
    Iterator<String> itr = hashset.iterator();
    while (itr.hasNext()) {
        String element = itr.next();
        if (element.equals("Second"))
            itr.remove();
    }
 
    assertEquals(2, hashset.size());
}

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

4. Как HashSet поддерживает уникальность?

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

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

Итак, объекты в пределах одного сегмента будут сравниваться с помощью метода equals().

5. Производительность HashSet

На производительность HashSet в основном влияют два параметра — его начальная емкость и коэффициент загрузки.

Ожидаемая временная сложность добавления элемента в набор составляет O(1), которая может упасть до O(n) в худшем случае (присутствует только одно ведро) — поэтому важно поддерживать правильный HashSet емкость.

Важное примечание: начиная с JDK 8 временная сложность в наихудшем случае составляет O(log*n).

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

Мы также можем создать HashSet с пользовательскими значениями начальной емкости и коэффициента загрузки:

В первом случае используются значения по умолчанию — начальная емкость 16 и коэффициент загрузки 0,75. Во втором мы переопределяем емкость по умолчанию, а в третьем мы переопределяем обе. 

Set<String> hashset = new HashSet<>();
Set<String> hashset = new HashSet<>(20);
Set<String> hashset = new HashSet<>(20, 0.5f);

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

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

Эмпирическое правило:

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

    Следовательно, , очень важно найти правильный баланс между ними. Обычно реализация по умолчанию оптимизирована и работает просто отлично, если мы почувствуем необходимость настроить эти параметры в соответствии с требованиями, нам нужно действовать разумно.

6. Заключение

В этой статье мы описали полезность HashSet, его назначение, а также лежащую в его основе работу. Мы увидели, насколько он эффективен с точки зрения удобства использования, учитывая его постоянную производительность и способность избегать дублирования.

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

Как всегда, фрагменты кода можно найти на GitHub.

«