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

Inhaltsverzeichnis
Vorwort
1 Java ist auch eine Sprache
2 Sprachbeschreibung
3 Klassen und Objekte
4 Der Umgang mit Zeichenketten
5 Mathematisches
6 Eigene Klassen schreiben
7 Angewandte Objektorientierung
8 Exceptions
9 Generics, innere Klassen
10 Die Klassenbibliothek
11 Threads und nebenläufige Programmierung
12 Datenstrukturen und Algorithmen
13 Raum und Zeit
14 Dateien und Datenströme
15 Die eXtensible Markup Language (XML)
16 Grafische Oberflächen mit Swing
17 Grafikprogrammierung
18 Netzwerkprogrammierung
19 Verteilte Programmierung mit RMI und Web–Services
20 JavaServer Pages und Servlets
21 Applets
22 Midlets und die Java ME
23 Datenbankmanagement mit JDBC
24 Reflection und Annotationen
25 Logging und Monitoring
26 Sicherheitskonzepte
27 Java Native Interface (JNI)
28 Dienstprogramme für die Java-Umgebung
Stichwort

Download:
- ZIP, ca. 14,1 MB
Buch bestellen
Ihre Meinung?

Spacer
<< zurück
Java ist auch eine Insel (8. Auflage) von Christian Ullenboom
Programmieren mit der Java Standard Edition Version 6
Buch: Java ist auch eine Insel (8. Auflage)

Java ist auch eine Insel (8. Aufl.)
8., aktual. Auflage, geb., mit DVD
1.475 S., 49,90 Euro
Galileo Computing
ISBN 978-3-8362-1371-4
Pfeil 12 Datenstrukturen und Algorithmen
Pfeil 12.1 Datenstrukturen und die Collection-API
Pfeil 12.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 12.1.2 Die Basis-Schnittstellen Collection und Map
Pfeil 12.1.3 Das erste Programm mit Container-Klassen
Pfeil 12.1.4 Die Schnittstelle Collection
Pfeil 12.1.5 Schnittstellen, die Collection erweitern, und Map
Pfeil 12.1.6 Konkrete Container-Klassen
Pfeil 12.1.7 Welche Klasse nehmen?
Pfeil 12.1.8 Generische Datentypen in der Collection-API
Pfeil 12.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 12.2 Mit einem Iterator durch die Daten wandern
Pfeil 12.2.1 Die Schnittstellen Enumeration und Iterator
Pfeil 12.2.2 Iteratoren von Sammlungen und das erweiterte for
Pfeil 12.2.3 Fail-Fast Iterator und die ConcurrentModificationException
Pfeil 12.3 Listen
Pfeil 12.3.1 Auswahlkriterium ArrayList oder LinkedList
Pfeil 12.3.2 Die Schnittstelle List
Pfeil 12.3.3 ArrayList
Pfeil 12.3.4 LinkedList
Pfeil 12.3.5 Der Feld-Adapter Arrays.asList()
Pfeil 12.3.6 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 12.3.7 Primitive Elemente in den Collection-Datenstrukturen
Pfeil 12.4 Vergleichen von Objekten
Pfeil 12.4.1 Die Schnittstellen Comparator und Comparable
Pfeil 12.4.2 Algorithmen mit Such- und Sortiermöglichkeiten
Pfeil 12.4.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 12.4.4 Sortieren
Pfeil 12.5 Mengen (Sets)
Pfeil 12.5.1 HashSet
Pfeil 12.5.2 TreeSet – die Menge durch Bäume
Pfeil 12.5.3 LinkedHashSet
Pfeil 12.6 Stack (Kellerspeicher, Stapel)
Pfeil 12.6.1 Die Methoden von Stack
Pfeil 12.6.2 Ein Stack ist ein Vector – aha!
Pfeil 12.7 Queues (Schlangen) und Deques
Pfeil 12.7.1 Die Schnittstelle Queue
Pfeil 12.7.2 Blockierende Queues und Prioritätswarteschlangen
Pfeil 12.7.3 Deque-Klassen
Pfeil 12.8 Assoziative Speicher
Pfeil 12.8.1 Die Klassen HashMap und TreeMap
Pfeil 12.8.2 Einfügen und Abfragen der Datenstruktur
Pfeil 12.8.3 equals(), hashCode() und IdentityHashMap
Pfeil 12.8.4 Das Problem von veränderbaren Elementen
Pfeil 12.8.5 Aufzählungen und Sichten auf den Assoziativspeicher
Pfeil 12.8.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
Pfeil 12.8.7 Die Arbeitsweise einer Hash-Tabelle
Pfeil 12.8.8 Multi-Maps
Pfeil 12.9 Die Properties-Klasse
Pfeil 12.9.1 Properties setzen und lesen
Pfeil 12.9.2 Properties verketten
Pfeil 12.9.3 Eigenschaften ausgeben
Pfeil 12.9.4 Hierarchische Eigenschaften
Pfeil 12.9.5 Properties speichern
Pfeil 12.9.6 Klassenbeziehungen: Properties und Hashtable
Pfeil 12.10 Algorithmen in Collections
Pfeil 12.10.1 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren, Durchmischen
Pfeil 12.10.2 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 12.10.3 Nicht-änderbare Datenstrukturen
Pfeil 12.10.4 Häufigkeit eines Elements
Pfeil 12.10.5 nCopies()
Pfeil 12.10.6 Singletons
Pfeil 12.11 Synchronisation der Datenstrukturen
Pfeil 12.11.1 Lock-free-Algorithmen aus java.util.concurrent
Pfeil 12.11.2 Wrapper zur Synchronisation
Pfeil 12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet
Pfeil 12.12 Die Klasse BitSet für Bitmengen
Pfeil 12.12.1 Ein BitSet anlegen, füllen und erfragen
Pfeil 12.12.2 Mengenorientierte Operationen
Pfeil 12.12.3 Methodenübersicht
Pfeil 12.12.4 Primzahlen in einem BitSet verwalten


Galileo Computing - Zum Seitenanfang

12.11 Synchronisation der Datenstrukturen Zur nächsten ÜberschriftZur vorigen Überschrift

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 vor nebenläufigen Ä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 über synchronisierende Wrapper.


Galileo Computing - Zum Seitenanfang

12.11.1 Lock-free-Algorithmen aus java.util.concurrent Zur nächsten ÜberschriftZur vorigen Überschrift

Wenn zum Beispiel bei einer verketteten Liste ein Thread vorn 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. Die Schnittstelle ConcurrentMap deklariert vier Operationen für Implementierungen, die atomar ausgeführt werden müssen:

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

Die Implementierungen der Schnittstelle sind ConcurrentHashMap, eine sehr schnelle Datenstruktur für gleichzeitig operierende Threads, und ConcurrentSkipListMap seit Java 6. Bei beiden lösen Veränderungen durch den Iterator keine ConcurrentModificationException aus.

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 verketteten Listen und nicht auf Arrays. Ein eigenes ConcurrentSet könnte auf der Basis von ConcurrentHashMap implementiert werden, so wie auch HashSet intern mit einer HashMap realisiert ist. In Java 6 ist die Klasse ConcurrentSkipListSet hinzugekommen.


Galileo Computing - Zum Seitenanfang

12.11.2 Wrapper zur Synchronisation Zur nächsten ÜberschriftZur vorigen Überschrift

Können zur Absicherung nebenläufiger Operationen die oben aufgeführten Datenstrukturen aus java.util.concurrent nicht verwendet werden, etwa bei Java 1.4 oder bei eigenen nicht-nebenläufig implementierten Versionen von Set, Map, List, Queue, lassen sich Zugriffe auf die Datenstrukturen extern synchronisieren. Dazu fordern statische Methoden wie synchronizedXXX() einen Wrapper an, der sich um die existierende Datenstruktur legt. Die Wrapper arbeiten nicht lock-free, und Parallelität in den Datenstrukturen ist nicht gegeben.


Beispiel Eine synchronisierte Liste:

List<Byte> syncList = Collections.synchronizedList( new LinkedList<Byte>() );

Der generische Typ der Datenstruktur geht auch weiter an den Wrapper.


Die synchronizedXXX()-Funktionen liefern eine neue Sammlung, die sich wie eine Hülle um die existierende Datenstruktur legt und alle Funktionsaufrufe synchronisiert. Paralleler Zugriff darf natürlich dann nur noch über den Wrapper laufen, wobei nicht-paralleler Zugriff weiterhin über die Original-Datenstruktur möglich ist.


class java.util.Collections


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

Iteratoren von synchronisierten Wrappern

Mit dem Wrapper ist der nebenläufige Zugriff über die Funktionen gesichert, aber nicht der Zugriff über den Iterator. Ist syncList eine synchronisierte Datenstruktur, die ein Iterator ablaufen möchte, und während des Ablaufens soll jeder andere Zugriff gesperrt sein, ist zu schreiben:

List<Byte> syncList = Collections.synchronizedList( new LinkedList<Byte>() ); 
synchronized ( syncList ) 
{ 
  Iterator iter = syncList.iterator(); 
}

Die Synchronisation ist immer auf dem Wrapper und nicht auf dem »Gewrappten«.


Galileo Computing - Zum Seitenanfang

12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet topZur vorigen Überschrift

Ist die Anzahl der Leseoperationen 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.



Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.






<< zurück
  Zum Katalog
Zum Katalog: Java ist auch eine Insel





Java ist auch eine Insel
Jetzt bestellen


 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Tipp
Zum Katalog: Coding for Fun





 Coding for Fun


 Buchempfehlungen
Zum Katalog: Objektorientierte Programmierung





 Objektorientierte
 Programmierung


Zum Katalog: Einstieg in Eclipse 3.4






 Einstieg in
 Eclipse 3.4


Zum Katalog: Java 6 lernen mit Eclipse






 Java 6 lernen
 mit Eclipse


Zum Katalog: NetBeans Platform 6






 NetBeans
 Platform 6


Zum Katalog: Java und XML






 Java und XML


Zum Katalog: Visual C# 2008






 Visual C# 2008


Zum Katalog: IT-Handbuch für Fachinformatiker






 IT-Handbuch für
 Fachinformatiker


Zum Katalog: C++ von A bis Z






 C++ von A bis Z


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Galileo Press 2009
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, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de