Hashset vs Treeset

495

Zawsze kochałem drzewa, takie ładne O(n*log(n))i uporządkowane. Jednak każdy inżynier oprogramowania, którego znałem, spytał mnie wyraźnie, dlaczego miałbym go użyć TreeSet. Z tła CS nie sądzę, żeby miało to tak duże znaczenie, z jakiego korzystasz, i nie dbam o to, aby bawić się funkcjami skrótu i ​​segmentami (w przypadku Java).

W jakich przypadkach powinienem użyć HashSetponad TreeSet?

heymatthew
źródło

Odpowiedzi:

859

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.

HashSet

  • 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.

TreeSet

  • 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 HashSeti 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);
sactiw
źródło
38
Tylko ja stwierdzam, że stwierdzenie „HashSet jest znacznie szybsze niż TreeSet (czas stały kontra czas dziennika ...)” jest po prostu błędne? Po pierwsze, chodzi o złożoność czasu, a nie o czas bezwzględny, a O (1) może być w zbyt wielu przypadkach wolniejsze niż O (f (N)). Po drugie, że O (logN) to „prawie” O (1). Nie zdziwiłbym się, gdyby w wielu typowych przypadkach TreeSet przewyższał HashSet.
lvella
22
Chcę tylko powtórzyć komentarz Ivelli. złożoność czasu NIE jest tym samym, co czas działania, a O (1) nie zawsze jest lepsze niż O (2 ^ n). Przewrotny przykład ilustruje tę kwestię: rozważ zestaw skrótów za pomocą algorytmu skrótu, który wymagał wykonania 1 biliona instrukcji maszyny (O (1)) w porównaniu do dowolnej wspólnej implementacji sortowania bąbelkowego (O (N ^ 2) średnia / najgorsza) dla 10 elementów . Sortowanie bąbelkowe wygrywa za każdym razem. Chodzi o to, że klasy algorytmów uczą wszystkich myśleć o przybliżeniach przy użyciu złożoności czasowej, ale w świecie rzeczywistym czynniki stałe MASZĄ często.
Peter Oehlert,
17
Być może to tylko ja, ale czy rada, aby najpierw dodać wszystko do zestawu skrótów, a następnie ukryć to w zestawie drzew, nie jest straszna? 1) Wstawianie do zestawu skrótów jest szybkie tylko wtedy, gdy znasz z góry rozmiar swojego zestawu danych, w przeciwnym razie zapłacisz O (n) ponowne mieszanie, być może wiele razy. oraz 2) Płacisz za wstawienie TreeSet i tak podczas konwersji zestawu. (z zemstą, ponieważ iteracja przez skrót nie jest zbyt wydajna)
TinkerTank
5
Ta rada opiera się na fakcie, że w przypadku zestawu przed dodaniem należy sprawdzić, czy element jest duplikatem; dlatego zaoszczędzisz czas eliminując duplikaty, jeśli używasz zestawu skrótów zamiast zestawu drzew. Jednak biorąc pod uwagę cenę, jaką należy zapłacić za utworzenie drugiego zestawu dla duplikatów, odsetek duplikatów powinien być naprawdę świetny, aby pokonać tę cenę i sprawić, że oszczędza się czas. I oczywiście dotyczy to średnich i dużych zestawów, ponieważ w przypadku małego zestawu zestaw drzew jest prawdopodobnie szybszy niż zestaw skrótów.
SylvainL
5
@PeterOehlert: proszę podać dla tego punkt odniesienia. Rozumiem twój punkt widzenia, ale różnica między oboma zestawami nie ma większego znaczenia przy małych rozmiarach kolekcji. I gdy tylko zestaw dojdzie do punktu, w którym wdrożenie ma znaczenie, log (n) staje się problemem. Ogólnie rzecz biorąc, funkcje skrótu (nawet te złożone) są o rząd wielkości szybsze niż kilka braków pamięci podręcznej (które masz na ogromnych drzewach dla prawie każdego poziomu dostępu), aby znaleźć / uzyskać dostęp / dodać / zmodyfikować liść. Przynajmniej takie jest moje doświadczenie z tymi dwoma zestawami w Javie.
Bramkarz
38

Jedną z niewymienionych jeszcze zalet a TreeSetjest 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ą, TreeSetmoże być znacznie lepszym wyborem.

Carl Andersen
źródło
3
Czy możesz zademonstrować, że jeśli w pobliżu znajdują się dwa wpisy, TreeSet umieszcza je blisko siebie w strukturze danych, a zatem w pamięci ?
David Soroko,
6
Zupełnie nie ma znaczenia dla Javy. Elementy zestawu i tak są Obiektami i wskazują gdzie indziej, więc nie oszczędzasz dużo.
Andrew Gallasch,
Poza innymi komentarzami dotyczącymi ogólnie braku lokalizacji w Javie, implementacja TreeSet/ TreeMapnie 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 .
kbolino
25

HashSetjest 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.

TreeSetjest 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 dlaTreeSet :

Ta implementacja zapewnia gwarantowany koszt dziennika (n) czasu dla podstawowych operacji ( add, removei contains).

duffymo
źródło
22

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

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine
SuReN
źródło
3
ts.add (null) będzie działać poprawnie w przypadku TreeSet, jeśli null zostanie dodany jako pierwszy obiekt w TreeSet. I każdy obiekt dodany po tym da NullPointerException w metodzie compareTo w Komparatorze.
Shoaib Chikate
2
Naprawdę nie powinieneś dodawać nulldo swojego zestawu w żaden sposób.
puszysty
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);
Dávid Horváth,
21

Opierając się na pięknej wizualnej odpowiedzi na mapach autorstwa @shevchyk, oto moje zdanie:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
   Property          HashSet             TreeSet           LinkedHashSet   
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                no guarantee order  sorted according                       
   Order       will remain constant to the natural        insertion-order  
                    over time          ordering                            
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
 Add/remove           O(1)              O(log(n))             O(1)         
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                                      NavigableSet                         
  Interfaces           Set                Set                  Set         
                                       SortedSet                           
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                                       not allowed                         
  Null values        allowed        1st element only        allowed        
                                        in Java 7                          
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
                 Fail-fast behavior of an iterator cannot be guaranteed      
   Fail-fast   impossible to make any hard guarantees in the presence of     
   behavior              unsynchronized concurrent modification              
╠══════════════╬═══════════════════════════════════════════════════════════════╣
      Is                                                                     
 synchronized               implementation is not synchronized               
╚══════════════╩═══════════════════════════════════════════════════════════════╝
kiedysktos
źródło
13

Powodem, dla którego najczęściej wykorzystuje się HashSetto, ż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ć, hashCodeaby go używać HashSet(chociaż Effective Java pokazuje jak), ale jeśli używasz TreeSet, musisz go utworzyć Comparablelub 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, TreeSetjest 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.

Kathy Van Stone
źródło
wszelkie punkty danych dla tych dużych elementów, takich jak 10K lub więcej
kuhajeyan
11

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 )

JasonTrue
źródło
7

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.

Joseph Weissman
źródło
4

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

subhash laghate
źródło
3

Podano wiele odpowiedzi, opartych na względach technicznych, zwłaszcza dotyczących wydajności. Według mnie wybór między TreeSeti ma HashSetznaczenie.

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ęTreeSetcompareTozwró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, equalsbędzie return false (chyba że zdecydujesz się zrobić ten ostatni zwrot prawdziwe, gdy dwie różne studenci mają tę samą ocenę, która stałaby equalsfunkcja mieć mylące znaczenie, żeby nie powiedzieć złego znaczenia).
Warto zauważyć, że spójność equalsi compareTojest 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.

Marek Stanley
źródło
3

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

użytkownik924272
źródło
1

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.

Nicholas Jordan
źródło
-3
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}
gli00001
źródło
1
W poście napisano, że generalnie szybsze jest dodawanie elementów do HashSet, a następnie konwertowanie kolekcji na TreeSet w celu posortowanego sortowania bez duplikatów. Ustaw <String> s = nowy TreeSet <String> (hashSet); Zastanawiam się, dlaczego nie ustawić <String> s = nowy TreeSet <String> (), jeśli wiemy, że będzie on używany do posortowanej iteracji, więc dokonałem tego porównania, a wynik pokazał, co jest szybsze.
gli00001
„W jakich przypadkach chciałbym użyć zestawu HashSet zamiast zestawu TreeSet?”
Austin Henley,
1
Chodzi mi o to, że jeśli potrzebujesz zamówienia, użycie TreeSet sam jest lepsze niż wkładanie wszystkiego do HashSet, niż tworzenie TreeSet na podstawie tego HashSet. Nie widzę wartości HashSet + TreeSet w ogóle z oryginalnego postu.
gli00001
@ gli00001: nie trafiłeś w sedno. Jeśli nie zawsze potrzebujesz sortować swój zestaw elementów, ale zamierzasz nim manipulować dość często, warto użyć skrótu, aby przez większość czasu korzystać z szybszych operacji. Dla okazjonalnych czasach, w których trzeba przetwarzać elementy w kolejności, a potem po prostu owinąć z TreeSet. Zależy to od twojego przypadku użycia, ale nie jest to zbyt rzadki przypadek użycia (i to prawdopodobnie zakłada zestaw, który nie zawiera zbyt wielu elementów i ze złożonymi regułami porządkowania).
haylem