Hashset gegen Treeset

Ich habe Bäume immer geliebt, so schön O(n*log(n)) und ordentlich. Jeder Softwareentwickler, den ich jemals gekannt habe, hat mich jedoch ausdrücklich gefragt, warum ich a verwenden würde TreeSet. Vor dem Hintergrund eines CS denke ich nicht, dass es so wichtig ist, was Sie verwenden, und es ist mir egal, ob ich mit Hash-Funktionen und Buckets herumspiele (im Fall vonJava ).

In welchen Fällen sollte ich ein HashSetüber ein verwenden TreeSet?

HashSet ist viel schneller als TreeSet (konstante Zeit gegenüber Protokollzeit für die meisten Vorgänge wie Hinzufügen, Entfernen und Enthalten), bietet jedoch keine Bestellgarantien wie TreeSet.

HashSet

• Die Klasse bietet eine konstante Zeitleistung für die grundlegenden Operationen (Hinzufügen, Entfernen, Enthalten und Größe).
• Es kann nicht garantiert werden, dass die Reihenfolge der Elemente über die Zeit konstant bleibt
• Die Iterationsleistung hängt von der Anfangskapazität und dem Auslastungsfaktor des HashSet ab.
  • Es ist ziemlich sicher, den Standardladefaktor zu akzeptieren, aber Sie können eine Anfangskapazität angeben, die ungefähr doppelt so groß ist, wie Sie erwarten, dass der Satz wächst.

TreeSet

• garantiert log (n) Zeitkosten für die Grundoperationen (Hinzufügen, Entfernen und Enthalten)
• garantiert, dass Elemente der Menge sortiert werden (aufsteigend, natürlich oder von Ihnen über den Konstruktor angegeben) (implementiert) SortedSet )
• bietet keine Optimierungsparameter für die Iterationsleistung
• bietet ein paar praktischen Methoden mit der geordneten Menge zu tun , wie first(), last(), headSet(), und tailSet()etc

Wichtige Punkte:

• Beide garantieren eine doppelte Sammlung von Elementen
• Im Allgemeinen ist es schneller, Elemente zum HashSet hinzuzufügen und die Sammlung dann in ein TreeSet zu konvertieren, um eine duplikationsfreie sortierte Durchquerung zu erzielen.
• Keine dieser Implementierungen ist synchronisiert. Das heißt, wenn mehrere Threads gleichzeitig auf eine Gruppe zugreifen und mindestens einer der Threads die Gruppe ändert, muss sie extern synchronisiert werden.
• LinkedHashSet liegt in gewisser Weise zwischen HashSetund TreeSet. Es wird als Hash-Tabelle implementiert, durch die eine verknüpfte Liste läuft. Es bietet jedoch eine Iteration in Einfügungsreihenfolge, die nicht mit der von TreeSet garantierten sortierten Durchquerung identisch ist .

Die Wahl der Verwendung hängt also ganz von Ihren Anforderungen ab, aber ich bin der Meinung, dass Sie HashSet auch dann bevorzugen sollten, wenn Sie eine geordnete Sammlung benötigen, um das Set zu erstellen und es dann in TreeSet zu konvertieren.

• z.B SortedSet<String> s = new TreeSet<String>(hashSet);

Ein Vorteil, der von a noch nicht erwähnt wurde, TreeSetbesteht darin, dass es eine größere "Lokalität" hat, was kurz gesagt ist: (1) Wenn zwei Einträge in der Reihenfolge TreeSetnahe beieinander liegen , platziert a sie in der Datenstruktur und damit im Speicher nahe beieinander; und (2) diese Platzierung nutzt das Prinzip der Lokalität, das besagt, dass auf ähnliche Daten häufig von einer Anwendung mit ähnlicher Häufigkeit zugegriffen wird.

Dies steht im Gegensatz zu a HashSet, das die Einträge im gesamten Speicher verteilt, unabhängig von ihren Schlüsseln.

Wenn die Latenzkosten für das Lesen von einer Festplatte das Tausendfache der Kosten für das Lesen aus dem Cache oder RAM betragen und wenn auf die Daten tatsächlich lokal zugegriffen wird, TreeSetkann dies eine viel bessere Wahl sein.

HashSetist O (1), um auf Elemente zuzugreifen, also ist es sicherlich wichtig. Es ist jedoch nicht möglich, die Reihenfolge der Objekte im Set beizubehalten.

TreeSetist nützlich, wenn die Aufrechterhaltung einer Reihenfolge (in Bezug auf Werte und nicht die Einfügereihenfolge) für Sie von Bedeutung ist. Wie Sie bereits bemerkt haben, tauschen Sie die Order für eine langsamere Zeit, um auf ein Element zuzugreifen: O (log n) für grundlegende Operationen.

Aus den Javadocs fürTreeSet :

Diese Implementierung bietet garantierte log (n) Zeitkosten für die Basisoperationen ( add, removeund contains).

1.HashSet erlaubt Nullobjekt.

2.TreeSet lässt kein Nullobjekt zu. Wenn Sie versuchen, einen Nullwert hinzuzufügen, wird eine NullPointerException ausgelöst.

3.HashSet ist viel schneller als TreeSet.

z.B

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

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

Basierend auf einer schönen visuellen Antwort auf Karten von @shevchyk hier ist meine Einstellung:

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

Der Grund, warum am häufigsten verwendet HashSetwird, ist, dass die Operationen (im Durchschnitt) O (1) anstelle von O (log n) sind. Wenn das Set Standardelemente enthält, werden Sie nicht "mit Hash-Funktionen herumspielen", wie dies für Sie getan wurde. Wenn der Satz benutzerdefinierte Klassen enthält, müssen Sie ihn implementieren, um ihn hashCodezu verwenden HashSet(obwohl Effective Java zeigt, wie), aber wenn Sie a verwenden TreeSet, müssen Sie ihn erstellen Comparableoder a angeben Comparator. Dies kann ein Problem sein, wenn die Klasse keine bestimmte Reihenfolge hat.

Ich habe manchmal verwendet TreeSet(oder tatsächlichTreeMap ) für sehr kleine Sets / Karten (<10 Elemente) verwendet, obwohl ich nicht überprüft habe, ob dies einen echten Gewinn bringt. Bei großen Sets kann der Unterschied erheblich sein.

Wenn Sie nun die Sortierung benötigen, TreeSetist dies angemessen. Auch wenn Aktualisierungen häufig sind und nur selten ein sortiertes Ergebnis erforderlich ist, kann es manchmal schneller sein, den Inhalt in eine Liste oder ein Array zu kopieren und zu sortieren.

Wenn Sie nicht genügend Elemente einfügen, um häufige Wiederholungen (oder Kollisionen, wenn die Größe Ihres HashSet nicht geändert werden kann) durchzuführen, bietet Ihnen ein HashSet mit Sicherheit den Vorteil eines konstanten zeitlichen Zugriffs. Bei Sets mit viel Wachstum oder Schrumpfung erzielen Sie mit Treesets je nach Implementierung möglicherweise eine bessere Leistung.

Die amortisierte Zeit kann mit einem funktionierenden rot-schwarzen Baum nahe an O (1) liegen, wenn mir das Gedächtnis dient. Okasakis Buch hätte eine bessere Erklärung, als ich durchziehen kann. (Oder siehe seine Publikationsliste )

HashSet-Implementierungen sind natürlich viel schneller - weniger Overhead, da keine Bestellung erfolgt. Eine gute Analyse der verschiedenen Set-Implementierungen in Java finden Sie unter http://java.sun.com/docs/books/tutorial/collections/implementations/set.html .

Die Diskussion dort zeigt auch einen interessanten "Mittelweg" -Ansatz für die Tree vs Hash-Frage auf. Java stellt ein LinkedHashSet bereit, bei dem es sich um ein HashSet handelt, durch das eine "einfügeorientierte" verknüpfte Liste läuft. Das heißt, das letzte Element in der verknüpften Liste ist auch das zuletzt in den Hash eingefügte. Auf diese Weise können Sie die Unregelmäßigkeit eines ungeordneten Hashs vermeiden, ohne die erhöhten Kosten eines TreeSet zu verursachen.

Das TreeSet ist eine von zwei sortierten Sammlungen (die andere ist TreeMap). Es verwendet eine rot-schwarze Baumstruktur (aber das wussten Sie) und garantiert, dass die Elemente in aufsteigender Reihenfolge gemäß der natürlichen Reihenfolge sind. Optional können Sie ein TreeSet mit einem Konstruktor erstellen, mit dem Sie der Sammlung mithilfe eines Vergleichs- oder Komparators Ihre eigenen Regeln für die Reihenfolge zuweisen können (anstatt sich auf die durch die Elementklasse definierte Reihenfolge zu verlassen)

und Ein LinkedHashSet ist eine geordnete Version von HashSet, die eine doppelt verknüpfte Liste über alle Elemente hinweg verwaltet. Verwenden Sie diese Klasse anstelle von HashSet, wenn Sie sich für die Iterationsreihenfolge interessieren. Wenn Sie ein HashSet durchlaufen, ist die Reihenfolge nicht vorhersehbar, während Sie mit einem LinkedHashSet die Elemente in der Reihenfolge durchlaufen können, in der sie eingefügt wurden

Aufgrund technischer Überlegungen, insbesondere in Bezug auf die Leistung, wurden viele Antworten gegeben. Meiner Meinung nach ist die Wahl zwischen TreeSetund HashSetwichtig.

Aber ich würde eher sagen, dass die Wahl zuerst von konzeptionellen Überlegungen bestimmt werden sollte.

Wenn für die Objekte, die Sie manipulieren müssen, eine natürliche Reihenfolge keinen Sinn ergibt, verwenden Sie sie nicht TreeSet.
Es ist eine sortierte Menge, da es implementiert SortedSet. Es bedeutet also, dass Sie die Funktion überschreiben müssen compareTo, was mit der Rückgabefunktion übereinstimmen sollte equals. Wenn Sie zum Beispiel eine Reihe von Objekten einer Klasse namens Student haben, dann denke ich nicht, dass aTreeSet sinnvollen , da es keine natürliche Reihenfolge zwischen den Schülern gibt. Sie können sie nach ihrer Durchschnittsnote bestellen, okay, aber dies ist keine "natürliche Reihenfolge". FunktioncompareTo die 0 nicht nur zurückgibt, wenn zwei Objekte denselben Schüler darstellen, sondern auch, wenn zwei verschiedene Schüler dieselbe Note haben. Für den zweiten Fallequalswürde false zurückgeben (es sei denn, Sie entscheiden sich dafür, dass letztere true zurückgeben, wenn zwei verschiedene Schüler dieselbe Note haben, wodurch die equalsFunktion eine irreführende Bedeutung hat, um keine falsche Bedeutung zu sagen.)
Bitte beachten Sie, dass diese Konsistenz zwischen equalsund compareTooptional ist, aber stark empfohlen. Ansonsten der Vertrag der SchnittstelleSet unterbrochen, wodurch Ihr Code für andere Personen irreführend wird und möglicherweise auch zu unerwartetem Verhalten führt.

Dieser Link könnte eine gute Informationsquelle zu dieser Frage sein.

Warum Äpfel haben, wenn Sie Orangen haben können?

Ernsthaft Jungs und Mädels - wenn Ihre Sammlung groß ist, millionenfach gelesen und geschrieben wird und Sie für CPU-Zyklen bezahlen, ist die Auswahl der Sammlung NUR dann relevant, wenn Sie eine bessere Leistung benötigen. In den meisten Fällen spielt dies jedoch keine Rolle - einige Millisekunden bleiben hier und da menschlich unbemerkt. Wenn es wirklich so wichtig ist, warum schreiben Sie dann keinen Code in Assembler oder C? [Stichwort eine weitere Diskussion]. Der Punkt ist also, wenn Sie glücklich sind, die von Ihnen ausgewählte Sammlung zu verwenden, und dies Ihr Problem löst (auch wenn es nicht speziell die beste Art von Sammlung für die Aufgabe ist), sich selbst auszuschalten. Die Software ist formbar. Optimieren Sie Ihren Code bei Bedarf. Onkel Bob sagt, vorzeitige Optimierung sei die Wurzel allen Übels. Onkel Bob sagt es

Nachrichtenbearbeitung ( vollständiges Umschreiben ) Wenn die Reihenfolge keine Rolle spielt, ist dies der Zeitpunkt. Beide sollten Log (n) geben - es wäre nützlich zu sehen, ob einer über fünf Prozent schneller ist als der andere. HashSet kann O (1) -Tests in einer Schleife geben, sollte zeigen, ob dies der Fall ist.

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