HashSet en TreeSet-vergelijking

1. Inleiding

In dit artikel gaan we twee van de meest populaire Java-implementaties van het java.util.Set koppel - HashSet en TreeSet.

2. Verschillen

HashSet en TreeSet zijn bladeren van dezelfde tak, maar ze verschillen in enkele belangrijke zaken.

2.1. Bestellen

HashSet slaat de objecten in willekeurige volgorde op, terwijl TreeSet past de natuurlijke volgorde van de elementen toe. Laten we het volgende voorbeeld bekijken:

@Test openbare leegte gegevenTreeSet_whenRetrievesObjects_thenNaturalOrder () {Set set = nieuwe TreeSet (); set.add ("Baeldung"); set.add ("is"); set.add ("Awesome"); assertEquals (3, set.size ()); assertTrue (set.iterator (). next (). equals ("Awesome")); }

Na het toevoegen van het Draad objecten in TreeSetzien we dat de eerste "Awesome" is, ook al werd hij helemaal aan het einde toegevoegd. Een vergelijkbare operatie gedaan met HashSet garandeert niet dat de volgorde van de elementen in de loop van de tijd constant zal blijven.

2.2. Nul Voorwerpen

Een ander verschil is dat HashSet kan opslaan nul objecten, terwijl TreeSet staat ze niet toe:

@Test (verwacht = NullPointerException.class) openbare ongeldige gegevenTreeSet_whenAddNullObject_thenNullPointer () {Set set = nieuwe TreeSet (); set.add ("Baeldung"); set.add ("is"); set.add (null); } @Test openbare leegte gegevenHashSet_whenAddNullObject_thenOK () {Set set = nieuwe HashSet (); set.add ("Baeldung"); set.add ("is"); set.add (null); assertEquals (3, set.size ()); }

Als we proberen het nul object in een TreeSet, zal de operatie resulteren in een throw NullPointerException. De enige uitzondering was in Java 7, toen het er precies één mocht hebben nul element in het TreeSet.

2.3. Prestatie

Simpel gezegd, HashSet is sneller dan de TreeSet.

HashSet biedt constante prestaties voor de meeste bewerkingen, zoals toevoegen(), verwijderen() en bevat (), versus de logboek(n) tijd aangeboden door de TreeSet.

Meestal kunnen we dat zien de uitvoeringstijd voor het toevoegen van elementen aan TreeSet is veel beter dan voor de HashSet.

Houd er rekening mee dat de JVM mogelijk niet is opgewarmd, dus de uitvoeringstijden kunnen verschillen. Een goede discussie over het ontwerpen en uitvoeren van microtests met behulp van verschillende Set implementaties is hier beschikbaar.

2.4. Geïmplementeerde methoden

TreeSet is rijk aan functionaliteiten, waarbij aanvullende methoden worden geïmplementeerd, zoals:

  • pollFirst () - om het eerste element te retourneren, of nul als Set is leeg
  • pollLast () - om het laatste element op te halen en te verwijderen, of terug te sturen nul als Set is leeg
  • eerste() - om het eerste artikel te retourneren
  • laatste()om het laatste item te retourneren
  • plafond() - om het kleinste element te retourneren dat groter is dan of gelijk is aan het gegeven element, of nul als er niet zo'n element is
  • lager() - om het grootste element strikt kleiner te retourneren dan het opgegeven element, of nul als er niet zo'n element is

De hierboven genoemde methoden maken TreeSet veel gemakkelijker te gebruiken en krachtiger dan HashSet.

3. Overeenkomsten

3.1. Unieke elementen

Beide TreeSet en HashSet garanderen een duplicaatvrije verzameling van elementen, omdat het een onderdeel is van de generieke Set koppel:

@Test openbare ongeldig gegevenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique () {Set set = new HashSet (); set.add ("Baeldung"); set.add ("Baeldung"); assertTrue (set.size () == 1); Set2 = nieuwe TreeSet (); set2.add ("Baeldung"); set2.add ("Baeldung"); assertTrue (set2.size () == 1); }

3.2. Niet gesynchroniseerd

Geen van de beschreven Set implementaties zijn gesynchroniseerd. Dit betekent dat als meerdere threads toegang hebben tot een Set gelijktijdig, en ten minste één van de threads wijzigt het, dan moet het extern worden gesynchroniseerd.

3.3. Faalsnelle iteratoren

De Iterators teruggestuurd door TreeSet en HashSet zijn fail-fast.

Dat betekent dat elke wijziging van de Set op elk moment na de Iterator wordt gemaakt, gooit een ConcurrentModificationException:

@Test (verwacht = ConcurrentModificationException.class) openbare ongeldige gegevenHashSet_whenModifyWhenIterator_thenFailFast () {Set set = nieuwe HashSet (); set.add ("Baeldung"); Iterator het = set.iterator (); while (it.hasNext ()) {set.add ("Awesome"); it.next (); }}

4. Welke implementatie te gebruiken?

Beide implementaties voldoen aan het contract van het idee van een set, dus het is aan de context welke implementatie we kunnen gebruiken.

Hier zijn enkele snelle punten om te onthouden:

  • Als we onze inzendingen gesorteerd willen houden, moeten we gaan voor de TreeSet
  • Als we prestaties meer waarderen dan geheugengebruik, moeten we gaan voor de HashSet
  • Als we een tekort aan geheugen hebben, moeten we gaan voor de TreeSet
  • Als we toegang willen krijgen tot elementen die relatief dicht bij elkaar liggen volgens hun natuurlijke ordening, zouden we dit kunnen overwegen TreeSet omdat het een grotere plaats heeft
  • HashSetDe prestaties kunnen worden afgesteld met de initialCapacity en ladingsfactor, wat niet mogelijk is voor de TreeSet
  • Als we de invoegvolgorde willen behouden en willen profiteren van constante tijdtoegang, kunnen we de LinkedHashSet

5. Conclusie

In dit artikel hebben we de verschillen en overeenkomsten tussen TreeSet en HashSet.

Zoals altijd zijn de codevoorbeelden voor dit artikel beschikbaar op GitHub.