Java Collection Framework
Implementierungen

Willemers Informatik-Ecke

Das einzig seriöse Javabuch :-) Mehr...


Errata

Bei Amazon bestellen


Ferien an der Flensburger Förde


2016-01-16

Implementierungen von List

Das Interface List beschreibt, was eine Liste ausmacht. Für die praktische Arbeit ist aber interessant, was eine Liste kann und das wird durch die Implementierung der Liste geprägt. Die wichtigsten Implementierungen von List sind LinkedList und ArrayList.

Eine ArrayList kann man sich vorstellen wie Bauklötze, die direkt nebeneinander stehen. Man findet über die Nummer einen Bauklotz sehr schnell, weil man nur die Breite eines Bausteins mit der Position multiplizieren muss und schon findet man auch bei sehr vielen Bauklötzen einen bestimmten Bauklotz. Immer vorausgesetzt, man hat einen beliebig langen Zollstock.

Eine LinkedList entspricht Bauklötzen, die durch Schnüre und Haken miteinander verbunden sind. Man hangelt sich von Klotz zu Klotz.

Wenn man direkt über Positionsnummern zugreifen willst, ist die ArrayList praktischer. Sollte es aber notwendig werden, Elemente nachträglich einzufügen oder zu entnehmen, müssen bei der ArrayList alle nachfolgenden Elemente verschoben werden, um seine geschlossene Nummerierung zu erhalten. Darum werden ArrayList und LinkedList in sehr unterschiedlichen Situationen eingesetzt.

ArrayList

Eine ArrayList ähnelt von den Datencontainern am ehesten einem Array. Die Elemente liegen direkt nebeneinander, sind durchnummeriert und ein Zugriff auf ein beliebiges Element über seinen Index ist so schnell wie jedes andere.

Das Array hat den klaren Nachteil, dass vor seiner ersten Benutzung festgelegt werden muss, wie groß es ist. Eine nachträgliche Änderung ist nicht mehr möglich. Diese Begrenzung hebt die ArrayList auf. Man kann die ArrayList jederzeit um ein paar Elemente erweitern. Aber auch ArrayList kann nicht zaubern. Diese Erweiterbarkeit kann Kosten verursachen.

Kapazitäten

Ja, auch eine ArrayList hat Grenzen. Allerdings sind sie durchbrechbar. Und was schöner ist: Der Programmierer muss sich nicht darum kümmern. Diese Grenze nennt sich Kapazität.

Standardmäßig hat eine ArrayList eine Kapazität von zehn Elementen. Wird mehr Platz benötigt, wird eine größere ArrayList angelegt und umkopiert. Aber das tut die ArrayList dankenswerterweise von sich aus.

Ist von vornherein absehbar, dass die ArrayList sehr viel größer wird, dann kann man die Kapazität bei Aufruf des Konstruktors übergeben.

ArrayList namen = new ArrayList(1000);
Sollte sich erst später herausstellen, dass eine höhere Kapazität erforderlich ist, kann mit der Methode esureCapacity nachgeholfen werden. Ihr Parameter legt die Kapazität fest.
void ensureCapacity(int minCapacity)
Sollte sich irgendwann herausstellen, dass eine ArrayList eine viel zu große Kapazität besitzt, kann diese duch den Aufruf von trimToSize auf die aktuelle Größe reduziert werden.
void trimToSize()

Zugriff auf die Elemente über den Index

Da die ArrayList aber kein eingebauter Container sondern eine Klasse ist, kann sie die eckigen Klammern, die das Array verwendet, nicht benutzen. Stattdessen verwendet ArrayList die Methoden get und set.

element = array[i];
element = arraylist.get(i);
array[i] = element;
arraylist.set(i, element);

Die Methode get erhält einfach den Index als Parameter und liefert das Element als Rückgabewert. Etwas umständlicher ist set. Hier wird der Index als erster Parameter verwendet und das Element wird als zweiter Parameter übergeben.

Zugriff auf die Elemente über einen Iterator

Der Zugriff über den Index ist die Spezialität der ArrayList. Wie alle anderen Container kann sie allerdings auch einen Iterator liefern, über den man, wie per Zeigestock auf die Elemente zugreifen kann.

Ein Iterator wird von der ArrayList geliefert. Er steht zunächst vor dem ersten Element. Der Iterator kann nun über seine Methode hasNext feststellen, ob sein Container noch Elemente enthält und über seine Methode next kann er ihn liefern und zum nächsten Element fortschreiten. Eine Schleife zum Auslesen eines Containers sieht also so aus:

Iterator iterator = container.iterator();
while (iterator.hasNext()) {
    Element element = iterator.next();
}
Dieses Verfahren funktioniert mit jeder Collection. Das Interface List kennt allerdings noch einen spezialisierten ListIterator. Während der normale Iterator nur das Vorwärtsbewegen, Auslesen und Löschen einzelner Elemente erlaubt, kann sich ein ListIterator durch die zusätzlichen Methoden hasPrevious und previous in beide Richtungen bewegen. Die Methoden nextIndex und previousIndex liefern den Index des Elements. Das folgende Beispiel zeigt, wie eine Liste zunächst vorwärts und dann wieder rückwärst durchlaufen wird.
ListIterator iterator = list.listIterator();
while (iterator.hasNext()) {
    Element element = iterator.next();
}
while (iterator.hasPrevious()) {
    Element element = iterator.previous();
}

Landkreise in der ArrayList

In einem Beispiel sollen Daten in einer ArrayList verwaltet werden. Bevor wir aber auf die Liste schauen, sehen wir uns die Elemente an. Unsere Beispieldaten sind Landkreise. Die haben eine Bezeichnung und eine Einwohnerzahl. Die Klasse ist sehr übersichtlich.
public class Kreis {
    private String wo;
    private long einwohner;

    Kreis(String w, long e) {
        wo = w; einwohner = e;
    }

    String getWo() {
        return wo;
    }

    long getEinwohner() {
        return einwohner;
    }
}
Das folgende Hauptprogramm legt eine ArrayList von Kreisen an und füllt sie ein paar Elementen. Dazu wird recht unspektakulär die Collection-Methode add verwendet, die die Daten am Ende anhängt.

In dem Programm werden die Elemente einmal per Iterator und einmal per Index durchlaufen. Dazwischen werden zwei Kreise getauscht und ein Kreis entfernt.

import java.util.ArrayList;
import java.util.Iterator;

public class TestArrayList {

    public static void main(String args[]) {
        ArrayList kreise = new ArrayList();
        kreise.add(new Kreis("Schleswig-Flensburg",197903));
            // Mit Collection-Methode add Elemente anhängen
        kreise.add(new Kreis("Hochtaunuskreis",227425));
        kreise.add(new Kreis("Mühlheim",167344));
        kreise.add(new Kreis("Pinneberg",303481));
        kreise.add(new Kreis("Recklinghausen",628817));
        System.out.println("--- Liste per Iterator ausgeben");
        Iterator iterator = kreise.iterator();
        while (iterator.hasNext()) {
            Kreis k = iterator.next();
            System.out.print("" + k.getWo());
            System.out.print(" (" + k.getEinwohner());
            System.out.println(" Einwohner)");
        }
        // tausche Pos 1 und 2 per Index mit set und get
        Kreis help = kreise.get(1);
        kreise.set(1, kreise.get(2));
        kreise.set(2, help);
        kreise.remove(3); // 4tes (Pos 3!) Element wegwerfen
        System.out.println("--- Liste per for nach Tausch und Löschung");
        for (int i=0; i<kreise.size(); i++) {
            System.out.print("" + i + ": " + kreise.get(i).getWo());
            System.out.print(" (" + kreise.get(i).getEinwohner());
            System.out.println(" Einwohner)");
        }
    }
}
Wie beim Array beginnen die Indizes der ArrayList bei 0. Das vierte Element steht also an Position 3.

Der Tausch zwischen den beiden Elementen über ihren Index erfolgt bei einer ArrayList schneller als bei einer LinkedList. Dagegen ist das remove nicht ganz so günstig, weil die Elemente aufgeschoben werden müssen. Immerhin ist der remove günstiger als beim Array, weil sich der Programmierer nicht selbst um die Organisation der Arraydaten kümmern muss.

Statt der for-Schleife, die über den Index geht, könnte auch die Spezial-for-Schleife für Arrays verwendet werden. Das Objekt der Klasse Kreis wird im Schleifenkopf als Element der ArrayList kreise deklariert. Daraufhin kann im Schleifenkörper auf dieses Objekt zugegriffen werden und die Schleife läuft über alle Elemente der Liste.

for (Kreis k : kreise) {
    System.out.print("" + k.getWo());
    System.out.print(" (" + k.getEinwohner());
    System.out.println(" Einwohner)");
}

Noch ein flexibles Array: Vector

Bevor die ArrayList im Zusammenhang mit dem Java Collection Framework entstand, gab es bereits die Klasse Vector, die das gleiche Ziel verfolgte, nämlich ein dynamisches Array zu implementieren.

Damit der Vector nicht so einsam ist, wurde er nachträglich auf die Basis des Interfaces List gestellt, so dass man eine ArrayList einfach gegen einen Vector im Listing ersetzen könnte. Einen feinen Unterschied gibt es. Die Methoden des Vectors sind synchronisiert. Das bedeutet, dass sie in Umgebungen mit mehreren Threads ununterbrechbar laufen. Das kann natürlich auch Konsequenzen in ihrer Laufzeit haben. Da die Definition atomarer Abläufe normalerweise sowieso von der Anwendung gemacht werden muss, bringt ein Vector in der Praxis keine Vorteile.

Den Vector sollte man schon deshalb kennen, weil er in vielen älteren Sourcen vorkommt. In diesen werden dann auch manchmal Methoden verwendet, die im Interface von List nicht vorkommen.

So wird manchmal setElementAt(Element, index) anstelle von set(index,Element) verwendet. ABgesehen vom Namen muss man hier beachten, dass die Parameter vertauscht sind. Zum Löschen wird hin und wieder removeElementAt(index) statt remove(index) eingesetzt. Da Vector inzwischen das Interface List implementiert, kann man natürlich set und remove verwenden.

Ein sehr hübsches Beispiel für den Umgang mit Vektoren ist ein MauMau-Kartenspiel unter der folgenden URL:

http://www.must.de/default.html?Java-Vector-Beispiel.html

Der Computer spielt nur gegen sich selbst und gewinnt dadurch natürlich immer.

LinkedList

Eine LinkedList ist eine doppelt verkettete Liste. Die Elemente sind nicht wie in einem Array indizierbar, sondern werden wie in einer Perlenkette nacheinander abgearbeitet. Doppelt heißt in diesem Zusammenhang, dass das Programm auf dieser Kette vor und zurück hangeln kann.

Typischerweise verwendet man zum Bearbeiten einer Linked List einen Iterator, da der Zugriff per Position recht teuer ist. Der Container muss bei jedem Zugriff von vorn durch die Liste gehen, bis er die Position erreicht hat. Ist es also erforderlich, wahlfrei auf die Positionen zugreifen zu können, ist es sinnvoller eine ArrayList zu verwenden.

Der Nachteil der fehlenden Indizierung wird dadurch ausgeglichen, dass das Aushängen und Einhängen in solchen Ketten viel effizienter ist, weil dazu die anderen Elemente nicht verschoben werden müssen. Auch die Problematik der Kapazitäten, wie wir sie in der ArrayList gesehen haben, erübrigen sich.

Um die Möglichkeiten zu nutzen, in der LinkedList in beide Richtungen zu bewegen, muss der ListIterator verwendet werden. Der ListIterator hat die gleichen Methoden wie der normale Iterator. Es gibt neben next eine Methode previous. Und analog zu hasNext gibt es hasPrevious. Mit den Methoden nextIndex und previusIndex können die Positionen bestimmt werden, zwischen denen der ListIndex steht.

Die LinkedList bietet sich aufgrund der Verkettung besonders auch als Implementierung der Queue an, die im folgenden beschrieben wird.

Queue und noch einmal LinkedList

Die LinkedList dient nicht nur als List-Implementierung, sondern ist auch als Queue eine Idealbesetzung. Sie implementiert die Methoden der Queue.

Mit den Methoden offer für das Einfügen, peek für das Lesen des ersten Elements und poll für das Entfernen wird der Erfolg der Operationen über die Rückgabewerte gelöst. Das folgende Beispiel füllt drei Strings in die Queue, schaut mal nach dem ersten und holt dann alle Strings wieder ab. Die Ausgabeschleife endet, wenn null zurückgegeben wird.

import java.util.LinkedList;
import java.util.Queue;

public class TestQueue {
    public static void main(String[] args) {
        Queue queue = new LinkedList();
        queue.offer("Alpha");
        queue.offer("Beta");
        queue.offer("Charlie");
        String liesdas = queue.peek();
        System.out.println("Mal luschern: " + liesdas);
        while ((liesdas = queue.poll()) != null) {
            System.out.println("Ausgelesen: " + liesdas);
        }
    }
}
Bei Verwendung der Methoden add, element und remove löst ein Fehler eine Exception aus. Das folgende Beispiel verwendet diese Befehle, setzt das Fangen der Exception erst beim Auslesen der Queue ein.
import java.util.LinkedList;
import java.util.Queue;

public class TestQueue {
    public static void main(String[] args) {
        Queue queue = new LinkedList();
        queue.add("Alpha");
        queue.add("Beta");
        queue.add("Charlie");
        String liesdas = queue.element();
        System.out.println("Mal luschern: " + liesdas);
        try {
            while (true) {
                System.out.println("Und abholen: " + queue.remove());
            }
        } catch(Exception e) {
            System.out.println("gefangen! ");
        }
        System.out.println("fertig! ");
    }
}
Auf dem Bildschirm erscheinen die folgenden Zeilen:
Mal luschern: Alpha
Und abholen: Alpha
Und abholen: Beta
Und abholen: Charlie
gefangen! 
fertig! 

Implementierungen von Set

Ein Set enthält eine Menge von Elementen, von denen keines doppelt auftreten darf. In diesem Sinne bildet es eine mathematische Menge ab.

Implementiert wird Set als HashSet, TreeSet und LinkedHashSet. HashSet liefert die beste Performance, liefert aber keine Gewähr bezüglich der Reihenfolge. TreeSet ordnet die Elemente in einem red-black-tree. LinkedHashSet sortiert in der Reihenfolge der Hinzufügung.

Zwischenfrage: Was ist ein Hash?

Ein Hash dient dazu, möglichst schnell an Informationen zu gelangen. Während der Mensch spontan die Daten ordnen würde, geht Hash einen anderen Weg. Stellen wir uns vor, wir sollten Städte anhand ihres Namens wiederfinden. Dann ginge ein Hash so vor, dass er die Quersumme der Buchstaben bildet und an dieser Position die Information ablegt. Liegt dort schon eine Stadt, so wird eine weitere Quersumme über die Zahl gebildet und die Stadt dort abgelegt. Ist dort auch schon eine Stadt, wird der Vorgang solange wiederholt, bis ein Platz gefunden wurde.

Quersummen werden tatsächlich nicht verwendet, weil diese sehr schnell in ihrem Bereich schrumpfen. Stattdessen verwendet man Funktionen, die dafür sorgen, dass die Streuung groß ist. Während eine binäre Suche nach einer Zahl im Bereich bis 1000 bereits zehn Zugriffe benötigt, ist ein Hash in der Regel deutlich schneller. Der einzige Haken: Die Daten sind nicht sortiert abgelegt.

Wortmenge

Als Beispiel werden einfache Sätze von einem Programm in einem Set abgelegt. Dabei werden doppelte Worte entfallen. Das folgende Beispiel nutzt den booleschen Rückgabewert von add um die Anzahl der Doppelungen zu zählen.
import java.util.*;

public class EntDoppler {
    public static void main(String[] args) {
        Set s = new TreeSet(); // hier HashSet, TreeSet und LinkedHashSet probieren!
        int doppelte = 0;
        doppelte +=  s.add("das")?0:1;  // Fragezeichenoperator!
        doppelte +=  s.add("buch")?0:1; // Nur erhöhen, wenn eine Dopplung vorliegt.
        doppelte +=  s.add("das")?0:1;
        doppelte +=  s.add("das")?0:1;
        doppelte +=  s.add("java")?0:1;
        doppelte +=  s.add("beschreibt")?0:1;
        System.out.println("Doppelte: " + doppelte);
        System.out.println("Anzahl Einzelne: " + s.size() + " und zwar "  + s);
    }
}
Bei der Erzeugung des Sets kann festgelegt werden, welche Implementierung verwendet wird. Hier kann schnell getestet werden, wie sich die Ergebnisse auswirken, wenn unterschiedliche Implementierungen gewählt werden. In der letzten Zeile wird der Inhalt des Sets ausgegeben und so zeigen die folgenden drei Zeilen die Ergebnisse von Hashset, TreeSet und LinkedHashSet.
beschreibt, das, buch, java
beschreibt, buch, das, java
das, buch, java, beschreibt
Das Ergebnis des HashSet erscheint völlig chaotisch. TreeSet liefert eine alphabetisch sortierte Reihenfolge. LinkedHashSet behält die Reihenfolge der Einfügung bei.

Ein Wort zu der Kapazität des HashSet. Wenn Sie abschätzen können, wie groß der Container wird, können Sie die Kapazität als Parameter angeben.

Set meinSet = new HashSet(64);
Der Vorgabewert ist 16. Verwenden Sie einen zu großen Speicher, vergeuden Sie Zeit und Speicherplatz. Ist die Kapazität zu klein, kommt es zu Zeitverlusten durch das notwendige Umkopieren des Sets.

Map-Implementierung: assoziativer Speicher

Für die Demonstration der Map eignet sich die Zuordnung des Kfz-Kennzeichens zu den Landkreisen geradezu ideal. Das Kennzeichen ist der Schlüssel, Objekte der Klasse Kreis dienen als Elemente bzw. Werte. Zunächst betrachten wir die Klasse namens Kreis.
public class Kreis {
    private String wo;
    long einwohner;
    Kreis(String w, long e) {
        wo = w; einwohner = e;
    }
    String getWo() {
        return wo;
    }
    long getEinwohner() {
        return einwohner;
    }
}
Als Schlüssel reicht ein einfacher String.

HashMap und sein Vorgänger Hashtable

Mit der Methode put werden Daten eingestellt. Dabei müssen immer der Schlüssel und das Element als Parameter angegeben werden.

Mit der Methode get wird ein Element hervorgeholt. Als Parameter wird der Schlüssel angegeben.

Die Methode containsKey prüft, ob der Schlüssel überhaupt vorhanden ist.

Um eine HashMap zu iterieren, erstellt man eine Set-View über den Schlüssel mit der Methode keySet. Von dieser lässt sich nun ein Iterator bilden, mit dem ein Durchlauf aller Elemente kein Problem darstellt. Die HashMap selbst stellt keinen Iterator zur Verfügung.

Das Beispiel füllt eine Map mit ein paar Kreisen, zeigt das Herausholen des Kreises Pinneberg über dessen Kennzeichen PI, um ihn gleich anschließend zu entfernen. Zuletzt wird die Map über einen Iterator ausgelesen und aufgelistet.

import java.util.HashMap;
import java.util.Set;
import java.util.Iterator;
import java.util.Enumeration;

public class TestHashMap {

    public static void main(String args[]) {
        HashMap kfzKennzeichen = new HashMap();
        kfzKennzeichen.put("SL", new Kreis("Schleswig-Flensburg",197903));
        kfzKennzeichen.put("HG", new Kreis("Hochtaunusgreis",227425));
        kfzKennzeichen.put("MH", new Kreis("Mühlheim",167344));
        kfzKennzeichen.put("PI", new Kreis("Pinneberg",303481));
        System.out.println("Es gibt " + kfzKennzeichen.size() + " Kennzeichen.");
        if (kfzKennzeichen.containsKey("PI")) {
            System.out.println("PI ist das Kennzeichen von: " + kfzKennzeichen.get("PI").getWo());
        } else {
            System.out.println("Kennzeichen PI unbekannt");
        }
        kfzKennzeichen.remove("PI");
        System.out.println("Eine Liste: ");
        Set s = kfzKennzeichen.keySet();
        Iterator e = s.iterator();
        while (e.hasNext()) {
            String k = (String) e.next();
            System.out.print(k + ": " + kfzKennzeichen.get(k).getWo());
            System.out.print(" (" + kfzKennzeichen.get(k).getEinwohner());
            System.out.println(" Einwohner)");
        }
    }
}

Der Vorgänger: Hashtable

Hashtable ist älter als HashMap und nicht Bestandteil des Java Collections Frameworks, erfüllt aber ähnliche Aufgaben. Aufgrund des Alters findet man ihn in diversen Programmen. Allerdings ist eine Überführung in das Java Collection Framework nicht so einfach möglich, so dass von seiner Verwendung abgeraten wird.

Die Unterschiede liegen darin, dass Hashtable synchronisiert ist, was bei HashMap durch das Programm durchgeführt werden muss. Ein Hashtable erlaubt null-Werte weder als Schlüssel noch als Wert. Ein Auslesen des Hashtable erfolgt nicht über einen Iterator, sondern über eine Enumeration, die ebenfalls nicht zum Java Collection Framework gehört.

import java.util.Hashtable;
import java.util.Enumeration;

public class TestHashtable {

    public static void main(String args[]) {
        Hashtable kfzKennzeichen = new Hashtable();
        kfzKennzeichen.put("SL", new Kreis("Schleswig-Flensburg",197903));
        kfzKennzeichen.put("HG", new Kreis("Hochtaunusgreis",227425));
        kfzKennzeichen.put("MH", new Kreis("Mühlheim",167344));
        kfzKennzeichen.put("PI", new Kreis("Pinneberg",303481));
        System.out.println("Es gibt " + kfzKennzeichen.size() + " Kennzeichen.");
        if (kfzKennzeichen.containsKey("PI")) {
            System.out.println("PI ist das Kennzeichen von: " + kfzKennzeichen.get("PI").getWo());
        } else {
            System.out.println("Kennzeichen PI unbekannt");
        }
        kfzKennzeichen.remove("PI");
        System.out.println("Eine Liste: ");
        Enumeration e = kfzKennzeichen.keys();
        while (e.hasMoreElements()) {
            String k = (String) e.nextElement();
            System.out.print(k + ": " + kfzKennzeichen.get(k).getWo());
            System.out.print(" (" + kfzKennzeichen.get(k).getEinwohner());
            System.out.println(" Einwohner)");
        }
    }
}

TreeMap und LinkedHashMap

Ein Hash ist zwar sehr schnell, aber unsortiert. Wird eine sortierte Reihenfolge benötigt, kann statt HashMap ein TreeMap verwendet werden. Der LinkedHashMap garantiert die Reihenfolge des Einfügens bei einer höheren Geschwindigkeit als beim TreeMap.

Homepage (C) Copyright 2011, 2016 Arnold Willemer