HashSet- und TreeSet-Vergleich

1. Einleitung

In diesem Artikel werden zwei der beliebtesten Java-Implementierungen der Schnittstelle java.util.Set verglichen - HashSet und TreeSet .

2. Unterschiede

HashSet und TreeSet sind Blätter desselben Zweigs, unterscheiden sich jedoch in wenigen wichtigen Punkten .

2.1. Bestellung

HashSet speichert die Objekte in zufälliger Reihenfolge, während TreeSet die natürliche Reihenfolge der Elemente anwendet. Sehen wir uns das folgende Beispiel an:

@Test public void givenTreeSet_whenRetrievesObjects_thenNaturalOrder() { Set set = new TreeSet(); set.add("Baeldung"); set.add("is"); set.add("Awesome"); assertEquals(3, set.size()); assertTrue(set.iterator().next().equals("Awesome")); }

Nach dem Hinzufügen der String- Objekte zu TreeSet sehen wir, dass das erste "Awesome" ist, obwohl es ganz am Ende hinzugefügt wurde. Eine ähnliche Operation mit HashSet garantiert nicht, dass die Reihenfolge der Elemente über die Zeit konstant bleibt.

2.2. Null- Objekte

Ein weiterer Unterschied besteht darin, dass HashSet Nullobjekte speichern kann, während TreeSet sie nicht zulässt :

@Test(expected = NullPointerException.class) public void givenTreeSet_whenAddNullObject_thenNullPointer() { Set set = new TreeSet(); set.add("Baeldung"); set.add("is"); set.add(null); } @Test public void givenHashSet_whenAddNullObject_thenOK() { Set set = new HashSet(); set.add("Baeldung"); set.add("is"); set.add(null); assertEquals(3, set.size()); }

Wenn wir versuchen, das Null- Objekt in einem TreeSet zu speichern , führt die Operation zu einer ausgelösten NullPointerException . Die einzige Ausnahme war in Java 7 , wenn es erlaubt war genau ein haben null Element in der TreeSet .

2.3. Performance

Einfach ausgedrückt ist HashSet schneller als das TreeSet .

HashSet bietet zeitkonstante Leistung für die meisten Vorgänge wie add () , remove () und includes () im Vergleich zur vom TreeSet angebotenen Protokollzeit ( n ) .

Normalerweise können wir feststellen, dass die Ausführungszeit für das Hinzufügen von Elementen zu TreeSet viel besser ist als für das HashSet .

Bitte denken Sie daran, dass die JVM möglicherweise nicht aufgewärmt ist, sodass die Ausführungszeiten unterschiedlich sein können. Eine gute Diskussion zum Entwerfen und Durchführen von Mikrotests mit verschiedenen Set- Implementierungen finden Sie hier.

2.4. Implementierte Methoden

TreeSet ist reich an Funktionen und implementiert zusätzliche Methoden wie:

  • pollFirst () - um das erste Element zurückzugeben, oder null, wenn Set leer ist
  • pollLast () - um das letzte Element abzurufen und zu entfernen oder null zurückzugeben, wenn Set leer ist
  • first () - um den ersten Artikel zurückzugeben
  • last () - um das letzte Element zurückzugeben
  • Decke () - um das kleinste Element zurückzugeben, das größer oder gleich dem angegebenen Element ist, oder null, wenn es kein solches Element gibt
  • lower () - um das größte Element zurückzugeben, das streng kleiner als das angegebene Element ist, oder null, wenn es kein solches Element gibt

Die oben genannten Methoden machen TreeSet viel einfacher und leistungsfähiger als HashSet .

3. Ähnlichkeiten

3.1. Einzigartige Elemente

Sowohl TreeSet als auch HashSet garantieren eine duplikationsfreie Sammlung von Elementen, da es Teil der generischen Set- Schnittstelle ist:

@Test public void givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique() { Set set = new HashSet(); set.add("Baeldung"); set.add("Baeldung"); assertTrue(set.size() == 1); Set set2 = new TreeSet(); set2.add("Baeldung"); set2.add("Baeldung"); assertTrue(set2.size() == 1); }

3.2. Nicht synchronisiert

Keine der beschriebenen Set- Implementierungen ist synchronisiert . Dies bedeutet, dass wenn mehrere Threads gleichzeitig auf einen Satz zugreifen und mindestens einer der Threads ihn ändert, dieser extern synchronisiert werden muss.

3.3. Ausfallsichere Iteratoren

Die von TreeSet und HashSet zurückgegebenen Iteratoren sind ausfallsicher.

Das bedeutet, dass jede Änderung des Sets zu einem beliebigen Zeitpunkt nach dem Erstellen des Iterators eine ConcurrentModificationException auslöst:

@Test(expected = ConcurrentModificationException.class) public void givenHashSet_whenModifyWhenIterator_thenFailFast() { Set set = new HashSet(); set.add("Baeldung"); Iterator it = set.iterator(); while (it.hasNext()) { set.add("Awesome"); it.next(); } }

4. Welche Implementierung soll verwendet werden?

Beide Implementierungen erfüllen den Vertrag der Idee eines Sets, so dass es dem Kontext überlassen bleibt, welche Implementierung wir verwenden könnten.

Hier sind einige wichtige Punkte, an die Sie sich erinnern sollten:

  • Wenn wir unsere Einträge sortieren möchten, müssen wir uns für das TreeSet entscheiden
  • Wenn wir mehr Wert auf Leistung als auf Speicherverbrauch legen , sollten wir uns für das HashSet entscheiden
  • Wenn wir wenig Speicher haben, sollten wir uns für das TreeSet entscheiden
  • Wenn wir auf Elemente zugreifen möchten, die gemäß ihrer natürlichen Reihenfolge relativ nahe beieinander liegen, sollten wir TreeSet in Betracht ziehen, da es eine größere Lokalität aufweist
  • Die Leistung von HashSet kann mithilfe von initialCapacity und loadFactor optimiert werden , was für TreeSet nicht möglich ist
  • Wenn wir die Einfügereihenfolge beibehalten und von einem zeitlich konstanten Zugriff profitieren möchten, können wir das LinkedHashSet verwenden

5. Schlussfolgerung

In diesem Artikel haben wir die Unterschiede und Ähnlichkeiten zwischen TreeSet und HashSet behandelt .

Wie immer sind die Codebeispiele für diesen Artikel auf GitHub verfügbar.