HashSet og TreeSet sammenligning

1. Introduktion

I denne artikel skal vi sammenligne to af de mest populære Java-implementeringer af java.util.Set grænseflade - HashSet og TreeSet.

2. Forskelle

HashSet og TreeSet er blade af samme gren, men de adskiller sig i få vigtige sager.

2.1. Bestilling

HashSet gemmer objekterne i tilfældig rækkefølge, mens TreeSet anvender den naturlige rækkefølge af elementerne. Lad os se følgende eksempel:

@Test offentlig ugyldighed givenTreeSet_whenRetrievesObjects_thenNaturalOrder () {Set set = new TreeSet (); set.add ("Baeldung"); set.add ("er"); set.add ("Awesome"); assertEquals (3, set.size ()); assertTrue (set.iterator (). næste (). er lig med ("Awesome")); }

Efter tilføjelse af Snor genstande ind i TreeSet, ser vi, at den første er “Awesome”, selvom den blev tilføjet i slutningen. En lignende operation udført med HashSet garanterer ikke, at rækkefølgen af ​​elementer forbliver konstant over tid.

2.2. Nul Objekter

En anden forskel er, at HashSet kan gemme nul genstande, mens TreeSet tillader dem ikke:

@Test (forventet = NullPointerException.class) offentlig ugyldighed givenTreeSet_whenAddNullObject_thenNullPointer () {Set set = new TreeSet (); set.add ("Baeldung"); set.add ("er"); set.add (null); } @Test offentlig ugyldighed givenHashSet_whenAddNullObject_thenOK () {Set set = new HashSet (); set.add ("Baeldung"); set.add ("er"); set.add (null); assertEquals (3, set.size ()); }

Hvis vi prøver at gemme nul objekt i en TreeSet, vil operationen resultere i et kast NullPointerException. Den eneste undtagelse var i Java 7, da det fik lov til at have nøjagtigt en nul element i TreeSet.

2.3. Ydeevne

Kort fortalt, HashSet er hurtigere end TreeSet.

HashSet giver konstant ydelse til de fleste operationer som tilføje(), fjerne() og indeholder(), versus log(n) tid tilbudt af TreeSet.

Normalt kan vi se det udførelsestid for tilføjelse af elementer i TreeSet er meget bedre end for HashSet.

Husk, at JVM muligvis ikke bliver opvarmet, så udførelsestiderne kan variere. En god diskussion om, hvordan man designer og udfører mikrotests ved hjælp af forskellige Sæt implementeringer er tilgængelig her.

2.4. Implementerede metoder

TreeSet er rig på funktionaliteter, implementering af yderligere metoder som:

  • pollFirst () - for at returnere det første element, eller nul hvis Sæt er tom
  • pollLast () - for at hente og fjerne det sidste element eller returnere nul hvis Sæt er tom
  • først() - for at returnere den første vare
  • sidst()for at returnere den sidste vare
  • loft() - at returnere det mindste element, der er større end eller lig med det givne element, eller nul hvis der ikke er noget sådant element
  • nederste() - at returnere det største element strengt mindre end det givne element, eller nul hvis der ikke er noget sådant element

De ovennævnte metoder gør TreeSet meget lettere at bruge og mere kraftfuld end HashSet.

3. Ligheder

3.1. Unikke elementer

Begge TreeSet og HashSet garantere en duplikatfri samling af elementer, da det er en del af det generiske Sæt grænseflade:

@Test offentlig ugyldighed givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique () {Set set = new HashSet (); set.add ("Baeldung"); set.add ("Baeldung"); assertTrue (set.size () == 1); Sæt set2 = nyt TreeSet (); set2.add ("Baeldung"); set2.add ("Baeldung"); assertTrue (set2.size () == 1); }

3.2. Ikke synkroniseret

Ingen af ​​de beskrevne Sæt implementeringer er synkroniseret. Dette betyder, at hvis flere tråde får adgang til a Sæt samtidigt, og mindst en af ​​trådene ændrer det, så skal det synkroniseres eksternt.

3.3. Fejlfaste itteratorer

Det Iterators returneret af TreeSet og HashSet er fail-hurtige.

Det betyder, at enhver ændring af Sæt når som helst efter Iterator er oprettet vil kaste en ConcurrentModificationException:

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

4. Hvilken implementering skal du bruge?

Begge implementeringer opfylder idéen om et sæt, så det er op til konteksten, hvilken implementering vi muligvis bruger.

Her er få hurtige punkter at huske:

  • Hvis vi vil holde vores poster sorteret, er vi nødt til at gå efter TreeSet
  • Hvis vi værdsætter ydeevne mere end hukommelsesforbrug, skal vi gå efter HashSet
  • Hvis vi mangler hukommelse, skal vi gå efter TreeSet
  • Hvis vi ønsker at få adgang til elementer, der er relativt tæt på hinanden i henhold til deres naturlige rækkefølge, vil vi måske overveje TreeSet fordi det har større lokalitet
  • HashSet'S ydeevne kan indstilles ved hjælp af initialCapacity og belastningsfaktor, hvilket ikke er muligt for TreeSet
  • Hvis vi vil bevare indsættelsesordren og drage fordel af konstant tidsadgang, kan vi bruge LinkedHashSet

5. Konklusion

I denne artikel dækkede vi forskellene og lighederne mellem TreeSet og HashSet.

Som altid er kodeeksemplerne til denne artikel tilgængelige på GitHub.