Galileo Computing :: Java 7 - Mehr als eine Insel - 3 Datenstrukturen und Algorithmen
Galileo Computing < openbook > Galileo Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger.

Inhaltsverzeichnis
Vorwort
1 Neues in Java 7
2 Threads und nebenläufige Programmierung
3 Datenstrukturen und Algorithmen
4 Raum und Zeit
5 Dateien, Verzeichnisse und Dateizugriffe
6 Datenströme
7 Die eXtensible Markup Language (XML)
8 Dateiformate
9 Grafische Oberflächen mit Swing
10 Grafikprogrammierung
11 Netzwerkprogrammierung
12 Verteilte Programmierung mit RMI
13 RESTful und SOAP Web-Services
14 JavaServer Pages und Servlets
15 Applets
16 Datenbankmanagement mit JDBC
17 Technologien für die Infrastruktur
18 Reflection und Annotationen
19 Dynamische Übersetzung und Skriptsprachen
20 Logging und Monitoring
21 Java Native Interface (JNI)
22 Sicherheitskonzepte
23 Dienstprogramme für die Java-Umgebung
Stichwort

Download:
- openbook, ca. 21,3 MB
Buch bestellen
Ihre Meinung?

Spacer
Java 7 - Mehr als eine Insel von Christian Ullenboom
Das Handbuch zu den Java SE-Bibliotheken
Buch: Java 7 - Mehr als eine Insel

Java 7 - Mehr als eine Insel
Galileo Computing
1433 S., 2012, geb.
49,90 Euro, ISBN 978-3-8362-1507-7
Pfeil 3 Datenstrukturen und Algorithmen
Pfeil 3.1 Datenstrukturen und die Collection-API
Pfeil 3.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 3.1.2 Die Basis-Schnittstellen Collection und Map
Pfeil 3.1.3 Die Utility-Klassen Collections und Arrays
Pfeil 3.1.4 Das erste Programm mit Container-Klassen
Pfeil 3.1.5 Die Schnittstelle Collection und Kernkonzepte
Pfeil 3.1.6 Schnittstellen, die Collection erweitern, und Map
Pfeil 3.1.7 Konkrete Container-Klassen
Pfeil 3.1.8 Generische Datentypen in der Collection-API
Pfeil 3.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 3.2 Listen
Pfeil 3.2.1 Erstes Listen-Beispiel
Pfeil 3.2.2 Auswahlkriterium ArrayList oder LinkedList
Pfeil 3.2.3 Die Schnittstelle List
Pfeil 3.2.4 ArrayList
Pfeil 3.2.5 LinkedList
Pfeil 3.2.6 Der Feld-Adapter Arrays.asList()
Pfeil 3.2.7 ListIterator *
Pfeil 3.2.8 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 3.2.9 Primitive Elemente in Datenstrukturen verwalten
Pfeil 3.3 Mengen (Sets)
Pfeil 3.3.1 Ein erstes Mengen-Beispiel
Pfeil 3.3.2 Methoden der Schnittstelle Set
Pfeil 3.3.3 HashSet
Pfeil 3.3.4 TreeSet – die sortierte Menge
Pfeil 3.3.5 Die Schnittstellen NavigableSet und SortedSet
Pfeil 3.3.6 LinkedHashSet
Pfeil 3.4 Stack (Kellerspeicher, Stapel)
Pfeil 3.4.1 Die Methoden von Stack
Pfeil 3.5 Queues (Schlangen) und Deques
Pfeil 3.5.1 Queue-Klassen
Pfeil 3.5.2 Deque-Klassen
Pfeil 3.5.3 Blockierende Queues und Prioritätswarteschlangen
Pfeil 3.5.4 PriorityQueue
Pfeil 3.6 Assoziative Speicher
Pfeil 3.6.1 Die Klassen HashMap und TreeMap
Pfeil 3.6.2 Einfügen und Abfragen der Datenstruktur
Pfeil 3.6.3 Über die Bedeutung von equals() und hashCode()
Pfeil 3.6.4 Eigene Objekte hashen
Pfeil 3.6.5 IdentityHashMap
Pfeil 3.6.6 Das Problem von veränderten Elementen
Pfeil 3.6.7 Aufzählungen und Ansichten des Assoziativspeichers
Pfeil 3.6.8 Die Arbeitsweise einer Hash-Tabelle *
Pfeil 3.7 Die Properties-Klasse
Pfeil 3.7.1 Properties setzen und lesen
Pfeil 3.7.2 Properties verketten
Pfeil 3.7.3 Hierarchische Eigenschaften
Pfeil 3.7.4 Eigenschaften auf der Konsole ausgeben *
Pfeil 3.7.5 Properties laden und speichern
Pfeil 3.7.6 Klassenbeziehungen: Properties und Hashtable *
Pfeil 3.8 Mit einem Iterator durch die Daten wandern
Pfeil 3.8.1 Die Schnittstelle Iterator
Pfeil 3.8.2 Der Iterator kann (eventuell auch) löschen
Pfeil 3.8.3 Einen Zufallszahleniterator schreiben
Pfeil 3.8.4 Iteratoren von Sammlungen, das erweiterte for und Iterable
Pfeil 3.8.5 Fail-Fast-Iterator und die ConcurrentModificationException
Pfeil 3.8.6 Die Schnittstelle Enumerator *
Pfeil 3.9 Algorithmen in Collections
Pfeil 3.9.1 Die Bedeutung von Ordnung mit Comparator und Comparable
Pfeil 3.9.2 Sortieren
Pfeil 3.9.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 3.9.4 Nicht-änderbare Datenstrukturen, immutable oder nur-lesen?
Pfeil 3.9.5 Null Object Pattern und leere Sammlungen/Iteratoren zurückgeben
Pfeil 3.9.6 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 3.9.7 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren *
Pfeil 3.9.8 Listen durchwürfeln *
Pfeil 3.9.9 Häufigkeit eines Elements *
Pfeil 3.9.10 Singletons *
Pfeil 3.9.11 nCopies() *
Pfeil 3.10 Spezielle thread-sichere Datenstrukturen
Pfeil 3.10.1 Wait-free-Algorithmen
Pfeil 3.10.2 Nebenläufiger Assoziativspeicher und die Schnittstelle ConcurrentMap
Pfeil 3.10.3 ConcurrentLinkedQueue
Pfeil 3.10.4 CopyOnWriteArrayList und CopyOnWriteArraySet
Pfeil 3.10.5 Wrapper zur Synchronisation
Pfeil 3.10.6 Blockierende Warteschlangen
Pfeil 3.10.7 ArrayBlockingQueue und LinkedBlockingQueue
Pfeil 3.10.8 PriorityBlockingQueue
Pfeil 3.11 Google Guava (aka Google Collections Library)
Pfeil 3.11.1 Beispiel Multi-Set und Multi-Map
Pfeil 3.11.2 Datenstrukturen aus Guava
Pfeil 3.11.3 Utility-Klassen von Guava
Pfeil 3.11.4 Prädikate
Pfeil 3.11.5 Transformationen
Pfeil 3.12 Die Klasse BitSet für Bitmengen *
Pfeil 3.12.1 Ein BitSet anlegen, füllen und erfragen
Pfeil 3.12.2 Mengenorientierte Operationen
Pfeil 3.12.3 Methodenübersicht
Pfeil 3.12.4 Primzahlen in einem BitSet verwalten
Pfeil 3.13 Zum Weiterlesen

Galileo Computing - Zum Seitenanfang

3.11 Google Guava (aka Google Collections Library)Zur nächsten Überschrift

Obwohl die Java-Bibliothek mit Listen, Mengen und Assoziativspeichern einen guten Grundstock für die alltäglichen Aufgaben zur Datenverwaltung bietet, gibt es dennoch Bedarf an weiteren Speicherstrukturen. Anstatt sie selbst zu definieren, ist es sinnvoll, in die Open-Source-Welt zu schauen. Besonders hervorzuheben ist Google Guava (http://code.google. com/p/guava-libraries/), das eine Open-Source-Bibliothek unter der Apache-Lizenz mit neuen Datenstrukturen, Utility-Methoden für die existierenden java.util-Datenstrukturen sowie einigen anderen Utility-Klassen, etwa für String-Behandlung oder zum Zerlegen von Zeichenketten, ist. Die Datenstrukturen von Guava stammen aus dem Projekt Google Collections Library, aber die Entwicklung geht bei Guava weiter.

Für die folgenden Beispiele muss von der Webseite die Distribution guava-r09.zip heruntergeladen und das im Zip enthaltende Java-Archiv guava-r09.jar in den Klassenpfad eingebunden werden.


Galileo Computing - Zum Seitenanfang

3.11.1 Beispiel Multi-Set und Multi-MapZur nächsten ÜberschriftZur vorigen Überschrift

Da Java schon alles Grundlegende mitbringt, stellt sich die Frage, was denn überhaupt fehlt. Dazu zwei Szenarien:

  • Beispiel 1: Eine Textdatei soll analysiert werden. Am Ende soll feststehen, wie oft jedes Wort (unabhängig von der Groß-/Kleinschreibung) in der Datei steht. Enthält die Datei etwa »In Ulm, um Ulm, um Ulm herum.«, so sollte Folgendes herauskommen: »in«: 1, »ulm«: 3, »um«: 2, »herum«: 1. Im Grunde müsste es eine Menge geben, die Elemente mehrmals enthalten kann, eine sogenannte Multi-Menge (auch Multi-Set genannt). Eine Anfrage an die Multi-Menge gibt dann nicht nur einen Wahrheitswert für »enthält« oder »enthält nicht« zurück, sondern gibt auch an, wie oft ein Element in der Multi-Menge enthalten ist. Die Datenstruktur ist nicht Teil von Java, kann aber mit Standardmitteln für unseren Anwendungsfall mit einer Map<String, Integer> realisiert werden.
  • Beispiel 2: Wieder soll eine Textdatei analysiert werden. Gespeichert werden soll Für jedes Wort soll auch die Position gespeichert werden, sodass sich später feststellen lässt, ob gewisse Wörter nicht vielleicht zu nah beieinander stehen, was schlechter Stil wäre. Bei der Zeichenfolge »In Ulm, um Ulm« wäre das: »in«: 0, »ulm«: 3, 11, »um«: 8. Kämen nicht mehrere Positionen für das gleiche Wort infrage – wie bei »Ulm«, das an Position 3 und 11 beginnt –, wäre eine Map perfekt. Nur gibt es in unserem Anwendungsfall zu einem Schlüssel gleich mehrere Werte. Gesucht ist eine sogenannte Multi-Map. Die Java-Bibliothek enthält bisher keine Multi-Map, da damals die Sun-Entwickler argumentierten, eine solche Datenstruktur werde selten benötigt.[27](http://java.sun.com/docs/books/tutorial/collections/interfaces/map.html) Für unseren Fall kann sie mit Map<String, List<Integer>> aber nachgebildet werden.

Galileo Computing - Zum Seitenanfang

3.11.2 Datenstrukturen aus GuavaZur nächsten ÜberschriftZur vorigen Überschrift

Guava bietet Entwicklern Klassen für Multi-Set, Mutli-Map und mehr. Dabei ist das Design vorbildlich und fügt sich perfekt in die Java-Standarddatenstrukturen ein. Das tut es aus zwei Gründen:

  • Schnittstellen deklarieren Operationen, die konkrete Klassen implementieren. So wie List eine Schnittstelle ist, die ArrayList implementiert, so wird Mulitmap etwa durch ArrayListMultimap implementiert.
  • Die Datenstrukturen nutzen sehr präzise die Möglichkeiten von Java Generics. So wie Map<K,V> aus java.util, ist es die Multimap<K,V> aus Guava.

Schauen wir uns ein paar Schnittstellen und Implementierungen aus dem Paket com.google. common.collect an – die API-Dokumentation gibt es online unter http://guava-libraries.googlecode.com/svn/trunk/javadoc/index.html (die Schnittstellen sind jeweils mit ihren generischen Typvariablen genannt, die Implementierungen zur Abkürzung nicht).

Tabelle 3.6: Schnittstellen und Implementierungen aus com.google.common.collect

Schnittstelle Aufgabe Implementierungen

BiMap<K,V>

Eine Map-Unterschnittstelle für bidirektionale Abbildungen, um nicht nur vom Schlüssel auf den Wert, sondern auch vom Wert auf den Schlüssel zu kommen

HashBiMap, EnumBiMap, EnumHashBiMap, ImmutableBiMap

Multimap<K,V>

Erlaubt für einen Schlüssel eine Sammlung von assoziierten Werten.

ArrayListMultimap, HashMultimap, LinkedHashMultimap, LinkedListMultimap, TreeMultimap, ImmutableListMultimap, ImmutableMultimap, ImmutableSetMultimap, ForwardingListMultimap, ForwardingMultimap, ForwardingSetMultimap, ForwardingSortedSetMultimap

Multiset<E>

Eine besondere Collection, die als Menge auch mehrere gleiche Elemente erlaubt

HashMultiset, LinkedHashMultiset, TreeMultiset, ConcurrentHashMultiset, EnumMultiset, ImmutableMultiset, ForwardingMultiset

SetMultimap<K,V>

Eine besondere Multimap <K,V>, die die zum Schlüssel gehörenden Werte in eine Menge speichert

HashMultimap, LinkedHashMultimap, TreeMultimap, ImmutableSetMultimap, ForwardingSetMultimap, ForwardingSortedSetMultimap

SortedSetMultimap<K,V>

Eine besondere SetMultimap, die die zum Schlüssel gehörende Menge sortiert hält

TreeMultimap, ForwardingSortedSetMultimap

ListMultimap<K,V>

Eine besondere Multimap <K,V>, die die zu einem Schlüssel gehörenden Werte in einer Liste speichert, um die Reihenfolge beim Einfügen festzuhalten

ArrayListMultimap, LinkedListMultimap, ImmutableListMultimap, ForwardingListMultimap,

Bei den Klassen springen zwei Dinge ins Auge: Klassen, die mit Immutable und mit Forwarding beginnen:

  • Immutable-Datenstrukturen kennen wir schon – das sind Datenstrukturen, die nur Lese-Zugriff erlauben, die aber nicht modifiziert werden können. Die Utility-Klasse Collections bietet uns ein Paar unmodifiableXXX()-Methoden, die einen nur Lese-Wrapper um die Basis-Typen Collection, List, Set, Map, SortedSet und SortedMap legen. Die ImmutableXXX-Klassen aus Guava sind die nicht-veränderbaren Google-Datenstrukturen.
  • Die abstrakten ForwardingXXX-Klassen arbeiten nach dem Dekorator-Pattern und leiten alle Operationen an eine andere Datenstruktur weiter. Es sind sehr spezielle Klassen, und Guava nutzt sie intern – für Entwickler sind sie weniger relevant.

Im Grunde bleiben dann nur noch ein paar Datenstrukturen übrig, und das Implementierungsmuster ist wie bei den Java-Standardbibliotheken: Einige Datenstrukturen speichern die tatsächlichen Daten in Array-Listen, andere in Hashing-Datenstrukturen, andere wiederum in Mengen, die über Binärbäume sortiert sind.

Tabelle 3.7: Mengen- und Assoziativspeicherimplementierungen

Realisierung Klassen

Hashing

HashBiMap, HashMultimap, LinkedHashMultimap, HashMultiset, LinkedHashMultiset

Array-List

ArrayListMultimap

Linked-List

LinkedListMultimap

Binärbaum

TreeMultimap, TreeMultimap, TreeMultiset

Die Klassen ConcurrentHashMultiset (eine sichere nebenläufige Muliset-Implementierung) und EnumBiMap, EnumHashBiMap (diese Typen sind auf Enum eingeschränkt) sind Sonderfälle.


Galileo Computing - Zum Seitenanfang

3.11.3 Utility-Klassen von GuavaZur nächsten ÜberschriftZur vorigen Überschrift

Auf der einen Seite bietet Guava neue Datenstrukturen, auf der anderen Seite Utility-Klassen, die eine Ergänzung zu der einen Standardklasse Collections sind.

Tabelle 3.8: Utility-Klassen von Guava

Utility-Klasse Aufgabe Beispielmethoden

Collections2

Filtert und transformiert eine Collection.

filter(), transform()

Lists

Erzeugt List-Exemplare, teilt oder transformiert sie.

asList(), newArrayList(), newLinkedList(), partition(), transform()

Maps

Erzeugt eine neue Map, filtert und transformiert sie.

newHashMap(), fromProperties(), difference(), transformValues()

Sets

Erzeugt neue Mengen und bietet mengenorientierte Funktionen.

newTreeSet(), newHashSet(), cartesianProduct(), complementOf(), difference(), union(), powerSet()

Iterators, Iterables

Operiert auf Iterator/Iterable, fügt etwa einige Iterator/Iterable zusammen oder setzt ihre Elemente in ein Feld.

addAll(), concat(), filter(), get(), limit(), reverse(), toString()

Weiterhin gibt es für die neuen Guava-Klassen die zwei Utility-Klassen Multimaps und Multisets.


Galileo Computing - Zum Seitenanfang

3.11.4 PrädikateZur nächsten ÜberschriftZur vorigen Überschrift

Ein Prädikat ist ein Objekt, das auf einem Argument eine Bedingung prüft und »wahr« oder »falsch« liefert. Guava gibt eine Prädikat-Schnittstelle Predicate<T> mit der Operation boolean apply(T input) vor. Ein Prädikat könnte etwa testen, ob eine Objektreferenz null ist oder ein String eine Mindestlänge besitzt. Prädikate verändern die Argumente nie und dürfen sie nicht »zurechtbiegen«.

Mit eigenen Predicate-Objekten lässt sich auf diverse Methoden zurückgreifen, die Sammlungen filtern. Ein paar Beispielmethoden:

  • static <E> Collection<E> Collections2.filter(Collection<E> unfiltered, Predicate<? super E> predicate)
    Liefert in der Rückgabe eine Collection, die alle Elemente von unfiltered enthält, die das Prädikat erfüllen.
  • static <E> Set<E> Sets.filter(Set<E> unfiltered, Predicate<? super E> predicate)
    Liefert als Rückgabe eine Menge, bei der jedes Element das Prädikat erfüllt.
  • static <T> boolean Iterables.all(Iterable<T> iterable, Predicate<? super T> predicate)
    Prüft, ob alle Elemente vom Iterable (eine List ist zum Beispiel Iterable, aber auch Set) das Prädikat erfüllen.

Zum Verknüpfen von Prädikaten bietet die Predicates-Klasse statische Kombinationsmethoden wie and(), compose() und or().


Galileo Computing - Zum Seitenanfang

3.11.5 TransformationenZur vorigen Überschrift

Oftmals müssen die Elemente in Datenstrukturen von einem Format in ein anderes gebracht werden. Zum Beispiel sollen bei String in einer Liste die Leerzeichen vorne und hinten abgeschnitten werden, oder Farben sollen in Graustufen übersetzt werden.

Für Transformationen deklariert Guava die Schnittstelle Function<F,T> mit einer Operation T apply(F from). In den Guava-Utility-Klassen gibt es jeweils transform()-Methoden, die alle Elemente einer Datenstruktur durch eine Function leiten und auf der anderen Seite das Ergebnis in eine Datenstruktur setzen und diese zurückgeben. Ein paar Beispiele:

  • static <F,T> Collection<T> Collections2.transform(Collection<F> fromCollection, Function<? super F,T> function)
  • static <F,T> Iterable<T> Iterables.transform(Iterable<F> fromIterable, Function<? super F,? extends T> function)
  • static <F,T> Iterator<T> Iterators.transform(Iterator<F> fromIterator, Function<? super F,? extends T> function)
  • static <F,T> List<T> Lists.transform(List<F> fromList, Function<? super F,? extends T> function)
  • static <K,V1,V2> Map<K,V2> Maps.transformValues(Map<K,V1> fromMap, Function<? super V1,V2> function)
  • static <E> Collection<E> Collections2.filter(Collection<E> unfiltered, Predicate<? super E> predicate)


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 7 – Mehr als eine Insel
Java 7 – Mehr als eine Insel
Jetzt bestellen


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

 Buchempfehlungen
Zum Katalog: Java und XML






 Java und XML


Zum Katalog: Einstieg in Eclipse 3.7






 Einstieg in
 Eclipse 3.7


Zum Katalog: Android 3






 Android 3


Zum Katalog: NetBeans Platform 7






 NetBeans Platform 7


Zum Katalog: Java ist auch eine Insel






 Java ist
 auch eine Insel


Zum Katalog: Apps entwickeln für Android 4






 Apps entwickeln
 für Android 4


Zum Katalog: Java 7






 Java 7


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Galileo Press 2012
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das 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