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.12 Die Klasse BitSet für Bitmengen Zur nächsten ÜberschriftZur vorigen Überschrift

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.


Galileo Computing - Zum Seitenanfang

12.12.1 Ein BitSet anlegen, füllen und erfragen Zur nächsten ÜberschriftZur vorigen Überschrift

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(bitPosition) und clear(bitPosition). Da der Bit-Container automatisch wachsen kann, 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(bitPosition). Sie gibt true zurück, falls das Bit gesetzt ist, andernfalls false. Nützliche Methoden 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().


Galileo Computing - Zum Seitenanfang

12.12.2 Mengenorientierte Operationen Zur nächsten ÜberschriftZur vorigen Überschrift

Das BitSet erlaubt mengenorientierte Operationen wie Und, Oder, Xor mit einem weiteren BitSet, etwa in der Methode 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 symmetrischen Durchschnitt.


Galileo Computing - Zum Seitenanfang

12.12.3 Methodenübersicht Zur nächsten ÜberschriftZur vorigen Überschrift

Die Methoden von BitSet sind überschaubar.


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.

Unter OpenDK 7 sind unter anderem die statischen Funktionen BitSet valueOf(long[]) und BitSet valueOf(byte[]) beziehungsweise die Objektmethoden byte[] toByteArray() und long[] toLongArray() hinzugekommen, um Bit-Mengen aus anderen Quellen zu importieren und zu exportieren. Auch previousSetBit() und previousClearBit() wurden nachgereicht.

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.


Galileo Computing - Zum Seitenanfang

12.12.4 Primzahlen in einem BitSet verwalten topZur vorigen Überschrift

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.






<< 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