Samlingar

Java Collections Framework (Samlingar)

Java Collections Framework innehåller ett antal klasser och interface. De implementerar diverse datastrukturer, till exempel länkade listor, balanserade binära sökträd och hashtabeller. För att systemet ska vara lätt att lära sig och smidigt att använda har man introducerat ett antal abstraktioner på hög nivå.

Abstraktionerna i collection classes är naturliga matematiska begrepp:

• mängder,
• sekvenser,
• avbildningar (maps/tabeller)

Våra mål med detta avsnitt:

• lära oss lite om Java Collections Framework (mycket användbart)
• få inblick i designen av ett avancerat klassbibliotek.

Kommentar

När man arbetar på hög abstraktionsnivå bör man försöka att utnyttja abstraktionerna och resonera om programmet på hög nivå.

Men man kan inte helt glömma det som finns under skalet. Det är framför allt viktigt att ha koll på komplexitet.

Samlingar (Collections Framework)

Programbiblioteket Collection Classes kom med Java 2 platform, version 1.2.

Idén är att definiera ett litet antal generella gränssnitt (interface) som beskriver mängder, sekvenser, tabeller

Klasserna i biblioteket implementerar ett eller flera av de här gränssnitten.

Flera utökningar i Java 5 underlättar användning av samlingar: generaliserad for-loop, autoboxing/unboxing, generiska typer.

Se även Skansholm Kapitel 17 samt Suns/Oracles tutorial om collections.

Motivation:

Vi vill samla olika datastrukturer för att representera tabeller, mängder, sekvenser i ett standardbibliotek.

Det är viktigt att alla datastrukturer kan hanteras på ett likartat sätt, så att

• det är lätt att lära sig använda biblioteket
• man kan lätt ändra val av datastruktur (olika datastrukturer har samma gränssnitt)
• det är lätt att bygga ett större program med komponenter som skickar och tar emot datastrukturer i form av samlingar där man bara anger vilket gränssnitt komponenterna skickar och tar emot.

Samlingar, ett första exempel

Vi börjar med att titta på ett enkelt exempel.

import java.util.*;

public class Simple {

    public static void main (String [] arg) {

	List <String> l = new ArrayList <String>();

	l.add("hej");
	l.add("hopp");
	l.add("goddag");

	System.out.println(l);

	System.out.println("---------------");

	for (String s : l) {
	    System.out.println(s);
	}
    }
}

Detta program skapar en samling (av typen ArrayList) för objekt av typen String. Vi binder variabeln l till denna samling. Notera att l har typ List<String>.

Sen stoppar vi in (med meddelandet add) tre strängar i listan: ("hej", "hopp" och "goddag").

Sen skriver vi först ut hela listan på en gång, loopar vi igenom listan och skriver ut ett element i taget.

Vid provkörning får vi utskriften:

[hej, hopp, goddag]
---------------
hej
hopp
goddag

(Jag berättar mer om gränssnittet List och datastrukturen ArrayList senare i detta avsnitt.)

Interface för samlingar

Vi kommer att titta på sex olika interface för olika typer. I bilden nedan har jag försökt illustrera hur de hänger ihop.

• Collection beskriver en samling av objekt. Ett objekt kan förekomma flera gånger, och vi tar ej (nödvändigtvis) hänsyn till ordningsföljd.
• List beskriver en sekvens av objekt. List är ett subinterface till Collection, vilket innebär att alla metoder som deklareras för Collection också är deklarerade för List. Man kan också säga: varje lista (List) är också en samling (Collection).
• Set beskriver en mängd av objekt. Ett objekt kan endast förekomma en gång i en mängd. Set är också ett subinterface till Collection, så man kan säga att varje mängd också är en samling.
• SortedSet (ordnade mängder). För vissa datatyper kan det finnas en 'naturlig' ordning, tex alfabetisk ordning för strängar. Det är också möjligt att konstruera egna sätt att ordna objekt.
• Map (avbildningar). En slags tabell där man kan koppla värden till nycklar. Ta som exempel en telefonkatalog där man kan snabbt slå upp ett namn och få fram ett telefonnummer.
• SortedMap. Som Map, men nycklarna är ordnade (som i telefonkatalogen).

Exempel på klasser som implementerar samlingar

Några exempel på klasser som implementerar de olika interfacen. Notera att klasserna och interfacen är parameteriserade med typen på de objekt de lagrar.

• ArrayList<T>

  Arrayer. Implementerar List<T>

• LinkedList<T>

  Länkade listor. Implementerar List<T>

• HashMap<K,V>

  Hashtabeller. Implementerar Map<K,V>

Konvention

Varje klass K som implementerar Collection har en konstruktor

K(Collection c)

som tar en godtycklig samling, skapar en ny samling och lägger objekten från samlingen c i den nya samlingen.

Denna konvention gör det enkelt att konvertera mellan olika samlingar.

Collection

Här är ett utdrag ur Oracles källkod för gränssnittet Collection. Jag har klippt bort kommentarer och annat för att göra själva koden tydligare.

public interface Collection<E> extends Iterable<E> {

    int size();
    boolean isEmpty();
    boolean contains(Object o);

    Iterator<E> iterator();

    [...]

    boolean add(E e);
    boolean remove(Object o);

    [...]

    void clear();

    boolean equals(Object o);

    int hashCode();
}

Om man har en samling av objekt, vad vill man kunna göra med samlingen?

Du kan räkna med att alla operationer som är användbara och inte alltför krångliga att implementera ingår i gränssnittet. Till exempel: Man vill kunna lägga till element (add), ta bort element (remove), kolla hur många element vi har (size), testa om samlingen är tom (isEmpty), jämföra två samlingar (equals). Det är också bra om vi enkelt kan rensa en samling (clear).

Notera att Collection utökar gränssnittet Iterable. Detta gränssnitt innehåller funktionalitet för att traversera samlingar och används av den utökade for-loopen.

Iteratorer i loopar

För att traversera samlingen c använde man i tidigare versioner av Java nåt som kallas iteratorer. Man skrev

Iterator i = c.iterator();
while (i.hasNext() ) {
    Object b = i.next();
    ...
}

eller

for (Iterator i=c.iterator; i.hasNext(); ) {
    Object b = i.next();
    ....
}

Kod av den här typen fungerar förstås fortfarande, men idag skriver man vanligtvis loopar över samlingar med den utökade for-loopen.

Traversering, Java 5

Numera skriver man:

for(T b : c) { ... }

om c är en samling eller av någon annan typ som implementerar gränssnittet Iterable<T>.

Detta översätts till kod som använder iteratorer.

Denna notation kan även användas för iteration över arrayer.

Collections: Enkla exempel

Med ArrayList: program/collect/A.java

Vi läser argumenten från kommandoraden och placerar dem i en ArrayList. Sedan skriver vi hela listan på en gång.

import java.util.*;

class A {
    public static void main(String args[]) {
        List<String> l = new ArrayList<String>();
        for (int i=0; i<args.length; i++)
            l.add(args[i]);
        System.out.println(l);
    }
}

Körexempel

$ javac A.java
$ java A en gång är ingen gång
[en, gång, är, ingen, gång]
$

Exempel: LinkedList

Som föregående, men vi placerar elementen i en LinkedList.

program/collect/B.java

List<String> l = new LinkedList<String>();
for (String s : args) {
    l.add(s);
}

Exempel, utökad for-loop:

Som föregående, men vi skriver ut elementen med en for-loop.

program/collect/C.java

for (String s : l) {
    System.out.println(s);
}

Körexempel

$ java C en gång är ingen gång
en
gång
är
ingen
gång

Gränssnittet Set

• Representerar mängder
• En samling objekt, utan inbördes ordning
• men varje objekt kan bara förekomma en gång.
• Samma operationer som Collection
• Implementeras av HashSet och TreeSet

Exempel: HashSet

Som föregående, men vi placerar elementen i en hashtabell.

Program: program/collect/D.java

Set<String> l = new HashSet<String>();

for (String s : args) {
    l.add(s);
}
System.out.println(l);

Körexempel

$ java D en gång är ingen gång
[är, en, gång, ingen]

Notera:

• inga duplicerade element
• resultatet är i oordning; det är inte sorterat eller ordnat enligt den ordning elementen sattes in.
• HashSet implementeras med en hashtabell—en effektiv datastruktur som är särskilt användbar när datamängderna är stora. Kostnad för insättning och uppslagning är ej beroende av hur många element som lagras i tabellen.

Gränssnittet SortedSet

En mängd som garanterar att dess iterator kommer att traversera mängden antingen

• enligt elementens "naturliga" ordning, eller
• enligt en Comparator (en slags jämförelseoperator) som ges till konstruktorn
• TreeSet implementerar även SortedSet

program/collect/lib/SortedSet.java

Exempel: TreeSet

Som tidigare, men med TreeSet:

program/collect/E.java

import java.util.*;

public class E {
    public static void main(String args[]) {

	Set<String> l = new TreeSet<String>();

	for (String s : args) {
	    l.add(s);
	}

	System.out.println(l);
    }
}

Klassen TreeSet lagrar elementen i ett binärt sökträd. Inte riktigt lika effektivt som hashtabeller, men elementen placeras i ordning.

Körexempel TreeSet

$ javac E.java
$ java E bättre en fågel i handen än tio i skogen
[bättre, en, fågel, handen, i, skogen, tio, än]
$ java E ö åra älv
[älv, åra, ö]
$

Notera:

• I första körexemplet skrevs elementen ut i alfabetisk ordning
• men i det andra exemplet såg vi att ordningen inte blev så bra med de svenska bokstäverna å ä ö.

  (Det är egentligen inte så konstigt; Java är ju ett internationellt programspråk och de svenska sorteringsreglerna gäller ju bara för svenska.)

Kort mellanspel 1: gränssnittet Comparator<E>:

public interface Comparator<T> {

    int compare(T o1, T o2);
    ...
}

compare(E o1, E o2) jämför argumenten och returnerar

• ett negativt tal om första argumentet är mindre
• noll om argumenten är lika
• ett positivt tal om första argumentet är större

Kort mellanspel 2: Svensk sortering

Klassen Locale representerar en geografisk, politisk eller kulturell region.

Skriv new Locale("sv", "se") för svenska språket (sv) och Sverige (se).

Klassen Collator implementerar gränssnittet Comparator<Object>. Den har en statisk metod

Collator getInstance(Locale desiredLocale)

som skapar en jämförelseoperator för en given region.

Exempel: Svensk sortering

class F {
  public static void main(String args[]) {

    Locale locale =
      new Locale("sv", "se");

    Collator collator =
      Collator.getInstance(locale);

    SortedSet<String> l =
      new TreeSet<String>(collator);

    [...]
  }}

Körexempel: Svensk sortering

$ javac F.java

$ java E Ögren Vallander Vikström Wiklund Åberg Änglund
[Vallander, Vikström, Wiklund, Änglund, Åberg, Ögren]

$ java F Ögren Vallander Vikström Wiklund Åberg Änglund
[Vallander, Wiklund, Vikström, Åberg, Änglund, Ögren]
$

Så bokstäverna å ä ö kommer i rätt ordning. Dessutom samsorteras v och w. (Detta gällde en tidigare version av Java. De senaste versionerna av Java samsorterar inte v och w.)

Så om man vill ha kan man få svensk sortering i Java. Naturligtvis stöds de flesta språken, och om man talar ett språk som inte stöds kan man definiera sin egen locale.

Definiera egna ordningar

Nå, kan vi definiera en egen ordning?

Exempel 1

Exempel 1: en ordning på strängar (CaseInsensitiveComparator).

Här definierar vi en klass som ärver av Comparator<String>.

class CaseInsensitiveComparator implements Comparator<String> {
    public int compare(String element1,
		       String element2) {
	String lowerE1 = element1.toLowerCase();
	String lowerE2 = element2.toLowerCase();
	return lowerE1.compareTo(lowerE2);
    }
}

Denna ordning sorterar stora och små bokstäver tillsammans.

Exempel 2

Exempel 2: en klass Person med en egen ordning enligt:

• Ordna först efter namn,
• sen efter ålder

Detta implementeras enklast genom att låta Person implementera gränssnittet Comparable.

Gränssnittet Comparable definierar en metod compareTo som jämför nuvarande objekt med ett annat. Precis som med metoden compare returneras ett heltal som beskriver objektens inbördes ordning.

class Person implements Comparable {
    String namn;
    int ålder;

    Person (String namn, int ålder) {
	this.namn = namn;
	this.ålder = ålder;
    }

    public int compareTo (Object o) {
	Person p = (Person)o;
	int t = namn.compareTo(p.namn);
	if (t!=0) { return t;}
	else if (ålder < p.ålder) {return -1;}
	else if (ålder == p.ålder) {return 0;}
	else return 1;
    }

    public String toString() {
	return "Person["+namn+", "+ålder+"]";
    }
}

Exempel 3: en klass Person2 som låter alla över 65 få företräde.

program/collect/Person2.java

Gränssnittet List<E>

En sekvens av objekt där samma objekt kan förekomma flera gånger

Operationer ur Collection, samt

• E get(int index)
• E set(int index, E element)
• E add(int index, E element)
• int indexOf(E element)

Gränssnittet List: implementationer

List implementeras av ArrayList och LinkedList

• ArrayList

  Access via position är snabbt.

  Att skjuta in eller ta bort element (med add och remove) är relativt dyrt.

• LinkedList

  (Länkad lista)

  Access via position är dyrt.

Men notera: om en operation är kostsam eller inte beror på sammanhanget. Om man har en dyr operation i sitt program men bara utför den ett fåtal gånger på en körning blir kostnaden inte så stor. Om man har en länkad lista som lagrar mycket data och gör många accesser via position kan kostnaden ha betydelse.

Gränssnittet Map<K,V>

En instans av en klass som implementerar detta gränssnitt implementerar en avbildning, eller tabell.

Skansholm kallar dessa Avbildningstabeller

Man kan se ett objekt av en klass som implementerar Map<K,V> som en association mellan objekt.

K är typen på nycklar; V är typen på värden.

Exempel: en telefonkatalog. Givet ett namn kan vi ta fram telefonnummer. En telefonkatalog i Java skulle kunna ha gränssnittet Map<String,Integer>.

Gränssnittet Map implementeras av klasserna HashMap och TreeMap.