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

 << zurück
Java ist auch eine Insel von Christian Ullenboom
Programmieren für die Java 2-Plattform in der Version 5
Java ist auch eine Insel

Java ist auch eine Insel
5., akt. und erw. Auflage
1454 S., mit CD, 49,90 Euro
Galileo Computing
ISBN 3-89842-747-1
gp Kapitel 11 Datenstrukturen und Algorithmen
  gp 11.1 Datenstrukturen und die Collection-API
    gp 11.1.1 Die Schnittstelle Collection
    gp 11.1.2 Das erste Programm mit Container-Klassen
    gp 11.1.3 Die Schnittstelle Iterable und das erweiterte for
    gp 11.1.4 Generische Datentypen in der Collection-API
    gp 11.1.5 Generischer Typ bei Iterable und konkreter Typ beim erweiterten for
    gp 11.1.6 Schnittstellen, die Collection erweitern, und Map
    gp 11.1.7 Konkrete Container-Klassen
  gp 11.2 Mit einem Iterator durch die Daten wandern
    gp 11.2.1 Die Schnittstellen Enumeration und Iterator
    gp 11.2.2 Der typisierte Iterator
  gp 11.3 Listen
    gp 11.3.1 Die Schnittstelle List
    gp 11.3.2 Beispiel mit List-Methoden
    gp 11.3.3 ArrayList
    gp 11.3.4 Arrays.asList() und die »echten« Listen
    gp 11.3.5 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
    gp 11.3.6 Die interne Arbeitsweise von ArrayList und Vector
    gp 11.3.7 LinkedList
  gp 11.4 Stack (Kellerspeicher, Stapel)
    gp 11.4.1 Die Methoden von Stack
    gp 11.4.2 Ein Stack ist ein Vector – aha!
  gp 11.5 Queues (Schlangen)
    gp 11.5.1 Blockierende Queues und Prioritätswarteschlangen
  gp 11.6 Assoziative Speicher HashMap und TreeMap
    gp 11.6.1 Ein Objekt der Klasse HashMap erzeugen
    gp 11.6.2 Einfügen und Abfragen der Datenstruktur
    gp 11.6.3 Wichtige Eigenschaften von Assoziativspeichern
    gp 11.6.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
    gp 11.6.5 Aufzählen der Elemente
    gp 11.6.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
    gp 11.6.7 Die Arbeitsweise einer Hash-Tabelle
  gp 11.7 Die Properties-Klasse
    gp 11.7.1 Properties setzen und lesen
    gp 11.7.2 Properties verketten
    gp 11.7.3 Eigenschaften ausgeben
    gp 11.7.4 Hierarchische Eigenschaften
    gp 11.7.5 Properties speichern
    gp 11.7.6 Über die Beziehung Properties und Hashtable
  gp 11.8 Mengen (Sets)
    gp 11.8.1 HashSet
    gp 11.8.2 TreeSet – die Menge durch Bäume
    gp 11.8.3 LinkedHashSet
  gp 11.9 Algorithmen in Collections
    gp 11.9.1 Datenmanipulation: Umdrehen, Füllen, Kopieren
    gp 11.9.2 Vergleichen von Objekten mit Comparator und Comparable
    gp 11.9.3 Größten und kleinsten Wert einer Collection finden
    gp 11.9.4 Sortieren
    gp 11.9.5 Elemente in der Collection suchen
    gp 11.9.6 Nicht-änderbare Datenstrukturen
    gp 11.9.7 nCopies()
    gp 11.9.8 Singletons
  gp 11.10 Synchronisation der Datenstrukturen
    gp 11.10.1 Lock-Free-Algorithmen aus java.util.concurrent
    gp 11.10.2 Wrapper zur Synchronisation
    gp 11.10.3 CopyOnWriteArrayList und CopyOnWriteArraySet
  gp 11.11 Die abstrakten Basisklassen für Container
    gp 11.11.1 Optionale Methoden
  gp 11.12 Die Klasse BitSet für Bitmengen
    gp 11.12.1 Ein BitSet anlegen und füllen
    gp 11.12.2 Mengenorientierte Operationen
    gp 11.12.3 Funktionsübersicht
    gp 11.12.4 Primzahlen in einem BitSet verwalten
  gp 11.13 Ein Design-Pattern durch Beobachten von Änderungen
    gp 11.13.1 Design-Pattern
    gp 11.13.2 Das Beobachter-Pattern (Observer/Observable)


Galileo Computing

11.12 Die Klasse BitSet für Bitmengedowntop

Die Klasse BitSet bietet komfortable Möglichkeiten zur bitweisen Manipulation von Daten. Das Datum kann beliebig groß sein, und über Methoden von BitSet lassen sich die einzelnen Bit leicht ändern. Zudem lassen sich Bit wie in einem Vektor hinzufügen und das Objekt verwaltet selbstständig die Größe. Ein leeres BitSet wird mit dem Standard-Konstruktor angelegt. Ein weiterer Konstruktor erlaubt eine Startgröße, die ein Vergrößern aufschiebt.


Galileo Computing

11.12.1 Ein BitSet anlegen und füllen  downtop

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 Bit 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 Bit das Bit 300 zu setzen. Das Objekt wird automatisch mit 200 Null-Bit aufgefüllt, bevor das Bit 300 gesetzt wird.

Über die Methode size() erfahren wir, wie viele Bit das Objekt umfasst. Spannender ist die Methode length(). Sie liefert die Position des höchsten gesetzten Bit. In size() werden überzählige führende Null-Bit mitgezählt, ähnlich wie ungenutzte Array-Elemente im capacity()-Wert eines Vektors. 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.


Beispiel   Setze in einem BitSet das erste und das dritte Bit.
BitSet bs = new BitSet();
bs.  set  ( 0 );
bs.  set  ( 2 );

Abbildung
Hier klicken, um das Bild zu Vergrößern


Galileo Computing

11.12.2 Mengenorientierte Operationen  downtop

Das BitSet erlaubt mengenorientierte Operationen mit einem weiteren BitSet, etwa in der Funktion and(BitSet). Jedes Bit des übergebenen BitSets wird mit dem aktuellen Objekt in einer bestimmten Weise verknüpft. Das Ergebnis der Operation wird dem aktuellen Objekt zugewiesen. Wichtige Operationen sind:

gp  Die Oder-Operation setzt das Bit, falls es im eigenen BitSet oder im zweiten BitSet gesetzt ist.
gp  Die Und-Operation setzt das Bit, falls es im eigenen Objekt und im zweiten BitSet gesetzt ist.
gp  Die Xor-Operation setzt das Bit, falls es nur in einem der beiden BitSet-Objekte gesetzt ist.

Damit werden die Operationen Mengenvereinigung, Durchschnitt und symmetrischer Durchschnitt implementiert.


Galileo Computing

11.12.3 Funktionsübersicht  downtop

Die Funktionen von BitSet sind überschaubar. Leider existieren keine Methoden, die Bit aus anderen Quellen, etwa einem Bitfeld aus byte[], übernehmen und einfügen.


class java.util.  BitSet
  implements Cloneable, Serializable

gp  BitSet() Erzeugt ein neues BitSet-Objekt.
gp  BitSet( int nbits ) Erzeugt ein BitSet mit der vorgegebenen Größe von nbits. Alle Bit sind am Anfang auf false gesetzt. Ist die Größe kleiner null, so wird eine NegativeArraySizeException ausgelöst.
gp  void andNot( BitSet set ) Löscht alle Bit im Bitset, die dort set gesetzt sind.
gp  boolean clear() Löscht den Container.
gp  void set( int bitIndex ), clear( int bitIndex ) Setzt oder löscht ein Bit. Ist der Index negativ, wird eine IndexOutOfBoundsException ausgelöst.
gp  void set( int bitIndex, boolen value ) Setzt den Wahrheitswert value an die Stelle bitIndex.
gp  void set( int fromIndex, int toIndex ), clear( int fromIndex, int toIndex ) Setzt oder löscht Bit im ausgewiesenen Bereich.
gp  void set( int fromIndex, int toIndex, boolen value ) Setzt den Wahrheitswert value im ausgewählten Bereich.
gp  boolen equals( Object o ) Vergleicht sich mit einem anderen BitSet-Objekt o.
gp  boolean get( int bitIndex ) Liefert den Wert des Bit am übergebenen Index. Kann bei negativem Index wieder eine IndexOutOfBoundsException auslösen.
gp  BitSet get( int fromIndex, int toIndex ) Liefert ein neues BitSet-Objekt mit den ausgewählten Bit.
gp  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.
gp  boolen isEmpty() Liefert true, wenn keine Bit gesetzt sind.

Implementierungsdetails

Um die Geschwindigkeit zu optimieren, wurden 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. Intern werden die Bit-Sammlungen in einem long-Array abgelegt.


Galileo Computing

11.12.4 Primzahlen in einem BitSet verwaltetoptop

Das folgende Programm zeigt die Anwendung der Klasse BitSet am Beispiel der Konstruktion der Menge von Primzahlen. Jedes 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 11.14   Primtest.java

import java.util.*;
public class Primtest
{
  final static int MAXPRIM = 30;
  public static void main( String[] args )
  {
    final BitSet b = new BitSet();
    for ( int i = 2; i <= MAXPRIM; ++i )
    {
      boolean ok = true;
      for ( int j = 2end = (int) Math.sqrt(MAXPRIM); j < end; ++j )
        if ( b.get(j) && (i % j) == 0 ) {
          ok = false;
          break;
        }
      if ( ok )
       b.set( i );
    }
    for ( int i = 1; i <= MAXPRIM; ++i )
      if ( b.get(i) )
        System.out.printf( "%d "i );
  }
}
 << zurück




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