Galileo Computing < openbook > Galileo Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger

 << zurück
Java ist auch eine Insel von Christian Ullenboom
Programmieren für die Java 2-Plattform in der Version 5
Java ist auch eine Insel

Java ist auch eine Insel
5., akt. und erw. Auflage
1454 S., mit CD, 49,90 Euro
Galileo Computing
ISBN 3-89842-747-1
gp Kapitel 11 Datenstrukturen und Algorithmen
  gp 11.1 Datenstrukturen und die Collection-API
    gp 11.1.1 Die Schnittstelle Collection
    gp 11.1.2 Das erste Programm mit Container-Klassen
    gp 11.1.3 Die Schnittstelle Iterable und das erweiterte for
    gp 11.1.4 Generische Datentypen in der Collection-API
    gp 11.1.5 Generischer Typ bei Iterable und konkreter Typ beim erweiterten for
    gp 11.1.6 Schnittstellen, die Collection erweitern, und Map
    gp 11.1.7 Konkrete Container-Klassen
  gp 11.2 Mit einem Iterator durch die Daten wandern
    gp 11.2.1 Die Schnittstellen Enumeration und Iterator
    gp 11.2.2 Der typisierte Iterator
  gp 11.3 Listen
    gp 11.3.1 Die Schnittstelle List
    gp 11.3.2 Beispiel mit List-Methoden
    gp 11.3.3 ArrayList
    gp 11.3.4 Arrays.asList() und die »echten« Listen
    gp 11.3.5 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
    gp 11.3.6 Die interne Arbeitsweise von ArrayList und Vector
    gp 11.3.7 LinkedList
  gp 11.4 Stack (Kellerspeicher, Stapel)
    gp 11.4.1 Die Methoden von Stack
    gp 11.4.2 Ein Stack ist ein Vector – aha!
  gp 11.5 Queues (Schlangen)
    gp 11.5.1 Blockierende Queues und Prioritätswarteschlangen
  gp 11.6 Assoziative Speicher HashMap und TreeMap
    gp 11.6.1 Ein Objekt der Klasse HashMap erzeugen
    gp 11.6.2 Einfügen und Abfragen der Datenstruktur
    gp 11.6.3 Wichtige Eigenschaften von Assoziativspeichern
    gp 11.6.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
    gp 11.6.5 Aufzählen der Elemente
    gp 11.6.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
    gp 11.6.7 Die Arbeitsweise einer Hash-Tabelle
  gp 11.7 Die Properties-Klasse
    gp 11.7.1 Properties setzen und lesen
    gp 11.7.2 Properties verketten
    gp 11.7.3 Eigenschaften ausgeben
    gp 11.7.4 Hierarchische Eigenschaften
    gp 11.7.5 Properties speichern
    gp 11.7.6 Über die Beziehung Properties und Hashtable
  gp 11.8 Mengen (Sets)
    gp 11.8.1 HashSet
    gp 11.8.2 TreeSet – die Menge durch Bäume
    gp 11.8.3 LinkedHashSet
  gp 11.9 Algorithmen in Collections
    gp 11.9.1 Datenmanipulation: Umdrehen, Füllen, Kopieren
    gp 11.9.2 Vergleichen von Objekten mit Comparator und Comparable
    gp 11.9.3 Größten und kleinsten Wert einer Collection finden
    gp 11.9.4 Sortieren
    gp 11.9.5 Elemente in der Collection suchen
    gp 11.9.6 Nicht-änderbare Datenstrukturen
    gp 11.9.7 nCopies()
    gp 11.9.8 Singletons
  gp 11.10 Synchronisation der Datenstrukturen
    gp 11.10.1 Lock-Free-Algorithmen aus java.util.concurrent
    gp 11.10.2 Wrapper zur Synchronisation
    gp 11.10.3 CopyOnWriteArrayList und CopyOnWriteArraySet
  gp 11.11 Die abstrakten Basisklassen für Container
    gp 11.11.1 Optionale Methoden
  gp 11.12 Die Klasse BitSet für Bitmengen
    gp 11.12.1 Ein BitSet anlegen und füllen
    gp 11.12.2 Mengenorientierte Operationen
    gp 11.12.3 Funktionsübersicht
    gp 11.12.4 Primzahlen in einem BitSet verwalten
  gp 11.13 Ein Design-Pattern durch Beobachten von Änderungen
    gp 11.13.1 Design-Pattern
    gp 11.13.2 Das Beobachter-Pattern (Observer/Observable)


Galileo Computing

11.10 Synchronisation der Datenstrukturedowntop

Ein großer Unterschied zwischen den klassischen Datenstrukturen wie Vector oder Hashtable und denen aus der Collection-API besteht darin, dass alle Methoden durch synchronisierte Blöcke vor parallelen Änderungen geschützt waren. Bei den neuen Klassen wie ArrayList und HashMap sind Einfüge- und Löschoperationen nicht mehr automatisch synchronized. Sollen allerdings Listen, Mengen oder Assoziativspeicher gegen nebenläufige Änderungen sicher sein, gibt es zwei Möglichkeiten: Einmal über spezielle so genannte Lock-Free-(bzw. Wait-Free-)Algorithmen, die tatsächlich parallele Zugriffe – wenn möglich – erlauben, und einmal synchronisierende Wrapper.


Galileo Computing

11.10.1 Lock-Free-Algorithmen aus java.util.concurrent  downtop

Wenn zum Beispiel bei einer verketteten Liste ein Thread vorne etwas anhängt und der andere hinten etwas entfernt, ist das tatsächlich nebenläufig möglich, und es muss nicht die ganze Datenstruktur gelockt werden. Java 5 definiert über die Schnittstelle ConcurrentMap vier Operationen für Implementierungen, die atomar ausgeführt werden müssen:

gp  V putIfAbsent( K key, V value )
gp  boolean remove( Object key, Object value )
gp  V replace( K key, V value ) und
gp  boolean replace( K key, V oldValue, V newValue )

Die bisher einzige Implementierung der Schnittstelle ist ConcurrentHashMap, eine sehr schnelle Datenstruktur für gleichzeitig operierende Threads. (Veränderungen durch den Iterator werden keine ConcurrentModificationException auslösen.)

Obwohl es keine Schnittstellen ConcurrentSet und ConcurrentList gibt, existiert zumindest eine Klasse ConcurrentLinkedQueue, die eine Thread-sichere und Lock-freie Liste (genauer: Queue) ist. Wie der Name schon andeutet, beruht die Realisierung auf der Basis von verketteten Listen und nicht von Arrays. Eine eigene ConcurrentSet könnte auf der Basis von ConcurrentHashMap implementiert werden, so wie auch HashSet intern mit einer HashMap realisiert ist.


Galileo Computing

11.10.2 Wrapper zur Synchronisation  downtop

Können die oben aufgeführten Datenstrukturen nicht verwendet werden, oder sind eigene Implementierungen gegeben, um nebenläufige Operationen abzusichern, beziehungsweise ein ganzes Bündel von Operationen mit einem existierenden Lock-Objekt, können Container extern synchronisiert werden. Dazu wird ein Wrapper mit einer statischen Funktion synchronizedXXX() angefordert. Die Wrapper arbeiten nicht Lock-Free, und Parallelität in den Datenstrukturen ist nicht gegeben.


Beispiel   Eine synchronisierte Liste.
List<Byte> list =   Collections.synchronizedList  ( new LinkedList<Byte>() );
Die generischen Typen übernimmt die Funktion!

Diese Funktion liefert eine neue Sammlung, die sich wie eine Hülle um die existierende Datenstruktur legt und alle Funktionsaufrufe synchronisiert.


class java.util.Collections

gp  static <T> Collection<T> synchronizedCollection( Collection<T> c )
gp  static <T> List<T> synchronizedList( List<T> list )
gp  static <K,V> Map<K,V> synchronizedMap( Map<K,V> m )
gp  static <T> Set<T> synchronizedSet( Set<T> s )
gp  static <K,V> SortedMap<K,V> synchronizedSortedMap( SortedMap<K,V> m )
gp  static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s ) Liefert synchronisierte, also Thread-sichere Datenstrukturen.

Galileo Computing

11.10.3 CopyOnWriteArrayList und CopyOnWriteArraySet  toptop

Ist die Anzahl der Lese-Operationen hoch, kann es sich lohnen, bei jedem Schreibzugriff erst die Daten zu kopieren und dann das Element hinzuzufügen, damit im Hintergrund andere Threads ohne einen Lock, der fürs Schreiben nötig ist, lesen können. Zwei dieser Datenstrukturen bietet Java an: CopyOnWriteArrayList für Listen und CopyOnWriteArraySet für Mengen. Die Klassen sind genau dann optimal, wenn wenig verändert – das ist teuer – und fast ausschließlich gelesen wird.

 << zurück




Copyright © Galileo Press GmbH 2005
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Galileo Computing]

Galileo Press GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de