Java >> Java tutorial >  >> Tag >> HashMap

ArrayList vs. LinkedList vs. HashMap i Java

HashMap

1. Oversigt

Samlinger i Java er baseret på et par kernegrænseflader og mere end et dusin implementeringsklasser. Det brede udvalg af forskellige implementeringer kan nogle gange føre til forvirring.

Det er ikke en triviel opgave at beslutte, hvilken indsamlingstype, der skal bruges til en bestemt brugssag. Den beslutning kan have stor indflydelse på vores kodelæsbarhed og ydeevne.

I stedet for at forklare alle typer samlinger i en enkelt artikel, vil vi forklare tre af de mest almindelige:ArrayList, LinkedList, og HashMap. I dette selvstudie vil vi se på, hvordan de gemmer data, deres ydeevne og anbefale, hvornår de skal bruges.

2. Samlinger

En samling er simpelthen et Java-objekt, der grupperer andre objekter sammen. Java Collections Framework indeholder et sæt datastrukturer og algoritmer til at repræsentere og manipulere samlinger. Hvis de anvendes korrekt, hjælper de medfølgende datastrukturer med at reducere programmeringsindsatsen og øge ydeevnen.

2.1. Grænseflader

Java Collections Framework indeholder fire grundlæggende grænseflader:Liste , Indstil , Kort og Kø . Det er vigtigt at forstå den tilsigtede brug af disse grænseflader, før du ser på implementeringsklasserne.

Lad os tage et hurtigt kig på tre af de fire kernegrænseflader, som vi vil bruge i denne artikel:

  • Listen interface er dedikeret til at gemme ordnede samlinger af objekter. Det giver os mulighed for positionelt at få adgang til og indsætte nye elementer samt gemme duplikerede værdier
  • Kortet interface understøtter en nøgleværdi-par-mapping af dataene. For at få adgang til en bestemt værdi skal vi kende dens unikke nøgle
  • Køen interface muliggør lagring af data baseret på først-ind-først-ud-rækkefølgen. Svarende til en kø i den virkelige verden

HashMap implementerer Kort interface. Listen grænsefladen implementeres af både ArrayList og LinkedList . LinkedList implementerer desuden Køen grænseflade.

2.2. Liste vs. Kort

Et almindeligt antimønster, vi nogle gange støder på, er at forsøge at opretholde orden ved hjælp af et kort. Således ikke at gøre brug af andre indsamlingstyper mere egnede til jobbet.

Bare fordi vi kan løse mange problemer med en enkelt indsamlingstype, betyder det ikke, at vi skal.

Lad os se på et dårligt eksempel, hvor vi bruger et kort til at gemme data baseret på positionsnøglen:

Map<Integer, String> map = new HashMap<>();
map.put(1, "Daniel");
map.put(2, "Marko");
for (String name : map.values()) {
    assertThat(name).isIn(map.values());
}
assertThat(map.values()).containsExactlyInAnyOrder("Daniel", "Marko");

Når vi gentager kortværdierne, er vi ikke garanteret at hente dem i samme rækkefølge, som vi satte dem i. Det er simpelthen fordi et kort ikke er designet til at opretholde rækkefølgen af ​​elementer.

Vi kan omskrive dette eksempel på en meget mere læsbar måde ved hjælp af en liste. Lister er ordnet pr. definition, så vi kan iterere gennem emnerne i samme rækkefølge, som vi indsatte dem:

List<String> list = new ArrayList<>();
list.add("Daniel");
list.add("Marko");
for (String name : list) {
    assertThat(name).isIn(list);
}
assertThat(list).containsExactly("Daniel", "Marko");

Kort er designet til hurtig adgang og søgning baseret på unikke nøgler. Når vi vil opretholde orden eller arbejde med positionsbaserede indekser, er lister et naturligt valg.

3. ArrayList

ArrayList er den mest almindeligt anvendte implementering af Listen grænseflade i Java. Det er baseret på indbyggede arrays, men kan dynamisk vokse og krympe, når vi tilføjer eller fjerner elementer.

Vi bruger indekser, der starter fra nul for at få adgang til listeelementer. Vi kan indsætte et nyt element enten i slutningen eller den specifikke placering af listen:

List<String> list = new ArrayList<>();
list.add("Daniel");
list.add(0, "Marko");
assertThat(list).hasSize(2);
assertThat(list.get(0)).isEqualTo("Marko");

For at fjerne et element fra listen skal vi angive objektreferencen eller dets indeks:

List<String> list = new ArrayList<>(Arrays.asList("Daniel", "Marko"));
list.remove(1);
assertThat(list).hasSize(1);
assertThat(list).doesNotContain("Marko");

3.1. Ydeevne

ArrayList giver os dynamiske arrays i Java. Selvom det er langsommere end de indbyggede arrays, ArrayList hjælper os med at spare noget programmeringsarbejde og forbedre kodelæsbarheden.

Når vi taler om tidskompleksitet, gør vi brug af Big-O-notationen. Notationen beskriver, hvordan tiden til at udføre algoritmen vokser med størrelsen af ​​inputtet.

ArrayList tillader tilfældig adgang, da arrays er baseret på indekser. Det betyder, at adgang til ethvert element altid tager en konstant tid O(1) .

Tilføjelse af nye elementer kræver også O(1) tid, undtagen når du tilføjer et element på en bestemt position/indeks, så tager det O(n) . Kontrol af, om et specifikt element findes i den givne liste, kører i lineær O(n) tid.

Det samme gælder for fjernelse af elementer. Vi er nødt til at iterere hele arrayet for at finde det element, der er valgt til fjernelse.

3.2. Brug

Når vi er i tvivl om, hvilken samlingstype vi skal bruge, er det sandsynligvis en god idé at starte med en ArrayList. Husk, at det vil være meget hurtigt at få adgang til elementer baseret på indekser. Det vil dog være dyrt at søge efter varer baseret på deres værdi eller tilføje/fjerne varer på en bestemt position.

Brug af ArrayList  giver mening, når det er vigtigt at opretholde den samme rækkefølge af varer, og hurtig adgangstid baseret på positionen/indekset er et vigtigt kriterium.

Undgå at bruge ArrayList når rækkefølgen af ​​varer ikke er vigtig. Prøv også at undgå det  når varer ofte skal tilføjes til en bestemt position. Ligeledes skal du huske at ArrayList er muligvis ikke den bedste mulighed, når du søger efter specifikke vareværdier, er et vigtigt krav, især hvis listen er stor.

4. LinkedList

LinkedList er en dobbeltforbundet listeimplementering. Implementering af både Listen og Deque (en udvidelse af Kø) grænseflader. I modsætning til ArrayList , når vi gemmer data i en LinkedList , vedligeholder hvert element et link til det forrige.

Udover standard Liste indsættelse  metoder, LinkedList understøtter yderligere metoder, der kan tilføje et element i begyndelsen eller slutningen af ​​listen:

LinkedList<String> list = new LinkedList<>();
list.addLast("Daniel");
list.addFirst("Marko");
assertThat(list).hasSize(2);
assertThat(list.getLast()).isEqualTo("Daniel");

Denne listeimplementering tilbyder også metoder til at fjerne elementer fra begyndelsen eller i slutningen af ​​listen:

LinkedList<String> list = new LinkedList<>(Arrays.asList("Daniel", "Marko", "David"));
list.removeFirst();
list.removeLast();
assertThat(list).hasSize(1);
assertThat(list).containsExactly("Marko");

Den implementerede Deque interface giver kølignende metoder til at hente, tilføje og slette elementer:

LinkedList<String> list = new LinkedList<>();
list.push("Daniel");
list.push("Marko");
assertThat(list.poll()).isEqualTo("Marko");
assertThat(list).hasSize(1);

4.1. Ydeevne

En LinkedList bruger lidt mere hukommelse end en ArrayList da hver node gemmer to referencer til det forrige og næste element.

Indsættelse, tilføjelse og fjernelse er hurtigere i en LinkedList fordi der ikke er nogen ændring af størrelsen af ​​en matrix udført i baggrunden. Når et nyt element tilføjes et sted i midten af ​​listen, er det kun referencer i omgivende elementer, der skal ændres.

LinkedList understøtter O(1) konstant-tidsindsættelse på enhver position i samlingen. Det er dog mindre effektivt til at få adgang til elementer i en bestemt position, idet det tager O(n)  tid.

Fjernelse af et element kræver også O(1) konstant-tid, da vi blot skal ændre nogle få pointer. At kontrollere om et specifikt element findes i den givne liste tager O(n) lineær tid, det samme som for en ArrayList.

4.2. Brug

Det meste af tiden kan vi bruge ArrayList  som standard Liste implementering. I visse tilfælde bør vi dog gøre brug af LinkedList. Disse omfatter, når vi foretrækker konstant indsættelse og sletningstid, frem for konstant adgangstid og effektiv hukommelsesbrug.

Brug af LinkedList   giver mening, når man opretholder den samme rækkefølge af elementer, og hurtig indsættelsestid (tilføjelse og fjernelse af elementer på enhver position) er et vigtigt kriterium.

Som en ArrayList , bør vi undgå at bruge LinkedList   når rækkefølgen af ​​varer ikke er vigtig. LinkedList er ikke den bedste mulighed, når hurtig adgangstid eller søgning efter varer er et vigtigt krav.

5. HashMap

I modsætning til ArrayList og LinkedList , HashMap implementerer Kort interface. Det betyder, at hver nøgle er knyttet til præcis én værdi. Vi skal altid kende nøglen for at hente den tilsvarende værdi fra samlingen:

Map<String, String> map = new HashMap<>();
map.put("123456", "Daniel");
map.put("654321", "Marko");
assertThat(map.get("654321")).isEqualTo("Marko");

På samme måde kan vi kun slette en værdi fra samlingen ved hjælp af dens nøgle:

Map<String, String> map = new HashMap<>();
map.put("123456", "Daniel");
map.put("654321", "Marko");
map.remove("654321");
assertThat(map).hasSize(1);

5.1. Ydeevne

Man kan spørge, hvorfor ikke bare bruge en Liste og slippe af med nøglerne alle sammen? Især siden HashMap bruger mere hukommelse til at gemme nøgler, og dens indtastninger er ikke bestilt. Svaret ligger i ydelsesfordelene ved at søge elementer.

HashMap er meget effektiv til at tjekke om der findes en nøgle eller hente en værdi baseret på en nøgle. Disse operationer tager O(1) i gennemsnit.

Tilføjelse og fjernelse af elementer fra et HashMap baseret på en nøgle tager O(1) konstant tid. At tjekke for et element uden at kende nøglen tager lineær tid O(n), da det er nødvendigt at sløjfe over alle elementerne.

5.2. Brug

Sammen med ArrayList , HashMap er en af ​​de mest brugte datastrukturer i Java. I modsætning til forskellige listeimplementeringer, HashMap gør brug af indeksering til at udføre et spring til en bestemt værdi, hvilket gør søgetiden konstant, selv for store samlinger.

Brug af HashMap giver kun mening, når unikke nøgler er tilgængelige for de data, vi ønsker at gemme. Vi bør bruge det, når vi søger efter varer baseret på en nøgle, og hurtig adgangstid er et vigtigt krav.

Vi bør undgå at bruge HashMap når det er vigtigt at bevare den samme rækkefølge af varer i en samling.

6. Konklusion

I denne artikel undersøgte vi tre almindelige samlingstyper i Java :ArrayList, LinkedList, og HashMap . Vi har set på deres ydeevne for tilføjelse, fjernelse og søgning efter elementer. Baseret på det gav vi anbefalinger om, hvornår de skal anvendes i vores Java-applikationer.

I eksemplerne dækkede vi kun grundlæggende metoder til at tilføje og fjerne elementer. For et mere detaljeret kig på hver implementerings-API, besøg venligst vores dedikerede ArrayList, ArrayList og HashMap artikler.

Som altid er den komplette kildekode tilgængelig på GitHub.


Java tag