HashSet jest znacznie szybszy niż TreeSet (stały czas w porównaniu do czasu logowania dla większości operacji takich jak dodawanie, usuwanie i zawiera), ale nie oferuje żadnych gwarancji porządkowania takich jak TreeSet.
- klasa oferuje stałą wydajność czasową dla podstawowych operacji (dodawanie, usuwanie, zawieranie i rozmiar).
- nie gwarantuje to, że kolejność elementów pozostanie stała w czasie
- wydajność iteracji zależy od początkowej pojemności i współczynnika obciążenia zestawu HashSet.
- Akceptowanie domyślnego współczynnika obciążenia jest dość bezpieczne, ale możesz chcieć określić początkową pojemność, która jest około dwa razy większa niż oczekiwany zestaw.
- gwarantuje dziennik (n) koszt czasu dla podstawowych operacji (dodawanie, usuwanie i zawiera)
- gwarantuje, że elementy zestawu zostaną posortowane (rosnąco, naturalne lub określone przez ciebie za pomocą konstruktora) (implementuje
SortedSet
)
- nie oferuje żadnych parametrów dostrajania wydajności iteracji
- oferuje kilka metod przydatny do czynienia z zamówionym zestawem jak
first()
, last()
, headSet()
, i tailSet()
etc
Ważne punkty:
- Oba gwarantują zbiór elementów bez duplikatów
- Zazwyczaj szybciej jest dodawać elementy do HashSet, a następnie konwertować kolekcję do TreeSet w celu posortowanego przejścia bez sortowania.
- Żadna z tych implementacji nie jest zsynchronizowana. Oznacza to, że jeśli wiele wątków jednocześnie uzyskuje dostęp do zestawu, a co najmniej jeden z nich modyfikuje zestaw, należy go zsynchronizować zewnętrznie.
- LinkedHashSet jest w pewnym sensie pośrednim pomiędzy
HashSet
i TreeSet
. Zaimplementowana jako tabela skrótów z przeglądaną przez nią połączoną listą, zapewnia jednak iterację w kolejności wstawiania, która nie jest taka sama jak posortowane przechodzenie gwarantowane przez TreeSet .
Wybór użycia zależy więc całkowicie od twoich potrzeb, ale uważam, że nawet jeśli potrzebujesz zamówionej kolekcji, nadal powinieneś preferować HashSet, aby utworzyć Zestaw, a następnie przekształcić go w TreeSet.
- na przykład
SortedSet<String> s = new TreeSet<String>(hashSet);
Jedną z niewymienionych jeszcze zalet a
TreeSet
jest to, że ma większą „lokalizację”, co jest skrótem od powiedzenia (1) jeśli dwa wpisy są w pobliżu w kolejności, aTreeSet
umieszcza je blisko siebie w strukturze danych, a zatem w pamięci; oraz (2) to umieszczenie korzysta z zasady lokalizacji, która mówi, że podobne dane są często dostępne dla aplikacji o podobnej częstotliwości.Jest to w przeciwieństwie do
HashSet
, który rozkłada wpisy w całej pamięci, bez względu na to, jakie są ich klucze.Kiedy koszt opóźnienia odczytu z dysku twardego jest tysiące razy większy niż koszt odczytu z pamięci podręcznej lub pamięci RAM, a gdy dane są naprawdę dostępne z lokalizacją,
TreeSet
może być znacznie lepszym wyborem.źródło
TreeSet
/TreeMap
nie jest zoptymalizowana pod kątem lokalizacji przez OpenJDK . Chociaż możliwe jest użycie b-drzewa rzędu 4 do przedstawienia drzewa czerwono-czarnego, a tym samym poprawienia lokalizacji i wydajności pamięci podręcznej, nie tak działa implementacja. Zamiast tego każdy węzeł przechowuje wskaźnik do własnego klucza, własnej wartości, swojego rodzica oraz jego lewego i prawego węzła potomnego, co jest widoczne w kodzie źródłowym JDK 8 dla TreeMap.Entry .HashSet
jest O (1), aby uzyskać dostęp do elementów, więc na pewno ma to znaczenie. Ale utrzymanie porządku obiektów w zestawie nie jest możliwe.TreeSet
jest przydatny, jeśli utrzymanie zamówienia (pod względem wartości, a nie zamówienia) jest dla Ciebie ważne. Ale, jak zauważyłeś, zamieniasz zlecenie na wolniejszy czas dostępu do elementu: O (log n) dla podstawowych operacji.Z javadocs dla
TreeSet
:źródło
1.HashSet zezwala na obiekt zerowy.
2.TreeSet nie zezwoli na obiekt zerowy. Próba dodania wartości null spowoduje zgłoszenie wyjątku NullPointerException.
3.HashSet jest znacznie szybszy niż TreeSet.
na przykład
źródło
null
do swojego zestawu w żaden sposób.TreeSet<String> badassTreeSet = new TreeSet<String>(new Comparator<String>() { public int compare(String string1, String string2) { if (string1 == null) { return (string2 == null) ? 0 : -1; } else if (string2 == null) { return 1; } else { return string1.compareTo(string2); } } }); badassTreeSet.add("tree"); badassTreeSet.add("asdf"); badassTreeSet.add(null); badassTreeSet.add(null); badassTreeSet.add("set"); badassTreeSet.add("tree"); System.out.println(badassTreeSet);
Opierając się na pięknej wizualnej odpowiedzi na mapach autorstwa @shevchyk, oto moje zdanie:
źródło
Powodem, dla którego najczęściej wykorzystuje się
HashSet
to, że operacje są (średnio) O (1) zamiast O (log n). Jeśli zestaw zawiera standardowe elementy, nie będziesz „bałagać się funkcjami skrótu”, jak to zostało zrobione dla Ciebie. Jeśli zestaw zawiera niestandardowe klasy, musisz zaimplementować,hashCode
aby go używaćHashSet
(chociaż Effective Java pokazuje jak), ale jeśli używaszTreeSet
, musisz go utworzyćComparable
lub dostarczyćComparator
. Może to stanowić problem, jeśli klasa nie ma określonej kolejności.Czasem używałem
TreeSet
(lub faktycznieTreeMap
) bardzo małych zestawów / map (<10 przedmiotów), chociaż nie sprawdziłem, czy to naprawdę przyniesie jakieś korzyści. W przypadku dużych zestawów różnica może być znaczna.Teraz, jeśli potrzebujesz posortowania,
TreeSet
jest to odpowiednie, chociaż nawet wtedy, gdy aktualizacje są częste, a potrzeba posortowanego wyniku jest rzadka, czasami kopiowanie zawartości do listy lub tablicy i sortowanie może być szybsze.źródło
Jeśli nie wstawiasz wystarczającej liczby elementów, aby spowodować częste powtórzenia (lub kolizje, jeśli Twój zestaw HashSet nie może zmienić rozmiaru), zestaw HashSet z pewnością zapewnia ci ciągły dostęp do czasu. Ale w zestawach z dużym wzrostem lub kurczeniem się, możesz faktycznie uzyskać lepszą wydajność dzięki zestawom drzew, w zależności od implementacji.
Zamortyzowany czas może być zbliżony do O (1) z funkcjonalnym czerwono-czarnym drzewem, jeśli pamięć mi służy. Książka Okasakiego miałaby lepsze wytłumaczenie niż ja. (Lub zobacz jego listę publikacji )
źródło
Implementacje HashSet są oczywiście znacznie szybsze - mniej narzutu, ponieważ nie ma konieczności zamawiania. Dobra analiza różnych implementacji zestawu w Javie znajduje się na stronie http://java.sun.com/docs/books/tutorial/collections/implementations/set.html .
Dyskusja wskazuje również na interesujące podejście „środkowej podstawy” do pytania Drzewo kontra Hasz. Java zapewnia LinkedHashSet, który jest HashSet z przebiegającą przez niego połączoną listą „zorientowaną na wstawianie”, co oznacza, że ostatni element na połączonej liście jest również ostatnio wstawiony do skrótu. Pozwala to uniknąć nieuprzejmości nieuporządkowanego skrótu bez ponoszenia zwiększonych kosztów TreeSet.
źródło
TreeSet jest jednym z dwóch posortowanych kolekcjach (druga istota TreeMap). Wykorzystuje czerwono-czarną strukturę drzewa (ale wiesz o tym) i gwarantuje, że elementy będą w porządku rosnącym, zgodnie z porządkiem naturalnym. Opcjonalnie możesz zbudować TreeSet za pomocą konstruktora, który pozwoli ci nadać kolekcji własne reguły dotyczące tego, czym powinna być kolejność (zamiast polegać na kolejności zdefiniowanej przez klasę elementów) za pomocą Porównywalnego lub Porównawczego
a LinkedHashSet to uporządkowana wersja HashSet, która utrzymuje podwójnie połączoną listę we wszystkich elementach. Użyj tej klasy zamiast HashSet, jeśli zależy Ci na kolejności iteracji. Podczas iteracji za pomocą HashSet kolejność jest nieprzewidywalna, a LinkedHashSet pozwala na iterację elementów w kolejności, w której zostały wstawione
źródło
Podano wiele odpowiedzi, opartych na względach technicznych, zwłaszcza dotyczących wydajności. Według mnie wybór między
TreeSet
i maHashSet
znaczenie.Wolałbym jednak powiedzieć, że wybór powinien opierać się na względach koncepcyjnych .
Jeśli dla obiektów, które musisz manipulować, naturalne uporządkowanie nie ma sensu, nie używaj
TreeSet
.Jest to posortowany zestaw, ponieważ implementuje
SortedSet
. Oznacza to, że konieczne jest zastąpienie funkcji , ponieważ nie ma naturalnego uporządkowania między uczniami. Możesz zamówić je według ich średniej oceny, dobrze, ale to nie jest „naturalne uporządkowanie”. FunkcjonowaćcompareTo
, która powinna być spójna z funkcją zwracanąequals
. Na przykład, jeśli masz zestaw obiektów klasy o nazwie Student, to nie sądzęTreeSet
compareTo
zwróci 0 nie tylko wtedy, gdy dwa obiekty reprezentują tego samego ucznia, ale także gdy dwóch różnych uczniów ma tę samą ocenę. W drugim przypadku,equals
będzie return false (chyba że zdecydujesz się zrobić ten ostatni zwrot prawdziwe, gdy dwie różne studenci mają tę samą ocenę, która stałabyequals
funkcja mieć mylące znaczenie, żeby nie powiedzieć złego znaczenia).Warto zauważyć, że spójność
equals
icompareTo
jest opcjonalny, ale zdecydowanie zalecany. W przeciwnym razie umowa o interfejsSet
zostanie zerwana, co spowoduje, że Twój kod będzie wprowadzać w błąd w stosunku do innych osób, co może również prowadzić do nieoczekiwanego zachowania.Ten link może być dobrym źródłem informacji dotyczących tego pytania.
źródło
Po co jeść jabłka, skoro można mieć pomarańcze?
Poważnie chłopaki i dziewczęta - jeśli twoja kolekcja jest duża, czytana i zapisywana w gazillach czasów, a płacisz za cykle procesora, to wybór kolekcji jest istotny TYLKO, jeśli POTRZEBUJESZ, aby działała lepiej. Jednak w większości przypadków nie ma to większego znaczenia - kilka milisekund tu i tam jest niezauważanych z ludzkiego punktu widzenia. Jeśli to tak naprawdę miało znaczenie, dlaczego nie piszesz kodu w asemblerze lub C? [kolejna dyskusja]. Chodzi o to, czy jesteś zadowolony z korzystania z dowolnej kolekcji, którą wybrałeś, i to rozwiązuje twój problem [nawet jeśli nie jest to specjalnie najlepszy rodzaj kolekcji do zadania] powalić. Oprogramowanie jest plastyczne. W razie potrzeby zoptymalizuj kod. Wujek Bob mówi, że przedwczesna optymalizacja jest źródłem wszelkiego zła. Tak mówi wujek Bob
źródło
Edycja wiadomości ( całkowite przepisanie ) Kiedy kolejność nie ma znaczenia, wtedy. Oba powinny dać Log (n) - przydatne byłoby sprawdzenie, czy któryś z nich jest ponad pięć procent szybszy niż drugi. HashSet może dać test O (1) w pętli powinien ujawnić, czy tak jest.
źródło
źródło