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

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("ForEach");
    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("ForEach");
    set.add("is");
    set.add(null);
}

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

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

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

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

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

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

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

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

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

• pollFirst() — вернуть первый элемент или ноль , если Set пуст
• pollLast() — для извлечения и удаления последнего элемента или возврата null , если Set пуст
• first() — вернуть первый элемент
• last() — вернуть последний элемент
• потолок () — вернуть наименьший элемент, больший или равный заданному элементу, или ноль , если такого элемента нет
• lower() — вернуть самый большой элемент, строго меньший заданного элемента, либо null , если такого элемента нет

Упомянутые выше методы делают TreeSet более простым в использовании и более мощным, чем HashSet .

3. Сходства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Вывод

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

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