Перейти к основному содержимому

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

· 6 мин. чтения

1. Обзор​

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

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

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

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

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

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

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

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

3. API​

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

3.1. добавлять()​

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

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

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

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

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

Переменная карты является ссылкой на внутреннюю поддержку HashMap:

private transient HashMap<E, Object> map;

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

Резюмируя:

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

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

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

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

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

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

3.3. удалять()​

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

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

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

3.4. Чисто()​

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

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

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

3.5. размер()​

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

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

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

3.6. пустой()​

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

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

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

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

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

@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());
    }
}

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

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

@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 с пользовательскими значениями начальной емкости и коэффициента загрузки :

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

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

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

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

**

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

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

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

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

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

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

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