1 Samlinger af data

En overfladisk forståelse af dette kapitel (især lister) forudsættes i det meste af bogen.

En samling (eng.: collection) er en datastruktur, der husker på en samling objekter.

Med JDK1.2 blev der tilføjet en række klasser til java.util-pakken, og de bliver under et bliver betegnet collections-klasserne. De kan meget mere end Vector og Hashtable, og det anbefales at bruge de nye klasser til programmer, der ikke behøver at kunne køre under JDK1.1.8 eller tidligere.

1.1 Lister og mængder

Den mest almindelige liste er ArrayList, en liste, der husker sine objekter, som lå de som perler på en snor lige som den gamle Vector-klasse. Man opretter en ArrayList med f.eks.:

  ArrayList liste;
  liste = new ArrayList();

Derefter kan man tilføje et objekt i enden af listen med add( objekt ), f.eks.:

  liste.add("æh");

tilføjer strengen "æh" sidst i listen.

Man kan sætte ind midt i listen med add( objekt, indeks ), f.eks.:

  liste.add("øh",0);

indsætter "øh" på plads nummer 0, sådan at listen nu indeholder først "øh" og så "æh". Alle elementerne fra og med det indeks, hvori man indsætter, får altså rykket deres indeks et frem. Ligeledes rykkes alle de efterfølgende elementer, hvis man fjerner et element med metoden remove( indeks ).

Man henter elementerne ud igen med get( indeks ).

Med liste.size() får man antallet af elementer i listen, i dette tilfælde 2.

Nogle af metoderne i List-klasserne (så som ArrayList og LinkedList)

Metoder

boolean add( objekt )
Føjer objekt til listen (sidst). Objektet kan være af en vilkårlig klasse. Simple typer (som int og double) tillades ikke (se afsnit 1.1.1). Returnerer altid true.

void add( objekt, int indeks )
Indsætter objekt i listen lige før plads nummer indeks.

void remove( int indeks )
Sletter objektet på plads nummer indeks.

boolean remove( objekt )
Sletter objekt fra listen, hvis det findes. Hvis det fandtes, returneres true, ellers false.

int size()
Returnerer antallet af elementer i listen.

Object get( int indeks )
Returnerer en reference til objektet på plads nummer indeks. Husk at lave en typekonvertering af referencen til den rigtige klasse, før resultatet lægges i en variabel. Listen selv bliver ikke ændret.

String toString ()
Returnerer listens indhold som en streng. Dette sker ved at konvertere hver af elementerne til en streng.

Ovenstående beskrivelse gælder ikke kun ArrayList, men er en beskrivelse af et interface, der gælder for alle List-objekter (lister), herunder ArrayList. Vi vil senere se på et andet List-objekt, nemlig LinkedList.

1.1.1 De simple typer og samlinger af data

Ligesom Vector kan lister (eller nogen af de andre nye samlinger) kun indeholde objekter, men ikke de simple typer som int og double:

  liste.add( 5 );                   // forkert!
  liste.add( 3.14 );                // forkert!

Man er nødt til at pakke dem ind i objekter, der svarer til de simple typer, f.eks.:

  liste.add( new Integer(5) );      // rigtigt
  liste.add( new Double(3.14) );    // rigtigt

1.1.2 Interfacene til lister og mængder

I stedet for bare at levere nogle klasser, som programmørerne så kan bruge (som med f.eks. Vector), er alle de væsentlige metoder beskrevet i interfaces, og der findes så flere forskellige implementationer af interfacene (klasser) til forskelligt brug.

Interfacene er vist herunder sammen med klasserne, der implementerer dem.

Interfacet Collection (samlinger af data)

Interfacet Collection (da.: samling) beskriver en samling data og indeholder metoder fælles for alle samlinger af data.

Der er ikke nogen klasser, der direkte implementerer Collection. I stedet implementerer de interfacene List, Set eller SortedSet, der udbygger (arver fra) Collection.

1.1.3 Lister

List beskriver en ordnet liste af elementer (dvs. elementerne har en rækkefølge og hvert element har en plads, ligesom med Vector).

Den indeholder derfor (ud over dem i Collection) metoder, der forudsætter at elementerne har et index, som f.eks. get(int index), Object remove(int index) og set(int index, Object element). Da hvert element identificeres med et indeks, kan der godt være dubletter (dvs. det samme element optræder flere gange i listen på forskellige indeks). Eksempel på brug:

List l = new ArrayList();      // variablen er bare af interfacets type
l.add("En");
l.add("snegl");

Læg mærke til, at man ofte bare lader variablen være af interfacets type. Det gør, at man nemt kunne ændre ovenstående kode til at bruge LinkedList eller en anden samling i stedet (der skal kun ændres fra "new ArrayList()" til "new LinkedList()".

Der findes to klasser, der implementerer List, nemlig ArrayList og LinkedList. Udefra bruges de på helt samme måde (og har de samme metoder), men de fungerer forskelligt indeni.

ArrayList

ArrayList bruger internt et array til at gemme sine data, og svarer til den gamle Vector-klasse (men ArrayList er dog lidt hurtigere end Vector, da dens metoder ikke er synkroniseret).

Den er derfor hurtig at finde elementer i, men langsom, hvis elementer skal indsættes et vilkårligt sted i listen (da de andre elementer i arrayet så skal rykkes). Se afsnit 1.6.2 for en nærmere diskussion af ArrayList's virkemåde.

LinkedList

LinkedList bruger internt en dobbelthægtet liste til at gemme sine data. I en dobbelthægtet liste gemmes data led i en kæde: hver indgang har en reference til ("er hægtet" med) forrige og næste indgang.

Skal man søge et bestemt index frem i en sådan liste, går det langsomt: Man må starte fra en ende og så løbe gennem hver indgang ("led i kæden"), indtil den ønskede indgang nås. Det er til gengæld meget hurtigt at føje nye elementer til listen (da de andre elementer ikke behøves at blive rykket). Se afsnit 1.6.3 for en nærmere diskussion af LinkedList's virkemåde.

1.1.4 Mængder

Interfacet Set

Set (da.: mængde) beskriver en uordnet mængde af elementer. I en mængde kan der højest være en af hvert element, og elementerne ligger "hulter til bulter" mellem hinanden, dvs. rækkefølgen, som elementerne blev sat ind, huskes ikke. Den indeholder ingen metoder, ud over metoderne fra Collection.

Klassen HashSet

Klassen HashSet implementerer Set. Den bruger en hashtabel til at holde styr på elementerne. En hashtabel er en opslagstabel, der laves ud fra objekternes hashkode (se afsnit 1.6.4). Hashtabeller er meget hurtige at søge og indsætte i. Eksempel på brug:

Set m = new HashSet();      // variablen er bare af interfacets type

m.addAll( l );              // tilføj alle elementer fra listen l
m.add("er");
m.add("tegn");

Se afsnit 1.6.4 for en diskussion af hashtabellers interne virkemåde.

Sorterede mængder (Interfacet SortedSet og klassen TreeSet)

SortedSet beskriver en ordnet mængde af elementer (dvs. elementerne har en rækkefølge, og der kan højest være én af hver).

Klassen TreeSet implementerer SortedSet. Den bruger et binært søgetræ til at holde styr på elementerne (se afsnit 1.6.5).

Ordningen (dvs. hvordan elementerne skal sorteres) kan bestemmes ved at angive et Comparator-objekt i konstruktøren til TreeSet (ellers skal elementerne være Comparable).

Eksempel på brug:

SortedSet sm = new TreeSet(); // variablen er bare af interfacets type

sm.addAll( m );               // tilføj alle elementer fra mængden m
sm.add("på");
sm.add("regn");

1.1.5 Iteratorer

En iterator er et lille objekt, der hjælper med at gennemløbe nogle data.

I stedet for at bruge en tællevariabel:

for (int i=0; i<liste.size(); i++) {                      // uden iterator
  String s = (String) liste.get(i);
  // gør noget med s
  System.out.println(s);
}

... kan man altså få et iterator-objekt ved at kalde metoden iterator() og bruge det:

for (Iterator iter=liste.iterator(); iter.hasNext(); ) {  // med iterator
  String s = (String) iter.next();
  // gør noget med s
  System.out.println(s);
}

Her er det samme skrevet om til at bruge en while-løkke (hvilket gør det lidt enklere):

Iterator iter=samling.iterator();                         // med iterator
while (iter.hasNext()) {
  String s = (String) iter.next();
  // gør noget med s
  System.out.println(s);
}

... der altså svarer til:

int i = 0;                                                // uden iterator
while (i<liste.size()) {
  String s = (String) liste.get(i);
  // gør noget med s
  System.out.println(s);
  i++;
}

Iterator-objekter har altså to¹ vigtige metoder:

boolean hasNext()
fortæller, om der er flere elementer i

Object next()
går til næste element og returnerer det samtidig.

Alle samlinger af data har metoden iterator(), der returnerer et Iterator-objekt. Iteratorer kan altså bruges på enhver samling af data, også på f.eks. mængder, hvor en almindelig tællevariabel kommer til kort.

1.2 Afbildninger (nøgleindekserede lister)

En afbildning (eng.: map) er noget, der afbilder nogle nøgler til værdier. Afbildninger er nyttige, når man vil indeksere nogle objekter ud fra f.eks. et navn i stedet for et nummer.

Afbildninger i forhold til lister

Før vi går videre, så husk, at lister går fra heltal til objekter, dvs. hvert element har en plads og et nummer. For eksempel har en liste metoderne:

void add( objekt, int indeks )
Indsætter objekt i listen lige før plads nummer indeks.

Object get( int indeks )
Returnerer en reference til objektet på plads nummer indeks i listen.

Man kan også sige, at elementerne i en liste indekseres (fremfindes) ud fra et tal.

1.2.1 Afbildninger (Interfacet Map)

Afbildninger går fra objekter til objekter på den måde, at til hvert element knyttes et nøgle-objekt. Elementerne kan derefter findes frem ud fra nøglerne.

Man kan altså sige, at elementerne (værdierne) i en afbildning indekseres (fremfindes) ud fra nøglerne, og at en afbildning består af nogle nøgle-værdi-par.

Interfacet Map beskriver metoderne, der kan kaldes på en afbildning.

Nogle af Map-klassernes metoder - afbildning eller nøgleindekseret liste af objekter (se appendiks for fuld liste)

void put(Object nøgle, Object værdi)
føjer objektet værdi til afbildningen under objektet nøgle. Objekterne kan være et vilkårligt objekt (men ikke en simpel type).

Object get(Object nøgle)
finder indgangen under nøgle og returnerer værdien. Husk at lave en typekonvertering af referencen til den rigtige klasse, før resultatet lægges i en variabel.

Object remove(Object nøgle)
sletter indgangen under nøgle og returnerer værdien.

boolean isEmpty()
returnerer sand, hvis afbildningen er tom (indeholder 0 indgange).

int size()
returnerer antallet af indgange (nøgle-værdi-par).

boolean containsKey(Object nøgle)
returnerer sand, hvis nøgle findes blandt nøglerne i afbildningen.

boolean containsValue(Object værdi)
returnerer sand, hvis værdi findes blandt værdierne i afbildningen.

Set keySet()
giver en datastruktur (en mængde) af afbildningens nøgler. Kan være nyttigt, hvis man vil gennemløbe alle indgangene i afbildningen.

String toString ()
Returnerer alle afbildningens indgange som én stor streng. Dette sker ved at konvertere hver af indgangenes nøgler og værdier til strenge.

Klassen HashMap er den eneste, der implementerer Map-interfacet direkte (indirekte er der to til, nemlig klassen LinkedHashMap, der kom til i JDK1.4, og klassen TreeMap).

1.2.2 Hashtabeller (klassen HashMap)

Man opretter en afbildning (i dette tilfælde en hashtabel) med f.eks.:

  Map tabel;
  tabel = new HashMap();

Derefter kan man lægge en indgang i tabellen med put( nøgle, værdi ). F.eks.:

  tabel.put("abc", "def");

husker strengen "def" under nøglen "abc". Vil vi finde strengen frem igen, skal vi slå op under "abc":

  String værdi = (String) tabel.get("abc");

HashMap afløser den gamle HashTable-klasse og kan nogenlunde det samme. Da hashtabeller oftest anvendes til at lave afbildninger med, bruger man i dagligdags sprogbrug mere ordet 'hashtabel' end ordet 'afbildning'.

1.2.3 Eksempel - ordbog

Vi kunne f.eks. bruge en afbildning (HashMap) til at lave en lille esperanto-dansk-ordbog med. Nøglerne er esperanto-ordene, og værdierne er de danske ord.

import java.util.*;

public class BenytHashMapOrdbog
{
  public static void main(String[] args)
  {
    HashMap ord = new HashMap();
    ord.put("granda", "stor");
    ord.put("longa", "lang");
    ord.put("hundo", "hund");
    ord.put("estas", "(det) er");

    String esperantotekst = "Estas longa granda hundo.";
    StringTokenizer st = new StringTokenizer(esperantotekst, " .,\t\n", true);
    while (st.hasMoreTokens()) {
      String da, eo;
      eo = st.nextToken().toLowerCase();
      da = (String) ord.get(eo);// slå esperantoordet op og få det danske ord
      if (da == null) da = eo;  // hvis intet fundet lader vi det være uoversat
      System.out.print( da );
    }
  }
}

(det) er lang stor hund.

Har vi en tekst på esperanto, kan vi nu oversætte teksten ord for ord til dansk. Hvert ord slås op i hashtabellen, og hvis det findes, erstattes det med det danske ord. Ord som ikke kan findes, efterlades uforandret.

1.2.4 Eksempel - fødselsdatoer

Nøglerne og værdierne behøver ikke være strenge. I eksemplet herunder opretter vi en hashtabel, der holder styr på fødselsdatoer for et antal personer ud fra deres fornavne.

import java.util.*;

public class BenytHashMapDatoer
{
  public static void main(String[] args)
  {
    HashMap hashtabel = new HashMap();
    Date dato;

    dato = new Date(71,0,1);                //  1. januar 1971
    hashtabel.put("Jacob",dato);

    dato = new Date(72,7,11);               // 11. august 1972
    hashtabel.put("Troels",dato);

    hashtabel.put("Ulrik",new Date(73,2,5));//  5. marts 1973
    hashtabel.put("Ulla",new Date(69,1,19));// 19. februar 1969
    hashtabel.put("Brian",new Date(70,3,1));//  1. april 1970
    hashtabel.put("Bo",new Date(76,6,9));// 9. juli 1976

    // Lav nogle opslag i tabellen under forskellige navne
    dato = (Date) hashtabel.get("Troels");
    System.out.println( "Opslag under Troels giver: "+dato);

    System.out.println( "Opslag under Jacob:     "+hashtabel.get("Jacob"));
    System.out.println( "Opslag under Kurtbørge: "+hashtabel.get("Kurtbørge"));
    System.out.println( "Opslag under Brian:     "+hashtabel.get("Brian"));

    // Gennemløb af alle elementer
    for (Iterator i = hashtabel.keySet().iterator() ; i.hasNext() ;) {
      String nøgle = (String) i.next();
      dato = (Date) hashtabel.get(nøgle);
      System.out.println(nøgle + " har fødselsåret: "+dato.getYear());
    }
  }
}

xxx udskrift genereres igen
Opslag under 'Troels' giver: Fri Aug 11 00:00:00 GMT+00:00 1972
.. og under Jacob: Fri Jan 01 00:00:00 GMT+00:00 1971
.. Kurtbørge: null
.. Eva: Mon Mar 05 00:00:00 GMT+00:00 1973
Jacob's fødselsår: 71
Ulla's fødselsår: 69
Eva's fødselsår: 73
Troels's fødselsår: 72

De sidste linjer i koden viser, hvordan man gennemløber alle indgangene i en afbildning. Vi kan ikke, som med en liste, bare lave en for-løkke, der løber fra 0 til antal elementer. I stedet skaffer vi mængden af alle nøgler med hashtabel.keySet() og kalder derefter .iterator() for at få et Iterator-objekt, der gennemløber nøglerne, hvorefter vi for hver nøgle fremfinder værdien².

Bemærk hvordan en HashMap ikke husker rækkefølgen af indgangene. Derfor er rækkefølgen, som elementerne bliver udskrevet i (Jacob, Ulla, Brian, Troels, Ulrik ogBo xxx tjek), ikke den samme som den rækkefølge, de blev sat ind i (Jacob, Troels, Ulrik, Ulla, Brian og Bo).

1.2.5 Avanceret: LinkedHashMap i JDK 1.4

1.2.6 Interfacet SortedMap (sorterede afbildninger) og klassen TreeMap

Dette er en afbildning, hvor nøglerne er sorteret på samme måde som SortedSet. Klassen TreeMap er den eneste, der implementerer SortedMap.

1.3 Opgaver

1. Lav et lille ordliste-program: Det skal tage en tekst og finde frem til de ord, der indgår i teksten, gemme dem i en ArrayList og derefter skrive listen pænt ud.
   Vink: StringTokenizer kan bruges til at dele op i ord.

2. Hvordan undgår du dubletter i ordlisten? Skriv programmet om så det fjerner dubletter.

3. Drop nu koden, der fjerner dubletter, men ændr datastrukturen til at være en HashSet (har du problemer med at hente elementer ud af listen, så læs afsnit 1.1.5 om iteratorer). Hvilken forskel gør det? Hvad sker der med ordlisten?

4. Ændr datastrukturen til at være en TreeSet.
   Hvilken forskel gør det? Hvad sker der med ordlistens rækkefølge?
   Prøv også med en LinkedHashSet.

5. Lav et vindue med en grafisk brugergrænseflade til dit ordliste-program:
   
   Når brugeren trykker på OK-knappen, skal ordlisten opdateres med de ord, den ikke allerede indeholder.

6. Læs kildeteksten til Vector, og prøv at forstå hvordan, den fungerer. Den kan findes i din java-installation (i filen src.zip) eller i afsnit 1.6.8. Studér især de metoder, du er fortrolig med, som elementAt(), addElement(), insertElementAt() og removeElementAt().

1.4 Videre læsning

En introduktion til samlinger af data kan findes på
http://developer.java.sun.com/developer/onlineTraining/collections/

En anden, mere opgave-orienteret vejledning kan findes på adressen
http://java.sun.com/docs/books/tutorial/collections/index.html

1.5 Appendiks

Her er en komplet oversigt over og forklaring på alle samlingerne af data og deres metoder.

1.5.1 Collection

Interfacet Collection - fællesnævnerne for alle samlinger af data (lister og mængder)

boolean add(Object) føjer et element til samlingen

boolean remove(Object) fjerner et element, hvis det findes i samlingen

boolean addAll(Collection) tilføjer elementerne fra en anden samling (foreningsmængde)

boolean removeAll(Collection) fjerner alle elementer, der findes i en anden samling

boolean retainAll(Collection) fjerner alt, der ikke også er i en anden samling (fællesmængde)

ovenstående metoder returnerer true, hvis data ændredes af operationen, false hvis samlingen var upåvirket

void clear() tømmer samlingen for alle elementer

int size() giver antal elementer

boolean isEmpty() returnerer true, hvis der er 0 elementer

boolean contains(Object) returnerer true, hvis elementet findes

boolean containsAll(Collection) returnerer true, hvis alle elementerne findes

Iterator iterator() giver en iterator (se afsnit 1.5.6)

Object[] toArray() giver et array med alle elementerne

Object[] toArray(Object[]) lægger alle elementer med en given type i et eksisterende array

boolean equals(Object) undersøger lighed (samme type samling med samme elementer)

1.5.2 Set

Interfacet Set repræsenterer en mængde. Det arver fra Collection, men tilføjer ingen nye metoder.

Klassen HashSet implementerer Set (og dermed Collection), Cloneable og Serializable og har konstruktørerne:

HashSet() opretter tom mængde med startkapacitet på ca. 10 elementer

HashSet(int startkapacitet) opretter tom mængde med specificeret startkapacitet

HashSet(int startkapacitet, float maxFyldningsfaktor) fyldningsfaktor =antal elementer/kapacitet

HashSet(Collection) opretter mængde med alle elementer fra en anden samling

Object clone() laver en overfladisk kopi (referencerne kopieres, ikke elementerne)

Med JDK1.4 kom klassen LinkedHashSet, der tillader hurtigere gennemløb af nøglerne, men ellers ikke adskiller sig fra HashSet.

1.5.3 SortedSet

Interfacet SortedSet er en ordnet mængde. Det arver fra Set (og dermed fra Collection) og tilføjer metoderne:

Object first() giver første element i mængden

Object last() giver sidste element i mængden

SortedSet tailSet(Object fra) giver alle elementer i mængden fra (og evt. med) elementet fra

SortedSet headSet(Object til) giver alle elementer i mængden, der kommer før elementet til

SortedSet subSet(Object fra, Object til) giver kombinationen af headSet() og tailSet()

Comparator comparator() giver ordningen (eller null, hvis standardordning benyttes)

Klassen TreeSet implementerer SortedSet (og dermed Set), Cloneable og Serializable og har konstruktørerne:

TreeSet() opretter tom mængde

TreeSet(Comparator) opretter tom mængde med specificeret ordning

TreeSet(Collection) opretter mængde med alle elementer fra en samling af data

TreeSet(SortedSet) opretter mængde med alle elementer fra en anden ordnet mængde

Object clone() laver en overfladisk kopi (referencerne kopieres, ikke elementerne)

1.5.4 List

Interfacet List repræsenterer en liste (hvor dubletter er tilladt). Det arver fra Collection og tilføjer metoderne:

void add(int, Object) indsætter element på bestemt plads i listen

Object get(int) aflæser, hvilket element der er på en bestemt plads i listen

Object set(int, Object) erstatter element på en bestemt plads (erstattet element returneres)

Object remove(int) fjerner element på en bestemt plads (fjernet element returneres)

boolean addAll(int, Collection) indsætter alle elementer fra en samling af data på en bestemt plads

int indexOf(Object) finder første position i listen, hvor et element optræder

int lastIndexOf(Object) finder sidste position i listen, hvor et element optræder

ListIterator listIterator() giver en iterator (se afsnit 1.5.6) med udvidede muligheder

ListIterator listIterator(int) giver en iterator (se afsnit 1.5.6), der starter fra en bestemt plads

List subList(int, int) giver en delliste (ændres i dellisten, ændres også i oprindelige liste)

Klassen ArrayList implementerer List (og dermed Collection), Cloneable, Serializable og har derudover:

ArrayList() opretter tom liste med startkapacitet på ca. 10 elementer

ArrayList(int) opretter tom liste med specificeret startkapacitet

ArrayList(Collection) opretter liste med alle elementer fra en anden samling af data

void trimToSize() trimmer listen, så kapaciteten lige netop kan rumme elementerne

void ensureCapacity(int kap) sikrer at kapacitet (antal elementer, listen kan rumme før den er nødt
til at udvide sig) er mindst kap

Object clone() laver en overfladisk kopi (referencerne kopieres, ikke elementerne)

Klassen LinkedList implementerer List (og dermed Collection), Cloneable, Serializable og har derudover:

LinkedList() opretter en tom liste

LinkedList(Collection) opretter en liste med alle elementer fra en anden samling af data

void addFirst(Object) tilføjer først i listen

void addLast(Object) tilføjer sidst i listen

Object getFirst() giver første element

Object getLast() giver sidste element

Object removeFirst() fjerner første element (fjernet element returneres)

Object removeLast() fjerner sidste element (fjernet element returneres)

Object clone() laver en overfladisk kopi (referencerne kopieres, ikke elementerne)

1.5.5 Map

Interfacet Map - fællesnævnerne for alle associative tabeller (afbildninger)

Object put(Object n, Object v) tilføjer v under nøglen n (evt. erstattet værdi returneres)

Object get(Object nøgle) finder værdien under nøgle og returnerer værdien

Object remove(Object nøgle) fjerner værdien under nøgle (evt. fjernet værdi returneres)

boolean containsKey(Object n) returnerer sand, hvis nøglen n findes i afbildningen

boolean containsValue(Object v) returnerer sand, hvis værdi v findes i afbildningen

void putAll(Map) føjer alle indgange fra en anden afbildning til denne

int size() returnerer antallet af indgange

boolean isEmpty() er sand, hvis afbildningen er tom (indeholder 0 indgange)

void clear() tømmer afbildningen for alle elementer

boolean equals(Object) undersøger lighed (afbildning med de samme nøgle-værdi-par)

Set keySet() giver mængde med alle nøgler

Collection values() giver samlingen af værdierne (der kan være dubletter)

Set entrySet() giver mængde med nøgle-værdi-par (se Map.Entry nedenfor)

Klassen HashMap implementerer Map, Cloneable, Serializable og har konstruktørerne:

HashMap() opretter tom afbildning med startkapacitet på ca. 10 elementer

HashMap(int startkapacitet) opretter tom afbildning med specificeret startkapacitet

HashMap(int startkapacitet, float maxFyldfaktor) fyldfaktor =antal elementer/kapacitet

HashMap(Map) opretter afbildning med alle indgange fra en anden afbildning

Object clone() laver en overfladisk kopi (referencer kopieres, ikke elementer)

Interfacet SortedMap er en afbildning, der er ordnet efter nøglerne. Det arver fra Set og tilføjer metoderne:

Object firstKey() giver første nøgle i afbildningen

Object lastKey() giver sidste nøgle i afbildningen

SortedMap tailMap(Object fra) giver en afbildning med alle nøgler fra (og evt. med) fra

SortedMap headMap(Object til) giver en afbildning med alle nøgler der kommer før til

SortedMap subMap(Object fra, Object til) kombinationen af tailMap() og headMap()

Comparator comparator() giver ordningen (null hvis standardordning benyttes)

Klassen TreeMap implementerer SortedMap (og dermed Map), Cloneable, Serializable og har konstruktørerne:

TreeMap() opretter tom afbildning

TreeMap(Comparator) opretter tom afbildning med specificeret ordning

TreeMap(Map) opretter afbildning med alle indgange fra en anden afbildning

TreeMap(SortedMap) opretter afbildning fra en anden ordnet afbildning

Object clone() laver overfladisk kopi (referencerne kopieres, ikke elementerne)

Metoden entrySet() giver mængden af alle indgangene i afbildningen, repræsenteret ved interfacet Map.Entry:

Object getKey() giver nøglen

Object getValue() giver værdien

Object setValue(Object) sætter værdien (erstattet værdi returneres)

1.5.6 Iteratorer

En iterator er et lille objekt, der hjælper en med at gennemløbe nogle data (se afsnit 1.1.5). Man kan man få et iterator-objekt ved at kalde metoden iterator() på enhver samling af data:

Iterator iter = samling.iterator();
while (iter.hasNext()) 
{
  String s = (String) iter.next();
  // gør noget med s
}

Interfacet Iterator:

boolean hasNext() returnerer sand, hvis der er flere elementer

Object next() går til næste element og returnerer det

void remove() fjerner aktuelle element fra samlingen (ikke altid implementeret)

Til lister (af typen List) kan man få et udvidet iterator-objekt ved at kalde listIterator():

Interfacet ListIterator arver fra Iterator og har derudover metoderne:

boolean hasPrevious() returnerer sand, hvis der er tidligere elementer

Object previous() går til næste element og returnerer det

int nextIndex() giver indeks på element, der ville returneres af next()

int previousIndex() giver indeks på element, der ville returneres af previous()

void set(Object) erstatter det aktuelle element i listen med et andet

void add(Object) indsætter element lige før næste element i listen

Når en iterator bruges på en samling, er det ulovligt at ændre samlingen strukturelt (f.eks. indsætte eller slette elementer) direkte, da iteratoren derved kommer ud af trit med samlingen. Kommer en iterator ud af trit med sin samling, er den ubrugelig og vil kaste undtagelsen ConcurrentModificationException, hvis next() nogen sinde kaldes på den igen.

Ønsker man at ændre i samlingen samtidig med at man bruger en iterator, bør man derfor bruge iteratorens ændringsmetoder.

Enumeration

Da Iterator og ListIterator kom først til med JDK 1.2 bruges I standardbiblioteket ofte som iterator et Enumeration-objekt (på dansk 'opremsning') i stedet, f.eks.:

Enumeration enum = vektor.elements();
while (enum.hasMoreElements())
{
  String s = (String) enum.nextElement();
  // gør noget med s
}

Interfacet Enumeration - har eksisteret længere end Iterator og findes derfor ofte brugt i standardbiblioteket

boolean hasMoreElements() returnerer sand, hvis der er flere elementer

Object nextElement() går til næste element og returnerer det

1.5.7 Manipulation og sortering af data

Der findes en række metoder til at manipulere og sortere array af data i klassen Arrays.

Klassen Arrays - alskens metoder til at arbejde med array.

static void sort(double*[]) sorterer array af simpel type (også m. byte, int, ...)

static void sort(double*[], int fra, int til) sorterer arrayet fra og med plads nr. fra til plads nr. til

static void sort(Object[]) sorterer array af objekter

static void sort(Object[], int fra, int til) sorterer arrayet fra og med plads nr. fra til plads nr. til

static void sort(Object[], Comparator) sorterer array af objekter efter en bestemt ordning

static void sort(Object[], int, int, Comparator) sorterer arrayet fra og med plads nr. fra til plads nr. til

static int binarySearch(double*[], double*) søger (binært) i allerede sorteret array af simpel type

static int binarySearch(Object[], Object) søger (binært) i allerede sorteret array af objekter

static int binarySearch(Object[], Object, Comparator) søger i array sorteret med bestemt ordning

static boolean equals(double*[], double*[]) lighed af to array af simpel type (også m. byte, int, ...)

static boolean equals(Object[], Object[]) undersøger, om to array har de samme objekter

static void fill(double*[], double*) sætter alle pladser til en bestemt værdi (også m. int..)

static void fill(double*[], int, int, double*) sætter værdier fra og med plads nr. fra til plads nr. til

static void fill(Object[], Object) sætter alle pladser i arrayet til et bestemt objekt

static void fill(Object[], int, int, Object) fylder med objekt fra og med plads nr. fra til nr. til

static List asList(Object[]) laver en liste ud fra et array af objekter

*) betyder, at metoden findes både med parameter af typen boolean, byte, char, int, float og double

Her er et eksempel på brug af nogle af funktionerne:

import java.util.*;

public class BenytArrays
{
  public static void main(String[] args)
  {
    int[] tal = new int[20];
    Arrays.fill(tal,42);        // sæt alle elementerne i arrayet til 42
    Arrays.fill(tal,5,15,44);   // sæt plads 5 til og med plads nr. 14 til 44
    tal[10] = 43;               // sæt plads nr 10 til 43
    Arrays.sort(tal);           // sortér array (for f.eks. at kunne søge i det)

    int pos44 = Arrays.binarySearch(tal,44); // hvad er nu index på tallet 44?
    System.out.println( "Tallet 44 er på plads nr: " + pos44 );
  }
}

Tallet 44 er på plads nr: 14

Bemærk, at vil man kopiere et array af objekter gøres det mest effektivt med metoden System.arraycopy().

Ligeledes findes metoder til at manipulere og sortere lister, mængder og afbildninger:

Klassen Collections - alskens metoder til at arbejde med samlinger af data.

static final Set EMPTY_SET repræsenterer en tom mængde
static final List EMPTY_LIST repræsenterer en tom liste
static final Map EMPTY_MAP repræsenterer en tom afbildning

static void sort(List) sorterer listen
static void sort(List, Comparator) sorterer listen efter en bestemt ordning

static int binarySearch(List, Object) giver indeks på et objekt ved binær søgning i en sorteret liste

static int binarySearch(List, Object, Comparator) søger i en sorteret (med bestemt ordning) liste

static void reverse(List) vender rækkefølgen af alle elementerne i listen om

static void shuffle(List) blander listen, så elementerne kommer i tilfældig rækkefølge

static void shuffle(List, Random) blander listen v.hj.a. et specificeret Random-objekt

static void fill(List, Object) erstatter alle pladser i listen med det samme element

static void copy(List til, List fra) kopierer liste. Til-listen skal have plads til elementerne.

static Object min(Collection) finder mindste element

static Object min(Collection, Comparator) finder mindste element (i forhold til en bestemt ordning)

static Object max(Collection) finder største element

static Object max(Collection, Comparator) finder største element (i forhold til en bestemt ordning)

static Collection unmodifiableCollection(Collection) laver en uforanderlig samling
static Set unmodifiableSet(Set) laver en uforanderlig mængde
static SortedSet unmodifiableSortedSet(SortedSet) laver en uforanderlig sorteret mængde
static List unmodifiableList(List) laver en uforanderlig liste
static Map unmodifiableMap(Map) laver en uforanderlig afbildning
static SortedMap unmodifiableSortedMap(SortedMap) laver uforanderlig sorteret afbildning

static Collection synchronizedCollection(Collection) laver en trådsikker samling
static Set synchronizedSet(Set) laver en trådsikker mængde
static SortedSet synchronizedSortedSet(SortedSet) laver en trådsikker sorteret mængde
static List synchronizedList(List) laver en trådsikker liste
static Map synchronizedMap(Map) laver en trådsikker afbildning
static SortedMap synchronizedSortedMap(SortedMap) laver en trådsikker sorteret afbildning

static Set singleton(Object) laver en uforanderlig mængde med ét element

static List singletonList(Object) laver en uforanderlig liste med ét element

static Map singletonMap(Object, Object) laver en uforanderlig afbildning med én indgang

static List nCopies(int n, Object elem) laver en uforanderlig liste med n kopier af elem

static Comparator reverseOrder() giver den omvendte ordning af den naturlige ordning

static Enumeration enumeration(Collection) giver en opremsning (Enumeration) af en samling

1.6 Avanceret

1.6.1 Store-O-notationen

1.6.2 Arraybaserede listers virkemåde

1.6.3 Hægtede listers virkemåde

1.6.4 Hashtabellers virkemåde

1.6.5 Søgetræers virkemåde

1.6.6 Uforanderlige samlinger

1.6.7 Trådsikre samlinger

1.6.8 Uddrag af kildeteksten til Vector-klassen