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.12 Die Klasse BitSet für Bitmengen Die Klasse BitSet bietet komfortable Möglichkeiten zur bitweisen Manipulation von Daten. Das Datum kann beliebig groß sein, und Methoden von BitSet lesen und modifizieren die einzelnen Bits leicht. Zudem lassen sich beliebig viele Bits wie in anderen dynamischen Datenstrukturen hinzufügen. Ein leeres BitSet wird mit dem Standard-Konstruktor angelegt. Ein weiterer Konstruktor erlaubt eine Startgröße, die ein Vergrößern der internen Datenstruktur aufschiebt. ### 12.12.1 Ein BitSet anlegen, füllen und erfragen Jedes Bit an einer Position besitzt zwei Zustände: gesetzt oder nicht gesetzt. Dies bringt es in die Nähe der Booleschen Werte, die ebenso zwei Zustände besitzen. Mit zwei Methoden lassen sich die Bits des BitSet leicht ändern: set(bitNummer) und clear(bitNummer). Da der Bit-Container automatisch wächst, ist es problemlos möglich, in einem BitSet-Exemplar mit 100 Bits das Bit 300 zu setzen. Das Objekt wird automatisch mit 200 false-Bits aufgefüllt, bevor das Bit 300 gesetzt wird. Die Abfrage, ob ein Bit gesetzt ist, erfolgt mit der Methode get(bitNummer). Sie gibt true zurück, falls das Bit gesetzt ist, andernfalls false. Nützliche Funktionen sind ebenso nextSetBit(int) und nextClearBit(int), die für einen Startindex die Position des nächsten gesetzten oder gelöschten Bits geben.
Beispiel Setze in einem BitSet das erste und das dritte Bit: Listing 12.30 com/tutego/insel/util/BitSetDemo.java. main()
    BitSet bs = new BitSet();
    bs.set( 0 );
    bs.set( 2 );
    System.out.println( bs.get(0) );        // true
    System.out.println( bs.get(1) );        // false
    System.out.println( bs.nextSetBit(1) ); // 2
Über die Methode size() erfahren wir, wie viele Bits das Objekt umfasst. size() zählt überzählige führende Null-Bits mit, ähnlich wie ungenutzte Array-Elemente im capacity()-Wert eines Vektors. Die Methode length() liefert die Position des höchsten gesetzten Bits. Die Anzahl gesetzter Bits liefert cardinality(). Hier klicken, um das Bild zu vergrößern ### 12.12.2 Mengenorientierte Operationen Das BitSet erlaubt mengenorientierte Operationen wie Und, Oder, Xor mit einem weiteren BitSet, etwa in der Funktion and(BitSet). Jedes Bit des übergebenen BitSet wird mit dem aktuellen Objekt in einer bestimmten Weise verknüpft. Das Ergebnis der Operation wird dem aktuellen Objekt zugewiesen. Wichtige Operationen sind: Die Oder-Operation setzt das Bit, falls es im eigenen BitSet oder im zweiten BitSet gesetzt ist. Die Und-Operation setzt das Bit, falls es im eigenen Objekt und im zweiten BitSet gesetzt ist. Die Xor-Operation setzt das Bit, falls es nur in einem der beiden BitSet-Objekte gesetzt ist. Die Operationen bilden die Basis für die Mengenvereinigung, Durchschnitt und symmetrischer Durchschnitt. ### 12.12.3 Funktionsübersicht Die Funktionen von BitSet sind überschaubar. Leider existieren keine Methoden, die Bit-Mengen aus anderen Quellen, etwa einem byte-Feld, übernehmen und einfügen.
    class java.util.BitSet
    implements Cloneable, Serializable
BitSet() Erzeugt ein neues BitSet-Objekt. BitSet( int nbits ) Erzeugt ein BitSet mit der vorgegebenen Größe von nbits. Alle Bits sind am Anfang auf false gesetzt. Ist die Größe kleiner null, so wird eine NegativeArraySizeException ausgelöst. boolean get( int bitIndex ) Liefert den Wert des Bits am übergebenen Index. Kann bei negativem Index wieder eine IndexOutOfBoundsException auslösen. BitSet get( int fromIndex, int toIndex ) Liefert ein neues BitSet-Objekt mit den ausgewählten Bits. void set( int bitIndex ), clear( int bitIndex ) Setzt oder löscht ein Bit. Ist der Index negativ, wird eine IndexOutOfBoundsException ausgelöst. void set( int bitIndex, boolean value ) Setzt den Wahrheitswert value an die Stelle bitIndex. void set( int fromIndex, int toIndex ), clear( int fromIndex, int toIndex ) Setzt oder löscht Bits im ausgewiesenen Bereich. void set( int fromIndex, int toIndex, boolean value ) Setzt den Wahrheitswert value im ausgewählten Bereich. void flip( int bitIndex ) Setzt das Bit an der Stelle bitIndex auf das Komplement. Aus true wird false und false wird true. void flip( int fromIndex, int toIndex ) Setzt alle Bits im gegebenen Bereich auf das Komplement. void and( BitSet set ), void or( BitSet set ), void xor( BitSet set ) Verknüpft dieses BitSet-Exemplar per Und-, Oder-, Xor-Operation mit dem angegebenen BitSet-Objekt. void andNot( BitSet set ) Löscht alle Bits im aktuellen BitSet, deren korrespondierendes Bit in set gesetzt ist. boolean intersects( BitSet set ) Liefert true, wenn das eigene BitSet die gleichen gesetzten Bits wie set hat. int cardinality() Liefert die Anzahl der Bits, die true sind. boolean clear() Leert den Container, in dem alle Bits auf false gesetzt werden. boolean isEmpty() Liefert true, wenn keine Bits gesetzt sind. int nextSetBit( int fromIndex ), int nextClearBit( int fromIndex ) Liefert den Index des ersten als true bzw. false gesetzten Bits ab fromIndex. Gibt es keine Position, ist die Rückgabe –1. boolean equals( Object o ) Vergleicht sich mit einem anderen BitSet-Objekt o. #### Implementierungsdetails Intern legt die Implementierung von BitSet die Bit-Sammlungen in ein long-Array ab. Um die Geschwindigkeit zu optimieren, sind die Methoden der Klasse BitSet nicht synchronisiert. Greift also ein Thread auf die Daten zu, während ein anderer modifiziert, kann es zu möglichen Inkonsistenzen kommen. ### 12.12.4 Primzahlen in einem BitSet verwalten Das folgende Programm zeigt die Anwendung der Klasse BitSet am Beispiel der Konstruktion der Menge von Primzahlen. Jedes nicht gesetzte Bit entspricht einer Primzahl. In diesem Fall ist der Einsatz der Klasse BitSet angebracht, da eine Zahl in einem Wertebereich nur eine Primzahl oder keine sein kann. Listing 12.31 com/tutego/insel/util/Primtest.java, main()
    final int    MAXPRIM = 30;
    final int    ROOT    = (int) Math.sqrt( MAXPRIM );
    final BitSet bs      = new BitSet();               // Stores non prim

    for ( int i = 2; i <= ROOT; ++i )
      if ( ! bs.get( i ) )
        for ( int j = 2 * i; j <= MAXPRIM; j += i )
          bs.set( j );

    for ( int i = 2; i <= MAXPRIM; i = bs.nextClearBit( i + 1 ) )
      System.out.printf( "%d ", i );
Zwar ist die Performance etwas schlechter als beim Einsatz eines boolean-Feldes, doch der Speicherverbrauch ist um etwa 1/8 geringer. ### 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