Avbildningar

I den här lektionen beskriver vi hur den abstrakta datatypen avbildning realiseras i Javas standardklasser/interface Map, TreeMap och HashMap

Den abstrakta datatypen mapp och interfacet Map

Matematiska definition: Givet en definitionsmängd D och en värdemängd V. En avbildning eller funktion (eng map) är då en hopkoppling av elementen i D och V så att till varje element i D hör exakt ett element i V. Elementen i definitionsmängden kallas nycklar

Detta är en ofta efterfrågad mekanism: personnummer -> personobjekt, registreringsnummer -> fordonsobjekt, variabel -> variabelvärde, filnamn -> fil ...

Exempel: Klassen Properties som du kan ha stött på tidigare implementerar en avbildning där både definitions- och värdemängd består av strängar.

En avbildning kan implementeras på flera olika sätt: array, lista, träd men så länge vi talar om den abstrakta datatypen avbildning koncentrerar vi oss på vad man vill göra med avbildningar. Detta definieras i Java av interfacet Map. Ett interface är ungefär som en klass där metoderna bara deklareras med namn och parametrar men saknar kod för hur de skall utföras. Ett interface definierar således vad man kan göra men inte hur det görs.

I Java skall vi ange vilken datatyp som förekommer i definitions- respektive värdemängden. Detta görs med "mallparametrar". Exempel: Map<String, Integer> anger att det är en avbildning med strängar som nycklar (definitionsmängd) och Integer-objekt som värden medan Map<Integer,Person> har Integer-objekt som nycklar och Person-objekt som värden.

Generellt brukar man använda en versal för att beteckna mallparametrar. Sålunda använder Java-dokumentationen beteckningen Map<K,V> för en avbildning med K som nyckel- och V som värdemängd.

Observera att K och V alltså skall uppfattas som någon form av parametrar som alltså vid användning måste ersättas med "aktuella" värden. Aktuella värden måste alltid vara klassnamn - man kan alltså t ex inte ha int som nyckel- eller värdemängd utan måste använda Integer i stället.

De viktigaste metoderna i interface Map:

V put(K key, V value) associerar nyckeln key med värdet value. Eventuellt gammalt värde tas bort men det returneras som värde.
V get(K key) returnerar det värdet lagrat för nyckeln key eller null om inget värde är lagrat.
boolean containsKey(K key) returnerar true om nyckeln key finns

Se vidare javadokumentationen för interfacet Map.

Implementation av mappar - klasserna TreeMap och HashMap

Det går inte att skapa objekt av typen Map eftersom det är ett interface och inte en klass. Man skapar i stället objekt av någon klass som implementerar interfacet. Exempel på en sådana klasser är TreeMap och HashMap. Att de implementerar interfacet Map betyder att de har de metoder som deklarerats i Map.

Exempel: Deklarationen 

   Map<String,Integer> a = new TreeMap<String,Integer>();

skapar ett TreeMap-objekt med strängar som nycklar och heltal som värden.

Observera att man kan deklarera a som en Map dvs man behöver inte i deklarationen ange vilken typ av map man har tänkt sig använda. Det är i själva verket en fördel att göra så för då kan man enkelt byta till någon annan typ av map genom att ändra konstruktoranropet t ex till 

   Map<String,Integer> a = new HashMap<String,Integer>();

Klasserna TreeMap och HashMap skiljer i sin interna organisation. TreeMap är implmenterat med ett (balanserat) binärt sökträd medan HashMap använder en hashtabell. En hashtabell är effektivast för ren åtkomst (put, get, containskey). Ett binärt sökträd underhåller en ordning mellan nycklarna så att operationer som hitta minsta, största, nästa i storleksordning är effektivt implementerade. Metoden toString ger nycklarna i storleksordning för en TreeMap medan de för HashMap kommer i "slumpmässig" ordning.

Rekommendation: Använd TreeMap om du inte har några starka skäl för att använda HashMap!

Exempel: Läs en fil och producera statistik över ordförekomster

  import java.util.Scanner;
  import java.util.Map;
  import java.util.TreeMap;

  public class TreeMapDemo {

    public static void main(String[] args) throws IOException {

      String filename = "vandrare";       // Name of input file
      File input = new File(filename);    // a File object
      Scanner sc = new Scanner(input);    // Connect a Scanner object to the file

      Map<String,Integer> f = new TreeMap<String,Integer>();

      while(sc.hasNext()) {           // As long as there are more things on the file
        String w = sc.next();         // read the 'thing'
        if (f.containsKey(w)) {       // if w already is stored in f
          int i = f.get(w);           //   get its frequence
          f.put(w, new Integer(i+1)); //   and store an increased frequence
        } else {                      // else
          f.put(w, new Integer(1));   //   store a new word with frequence 1
        }
      }
      System.out.println(f);          // Primitive output (toString())
    }
  }

Systematisk behandling av elementen i mappen

(Detta avsnitt kan överhoppas om man man är nöjd med operationerna ovan)

Om man vill gå igenom mappen på något systematiskt sätt (t ex för att skriva ut den på något mer strukturerat sätt än det toString-metoden ger) skapar man ett Set av elementen i mappen och kopplar en iterator till denna. Hur detta görs framgår av den fullständiga exempelkoden. Kopiera gärna den och indatafilen (eller gör en egen indatafil) och testkör!

Tillbaka