Datastrukturer

Denne korte artikel skitserer de tre mest brugte generiske datastrukturer i Java, hvad de bruges til, og hvordan de adskiller sig.

• Ordnet sekvens af elementer, hvor rækkefølgen bevares, og duplikater er tilladt.
• Typiske anvendelser: bevare indsættelsesrækkefølge, indeksbaseret opslag, datastrømme der kan indeholde gentagelser.
• Centrale implementationer:
  • ArrayList (hyppigst): hurtige indeksopslag, amortiseret O(1) add i slutningen, men dyr insert/remove i midten pga. kopiering.
  • LinkedList: O(1) indsættelse/fjernelse i ender, langsommere tilfældige opslag (O(n)).
  • List.of(...)/Collections.unmodifiableList(...): immutabel visning, godt til defensiv kopi og trådsikker deling.

• Samling uden duplikater; typisk ingen garanteret orden (afhænger af implementation).
• Typiske anvendelser: medlemskabstest, fjernelse af duplikater, hurtig deduplikering i streams.
• Centrale implementationer:
  • HashSet: O(1) forventet for add/contains/remove, ingen stabil iteration-orden.
  • LinkedHashSet: Bevarer indsættelsesrækkefølge; lidt højere overhead end HashSet.
  • TreeSet: Sorteret efter Comparable/Comparator; O(log n) operationer, muliggør range-forespørgsler (subSet, headSet).

• Nøgleværdi-par, hvor nøgler er unikke; typisk ingen garanteret orden (afhænger af implementation).
• Typiske anvendelser: opslagstabeller, caches, frekvenstælling, konfigurationer.
• Centrale implementationer:
  • HashMap: O(1) forventet for put/get/remove, ingen iteration-orden.
  • LinkedHashMap: Bevarer indsættelsesrækkefølge eller adgangsorden (kan bruges til simple LRU-caches via removeEldestEntry).
  • TreeMap: Sorteret på nøgle; O(log n) operationer og understøtter range-forespørgsler (subMap, floorEntry).
  • ConcurrentHashMap: Trådsikker med høj parallelitet; undgå Hashtable i nyt kode.

• Immutabilitet: Brug List.of, Set.of, Map.of eller Collections.unmodifiable* når datastrukturen ikke må ændres; reducerer fejl og gør deling mellem tråde enklere.
• Iteration-orden: Vælg LinkedHash* hvis du skal bevare rækkefølge; vælg Tree* hvis du skal have sortering eller range-forespørgsler.
• Præstation: Hash* varianter er hurtigst for konstante opslag; Tree* giver orden på bekostning af logaritmisk tid; LinkedList er niche og bør primært bruges ved mange indsættelser i enderne.
• Nøgler og hashing: Sørg for stabile equals/hashCode på nøgler til HashMap/HashSet; mutable nøgler i disse strukturer skaber hårde fejl.
• Tråde: Brug Collections.synchronized* eller ConcurrentHashMap/immutables for trådsikkerhed; undgå manuel synkronisering hvor høj konkurrence forventes.

*Kompleksitet er for de mest brugte implementationer og under antagelse af gode hashfunktioner.

• Vælg List når rækkefølge og duplikater er acceptable, f.eks. log-lister eller inputrækker.
• Vælg Set når du vil sikre unikhed eller teste medlemskab hurtigt.
• Vælg Map når du skal forbinde nøgler til værdier, f.eks. cache eller slå-tabeller.