Hashset vs Treeset

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?

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);

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.

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

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

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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

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.

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 )

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.

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

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.

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

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.

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));
    }
}