Hashset vs Treeset

Jedną z zalet, o których jeszcze nie wspomniano, jest to, że its ma większą "lokalność", która jest skrótem od powiedzenia (1) jeśli dwa wpisy są w pobliżu w kolejności, a TreeSet umieszcza je blisko siebie w strukturze danych, a tym samym w pamięci; oraz (2) to umieszczenie wykorzystuje zasadę lokalności, która mówi, że podobne dane są często dostępne przez aplikację o podobnej częstotliwości.

Jest to w przeciwieństwie do HashSet, który rozprzestrzenia wpisy po całej pamięci, bez względu na wszystko ich klucze są.

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

HashSet jest O(1), Aby uzyskać dostęp do elementów, więc z pewnością 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 reklamowego) ma dla Ciebie znaczenie. Ale, jak już zauważyłeś, handlujesz zleceniem na wolniejszy czas, aby uzyskać dostęp do elementu: O (log n) dla podstawowych operacji.

Z javadocs dla TreeSet:

Ta implementacja zapewnia gwarantowany koszt czasu log (n) dla podstawowe operacje (add, remove i contains).

1.HashSet pozwala obiektowi null.

2.TreeSet nie pozwoli obiektowi null. Jeśli spróbujesz dodać wartość null, spowoduje to wywołanie NullPointerException.

3.HashSet jest znacznie szybszy niż TreeSet.

Np.

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

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine

Na podstawie 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 większość używa HashSet jest to, że operacje są (średnio) O(1) zamiast o (log n). Jeśli Zestaw zawiera standardowe elementy, nie będziesz "mieszał się z funkcjami hashowymi", jak to zostało zrobione za Ciebie. Jeśli Zestaw zawiera niestandardowe klasy, musisz zaimplementować hashCode, Aby użyć HashSet (chociaż efektywna Java pokazuje jak), ale jeśli używasz TreeSet musisz zrobić to Comparable lub dostarczyć Comparator. Może to być problem, jeśli klasa nie ma określonego porządku.

Mam czasami używane TreeSet (a właściwie TreeMap) dla bardzo małych zestawów / map (

Teraz, jeśli potrzebujesz sortowania, to TreeSet jest odpowiednie, chociaż nawet wtedy, gdy aktualizacje są częste i potrzeba sortowania wyników jest rzadka, czasami kopiowanie zawartości do listy lub tablicy i sortowanie ich może być szybsze.

Jeśli nie wstawiasz wystarczającej ilości elementów, aby spowodować częste ponowne odświeżanie (lub kolizje, jeśli twój HashSet nie może zmienić rozmiaru), HashSet z pewnością daje ci korzyść stałego dostępu w czasie. Ale na zestawach z dużą ilością wzrostu lub skurczu możesz uzyskać lepszą wydajność z zestawami drzew, w zależności od wdrożenia.

Amortyzowany czas może być bliski O(1) z funkcjonalnym czerwono-czarnym drzewem, jeśli dobrze pamiętam. Książka Okasaki ma lepsze wytłumaczenie niż ja. (Lub zobacz jego listę publikacji )

Implementacje HashSet są oczywiście o wiele szybsze - mniej narzutu, ponieważ nie ma porządkowania. Dobra analiza różnych implementacji zestawów w Javie znajduje się pod adresem http://java.sun.com/docs/books/tutorial/collections/implementations/set.html .

Dyskusja tam również wskazuje na interesujące podejście "middle ground" do pytania drzewo vs Hash. Java dostarcza LinkedHashSet, który jest Hashsetem z" zorientowaną na wstawianie " listą połączoną biegnącą przez to znaczy, że ostatni element na liście linkowanych jest również ostatnio wstawionym do Hasha. Pozwala to uniknąć niesforności nieuporządkowanego hasha bez ponoszenia zwiększonych kosztów zestawu drzew.

Zbiór drzew jest jednym z dwóch posortowanych zbiorów (drugim jest TreeMap). Wykorzystuje czerwono-czarną strukturę drzewa (ale o tym wiedziałeś) i gwarantuje że elementy będą w porządku rosnącym, zgodnie z naturalnym porządkiem. Opcjonalnie, możesz zbudować TreeSet za pomocą konstruktora, który pozwoli Ci nadać kolekcji swój własne zasady, jakie ma być zamówienie (a nie poleganie na zamówieniu zdefiniowanym by the elements ' class) za pomocą porównywarki lub komparatora

I A LinkedHashSet jest uporządkowaną wersją HashSet, która utrzymuje podwójnie połączoną listę wszystkich elementów. Użyj tej klasy zamiast HashSet kiedy zależy ci na kolejności iteracji. Po iteracji przez HashSet kolejność jest nieprzewidywalna, a Zestaw LinkedHashSet umożliwia iterację elementów w kolejności w jakiej zostały wstawione

Udzielono wielu odpowiedzi, w oparciu o względy techniczne, zwłaszcza dotyczące wydajności. Według mnie wybór między TreeSet a HashSet ma znaczenie.

Ale wolałabym powiedzieć, że wybór powinien być kierowany przez koncepcyjne najpierw rozważania.

Jeśli dla obiektów, którymi musisz manipulować, naturalne uporządkowanie nie ma sensu, nie używaj TreeSet.
Jest to zbiór uporządkowany, ponieważ implementuje SortedSet. Więc to oznacza, że musisz nadpisać function compareTo, która powinna być zgodna z tym, co zwraca function equals. Na przykład, jeśli masz zbiór obiektów klasy o nazwie Student, to nie sądzę, aby TreeSet miało sens, ponieważ nie ma naturalnego porządku między uczniami. Możesz zamówić je według średniej oceny, ok, ale to nie jest "naturalne zamówienie". Funkcja compareTo zwróci 0 nie tylko wtedy, gdy dwa obiekty reprezentują tego samego ucznia, ale także wtedy, gdy dwóch różnych uczniów ma tę samą ocenę. Dla drugiego przypadku, equals zwróci false (chyba, że zdecydujesz się, aby ten ostatni wrócił true, gdy dwóch różnych uczniów ma tę samą ocenę, co sprawi, że funkcja equals będzie miała mylące znaczenie, nie mówiąc o złym znaczeniu.)
Należy pamiętać, że spójność pomiędzy equals i compareTo jest opcjonalna, ale zdecydowanie zalecana. W przeciwnym razie umowa interfejsu Set zostanie zerwana, co sprawi, że Twój kod wprowadzi w błąd innych ludzi, co może również prowadzić do nieoczekiwanego zachowania.

This link może być dobrym źródłem informacji na ten temat.

Po co mieć jabłka, skoro można mieć pomarańcze?

Poważnie chłopaki i dziewczyny-jeśli Twoja kolekcja jest duża, czytana i pisana milionami razy, a płacisz za cykle procesora, to wybór kolekcji jest istotny tylko wtedy, gdy potrzebujesz jej, aby działała lepiej. Jednak w większości przypadków nie ma to znaczenia - kilka milisekund tu i ówdzie pozostaje niezauważone w kategoriach ludzkich. Jeśli to naprawdę tak ważne, dlaczego nie piszesz kodu w asemblerze lub C? [cue another dyskusja]. Chodzi o to, czy jesteś zadowolony z korzystania z dowolnej kolekcji, którą wybrałeś, i rozwiązuje to twój problem (nawet jeśli nie jest to najlepszy rodzaj kolekcji do zadania). Oprogramowanie jest plastyczne. W razie potrzeby zoptymalizuj swój kod. Wujek Bob mówi, że przedwczesna Optymalizacja jest źródłem wszelkiego zła. Wujek Bob tak mówi

Message Edit (complete rewrite ) gdy kolejność nie ma znaczenia, wtedy. Oba powinny dawać Log (n) - przydatne byłoby sprawdzenie, czy któryś z nich jest o ponad pięć procent szybszy od drugiego. HashSet może dać o (1) testowanie w pętli powinno 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));
    }
}