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 Die Funktionsbibliothek
10 Threads und nebenläufige Programmierung
11 Raum und Zeit
12 Datenstrukturen und Algorithmen
13 Dateien und Datenströme
14 Die eXtensible Markup Language (XML)
15 Grafische Oberflächen mit Swing
16 Grafikprogrammierung
17 Netzwerkprogrammierung
18 Verteilte Programmierung mit RMI und Web-Services
19 JavaServer Pages und Servlets
20 Applets
21 Midlets und die Java ME
22 Datenbankmanagement mit JDBC
23 Reflection und Annotationen
24 Logging und Monitoring
25 Sicherheitskonzepte
26 Java Native Interface (JNI)
27 Dienstprogramme für die Java-Umgebung
A Die Begleit-DVD
Stichwort
Download: - ZIP, ca. 12,5 MB
Buch bestellen
Ihre Meinung?
<< zurück | Galileo Computing / <openbook> /Java-Insel | vor >>
Java ist auch eine Insel von Christian Ullenboom Programmieren mit der Java Standard Edition Version 6
Java ist auch eine Insel 7., aktualisierte Auflage geb., mit DVD (November 2007) 1.492 S., 49,90 Euro Galileo Computing ISBN 978-3-8362-1146-8 |
| 12 Datenstrukturen und Algorithmen
|  | 12.1 Datenstrukturen und die Collection-API
|  |  | 12.1.1 Designprinzip mit Schnittstellen, abstrakten Klassen, konkreten Klassen
|  |  | 12.1.2 Die Basis-Schnittstellen Collection und Map
|  |  | 12.1.3 Das erste Programm mit Container-Klassen
|  |  | 12.1.4 Die Schnittstelle Collection
|  |  | 12.1.5 Schnittstellen, die Collection erweitern, und Map
|  |  | 12.1.6 Konkrete Container-Klassen
|  |  | 12.1.7 Welche Klasse nehmen?
|  |  | 12.1.8 Generische Datentypen in der Collection-API
|  |  | 12.1.9 Die Schnittstelle Iterable und das erweiterte for
|  | 12.2 Mit einem Iterator durch die Daten wandern
|  |  | 12.2.1 Die Schnittstellen Enumeration und Iterator
|  |  | 12.2.2 Iteratoren von Sammlungen und das erweiterte for
|  |  | 12.2.3 Fail-Fast Iterator und die ConcurrentModificationException
|  | 12.3 Listen
|  |  | 12.3.1 ArrayList oder LinkedList? Speicherung im Feld oder in einer verketteten Liste
|  |  | 12.3.2 Die Schnittstelle List
|  |  | 12.3.3 ArrayList
|  |  | 12.3.4 LinkedList
|  |  | 12.3.5 Der Feld-Adapter Arrays.asList()
|  |  | 12.3.6 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
|  |  | 12.3.7 Primitive Elemente in den Collection-Datenstrukturen
|  | 12.4 Vergleichen von Objekten
|  |  | 12.4.1 Die Schnittstellen Comparator und Comparable
|  |  | 12.4.2 Algorithmen mit Such- und Sortiermöglichkeiten
|  |  | 12.4.3 Den größten und kleinsten Wert einer Collection finden
|  |  | 12.4.4 Sortieren
|  | 12.5 Mengen (Sets)
|  |  | 12.5.1 HashSet
|  |  | 12.5.2 TreeSet – die Menge durch Bäume
|  |  | 12.5.3 LinkedHashSet
|  | 12.6 Stack (Kellerspeicher, Stapel)
|  |  | 12.6.1 Die Methoden von Stack
|  |  | 12.6.2 Ein Stack ist ein Vector – aha!
|  | 12.7 Queues (Schlangen) und Deques
|  |  | 12.7.1 Die Schnittstelle Queue
|  |  | 12.7.2 Blockierende Queues und Prioritätswarteschlangen
|  |  | 12.7.3 Deque-Klassen
|  | 12.8 Assoziative Speicher
|  |  | 12.8.1 Die Klassen HashMap und TreeMap
|  |  | 12.8.2 Einfügen und Abfragen der Datenstruktur
|  |  | 12.8.3 Die Bedeutung von equals(), hashCode() und IdentityHashMap
|  |  | 12.8.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
|  |  | 12.8.5 Aufzählungen und Sichten auf den Assoziativspeicher
|  |  | 12.8.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
|  |  | 12.8.7 Die Arbeitsweise einer Hash-Tabelle
|  |  | 12.8.8 Multi-Maps
|  | 12.9 Die Properties-Klasse
|  |  | 12.9.1 Properties setzen und lesen
|  |  | 12.9.2 Properties verketten
|  |  | 12.9.3 Eigenschaften ausgeben
|  |  | 12.9.4 Hierarchische Eigenschaften
|  |  | 12.9.5 Properties speichern
|  |  | 12.9.6 Klassenbeziehungen: Properties und Hashtable
|  | 12.10 Algorithmen in Collections
|  |  | 12.10.1 Listenoperationen: Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren, Durchmischen
|  |  | 12.10.2 Mit der Halbierungssuche nach Elementen fahnden
|  |  | 12.10.3 Nicht-änderbare Datenstrukturen
|  |  | 12.10.4 Häufigkeit eines Elements
|  |  | 12.10.5 nCopies()
|  |  | 12.10.6 Singletons
|  | 12.11 Synchronisation der Datenstrukturen
|  |  | 12.11.1 Lock-Free-Algorithmen aus java.util.concurrent
|  |  | 12.11.2 Wrapper zur Synchronisation
|  |  | 12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet
|  | 12.12 Die Klasse BitSet für Bitmengen
|  |  | 12.12.1 Ein BitSet anlegen, füllen und erfragen
|  |  | 12.12.2 Mengenorientierte Operationen
|  |  | 12.12.3 Funktionsübersicht
|  |  | 12.12.4 Primzahlen in einem BitSet verwalten
## 12.11 Synchronisation der Datenstrukturen 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. ### 12.11.1 Lock-Free-Algorithmen aus java.util.concurrent 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. 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. ### 12.11.2 Wrapper zur Synchronisation 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 Funktionen 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«. ### 12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet 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. ### Ihr Kommentar Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.
Name |
E-Mail |
Ihr Kommentar |
<< zurück | <top> | vor >>

Copyright © Galileo Press 2008
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