Treeset and hashset in java

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

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

2. Различия

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

2.1. заказ

HashSet stores the objects in random order, whereas TreeSet applies the natural order of the elements. Рассмотрим следующий пример:

@Test public void givenTreeSet_whenRetrievesObjects_thenNaturalOrder() < Setset = new TreeSet<>(); set.add("example"); set.add("is"); set.add("Awesome"); assertEquals(3, set.size()); assertTrue(set.iterator().next().equals("Awesome")); >

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

2.2. Null Объекты

Другое отличие состоит в том, чтоHashSet can store null objects, while TreeSet does not allow them:

@Test(expected = NullPointerException.class) public void givenTreeSet_whenAddNullObject_thenNullPointer() < Setset = new TreeSet<>(); set.add("example"); set.add("is"); set.add(null); > @Test public void givenHashSet_whenAddNullObject_thenOK() < Setset = new HashSet<>(); set.add("example"); set.add("is"); set.add(null); assertEquals(3, set.size()); >

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

2.3. Спектакль

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

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

Обычно мы видим, чтоthe execution time for adding elements into TreeSet is much better than for the HashSet.

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

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

TreeSet is rich in functionalities, реализуя дополнительные методы, например:

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

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

3. сходства

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

ИTreeSet, иHashSet гарантируютduplicate-free collection of elements,, так как это часть общего интерфейсаSet:

@Test public void givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique() < Setset = new HashSet<>(); set.add("example"); set.add("example"); assertTrue(set.size() == 1); Set set2 = new TreeSet<>(); set2.add("example"); set2.add("example"); assertTrue(set2.size() == 1); >

3.2. Неsynchronized

None of the described Set implementations are synchronized. Это означает, что если несколько потоков обращаются кSet одновременно, и хотя бы один из потоков изменяет его, то он должен быть синхронизирован извне.

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

Iterators, возвращаемыеTreeSet иHashSet, работают без сбоев.

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

@Test(expected = ConcurrentModificationException.class) public void givenHashSet_whenModifyWhenIterator_thenFailFast() < Setset = new HashSet<>(); set.add("example"); Iterator it = set.iterator(); while (it.hasNext()) < set.add("Awesome"); it.next(); >>

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

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

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

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

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

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

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

Источник

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

Одной из основных задач при программировании на языке Java является выбор подходящих структур данных для решения конкретных задач. В этом контексте часто возникает вопрос о выборе между двумя популярными типами наборов, доступных в Java — HashSet и TreeSet .

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

HashSet

HashSet является одной из наиболее используемых структур данных в Java. Он использует хеширование для хранения элементов, и, следовательно, время выполнения основных операций, таких как add() , remove() и contains() , составляет в среднем константное время O(1) .

Однако HashSet не гарантирует порядок элементов. Это означает, что при добавлении элементов в HashSet , их порядок может быть произвольным.

TreeSet

TreeSet , с другой стороны, обеспечивает упорядоченность элементов. Это достигается за счет использования красно-черного дерева (формы бинарного дерева поиска) для хранения данных. Время выполнения основных операций, таких как add() , remove() и contains() , составляет O(log(n)) , где n — число элементов в наборе.

Однако это преимущество может стать недостатком, если требуется значительное количество операций вставки, удаления или поиска, поскольку TreeSet работает медленнее, чем HashSet .

Выбор между HashSet и TreeSet

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

Источник