Angelika Langer - Training & Consulting
HOME | COURSES | TALKS | ARTICLES | GENERICS | LAMBDAS | IOSTREAMS | ABOUT | NEWSLETTER | CONTACT | Twitter | Lanyrd | Linkedin
 
HOME 

  OVERVIEW

  BY TOPIC
    JAVA
    C++

  BY COLUMN
    EFFECTIVE JAVA
    EFFECTIVE STDLIB

  BY MAGAZINE
    JAVA MAGAZIN
    JAVA SPEKTRUM
    JAVA WORLD
    JAVA SOLUTIONS
    JAVA PRO
    C++ REPORT
    CUJ
    OTHER
 

GENERICS 
LAMBDAS 
IOSTREAMS 
ABOUT 
NEWSLETTER 
CONTACT 
Java Generics - Einführung

Java Generics - Einführung
Java Generics - Parametrisierte Typen und Methoden
 

JavaMagazin, April 2004
Angelika Langer & Klaus Kreft


 

Java Generics


Mit der nächsten Version 1.5 der Java 2 Standard Edition (J2SE) wird die Programmiersprache Java um einige neue Sprachmittel erweitert.  Die gravierendste Änderung an der Sprache ist die Einführung von generischen Typen und Methoden, den sogenannten Java Generics (JG).  Die Freigabe von J2SE 1.5 ist für den August 2004 geplant.  Aus diesem Anlass wollen wir das neue Sprachmittel der Java Generics in diesem Artikel vorstellen.
 

1 Überblick über die Sprachmittel der Java Generics

1.1 Wozu braucht man Generics?


Der Wunsch nach generischen Typen liegt in allen Sprachen, die ein solches Sprachmittel haben, in der Implementierung von Datenstrukturen wie Collections oder Containern. Generische Typen werden benötigt, um solche Datenstrukturen effizient implementieren zu können.  Wenn man eine Collection implementieren will, dann stellt man fest, dass die Implementierung weitgehend unabhängig vom Typ der Elemente ist, die in der Collection abgelegt werden. Man möchte deshalb idealerweise nur eine einzige Implementierung der Collection zur Verfügung stellen, die dann für das Ablegen beliebiger Elementtypen verwendet werden kann.

Traditionell (in nicht-generischem Java) erreicht man das dadurch, dass die Collection-Klassen (siehe z.B. die Klassen aus dem J2SE Collection Framework) Referenzen vom Typ Object verwalten.  Da Object die Superklasse aller Java-Klassen ist, kann eine Collection Elemente beliebigen Typs enthalten.  Ausgenommen sind lediglich die primitiven Typen, weil sie nicht von Object abgeleitet sind.  Aber das ist kein größeres Problem, weil es zu jedem primitiven Typ einen korrespondierenden Referenztyp gibt.  Die Umwandlung eines primitiven Typs in den korrespondierenden Referenztyp bezeichnet man als Boxing .  Das musste man bisher von Hand machen, aber in J2SE 1.5 wird das Boxing eine automatische Konvertierung (Autoboxing) sein, die man nicht mehr explizit hinschreiben muss.

Eine Eigenschaft der so implementierten Collections ist, dass sie nicht notwendig homogen sind, in dem Sinne, dass sie nicht notwendig Elemente desselben Typs enthalten.  Vielmehr kann eine Collection eine Mischung von Objekten unterschiedlichen Typs verwalten.  Das führt dazu, dass man beim Herausholen eines Elements aus einer Collection niemals genau weiß, von welchem Typ das betreffende Element ist.  Deshalb muss man einen Cast machen, ehe man das Element verwenden kann.  Hier ein Beispiel:

LinkedList list = new LinkedList();
list.add(new Integer(0));
Integer i = (Integer) list.get(0);

Dieser Cast ist ein Laufzeit-Cast vom Typ Object-Referenz auf den Typ Integer-Referenz.  Sollte sich zur Laufzeit herausstellen, dass das Element kein Integer ist, dann wird eine ClassCastException ausgelöst.  Die traditionellen Implementierungen von Collections erfordern also relativ viele Casts, die zur Laufzeit scheitern können.

Java Generics erlauben nun eine alternative Implementierungstechnik, bei der die Collections mit einem Element-Typ parametrisiert werden und dann homogen sind, also Elemente desselben Typs enthalten. Das Einfügen eines Elements eines "fremden" Typs wird zur Compilezeit bereits abgewiesen.  Infolgedessen muss beim Herausholen eines Elements aus der Collection nicht mehr geprüft werden, ob das gefundene Element vom gewünschten Typ ist. Der lästige Laufzeit-Cast entfällt deshalb.  Hier ein Beispiel:

LinkedList<Integer> list = new LinkedList<Integer>();
list.add(new Integer(0));
Integer i = list.get(0);

Im Vergleich zu einer traditionell implementierten Collection, wo Laufzeit-Casts beim Herausholen der Elemente nötig sind, werden bei einer parametrisierten Collection Typprüfungen bereits zur Compilezeit beim Einfügen der Elemente gemacht.  Traditionelle Collections sind ein Beispiel für Weak Typing mit Typprüfungen zur Laufzeit; parametrisierte Collections sind ein Beispiel für Strong Typing, bei dem Typprüfungen zur Compilezeit bereits gemacht werden.  In J2SE 1.5 hat der Programmierer nun beide Techniken zur Verfügung.

Die Collections des traditionellen Collection-Frameworks werden im übrigen in J2SE 1.5 durch entsprechende parametrisierte Collections ersetzt.  Wie oben bereits gezeigt, kann die LinkedList in J2SE1.5 als LinkedList<String> oder LinkedList<Integer> oder LinkedList<AnyType> verwendet werden.  Die herkömmliche Verwendung als LinkedList ist aber weiterhin möglich.  Auf diesen Kompatibilitätsaspekt gehen wir später noch genauer ein.

Sehen wir uns aber zunächst einmal die Syntax der Java Generics genauer an.  Man kann nämlich nicht nur die vorgefertigten parametrisierten Typen des Collection-Frameworks verwenden (wie im obigen Beispiel gezeigt), sondern man kann selber parametrisierte Typen implementieren.  Sehen wir uns an, wie das im Detail aussieht.
 

1.2 Generische Typen

Listing 1 zeigt Beispiele verschiedener parametrisierter Typen, die angelehnt sind an die Typen, die im 1.5 Collection-Framework zur Verfügung stehen.  Der Beispiel-Code zeigt eine parametrisierte Klasse LinkedList<A>, ihr Super-Interface Collection<A> und ihren Iterator vom Typ Iterator<A>.
 
Listing 1: Parametrisierter Typen am Beispiel einer LinkedList *)  Die Implementierung ist stark vereinfacht und dient lediglich als Anschauungsmaterial für die Nutzung von Typparametern. Eine realistische Implementierung findet man in den Sourcen des JDK 1.5.  Vielen Dank an Herrn Martin Jung <mjung@gitarren-tools.de> für seinen Korrekturvorschlag zur Implementierung des Iterators.

interface Collection<A>  {
 public void add (A x);
 public Iterator<A> iterator ();
}
interface Iterator<A> {
 public A next ();
 public boolean hasNext();
}
class NoSuchElementException extends RuntimeException {}

class LinkedList<A> implements Collection<A>{
    protected class Node{
        A elt;
        Node next = null;
        Node(A elt){this.elt=elt;}
    }
 
    protected Iterator<A> myIterator = null;
    protected Node head = null;
    protected Node tail = null;
 
    public LinkedList(){
    }
 
    public void add(A elt){
        if(head==null){
            head=new Node(elt);
            tail=head;
        } else{
            tail.next = new Node(elt);
            tail=tail.next;
        }
    }
 
    public Iterator<A>iterator(){
        if (myIterator == null) {
            myIterator = new Iterator<A>(){
                protected Node ptr = head;
                public boolean hasNext(){
                    return ptr != null;
                }
                public A next(){
                    if(ptr != null){
                        A elt = ptr.elt;
                        ptr = ptr.next;
                        return elt;
                    } else {
                        throw new NoSuchElementException();
                    }
                }
            };
        }
        return myIterator;
    }
}
final class Test {
 public static void main (String[ ] args) {
   LinkedList<String> ys = new LinkedList<String>();
   ys.add("zero"); ys.add("one");
   String y = ys.iterator().next();
 }
}

Parametrisierte Typen unterscheiden sich von regulären Typen dadurch, dass sie Typparameter haben. (Typparameter werden auch als Typvariablen bezeichnet; beide Begriffe sind synonym.)  In unserem Beispiel haben die parametrisierten Typen genau einen Parameter mit dem Namen A. A bezeichnet dabei den Typ der Elemente, die in der Liste abgelegt werden können. Den Typparameter A kann man sich als Platzhalter für einen Typ vorstellen, der später durch einen konkreten Typ ersetzt wird.  Beispielsweise wäre in einer LinkedList<String>, der Typparameter A durch den konkreten Typ String ersetzt.  Die Sache mit dem Platzhalter stimmt nicht ganz, wie wir später noch erläutern werden; aber in erster Näherung ist das eine angemessene Vorstellung von einem Typparameter.
 

1.3 Bounds

Für die Implementierung der LinkedList mussten wir eigentlich nichts über den unbekannten Elementtyp A wissen.  Wir haben lediglich die Objekt-Referenzen verwaltet.  Da wir keine Methode des Typs A aufgerufen haben, ist es völlig egal, welche Felder oder Methoden der konkrete Typ später hat.

Das ist nicht bei allen Collections so.  Nehmen wir zum Beispiel die Implementierung einer Baum-basierten Collection wie TreeMap.  Eine TreeMap enthält Paare bestehend aus einem Schlüssel (Key) und einem assoziierten Wert (Data).  Diese Einträge werden in sortierter Reihenfolge gehalten.  Die Sortierreihenfolge wird mit Hilfe der compareTo()-Methode des Key-Typs bestimmt; deshalb wird verlangt, dass der Key-Typ das Comparable-Interface implementiert, welches eine compareTo()-Methode verlangt.  Listing 2 zeigt einen Auszug aus einer denkbaren Implementierung einer parametrisierten TreeMap.

Listing 2: Implementierung einer Baum-basierten Collection – ohne Bounds

public interface Comparable<T> {
 public int compareTo(T arg);
}
public class TreeMap<Key,Data>{
   private static class Entry<K,V> {
     K key;
     V value;
     Entry<K,V> left = null;
     Entry<K,V> right = null;
     Entry<K,V> parent;
   }
   private transient Entry<Key,Data> root = null;
   …
   private Entry< Key,Data > getEntry(Key key) {
       Entry<Key,Data> p = root;
       Key k = key;
       while (p != null) {
           int cmp = ((Comparable<Key>)k).compareTo(p.key);
           if (cmp == 0)
               return p;
           else if (cmp < 0)
               p = p.left;
           else
               p = p.right;
       }
       return null;
   }
   public boolean containsKey(Key key) {
       return getEntry(key) != null;
   }
   …
}

Die Klasse TreeMap hat 2 Typparameter Key und Data, die für den Typ des Schlüssels und den Typ des assoziierten Werts stehen. Außerdem gibt es eine eingeschachtelte parametrisierte Klasse Entry, die ebenfalls 2 eigene Typparameter K und V mit analoger Bedeutung hat. Auch das Interface Comparable ist parametrisiert - mit einem Typparameter, der beschreibt, zu welchem Typ ein Comparable-Objekt vergleichbar ist.

Interessant ist der Aufruf der compareTo()-Methode in der Implementierung von getEntry().  Da über den Key-Typ nichts bekannt ist, ist zunächst einmal ein Cast auf den Typ Comparable<Key> nötig, ehe die compareTo()-Methode aufgerufen werden kann. Sollte sich in der Collection ein Element befinden, dass nicht Comparable ist, dann würde dieser Cast zur Laufzeit eine ClassCastException auslösen.  Man hat also wieder eine relativ späte Typprüfung zur Laufzeit.

Um eine frühe Typprüfung zur Compilezeit zu ermöglichen, gibt es in Java Generics das Sprachmittel der Bounds.   Ein Typparameter kann einen oder mehrere sogenannte Bounds haben.  Bounds sind Klassen oder Interfaces, von denen der unbekannte Typ abgeleitet sein muss.  Der Compiler prüft dann, ob der konkrete Typ, der für den Typparameter später eingesetzt wird, von den spezifizierten  Bounds abgeleitet ist.

In unserem Beispiel der TreeMap können wir Bounds benutzen, um sicher zu stellen, dass der Key-Typ immer das Interface Comparable<Key> implementiert. Das sieht dann so aus, wie in Listing 3 dargestellt.

Listing 3: Implementierung einer Baum-basierten Collection  - mit  Bounds

public class TreeMap<Key extends Comparable<Key>,Data> {
   static class Entry<K,V> {
     K key;
     V value;
     Entry<K,V> left = null;
     Entry<K,V> right = null;
     Entry<K,V> parent;
   }
   private transient Entry<Key,Data> root = null;
   …
   private Entry< Key,Data > getEntry(Key key) {
       Entry<Key,Data> p = root;
       Key k = key;
       while (p != null) {
           int cmp = k.compareTo(p.key);
           if (cmp == 0)
               return p;
           else if (cmp < 0)
               p = p.left;
           else
               p = p.right;
       }
       return null;
   }
   public boolean containsKey(Key key) {
       return getEntry(key) != null;
   }
   …
}

Da nun sichergestellt ist, dass für den Typparameter Key nur Typen eingesetzt werden können, die das Interface Comparable<Key> implementieren, kann der Cast beim Aufruf von compareTo() entfallen.

Der Hauptzweck der Bounds besteht darin, dem Compiler die Möglichkeit zu geben, gewisse Typeigenschaften der Typparameter bereits zur Compilezeit zu prüfen. Beispielsweise würde der Compiler eine Instanziierung als TreeMap<Number,String> abweisen, weil Number nicht Comparable<Number> ist.  Eine TreeMap<String,Number> wäre hingegen in Ordnung, weil String (in J2SE 1.5) das Interface  Comparable<String> implementiert.

Desweiteren haben die Bounds die Funktion, dem Compiler den Aufruf von Methoden des unbekannten Typs zu ermöglichen.  Über einen Typparameter ohne Bounds weiß der Compiler nichts; er kann also ohne Cast nur die Methoden aufrufen, die bereits in Object definiert sind.  Wenn hingegen ein Typparameter Bounds hat, dann kann der Compiler alle Methoden, die in den Bounds definiert sind, ohne Cast aufrufen.  Das gilt allerdings nur für nicht-statische Methoden; Konstruktoren oder statische Methoden können nicht durch Bounds zugänglich gemacht werden.  Die meisten Bounds sind in der Praxis Interfaces, wie das Comparable-Interface in unserem Beispiel.

Die Syntax für einen Typparameter mit mehreren Bounds sieht wie folgt aus:

TypParameter implements SuperClass & Interface1 & Interface2 & ... & InterfaceN
Es gibt eine Einschränkung:  in den Bounds dürfen nicht mehrere Instanziierungen desselben parametrisierten Interfaces vorkommen.  Die folgende Deklaration wäre beispielsweise illegal:

class SomeType<T implements Comparable<String> & Comparable<StringBuffer>>
{ … }

Comparable<String> und Comparable<StringBuffer> sind Instanziierungen des Comparable-Interfaces und dürfen deshalb nicht beide in den Bounds des Typparameters T vorkommen.  Woher diese Einschränkung kommt, erläutern wir später noch.
 

1.4 Generische Methoden

Zusätzlich zu den generischen Typen lassen sich auch generische Methoden definieren.  Die Syntax ist ein wenig anders als bei den generischen Typen, aber alles bisher Gesagte über Typparameter und Bounds gilt genauso auch für generische Methoden.  Alle Arten von Methoden können parametrisiert werden: statische und nicht-statische Methoden sowie Konstruktoren.  Listing 4 zeigt das Beispiel einer parametrisierten max()-Methode, die das größte Element in einer Collection findet:

Listing 4: Beispiel einer parametrisierten Methode

interface Comparable<A> {
  public int compareTo(A that);
}
final class Byte implements Comparable<Byte> {
 private byte value;
 public Byte (byte value) { this.value = value; }
 public byte byteValue () { return value; }
 public int compareTo (Byte that) {
   return this.value - that.value;
 }
}
class Collections {
 public static <A extends Comparable<A>> A max (Collection<A> xs) {
   Iterator<A> xi = xs.iterator();
   A w = xi.next();
   while (xi.hasNext()) {
     A x = xi.next();
     if (w.compareTo(x) < 0) w = x;
   }
   return w;
 }
}
final class Test {
 public static void main (String[ ] args) {
   LinkedList<Byte> byteList = new LinkedList<Byte>();
   byteList.add(new Byte((byte)0));
   byteList.add(new Byte((byte)1));
   Byte y = Collections.max(byteList);
 }
}

Parametrisierte Methoden werden wie ganz normale Methoden aufgerufen, wie man in der main()-Methode sehen kann.  Der konkrete Typ, der den Typparameter ersetzt, muss nicht explizit angegeben werden.  Er wird automatisch vom Compiler aus dem Typ des Arguments deduziert, das beim Aufruf an die parametrisierte Methode übergeben wird.  In unserem Beispiel wird eine LinkedList<Byte> als Argument an die max()-Methode übergeben.  Der Compiler ruft dann automatisch die Instanziierung max<Byte>() auf, ohne dass explizit spezifiziert werden muss, dass der Typparameter A durch Byte ersetzt werden soll.  Das überlegt sich der Compiler von ganz alleine.  Diesen Prozess bezeichnet man als Type Inference.

1.5 Wildcard-Instanziierungen

Der Vollständigkeit halber wollen wir noch die sogenannten Wildcard-Instanziierungen parametrisierter Typen erwähnen. Bisher haben wir ausschließlich Instanziierungen von parametrisierten Typen gezeigt, bei denen der Typparameter durch einen konkreten Typ ersetzt war.  Ein Beispiel ist List<String>.  Nun kann man aber nicht nur konkrete Typen für den Typparameter einsetzen, sondern auch sogenannte Wildcards.  Es gibt 3 Arten von Wildcards: "? extends Type", "? super Type" und "?".  Wildcard-Instanziierungen sehen dann zum Beispiel so aus:  List<? extends Number>, oder List<? super Long> oder List<?>.

Ein Wildcard bezeichnet keinen konkreten Typ, sondern eine Familie von Typen. Das Wildcard "? extends Number" bezeichnet beispielsweise die Menge aller Typen, die vom Typ Number direkt oder indirekt abgeleitet sind, d.h. die Familie aller Subtypen von Number, also Long, Integer, usw., inklusive Number selbst.  Die Wildcard-Instanziierung List<? extends Number>  bezeichnet daher logischerweise die Familie aller Instanziierungen des parametrisierten Typs List, bei dem ein Typ aus der Familie der Subtypen von Number für den Typparameter eingesetzt wurde, also List<Long>, List<Integer>, usw. inklusive List<Number>.  Ein Wildcard wie "? super Long" bezeichnet die Familie aller Supertypen von Long und das Wildcard "?" steht für die Menge aller Typen.

Eine Wildcard-Instanziierung eines parametrisierten Typs kann verglichen mit einer konkreten Instanziierung nicht dazu verwendet werden, um Objekte zu erzeugen.  Man kann zwar eine Variable vom Typ List<? extends Number>  deklarieren, aber man kann kein Objekt vom Typ List<? extends Number>  erzeugen.  Eine Variable vom Typ List<? extends Number>  kann aber auf Objekte von kompatiblen Typen verweisen.  Die kompatiblen Typen sind genau die Typen aus der Familie von Typen, die die Wildcard-Instanziierung bezeichnet.  Eine Referenzvariable vom Typ List<? extends Number>  kann also auf ein Objekt vom Typ List<Long> oder List<Integer> usw. verweisen.   Analog kann eine Variable vom Typ List<? super Long> auf Objekte vom Typ List<Long> oder List<Number> oder List<Comparable> usw. verweisen.   Eine Variable vom Typ List<?> kann auf beliebige Instanziierungen von List verweisen.

Der Zugriff auf ein Objekt, das über eine Referenzvariable vom Typ Wildcard-Instanziierung referenziert wird, ist eingeschränkt.  Über eine Variable  vom Typ List<? extends Number> beispielsweise dürfen keine Methoden des Typs List aufgerufen werden, die ein Argument vom dem Typ nehmen, für den das Wildcard steht.  Hier ist ein Beispiel:

List<? extends Number> list = new LinkedList<Integer>();
list.add(new Integer(25));  // compile-time error

Bei einem Wildcard mit "super" ist der Aufruf von Methoden unmöglich, deren Returntyp vom dem Typ ist, für den das Wildcard steht.  Für das "?" Wildcard gelten beide Einschränkungen.

Warum diese Einschränkungen gelten, wollen wir an dieser Stelle nicht erläutern, weil es den Rahmen des Artikels sprengen würde.  Auch auf die Benutzung der Wildcard-Instanziierungen können wir an dieser Stelle nicht eingehen.  In der Praxis wird man Wildcard-Instanziierungen in der Regel als Argument- und Returntyp von Methoden finden, und eher seltener für die Deklaration von Referenzvariablen. Dabei dürfte das Wildcard mit "extends" am häufigsten Verwendung finden.  In den J2SE 1.5 Plattform-Bibliotheken findet man Beispiele dafür (siehe z.B. die Methode boolean addAll(Collection<? extends E> c) der Klasse java.util.List).
 

1.6 Nachsatz zum Überblick

Damit wären die Grundbegriffe von Java Generics erklärt.  Das neue Sprachmittel ist in der Tat ausgesprochen nützlich und erlaubt es, stärker selbsterklärenden Code zu schreiben.  Der Software-Entwickler kann jetzt klar und unmissverständlich sagen, dass eine Methode beispielsweise eine Collection von Strings erwartet, und nicht eine Collection irgendeinen anderen Inhalts  Es kann also mehr Information im Source-Code hinterlegt werden und damit dem Leser des Codes das Verständnis erleichtert, aber auch dem Compiler die Möglichkeit gegeben werden, viele Typprüfungen bereits zur Compilezeit zu machen, die traditionell erst zur Laufzeit gemacht wurden.  Beides erweist sich in der praktischen Arbeit als nützlich.

Die Praxis zeigt aber auch, dass Java Generics allerlei Überraschungen zu bieten haben, wobei mit "Überraschungen" unerwartete Einschränkungen, gewöhnungsbedürftige Semantik, und ähnliche Phänomene gemeint sind. Insbesondere Entwickler mit C++-Kenntnissen, die sich bei Java Generics an C++-Templates erinnert fühlen, werden überrascht sein zu sehen, dass Java Generics mit C++-Templates, abgesehen von der Syntax, nicht viel gemeinsam haben.

Um die Semantik von Java Generics im Detail verstehen zu können, ist es hilfreich zu wissen, wie der Java Compiler parametrisierte Typen und Methoden übersetzt.  Die Implementierung des Sprachmittels erklärt viele der eher überraschenden Seiten von Java Generics.  Deshalb sehen wir uns im folgenden die Implementierung des Sprachmittels an.
 
 

2 Implementierung von Java Generics


Wie üblich, übersetzt der Java Compiler parametrisierte Typen und Methoden in Java Bytecode.  Wir wollen uns ansehen, wie ein Compiler diese Übersetzung prinzipiell bewerkstelligt.  Betrachten wir das zunächst einmal völlig unabhängig von der Programmiersprache Java.  Es gibt ja auch andere Sprachen, die parametrisierte Typen und Methoden unterstützen (z.B. Ada, C++, C#).

2.1 Übersetzung von Generics

Ein Compiler hat im Prinzip 2 Möglichkeiten, um einen parametrisierten Typ oder eine parametrisierte Methode zu übersetzen.
  • Code-Spezialisierung. Dabei erzeugt der Compiler eine jeweils separate Repräsentation für jede einzelne Instanziierung eines parametrisierten Typs/Methode.  Beispielsweise würde ein Compiler mit dieser Technik Code für eine Liste von Strings und Code für eine Liste von Integers erzeugen.
  • Code-Sharing. Dabei erzeugt der Compiler nur eine einzige Repräsentation pro parametrisiertem Typ/Methode.  Die verschiedenen Instanziierungen des parametrisierten Typs/Methode werden auf diese eine Repräsentation abgebildet, wobei Typprüfungen und Typkonvertierungen eingefügt werden, wo immer das nötig ist.
Code-Spezialisierung ist die in C++ verwendete Übersetzungstechnik.  Ein C++-Compiler generiert aus einem Template für jede Instanziierung unterschiedlichen Binärcode. Aus einem Listen-Template beispielsweise entsteht der Binärcode für mehrere Listen-Klassen.  Bei dieser Technik besteht die Gefahr, dass sehr viel Binärcode entsteht.

Das ist insbesondere dann reine Verschwendung, wenn beispielsweise eine Collection ausschließlich Pointer oder Referenzen auf Elemente verwaltet.  Pointer und Referenzen sind alle gleich groß und ihre Verwendung ist völlig unabhängig vom Typ des referenzierten Objekts. Der generierte Binärcode für eine Liste von String-Referenzen ist nahezu identisch mit dem Binärcode für eine Liste von Integer-Referenzen.  Der Unterschied liegt lediglich in einigen Typprüfungen und –konvertierungen, wenn Elemente in die Collection hineingegeben oder aus der Collection herausgeholt werden..

Da in Java fast alle Typen Referenztypen sind, ist es naheliegend, dass für die Übersetzung von parametrisierten Typen und Methoden in Java die Code-Sharing-Technik verwendet wird.

Code-Sharing hat den Vorteil, dass tendenziell weniger Binärcode erzeugt wird.  Es verhindert aber andererseits die Verwendung von primitiven Typen als Typargumente einer Instanziierung. Und so kann man in Java Generics beispielsweise keine LinkedList<int> verwenden; lediglich die LinkedList<Integer> ist erlaubt.
 

2.2 Type Erasure

Java übersetzt parametrisierte Typen und Methoden mit der Code-Sharing-Technik.  Dabei müssen die verschiedenen Instanziierungen auf die eine gemeinsame Repräsentation des parametrisierten  Typs/Methode abgebildet werden.  Wie erfolgt diese Abbildung?

In Java Generics erfolgt diese Abbildung über eine sogenannte Type Erasure .  Die Übersetzung mittels Type Erasure kann man sich vorstellen wie eine Übersetzung von generischem Java in reguläres Java: von der Instanziierung eines parametrisierten Typs/Methode werden sämtliche Typparameter entfernt, und in der Definition eines parametrisierten Typs/Methode  wird der Typparameter durch sein erstes Bound oder den Typ Object ersetzt, falls keine Bounds angegeben waren.

Aus der parametrisierten LinkedList<A> wird eine LinkedList<Object> und aus ihren Instanziierungen wie LinkedList<String> und LinkedList<Integer> wird LinkedList. Parametrisierte Methoden wie max<A extends Comparable<A>>() und ihre Instanziierungen wie max<Integer>() und max<String>() werden übersetzt in eine Methode max<Comparable>() bzw. max().  Listing 5 und 6 zeigen die parametrisierten Typen aus Listing 1 und 4 nach der Type Erasure.

Listing 5:  Parametrisierte Typen nach der Type Erasure

interface Collection {
 public void add (Object x);
 public Iterator iterator();
}
interface Iterator {
 public Object next();
 public boolean hasNext();
}
class NoSuchElementException extends RuntimeException {}

class LinkedList implements Collection{
    protected class Node{
        Object elt;
        Node next = null;
        Node(Object elt){this.elt=elt;}
    }
 
    protected Iterator myIterator = null;
    protected Node head = null;
    protected Node tail = null;
 
    public LinkedList(){
    }
    public void add(Object elt){
        if(head==null){
            head=new Node(elt);
            tail=head;
        } else{
            tail.next = new Node(elt);
            tail=tail.next;
        }
    }
    public Iterator iterator(){
        if (myIterator == null) {
            myIterator = new Iterator(){
                protected Node ptr = head;
                public boolean hasNext(){
                    return ptr != null;
                }
                public Object next(){
                    if(ptr != null){
                        Object elt = ptr.elt;
                        ptr = ptr.next;
                        return elt;
                    } else {
                        throw new NoSuchElementException();
                    }
                }
            };
        }
        return myIterator;
    }
}
final class Test {
 public static void main (String[ ] args) {
   LinkedList ys = new LinkedList();
   ys.add("zero"); ys.add("one");
   String y = (String)ys.iterator().next();    // cast inserted
 }
}

Wie man sehen kann, wurde der Typparameter A überall durch den Typ Object ersetzt.  Das Ergebnis dieser Transformation ist exakt die Implementierung einer LinkedList, die man ohne Java Generics gebaut hätte: die entstandene nicht-parametrisierte Liste verwaltet alle Elemente per Object-Referenz.  Das ist ein beabsichtigter Effekt, weil auf dieser Weise die neuen parametrisierten Collections kompatibel zu den traditionellen nicht-parametrisierten Collections sind.  Nach der Übersetzung per Type Erasure kann man die parametrisierte Collection von der nicht-parametrisierten traditionellen Collection-Implementierung nicht mehr unterscheiden.

Listing 5 zeigt noch ein weiteres typisches Element der Übersetzung von generischem in nicht-generisches Java: beim Herausholen von Elementen aus der Collection wird automatisch ein Cast eingefügt.  Das ist genau der Cast, den man bei den traditionellen Collections schon immer gebraucht hat.  Wenn ein Element aus einer LinkedList<String> (nach der Übersetzung nur noch eine LinkedList) geholt wird, dann ist das Ergebnis eine Object-Referenz, die auf den Typ String gecastet wird.  Den entsprechenden Cast hat der Compiler im Zuge der Übersetzung automatisch eingefügt.

Ganz ähnlich funktioniert die Übersetzung einer generischen Methode. Listing 6 zeigt die Type Erasure der parametrisierten Methode max() aus Listing 4:

Listing 6: Parameterisierte Methode nach der Type Erasure

interface Comparable {
  public int compareTo(Object that);
}
final class Byte implements Comparable {
 private byte value;
 public Byte (byte value) { this.value = value; }
 public byte byteValue () { return value; }
 public int compareTo (Byte that) {
   return this.value - that.value;
 }
 public int compareTo (Object that) { // bridge method inserted
   return this.compareTo((Byte)that);
 }
}
class Collections {
 public static Comparable max (Collection xs) {
   Iterator xi = xs.iterator();
   Comparable w = (Comparable)xi.next();
   while (xi.hasNext()) {
     Comparable x = (Comparable)xi.next();
     if (w.compareTo(x) < 0) w = x;
   }
   return w;
 }
}
final class Test {
 public static void main (String[ ] args) {
   LinkedList ys = new LinkedList();
   ys.add(new Byte((byte)0)); ys.add(new Byte((byte)1));
   Byte y = (Byte)Collections.max(ys);    // cast inserted
 }
}

Wieder wurden die Typparameter an allen Stellen durch ihr erstes Bound oder Object ersetzt.  Man sieht in main() wieder den automatisch eingefügten Cast für das Ergebnis der max()-Methode. Das Beispiel demonstriert darüber hinaus ein weiteres Element der Übersetzung per Type Erasure: die sogenannte Bridge-Methode.

Bridge-Methoden werden eingefügt, damit das Überschreiben von Methoden in Subklassen funktioniert, die von parametrisierten Superklassen oder –interfaces abgeleitet sind. In dem gewählten Beispiel implementiert die Klasse Byte das Interface Comparable<Byte> und muss die Methode int compareTo(Byte) implementieren.  Nach der Type Erasure ist aus dem Interface Comparable<Byte> ein schlichtes Interface Comparable mit einer Methode int compareTo(Object) geworden.  Die implementierende Klasse Byte hat aber keine Implementierung für diese Methode; statt dessen hat sie eine Methode int compareTo(Byte).  Diese Methode ist aber keine überschreibende Variante der im Interface verlangten Methode, weil die Signatur anders ist.  Die Klasse Byte, die vor der Type Erasure das Interface Comparable<Byte> implementiert hat, implementiert nach der Type Erasure das nun entstandene Interface Comparable nicht mehr.  Der generierte Code würde sich also ohne weitere Maßnahmen nicht übersetzen lassen.  Um dies zu vermeiden, fügt der Compiler nun die Bridge-Methode ein.

Eine Bridge-Methode wird in Subklassen benötigt, die von einem parametrisierten Interface oder einer parametrisierten Superklasse abgeleitet sind.  Die Bridge-Methode hat genau die Signatur, die der Supertyp nach der Type Erasure verlangt.  In unserem Beispiel hat die Bridge-Methode die Signatur int compareTo(Object).  Bridge-Methoden sind immer so implementiert, dass sie an die eigentliche Methode delegieren, in unserem Beispiel an die Methode int compareTo(Byte).  Der Compiler fügt die Bridge-Methoden im Zuge der Übersetzung per Type Erasure automatisch ein.
 

2.3 Repräsentation von Generics im Laufzeitsystem

Die Übersetzung per Type Erasure haben wir zur Veranschaulichung als Übersetzung von generischem Java in reguläres Java erklärt.  In Wahrheit erzeugt der Compiler selbstverständlich keine temporäres .java-Datei, die er dann in eine .class-Datei übersetzt, sondern die Übersetzung erfolgt direkt von generischem Java nach Java Bytecode.  Der generierte Bytecode entspricht exakt dem nicht-generischen Javacode, den wir in den Beispielen gezeigt haben.  Davon kann man sich leicht durch eine Decompilation der .class-Datei überzeugen.

Es gibt einige wenige Spuren, die die Generics in einer .class-Datei dennoch hinterlassen: es werden sogenannte Signature-Attribute im Bytecode ablegen; sie enthalten statische Information über die Typparameter einer Klasse oder Methode.  Diese Signature-Attribute werden von der virtuellen Maschine als Kommentar behandelt und nicht ausgewertet.  Die Signature-Attribute  werden lediglich vom Compiler ausgewertet, um beispielsweise zu prüfen, ob eine Instanziierung zulässig im Sinne der Bounds ist.  Für die virtuelle Maschine ist hingegen keinerlei Unterschied zwischen einem parametrisierten Typ/Methode und einem regulären Typ/Methode zu erkennen. Nach der Type Erasure sind die Typparameter (bis auf die Signature-Attribute) verschwunden und damit sieht 1.5-Bytecode für die JVM so aus wie 1.4-Bytecode.

Die Übersetzung per Type Erasure wurde bewusst von den Designern der Java Generics als Übersetzungstechnik gewählt.  Ziel des Designs der Java Generics ist die hundertprozentige Kompatibilität des aus Generics generierten Bytecode mit herkömmlichem Bytecode.  Es soll problemlos möglich sein,  generischen mit nicht-generischem Code zu mischen und beides sowohl unter einer neuen, aber auch unter einer alten (d.h. 1.4) JVM ablaufen zu lassen.  Mit Hilfe der Type Erasure wurde dieses Kompatibilitätsziel erreicht.

Die vollständige Eliminierung der Typparameter im Rahmen der Type Erasure hat den Vorteil der Kompatibilität mit nicht-generischem Java.  Dies wird erkauft durch verschiedene Einschränkungen, die sich aus der Type Erasure ergeben.  Der wohl wesentlichste Nebeneffekt ist das Fehler jeglicher Information über die Typparameter zur Laufzeit.  Beim Ablauf des Programm kann eine LinkedList<String> nicht von einer LinkedList<Integer> unterschieden werden.  Beide haben zur Laufzeit nur noch den Type LinkedList.  Das führt zu allerlei interessanten Effekten und Überraschungen, deren Darstellung den Rahmen dieses Artikels sprengen würden. Zu den Einschränkungen gehört u.a., dass keine Arrays von parametrisierten Typen verwendet werden dürfen. Eine Deklaration wie Comparable<String>[] ist beispielsweise nicht zulässig.  Das ist auf den ersten Blick ziemlich überraschend und in der Praxis reichlich störend.  Es gibt natürlich gute Gründe, warum diese Einschränkung sinnvoll und notwendig ist.  Insgesamt aber stellt man bei näherem Hinsehen fest, dass  diese und andere Restriktionen wenig intuitiv sind und den Umgang mit Java Generics relativ gewöhnungsbedürftig machen.  Java Generics sind kein triviales Sprachfeature, dass sich dem Programmierer quasi wie von selbst erschließt.  Im Gegenteil, ein gewisser Lernaufwand für einen sicheren Umgang mit Java Generics wird sich nicht vermeiden lassen.
 
 

3 Zusammenfassung

In diesem Artikel haben wir die wesentlichen Sprachmittel für die Definition und Verwendung von parametrisierten Typen und Methoden in Java betrachtet. Mit Hilfe von parametrisierten Typen und Methoden können zahlreiche Laufzeit-Typprüfungen durch Compilezeit-Typprüfungen ersetzt werden.  Der Compiler übersetzt Generics per Type Erasure in herkömmlichen Bytecode.  Die Übersetzungstechnik per Type Erasure stellt sicher, dass generisches Java zu herkömmlichem Java kompatibel ist.  Der Nachteil dieser Technik ist das Fehlen jeglicher Information über die Typparameter  zur Laufzeit.  Für weitere Informationen sei an dieser Stelle auf die nachfolgenden Links verwiesen.
 
 

4 Weitere Informationen

 
/JDK15/  Java TM 2 SDK, Standard Edition 1.5.0
Update 1
http://java.sun.com/developer/earlyAccess/j2sdk150_alpha/
/TUT/ Java Generics Tutorial
Gilad Bracha
http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf
/FAQ/ Java Generics FAQ
Angelika Langer
http://www.AngelikaLanger.com/GenericsFAQ/JavaGenericsFAQ.html
/LAN/  Links related to Java Generics
Further references to articles, tutorials, conversations and other information related to Java Generics can be found on this website at http://www.AngelikaLanger.com/Resources/Links/JavaGenerics.htm .
/MAG1/ Java Generics - Parametrisierte Typen und Methoden
Klaus Kreft & Angelika Langer
JavaMagazin, April 2004
http://www.AngelikaLanger.com/Articles/JavaMagazin/Generics/GenericsPart1.html
/MAG2/ Wildcard Instantiations of Parameterized Types
Klaus Kreft & Angelika Langer
JavaMagazin, Oktober 2004
http://www.AngelikaLanger.com/Articles/JavaMagazin/Generics/GenericsPart2.html

 
 

If you are interested to hear more about this and related topics you might want to check out the following seminar:
Seminar
 
Java 5.0 - New Features in J2SE 5.0
1 day seminar (open enrollment and on-site)
Effective Java - Advanced Java Programming Idioms 
5 day seminar (open enrollment and on-site)
 
 
  © Copyright 1995-2007 by Angelika Langer.  All Rights Reserved.    URL: < http://www.AngelikaLanger.com/Articles/JavaMagazin/Generics/GenericsPart1.html  last update: 10 Aug 2007