Java Collections

 + andere TechDocs
+




Inhalt

  1. 'Traditionelle' und 'neue' Collections
  2. Vereinfachte Vererbungsbäume zu einigen Collection-Klassen
  3. Klassen-Hierarchie einiger Collection-Klassen
  4. Collection- und Map-Interface-Hierarchie
  5. 'Traditionelle' Collections Vector, Stack, Hashtable, Properties und BitSet
  6. 'Neue' Collections LinkedList, ArrayList, HashSet, TreeSet, HashMap und TreeMap
  7. Sortierung
  8. Programmierbeispiel für TreeMap-Sortierung


'Traditionelle' und 'neue' Collections

Seit JDK 1.0 gibt es die 'traditionellen' Collections
Seit Java 2 JDK 1.2 wurde ein neues Collection-API eingeführt. Einige bisherige Klassen (Vector und Stack) wurden neu implementiert, viele neue Interfaces und Klassen eingeführt und insgesamt die Struktur verbessert.
Es gibt seitdem die Interfaces
sowie die
und noch einige weitere Interfaces und Klassen (z.B. Collections).
Bitte nicht das Interface Collection (ohne s) und die Klasse Collections (mit s) verwechseln oder HashSet, HashMap und Hashtable verwechseln.

Die im folgenden erläuterten Strukturen und Eigenschaften beziehen sich auf Java 2 JDK 1.3.



Vereinfachte Vererbungsbäume zu einigen Collection-Klassen

  Collection  
        |  
  AbstractCollection    
        |____________
        |		   AbstractList      
        |
        |		         |____________
        |		   AbstractSequentialList    
        |
        |		         |
        |		         |________________

   LinkedList  
        |
        |		         |____________
        |		 ArrayList  
        |
        |		         |____________

 Vector  
        |
        |		           |________________

 Stack
        |____________

   AbstractSet      
          |____________
        |		 HashSet  
          |____________

 TreeSet  
 
  Map  
        |  
  AbstractMap    
        |____________
        |		   HashMap      
        |____________

   TreeMap      
 
  Dictionary    
        |____________

   Hashtable      
          |____________

   Properties    



Klassen-Hierarchie einiger Collection-Klassen



Collection- und Map-Interface-Hierarchie




'Traditionelle' Collections (existieren seit JDK 1.0, aber hier beschrieben wie in JDK 1.3 implementiert)

Klasse Beschreibung Einige wichtige Methoden   

Vector

 public class Vector
extends AbstractList
implements List, Cloneable, Serializable

 Vector repräsentiert eine lineare Liste von Elementen beliebiger Typen, auch unterschiedlicher Typen.
 size()
addElement()
insertElement()
elementAt()
Enumeration elements()

Stack

 public class Stack
extends Vector

 Ein Stack arbeitet nach dem LIFO-Prinzip (last-in-first-out). Die zuletzt eingefügten Elemente werden zuerst entnommen. 		push()
pop()
peek()

Hashtable

 public class Hashtable
extends Dictionary
implements Map, Cloneable, Serializable

 Hashtable konkretisiert die abstrakte Klasse Dictionary.
Hashtable bietet einen assoziativen Speicher, der Paare von Schlüsseln und dazugehörigen Werten verwaltet.
Über den Schlüssel ist ein Zugriff auf den Wert möglich. Der Schlüssel kann als Name des Wertes interpretiert werden.
Intern benutzt Hashtable eine Hash-Funktion zur Transformierung (Abbildung) des Schlüssels auf Indexpositionen eines Arrays. 		put()
get()
contains()
containsKey()
Enumeration elements()
Enumeration keys()

Properties

 public class Properties
extends Hashtable

 Properties ist eine auf String-Paare spezialisierte Hashtable, deren Inhalt leicht auf Festplatte gespeicht oder von dort geladen werden kann. 		getProperty()
Enumeration propertyNames()
load()
store()

BitSet

 public class BitSet
extends Object
implements Cloneable, Serializable

 BitSet repräsentiert Mengen ganzer Zahlen. Zahlen können eingefügt, gelöscht und auf Existenz geprüft werden. Es können Teil- und Vereinigungsmengen gebildet werden.
BitSet kann auch als eine Menge von gesetzten oder nicht gesetzten Bits interpretiert werden und die Vereinigungs- und Schnittmengenoperation als ODER- bzw. UND-Operation. 		set()
clear()
get()
or()
and()
xor()
andNot()



'Neue' Collections (seit Java 2 JDK 1.2)

Alle folgenden Collections implementieren eines der Interfaces List, Set oder Map.
Während die 'traditionellen' Collection-Klassen alle Thread-sicher synchronisiert sind, sind die 'neuen' Collection-Klassen alle unsynchronisiert (aus Performance-Gründen). Wird von mehreren Threads aus auf eine dieser Collection-Klassen zugegriffen, müssen die Zugriffe synchronisiert werden (z.B. mit Collections.synchronizedCollection()).

Klasse Beschreibung Einige wichtige Methoden   

LinkedList

 public class LinkedList
extends AbstractSequentialList
implements List, Cloneable, Serializable

 LinkedList realisiert eine doppelt verkettete lineare Liste.
Einfüge- und Löschoperationen sind performanter als bei ArrayList. Der wahlfreie Zugriff ist langsamer.
LinkedList ist besonders für große Listen oder bei häufigen Änderungen vorzuziehen. 		size()
add()
remove()
contains()
Iterator iterator()
get()
set()

ArrayList

 public class ArrayList
extends AbstractList
implements List, Cloneable, Serializable

 ArrayList realisiert eine lineare Liste als dynamisches Array.
Wahlfreier Zugriff ist schneller als bei LinkedList, Einfügen und Löschen dagegen langsamer.
ArrayList ist besonders bei überwiegend lesendem Zugriff oder bei kleinen Listen vorzuziehen. 		size()
add()
remove()
contains()
Iterator iterator()
get()
set()

Vector

 public class Vector
extends AbstractList
implements List, Cloneable, Serializable

 Vector ist zu bevorzugen, wenn Java 2 nicht eingesetzt werden kann (z.B. für Applets für ältere oder Microsoft-Web-Browser ohne Sun-Plug-in) sowie wenn gleichzeitige Zugriffe von mehreren Threads möglich sind (Vector ist bereits synchronisiert). Ansonsten sind LinkedList oder ArrayList vorzuziehen. 		size()
add()
remove()
contains()
Iterator iterator()
get()
set()

HashSet

 public class HashSet
extends AbstractSet
implements Set, Cloneable, Serializable

 HashSet realisiert eine doublettenlose ungeordnete Menge von Elementen, auf die mit Mengenoperationen zugegriffen werden kann.
Die Iterationsreihenfolge ist ungeordnet und muss nicht reproduzierbar sein. 		size()
add()
remove()
contains()
Iterator iterator()

TreeSet

 public class TreeSet
extends AbstractSet
implements SortedSet, Cloneable, Serializable

 TreeSet ist ähnlich wie HashSet, aber geordnet.
Die Sortierreihenfolge ist entweder die natürliche der Elemente oder wird durch ein Comparator-Objekt vorgegeben. 		size()
add()
remove()
contains()
Iterator iterator()

HashMap

 public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable

 Wie Hashtable bietet HashMap einen assoziativen Speicher, der Paare von Schlüsseln und dazugehörigen Werten verwaltet. Über den Schlüssel ist ein Zugriff auf den Wert möglich. Der Schlüssel kann als Name des Wertes interpretiert werden.
Anders als Hashtable erlaubt HashMap das Einfügen von null-Werten und ist nicht synchronisiert.
HashMap bietet nicht direkt einen Iterator. Dieser kann jedoch leicht über keySet(), values() oder entrySet() gebildet werden (z.B. Iterator = HashMap.entrySet().iterator()). 		size()
get()
put()
containsKey()
containsValue()
Set keySet()
Collection values()
Set entrySet()

TreeMap

 public class TreeMap
extends AbstractMap
implements SortedMap, Cloneable, Serializable

 TreeMap ist ähnlich wie HashMap, aber die Reihenfolge der Elemente ist sortiert. 		size()
get()
put()
containsKey()
containsValue()
Set keySet()
Collection values()
Set entrySet()



Sortierung

Eine Sortierung erfolgt entweder auf Grund der sogenannten 'natürlichen' Ordnung oder mit Hilfe eines explizit angegebenen Objekts, welches eine Vergleichsfunktion implementiert hat.
Eine Sortierung nach 'natürlicher' Ordnung ist nur möglich, wenn alle Elemente das
Interface Comparable mit der Funktion 'int compareTo(Object o)' implementiert haben.
Eine Sortierung mit Hilfe eines explizit angegebenen Objekts ist möglich, wenn dieses Objekt das
Interface Comparator mit der Funktion 'int compare(Object o1, Object o2)' implementiert hat.

TreeSet und TreeMap sind immer sortiert, entweder nach 'natürlicher' Ordnung oder an Hand eines dem Konstruktor übergebenen Comparator-Objekts.

LinkedList, ArrayList und Vector sowie alle weiteren das Interface List implementierende Klassen können mit der Klasse Collections sortiert werden (nicht Collections mit s und Collection ohne s verwechseln):
Collections.sort( List lst ) sortiert nach 'natürlicher' Ordnung,
Collections.sort( List lst, Comparator cmp ) sortiert an Hand des Comparator-Objekts.

Muss in einer großen Liste häufig gesucht werden, empfiehlt sich, diese Liste zuerst zu sortieren und anschließend
Collections.binarySearch() zu verwenden.

Ausser in der Klasse Collections gibt es auch in der Klasse Arrays viele sort()-Funktionen, z.B.
Arrays.sort( Object[] arr ) und
Arrays.sort( Object[] arr, Comparator cmp ).



Programmierbeispiel für TreeMap-Sortierung

TreeMapTest demonstriert drei Varianten zur Sortierung:
- tm1 mit 'natürlicher' Ordnung der Schlüssel (ohne Comparator),
- tm2 mit externer Comparator-Klasse für die Schlüssel und
- tm3 mit internem this-Comparator und diesmal für die Werte.

Die 'natürliche' Ordnung ist bei Text-Strings selten sinnvoll, da deutsche Umlaute und Sonderzeichen nicht korrekt eingeordnet werden (wie die Ausgabe von tm1 zeigt).
Der Comparator MyStringComparator (für tm2) implementiert eine einfache Berücksichtigung und zusätzlich eine Ignorierung der Groß-/Kleinschreibung.
tm3 zeigt, wie ohne externe Comparator-Klasse das Comparator-Interface implementiert werden kann, nämlich mit einer compare()-Funktion in der eigenen Klasse.
Ausserdem zeigt tm3, wie nach beliebigen anderen Kriterien sortiert werden kann (hier im Beispiel nach dem zweiten double-Wert).

Der interne this-Comparator hat den Vorteil, dass seine compare()-Funktion Zugriff auf die privaten Variablen der Klasse hat (hier tm1).
Die externe Comparator-Klasse hat den Vorteil, dass sie in vielen verschiedenen Klassen verwendet werden kann.

Die beiden compare()-Funktionen zeigen eine Besonderheit:
Wird als Rückgabewert 0 ermittelt, muss erst geprüft werden, ob die Elemente wirklich gleich sind (hier mit '((String)o2).compareTo((String)o1)').
Dies ist wichtig, da die compare()-Funktion nicht nur für die Sortierreihenfolge benutzt wird, sondern auch um festzustellen, ob ein neu einzufügendes Element noch nicht vorhanden ist. Eine Map erlaubt nämlich keine Doubletten. Andernfalls würden bei tm2 'uvw' und 'UVW' und bei tm3 Elemente mit gleichem zweiten double-Wert als gleiche Elemente angesehen und das zuletzt mit put() eingefügte Element würde nicht als weiteres Element hinzugefügt, sondern würde das vorherige als gleich angesehene Element überschreiben (wie es übrigens an dieser Stelle gewollt das zweite 'abc'-Element mit dem vorherigen macht).

Der Zugriff auf die Elemente ist etwas umständlich. Da TreeMap keinen eigenen Enumerator oder Iterator anbietet, muss er mit entrySet().iterator() beschafft werden. Die von Iterator.next() gelieferten Objekte sind vom Typ Map.Entry. Diese liefern mit getKey() den Schlüssel und mit getValue() den Wert (hier das double-Array).

import java.util.*;
import java.awt.*;
import java.awt.event.*;

public class TreeMapTest extends Frame implements Comparator
{
  private TreeMap tm1 = new TreeMap();                      // tm1: natürliche Sortierung ohne Comparator

  public static void main( String[] args )
  {
    TreeMapTest tmt = new TreeMapTest();
    tmt.setSize( 460, 540 );
    tmt.setVisible( true );
  }

  public TreeMapTest()
  {
    tm1.put( "abc", new double[] { 2.00,   0 } );
    tm1.put( "abc", new double[] { 2.01, 100 } );
    tm1.put( "äx ", new double[] { 2.02, 500 } );
    tm1.put( "öx ", new double[] { 2.03, 300 } );
    tm1.put( "üx ", new double[] { 2.07, 800 } );
    tm1.put( "ßx ", new double[] { 2.04, 700 } );
    tm1.put( "xyz", new double[] { 2.08, 600 } );
    tm1.put( "uvw", new double[] { 2.05, 900 } );
    tm1.put( "UVW", new double[] { 2.06, 900 } );

    String s1 = "Sortiere TreeMap auf verschiedene Arten.\n";
    s1 += printTreeMap( "'Natural Order' der Schlüssel:", tm1 );

    TreeMap tm2 = new TreeMap( new MyStringComparator() );  // tm2: externer Comparator
    tm2.putAll( tm1 );
    s1 += printTreeMap( "Berücksichtigung deutscher Umlaute und Ignorierung der Großschreibung:", tm2 );

    TreeMap tm3 = new TreeMap( this );                      // tm3: interner Comparator
    tm3.putAll( tm1 );
    s1 += printTreeMap( "Sortierung nach zweitem double-Wert:", tm3 );

    TextArea txt = new TextArea( s1 );
    add( txt );

    addWindowListener(
      new WindowAdapter() {
        public void windowClosing( WindowEvent ev ) {
          dispose();
          System.exit( 0 ); } } );
  }

  public static String printTreeMap( String sTitle, TreeMap trmp )
  {
    String s1 = "\n" + sTitle + "\n";
    Iterator it = trmp.entrySet().iterator();
    while( it.hasNext() )
    {
      Map.Entry me = (Map.Entry)it.next();
      double[]  da = (double[])me.getValue();
      s1 += me.getKey() + "  " + da[0] + "  " + da[1] + "\n";
    }
    return s1;
  }

  public int compare( Object o1, Object o2 )
  {
    double[] dd1 = (double[])(tm1.get( o1 ));
    double[] dd2 = (double[])(tm1.get( o2 ));
    return ( dd1[1] > dd2[1] ) ?  1 :
           ( dd1[1] < dd2[1] ) ? -1 :
           ((String)o2).compareTo( (String)o1 );
  }
}

class MyStringComparator implements Comparator
{
  public int compare( Object o1, Object o2 )
  {
    int i = prepareForCompare( o1 ).compareTo( prepareForCompare( o2 ) );
    return ( 0 != i ) ? i : ((String)o1).compareTo( (String)o2 );
  }

  private String prepareForCompare( Object o )
  {
    return ((String)o).toLowerCase().replace( 'ä', 'a' )
                                    .replace( 'ö', 'o' )
                                    .replace( 'ü', 'u' )
                                    .replace( 'ß', 's' );
  }
}

'Natural Order' der Schlüssel Berücksichtigung deutscher Umlaute
und Ignorierung der Großschreibung		 Sortierung nach zweitem double-Wert 
UVW  2.06  900.0
abc  2.01  100.0
uvw  2.05  900.0
xyz  2.08  600.0
ßx   2.04  700.0
äx   2.02  500.0
öx   2.03  300.0
üx   2.07  800.0
 
abc  2.01  100.0
äx   2.02  500.0
öx   2.03  300.0
ßx   2.04  700.0
uvw  2.05  900.0
UVW  2.06  900.0
üx   2.07  800.0
xyz  2.08  600.0
 
abc  2.01  100.0
öx   2.03  300.0
äx   2.02  500.0
xyz  2.08  600.0
ßx   2.04  700.0
üx   2.07  800.0
uvw  2.05  900.0
UVW  2.06  900.0



Weitere Themen: andere TechDocs
© 1998-2007 Torsten Horn, Aachen