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

1. Въведение

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

2. Различия

HashSet и TreeSet са листа от един и същ клон, но те се различават по няколко важни въпроса.

2.1. Поръчка

HashSet съхранява обектите в произволен ред, докато TreeSet прилага естествения ред на елементите. Нека да видим следния пример:

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

След добавяне на обектите String в TreeSet , виждаме, че първият е „Страхотен“, въпреки че е добавен в самия край. Подобна операция, извършена с HashSet , не гарантира, че редът на елементите ще остане постоянен във времето.

2.2. Null Обекти

Друга разлика е, че HashSet може да съхранява нулеви обекти, докато TreeSet не ги позволява :

@Test(expected = NullPointerException.class) public void givenTreeSet_whenAddNullObject_thenNullPointer() { Set set = new TreeSet(); set.add("Baeldung"); set.add("is"); set.add(null); } @Test public void givenHashSet_whenAddNullObject_thenOK() { Set 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 е празен
  • first () - за връщане на първия елемент
  • last () - за връщане на последния елемент
  • таван () - за връщане на най-малкия елемент, по-голям или равен на дадения елемент, или null, ако няма такъв елемент
  • lower () - за връщане на най-големия елемент, строго по-малък от дадения елемент, или null, ако няма такъв елемент

Споменатите по-горе методи правят TreeSet много по-лесен за използване и по-мощен от HashSet .

3. Прилики

3.1. Уникални елементи

Както TreeSet, така и HashSet гарантират събиране на елементи без дубликати, тъй като е част от общия интерфейс Set :

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

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

Нито една от описаните реализации на Set не се синхронизира . Това означава, че ако множество нишки имат достъп едновременно до Set и поне една от нишките го модифицира, то той трябва да бъде синхронизиран външно.

3.3. Неуспешни итератори

В итератор е върната от TreeSet и HashSet са се провали-бързо.

Това означава, че всяка модификация на набора по всяко време след създаването на итератора ще изведе ConcurrentModificationException:

@Test(expected = ConcurrentModificationException.class) public void givenHashSet_whenModifyWhenIterator_thenFailFast() { Set set = new HashSet(); set.add("Baeldung"); Iterator it = set.iterator(); while (it.hasNext()) { set.add("Awesome"); it.next(); } }

4. Коя реализация да използвам?

И двете изпълнения изпълняват договора на идеята за набор, така че зависи от контекста, коя реализация бихме могли да използваме.

Here are few quick points to remember:

  • If we want to keep our entries sorted, we need to go for the TreeSet
  • If we value performance more than memory consumption, we should go for the HashSet
  • If we are short on memory, we should go for the TreeSet
  • If we want to access elements that are relatively close to each other according to their natural ordering, we might want to consider TreeSet because it has greater locality
  • HashSet‘s performance can be tuned using the initialCapacity and loadFactor, which is not possible for the TreeSet
  • If we want to preserve insertion order and benefit from constant time access, we can use the LinkedHashSet

5. Conclusion

В тази статия разгледахме разликите и приликите между TreeSet и HashSet .

Както винаги, примерите за кодове за тази статия са достъпни в GitHub.