Hashset vs. Treeset

Question

Ich habe Bäume schon immer geliebt, so schön O(n*log(n)) und ihre Sauberkeit. Allerdings hat mich jeder Software-Ingenieur, den ich kenne, gefragt, warum ich eine TreeSet . Mit einem CS-Hintergrund glaube ich nicht, dass es so wichtig ist, was Sie verwenden, und ich habe keine Lust, mit Hash-Funktionen und Buckets herumzuspielen (im Fall von Java ).

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

Answer 1

HashSet ist viel schneller als TreeSet (konstante Zeit im Vergleich zur Protokollzeit für die meisten Operationen wie add, remove und contains), bietet aber keine Ordnungsgarantie wie TreeSet.

HashSet

• die Klasse bietet eine konstante Zeitleistung für die Grundoperationen (add, remove, contains und size).
• sie garantiert nicht, dass die Reihenfolge der Elemente im Laufe der Zeit konstant bleibt
• Iterationsleistung hängt von der Anfangskapazität und die Belastungsfaktor des HashSet.
  • Es ist ziemlich sicher, den Standardauslastungsfaktor zu akzeptieren, aber Sie sollten eine Anfangskapazität angeben, die etwa doppelt so groß ist wie die Größe, auf die Sie das Set wachsen lassen wollen.

TreeSet

• garantiert log(n)-Zeitaufwand für die Grundoperationen (hinzufügen, entfernen und enthalten)
• garantiert, dass die Elemente der Menge sortiert werden (aufsteigend, natürlich, oder die von Ihnen über den Konstruktor angegebene Sortierung) (implementiert SortedSet )
• bietet keine Einstellparameter für die Iterationsleistung
• bietet einige praktische Methoden zum Umgang mit der geordneten Menge wie first() , last() , headSet() y tailSet() usw.

Wichtige Punkte:

• Beide garantieren eine duplikatfreie Sammlung von Elementen
• Im Allgemeinen ist es schneller, Elemente zum HashSet hinzuzufügen und die Sammlung dann in ein TreeSet zu konvertieren, um eine duplikatfreie sortierte Durchquerung zu ermöglichen.
• Keine dieser Implementierungen ist synchronisiert. Das heißt, wenn mehrere Threads gleichzeitig auf eine Menge zugreifen und mindestens einer der Threads die Menge verändert, muss sie extern synchronisiert werden.
• LinkedHashSet ist in gewisser Weise ein Mittelding zwischen HashSet y TreeSet . Implementiert als Hash-Tabelle mit einer verknüpften Liste, die durch sie läuft, jedoch, es bietet eine geordnete Iteration, die nicht mit der durch TreeSet garantierten sortierten Traversierung identisch ist .

Also eine Wahl der Verwendung hängt ganz von Ihren Bedürfnissen, aber ich denke, dass selbst wenn Sie eine geordnete Sammlung benötigen, dann sollten Sie immer noch lieber HashSet, um die Menge zu erstellen und dann konvertieren sie in TreeSet.

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

Answer 2

Ein noch nicht erwähnter Vorteil eines TreeSet ist, dass sie eine größere "Lokalität" aufweist, was kurz gesagt bedeutet, dass (1) wenn zwei Einträge in der Reihenfolge nahe beieinander liegen, ein TreeSet platziert sie in der Datenstruktur und damit im Speicher nahe beieinander; und (2) diese Platzierung macht sich das Prinzip der Lokalität zunutze, das besagt, dass ähnliche Daten von einer Anwendung häufig mit ähnlicher Häufigkeit aufgerufen werden.

Dies steht im Gegensatz zu einer HashSet , wodurch die Einträge über den gesamten Speicher verteilt werden, unabhängig davon, welche Schlüssel sie haben.

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 der Zugriff auf die Daten wirklich ortsgebunden erfolgt, ist die TreeSet kann eine viel bessere Wahl sein.

Answer 3

Basierend auf schönen visuelle Antwort on Maps by @shevchyk hier ist meine Meinung:

   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

Answer 4

HashSet ist O(1), um auf Elemente zuzugreifen, also ist es durchaus von Bedeutung. Aber es ist nicht möglich, die Reihenfolge der Objekte in der Menge beizubehalten.

TreeSet ist nützlich, wenn es Ihnen wichtig ist, eine Reihenfolge einzuhalten (in Bezug auf die Werte und nicht auf die Einfügereihenfolge). Aber, wie Sie festgestellt haben, tauschen Sie Ordnung gegen langsamere Zugriffszeiten auf ein Element: O(log n) für grundlegende Operationen.

Von der Javadocs für TreeSet :

Diese Implementierung bietet garantierte log(n)-Zeitkosten für die Grundoperationen ( add , remove y contains ).

Answer 5

1.HashSet erlaubt Null-Objekt.

(2) TreeSet erlaubt kein Null-Objekt. 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