«Сравнение HashSet и TreeSet» - Spring на русском

«1. Введение

В этой статье мы сравним две самые популярные Java-реализации интерфейса java.util.Set — HashSet и TreeSet.

2. Различия

HashSet и TreeSet являются листьями одной и той же ветки, но они отличаются несколькими важными моментами.

2.1. Порядок

HashSet хранит объекты в случайном порядке, тогда как TreeSet применяет естественный порядок элементов. Давайте посмотрим на следующий пример:

@Test
public void givenTreeSet_whenRetrievesObjects_thenNaturalOrder() {
    Set<String> set = new TreeSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add("Awesome");
 
    assertEquals(3, set.size());
    assertTrue(set.iterator().next().equals("Awesome"));
}

После добавления объектов String в TreeSet мы видим, что первый из них — «Awesome», хотя он был добавлен в самом конце. Аналогичная операция, проделанная с HashSet, не гарантирует, что порядок элементов останется неизменным с течением времени.

2.2. Нулевые объекты

Еще одно отличие состоит в том, что HashSet может хранить нулевые объекты, в то время как TreeSet не разрешает их:

@Test(expected = NullPointerException.class)
public void givenTreeSet_whenAddNullObject_thenNullPointer() {
    Set<String> set = new TreeSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add(null);
}

@Test
public void givenHashSet_whenAddNullObject_thenOK() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add(null);
 
    assertEquals(3, set.size());
}

Если мы попытаемся сохранить нулевой объект в TreeSet, операция приведет к возникновению исключения NullPointerException. Единственное исключение было в Java 7, когда в TreeSet разрешалось иметь ровно один нулевой элемент.

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

Проще говоря, HashSet быстрее, чем TreeSet.

HashSet обеспечивает производительность с постоянным временем для большинства операций, таких как add(), remove() и contains(), по сравнению с временем log(n), предлагаемым TreeSet.

Обычно мы видим, что время выполнения добавления элементов в TreeSet намного лучше, чем для HashSet.

Помните, что JVM может быть не прогрета, поэтому время выполнения может отличаться. Хорошее обсуждение того, как разрабатывать и выполнять микротесты с использованием различных реализаций Set, доступно здесь.

2.4. Реализованные методы

TreeSet обладает богатыми функциональными возможностями, реализуя дополнительные методы, такие как:

pollFirst() — для возврата первого элемента или null, если Set пуст, pollLast() — для извлечения и удаления последнего элемента , или вернуть null, если Set пуст. или null, если нет такого элемента. чем Хэшсет.

3. Сходства

3.1. Уникальные элементы

Как TreeSet, так и HashSet гарантируют коллекцию элементов без дубликатов, поскольку они являются частью универсального интерфейса Set:

3.2. Не синхронизировано

@Test
public void givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    set.add("Baeldung");
 
    assertTrue(set.size() == 1);
        
    Set<String> set2 = new TreeSet<>();
    set2.add("Baeldung");
    set2.add("Baeldung");
 
    assertTrue(set2.size() == 1);
}

Ни одна из описанных реализаций Set не синхронизирована. Это означает, что если несколько потоков одновременно получают доступ к набору и хотя бы один из потоков изменяет его, то он должен быть синхронизирован извне.

3.3. Отказоустойчивые итераторы

Итераторы, возвращаемые TreeSet и HashSet, являются отказоустойчивыми.

Это означает, что любая модификация набора в любое время после создания итератора вызовет исключение ConcurrentModificationException:

4. Какую реализацию использовать?

@Test(expected = ConcurrentModificationException.class)
public void givenHashSet_whenModifyWhenIterator_thenFailFast() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    Iterator<String> it = set.iterator();

    while (it.hasNext()) {
        set.add("Awesome");
        it.next();
    }
}

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

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

Если мы хотим, чтобы наши записи были отсортированы, нам нужно выбрать TreeSet Если мы ценим производительность больше, чем потребление памяти, мы должны выбрать HashSet Если нам не хватает память, мы должны выбрать TreeSet. Если мы хотим получить доступ к элементам, которые относительно близки друг к другу в соответствии с их естественным порядком, мы могли бы рассмотреть TreeSet, потому что он имеет большую локальность. Производительность HashSet можно настроить с помощью initialCapacity и loadFactor, который невозможен для TreeSet. Если мы хотим сохранить порядок вставки и получить выгоду от постоянного доступа по времени, мы можем использовать LinkedHashSet

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

В этой статье мы рассмотрели различия и сходства между TreeSet и Хэшсет.

Как всегда, примеры кода для этой статьи доступны на GitHub.

«Сравнение HashSet и TreeSet»