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 .