home  |  suche  |  kontakt/johner  |  institut  |  hinweise 
studierende  |  tech-docs  |  blog  |  mindmailer 
Java Grundlagen
Java Enterprise
Web-Entwicklung
Softwareentwicklung
Qualitätssicherung
Datenstrukturen
Med. Bildgebung
Skripts
Links und Literatur
SOTE1-Skript
SOTE2-Skript
Archi-Skript
Med-Imaging
1 Grundlagen Java
2 Vertiefung Java
3 Java Collections
4 Bäume und Graphen

3 Java Collections

3.1 Objektsammlungen

Oft muss eine 1-n Beziehung zwischen Objekten dargestellt werden.

Das Objekt, dem mehrere Objekte vom gleichen Typ zugeordnet sind, hat eine Objektsammlung von diesen Objekten. Objektsammlungen können unterschiedlich implementiert werden.

  1. statische Datenstrukturen
    Bsp: Array
    Vorteil: der Zugriff auf ein Objekt kann schnell über einen Index erfolgen
    Nachteil: feste Größe

    Die Lösung wäre hier ein dynamische Array. Ein dynamisches Array müsste noch Methoden zur Verfügung stellen, wie z.B. newInstance(), die das Array vergrößert und das Objekt hinzufügt oder Methoden, die das Array um ein Feld vergrößert oder verkleinert.

  2. dynamische Datenstrukturen
    Bsp.: Verkettete Liste
    Nachteil: langsame Suche und kein direkter Zugriff mit Hilfe eines keys

Die verkettete Liste soll hier genauer betrachtet werden. Jedes Objekt kennt seinen Nachfolger, in dem es eine Referenz darauf speichert. Im oberen Beispiel kennt der Student dabei das erste Buch und dieses kennt seinen Nachfolger und so weiter.

 

Hier ist man allerdings auf den Objekttyp Buch beschränkt und kennt nur das erste Element und muss sich bei jedem Zugriff durch die Liste arbeiten.

Deswegen kapselt man die Elemente der Liste in einer Klasse Node. Unabhängig vom Objekttyp können damit Elemente in die Liste eingefügt werden.

Das Objekt mit der Objektsammlung hat jetzt nicht mehr nur eine Referenz auf das erste Objekt sonder hält eine lineare Liste. Die lineare Liste hat eine Referenz auf die erste und letzte Node. Die Klasse Studentin ist nun völlig unabhängig vom Typ Buch und kennt nur die LinearList. Welche Objekte in den Nodes stehen ist frei wählbar.

Es gibt noch weitere dynamische Datenstrukturen wie z.B. den Stack, Queue oder Ringpuffer.

Ein Stack arbeitete nach dem LIFO-Prinzip (last-in-first-out). Die Elemente werden am vorderen Ende der Liste eingefügt und von dort auch wieder entnommen. Das heißt, die zuletzt eingefügten Elemente werden zuerst entnommen und die zuerst eingefügten zuletzt.

Eine Queue arbeitete nach dem FIFO-Prinzip ( first-in-first-out). Das Element, das als erstes einfügt wurde wird auch als erstes wieder entfernt. Das ist zu vergleichen mit einer normalen Warteschlange an einer Kasse. Der Erste, der in der Warteschlange wird als erstes bedient und kann die Warteschlange verlassen.

3.1.1 Collections des Typs Map

Dynamische Datenstrukturen können auch mit Hilfe eines Assoziativspeichers realisiert werden. Dieser Speicher bildet Schlüssel-Wert-Paare, d.h. ein Schlüssel wird auf einen Wert abgebildet und mit Hilfe dieses Wertes kann der passende Eintrag wieder gefunden werden. Eine solche Sammlung bzeichnet man als Hashtable.

So kann z.B.

  • ein Buch anhand der ISBN
  • ein Student anhand seiner Matrikelnummer
  • und ein Bürger anhand der Ausweisnummer

gesucht werden.

Für die Bildung des Schlüssel-Wert-Paars muss es eine Hashfunktion geben.

Regeln für die Hashfunktion

  • Übergabeparameter: Object (nur wenn die Hashfunktion nicht auf dem zu berechnenden Object implementiert wird)
  • Rückgabetyp: int
  • verschiedene Objekte sollten zu verschiedenen Ganzzahlen führen (Injektivität)
  • gleiche Objekte müssen zu gleichen Ganzzahlen führen (beim Einfügen und Suchen)
  • die Ganzzahlen müssen im Intervall [1,GrößeArray] liegen
  • der Aufwand für die Erstellung der Ganzzahlen sollte noch oben begrenzt sein
  • Zahlen sollten gleichmäßig über den Wertebereich verteilt sein

Die Tatsache von Punkt 4, das gleiche Objekte zu gleichen Ganzzahlen führen müssen, führt zu einer engen Beziehung zwischen equals() und der Hashfunktion. Das heißt, wenn x.equals(y) true ist muss auch folgendes gelten:

x.hashCode() == y.hashCode()

Um sicherzustellen, dass beide Methoden konsistent zueinander sind, müssen bei der Berechnung des Hashcodes nur die Informationen eingehen, die auch für die Implementierung von equals() berücksichtigt werden. Es müssen natürlich nicht alle Feldwerte auf den Objekte genutzt werden.

Zur Hilfestellung hier eine Vorgehensweise, wie eine Hashfunktion implementiert werden kann. Das ist nicht die einige Berechnung und bestimmt auch nicht die optimale, reicht aber oft aus. Folgende Formel wird verwendet:

hashcodeNeu = hashcodeAlt * multiplikator + feldwert

  • Der Anfangswert ist ungleich 0 und kann frei gewählt werden, im Beispiel wird 17 verwendet.
  • Mulitplikator ist eine nicht zu grosse Primzahl, im Beispiel 59.
  • alle Feldwerte müssen in ein Integert-Wert umgewandelt werden, zum Beispiel wie folgt:
    • boolean: 0 oder 1
    • byte, char, short, int: auf int casten
    • Referenz (anderes Objekt): dessen hashCode() Methode aufrufen
    • long: in zwei Integer zerlegen
    • double: Double.doubleToLongBits(feldwert) aufrufen, dann in long casten und als long behandeln
package progstruk.hashfunktion;

public class Student {

  private String name;
  private int matrikel;
  private Hochschule hochschule;

  @Override
  public int hashCode() {
    // nicht zu große primzahl
    final int multiplikator = 59;
    // start des hashcode auf eine bliebige Zahl setzen (!= 0)
    int hashcode = 17;
    // hochschule ist selbst ein objekt, dessen hashCode() nutzen
    hashcode = multiplikator * hashcode + hochschule.hashCode();
    // der feldwert 'matrikel' ist bereits ein Integer, keine konvertierung
    hashcode = multiplikator * hashcode + matrikel;
    // hashCode() von String nutzen
    hashcode = multiplikator * hashcode + name.hashCode();
    // alle Werte wurden auf den Startwert aufaddierd und kann so
    // zurückgegeben werden
    return hashcode;
  }

  @Override
  public boolean equals(Object obj) {
    // TODO
    // benutze hier ebenfalls die Feldwerte: name, matrikel, hochschule
    return true;
  }

}

Das Problem bei Maps, in der Objekte mit einem Schlüssel abgespeichert werden ist in den Regeln für die Hashfunktion in Punkt 2 beschrieben. Zwar sollten verschiedene Objekte (bzw. Schlüssel) zu verschiedenen Ganzzahlen führen, das kann aber nicht garantiert werden. Es kann und darf durch aus passieren, dass zwei verschiedene Objekte an den gleichen Index im Array gesetzt werden müssen. Für diesen Fall gibt es zwei Verfahren sogenannte Überlaufbehandlungen.

  1.  offenes Hashverfahren
    Wird festgestellt, dass bereits ein Objekt unter dem selben Index gespeichert ist, wird nach einer freien Stelle im Array gesucht. Die Suche nach dieser freien Stelle kann mit Hilfe einer dieser Sondierungsfunktionen erfolgen.
    • suche solange bis etwas frei ist
    • suche bei jedem n-ten Eintrag
    • nutze quadratische/kubische Funktionen (jeder 3.,9.,27.,..Eintrag)

    Egal welche Sondierungsregel benutzt wird um den neuen Index zu berechnen, der neue Index definiert sich wie folgt:

    neuerIndex =
    ( UrspruenglicherIndex(i) + Sondierungsregel(i) ) % groesseHash;

  2. linear verkettete Liste als Überlauf
    Alle Objekte, die den gleichen Index haben, werden in einer linear verketten Liste (Überlaufliste) gespeichert.
    In der Stelle im Array, auf die der Schlüssel verweist, steht jetzt nicht mehr das Objekt, sondern eine lineare Liste, die ein oder mehrere Objekte enthält. Die Objekte in der Liste haben alle einen Schlüssel, aus dem der selbe Index erzeugt wird.

Eine Hashtabelle stellt nun eine Objektstruktur dar, die nicht nur die Objekte mit Hilfe eines Schlüssels in eine Liste speichert, sonder sie stellte einen assoziativen Speicher dar, der sowohl Schlüssel als auch Wert abbildet. Über den Schlüsselbegriff ist ein direkter Zugriff auf den Wert möglich. Der Oberbegriff für solche Ojektstrukturen ist Map.

Im folgender Abbildung wird z.B. das Object 'Christopher' in einer Hashtabelle gespeichert. Der Schlüssel ist hier die Matrikelnummer (christopher.getMatrikelnummer()) und in ein Integer-Object gewrappt, weil der Schüssel auch ein Object sein muss. Mit Hilfe der Hashfunktion und dem Schlüssel wird der Index '3' ermittelt. Somit wird an die Stelle 3 in der Hashtabelle der Schlüssel (Matrikelnummer) und der Wert (Christopher) mit Hilfe der put-Methode gespeichert.

3.2 Java Collection Framework

Java bietet ein umfassendes Collection-Framework an. Eine Collection kann man sich als einen Container vorstellen, der Objekte in sich aufnehmen kann. Zudem haben diese Collections Methoden, mit welchen die Menge der enthaltenen Elemente bearbeitet werden kann, beispielsweise Elemente der Collection hinzufügen, entfernen oder sortieren.

Folgende wichtige Methoden stehen zur Verfügung:

 

Collection

List

Set

Map

int size()

Object get(int index)

boolean isEmpty()

void put(Object key, Object value)

boolean contains(Object element)

void add(Object element)

boolean add(Object element)

Object get(Object key)

add(Object element)

void add(Object element, in index)

boolean remove(Object element)

int size()

boolean remove(Object element)

int indexOf(Object element)

remove(Object key)


Object[] toArray()

HashSet keySet()

Collection values()

 

 Bei der Implementationsklasse Queue sind einige Besonderheiten zu beachten. Einige Methoden werfen Fehler wenn das zu bearbeitende Element nicht vorhanden ist.

 

Queue

wirft Fehler

gibt Wert zurück

Einfügen

add(Element e)

Das Element wird in die Queue eingefügt, ein Fehler wird geworfen wenn nicht möglich

offer(Element e)

wenn möglich, wird das Element in die Queue eingefügt

Entfernen

remove()

liefert und löscht das erste Element, wenn Queue leer ist wird Fehler geworfen

poll()

liefert und löscht das erste Element, wenn Queue leer ist wird null zurückgegeben.

Suchen

element()

liefert aber löscht das erste Element nicht, wenn Queue leer ist wird Fehler geworfen

peek()

liefert aber löscht das erste Element nicht, wenn Queue leer ist wird null zurückgegeben.

 3.2.1 Umsetzen einer 1:n Beziehung mit JCF

 Gegeben sei foglendes UML-Diagramm, dass in Java Code mit dem JCF umgesetzt werden soll.

Die Klasse Buch bleibt unverändert. Nur in der Klasse Student wird eine Collection, in der alle Bücher, die der Student ausgeliehen hat, gespeichert.

package objektsammlung;

public class Buch {
  private int isbn;
  private String titel;
  public int getIsbn() {
    return isbn;
  }
  public void setIsbn(int isbn) {
    this.isbn = isbn;
  }
  public String getTitel() {
    return titel;
  }
  public void setTitel(String titel) {
    this.titel = titel;
  }
  public  Buch(int isbn, String titel) {
    super();
    this.isbn = isbn;
    this.titel = titel;
  }
}

package objektsammlung;

import java.util.Collection;
import java.util.HashSet;

public class Student {
  private String name;
  private Collection<Buch> buecher = new HashSet<Buch>();
  
  public void buchausleihen(Buch buch){
    buecher.add(buch);
  }
  
  public int getAnzahlBuecher(){
    return buecher.size();
  }
  
  public boolean isBuchAusgeliehen(Buch b) {
    return buecher.contains(b);
  }
  
  public Collection<Buch> getBuecher(){
    return buecher;
  }
}