Рубрики
Без рубрики

Руководство по HashSet в Java

Краткое, но всестороннее введение в HashSet на Java.

Автор оригинала: baeldung.

1. Обзор

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

2. Введение в HashSet

HashSet – это одна из фундаментальных структур данных в Java Collections API .

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

  • Он хранит уникальные элементы и допускает нули
  • Он поддерживается хэш-картой
  • Он не поддерживает порядок вставки
  • Это не потокобезопасно

Обратите внимание, что этот внутренний HashMap инициализируется при создании экземпляра HashSet :

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

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

3. API

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

3.1. добавить()

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

Мы можем добавить элемент в HashSet like:

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

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

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

Переменная map является ссылкой на внутреннюю, резервную HashMap:

private transient HashMap map;

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

Подведение:

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

3.2. содержит()

Цель метода contains состоит в том, чтобы проверить, присутствует ли элемент в данном HashSet . Он возвращает true если элемент найден, в противном случае false.

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

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

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

3.3. удалить()

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

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

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

3.4. очистить()

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

Давайте посмотрим на это в действии:

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

3.5. размер()

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

Давайте посмотрим на это в действии:

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

3.6. isEmpty()

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

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

3.7. итератор()

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

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

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

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

Давайте посмотрим на это в действии:

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

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

@Test
public void whenRemovingElementUsingIterator_shouldRemoveElement() {
 
    Set hashset = new HashSet<>();
    hashset.add("First");
    hashset.add("Second");
    hashset.add("Third");
    Iterator 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) в худшем случае (присутствует только одно ведро) – поэтому важно поддерживать правильную емкость хэш-набора.

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

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

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

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

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

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

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

Как правило большого пальца:

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

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

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

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

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

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

Читайте ещё по теме: