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

Jetzt Buch bestellen
Ihre Meinung?

Spacer
<< zurück
Java SE 8 Standard-Bibliothek von Christian Ullenboom
Das Handbuch für Java-Entwickler
Buch: Java SE 8 Standard-Bibliothek

Java SE 8 Standard-Bibliothek
Pfeil 4 Datenstrukturen und Algorithmen
Pfeil 4.1 Datenstrukturen und die Collection-API
Pfeil 4.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 4.1.2 Die Basisschnittstellen Collection und Map
Pfeil 4.1.3 Die Utility-Klassen Collections und Arrays
Pfeil 4.1.4 Das erste Programm mit Container-Klassen
Pfeil 4.1.5 Die Schnittstelle Collection und Kernkonzepte
Pfeil 4.1.6 Schnittstellen, die Collection erweitern, und Map
Pfeil 4.1.7 Konkrete Container-Klassen
Pfeil 4.1.8 Generische Datentypen in der Collection-API
Pfeil 4.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 4.2 Listen
Pfeil 4.2.1 Erstes Listen-Beispiel
Pfeil 4.2.2 Auswahlkriterium ArrayList oder LinkedList
Pfeil 4.2.3 Die Schnittstelle List
Pfeil 4.2.4 ArrayList
Pfeil 4.2.5 LinkedList
Pfeil 4.2.6 Der Feld-Adapter Arrays.asList(…)
Pfeil 4.2.7 ListIterator *
Pfeil 4.2.8 toArray(…) von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 4.2.9 Primitive Elemente in Datenstrukturen verwalten
Pfeil 4.3 Mengen (Sets)
Pfeil 4.3.1 Ein erstes Mengen-Beispiel
Pfeil 4.3.2 Methoden der Schnittstelle Set
Pfeil 4.3.3 HashSet
Pfeil 4.3.4 TreeSet – die sortierte Menge
Pfeil 4.3.5 Die Schnittstellen NavigableSet und SortedSet
Pfeil 4.3.6 LinkedHashSet
Pfeil 4.4 Queues (Schlangen) und Deques
Pfeil 4.4.1 Queue-Klassen
Pfeil 4.4.2 Deque-Klassen
Pfeil 4.4.3 Blockierende Queues und Prioritätswarteschlangen
Pfeil 4.4.4 PriorityQueue
Pfeil 4.5 Stack (Kellerspeicher, Stapel)
Pfeil 4.5.1 Die Methoden von java.util.Stack
Pfeil 4.6 Assoziative Speicher
Pfeil 4.6.1 Die Klassen HashMap und TreeMap
Pfeil 4.6.2 Einfügen und Abfragen des Assoziativspeichers
Pfeil 4.6.3 Über die Bedeutung von equals(…) und hashCode() bei Elementen
Pfeil 4.6.4 Eigene Objekte hashen
Pfeil 4.6.5 LinkedHashMap und LRU-Implementierungen
Pfeil 4.6.6 IdentityHashMap
Pfeil 4.6.7 Das Problem veränderter Elemente
Pfeil 4.6.8 Aufzählungen und Ansichten des Assoziativspeichers
Pfeil 4.6.9 Die Arbeitsweise einer Hash-Tabelle *
Pfeil 4.6.10 Die Properties-Klasse
Pfeil 4.7 Mit einem Iterator durch die Daten wandern
Pfeil 4.8 Iterator-Schnittstelle
Pfeil 4.8.1 Der Iterator kann (eventuell auch) löschen
Pfeil 4.8.2 Operationen auf allen Elementen durchführen
Pfeil 4.8.3 Einen Zufallszahlen-Iterator schreiben
Pfeil 4.8.4 Iteratoren von Sammlungen, das erweiterte for und Iterable
Pfeil 4.8.5 Fail-Fast-Iterator und die ConcurrentModificationException
Pfeil 4.8.6 Die Schnittstelle Enumerator *
Pfeil 4.9 Algorithmen in Collections
Pfeil 4.9.1 Die Bedeutung von Ordnung mit Comparator und Comparable
Pfeil 4.9.2 Sortieren
Pfeil 4.9.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 4.9.4 Nichtänderbare Datenstrukturen, immutable oder nur lesen?
Pfeil 4.9.5 Null Object Pattern und leere Sammlungen/Iteratoren zurückgeben
Pfeil 4.9.6 Echte typsichere Container
Pfeil 4.9.7 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 4.9.8 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren *
Pfeil 4.9.9 Listen durchwürfeln *
Pfeil 4.9.10 Häufigkeit eines Elements *
Pfeil 4.9.11 Singletons *
Pfeil 4.9.12 nCopies(…) *
Pfeil 4.10 Datenstrukturen mit Änderungsmeldungen
Pfeil 4.10.1 Das Paket javafx.collections
Pfeil 4.10.2 Fabrikmethoden in FXCollections
Pfeil 4.10.3 Änderungen melden über InvalidationListener
Pfeil 4.10.4 Änderungen melden über XXXChangeListener
Pfeil 4.10.5 Change-Klassen
Pfeil 4.10.6 Weitere Hilfsmethoden einer ObservableList
Pfeil 4.10.7 Melden von Änderungen an Arrays
Pfeil 4.10.8 Transformierte FXCollections
Pfeil 4.10.9 Weitere statische Methoden in FXCollections
Pfeil 4.11 Stream-API
Pfeil 4.11.1 Stream erzeugen
Pfeil 4.11.2 Terminale Operationen
Pfeil 4.11.3 Intermediäre Operationen
Pfeil 4.11.4 Streams mit primitiven Werten
Pfeil 4.11.5 Stream-Beziehungen, AutoCloseable
Pfeil 4.11.6 Stream-Builder
Pfeil 4.11.7 Spliterator
Pfeil 4.11.8 Klasse StreamSupport
Pfeil 4.12 Spezielle threadsichere Datenstrukturen
Pfeil 4.12.1 Zu Beginn nur synchronisierte Datenstrukturen in Java 1.0
Pfeil 4.12.2 Nicht synchronisierte Datenstrukturen in der Standard-Collection-API
Pfeil 4.12.3 Nebenläufiger Assoziativspeicher und die Schnittstelle ConcurrentMap
Pfeil 4.12.4 ConcurrentLinkedQueue
Pfeil 4.12.5 CopyOnWriteArrayList und CopyOnWriteArraySet
Pfeil 4.12.6 Wrapper zur Synchronisation
Pfeil 4.12.7 Blockierende Warteschlangen
Pfeil 4.12.8 ArrayBlockingQueue und LinkedBlockingQueue
Pfeil 4.12.9 PriorityBlockingQueue
Pfeil 4.12.10 Transfer-Warteschlangen – TransferQueue und LinkedTransferQueue
Pfeil 4.13 Google Guava (Google Collections Library)
Pfeil 4.13.1 Beispiel Multi-Set und Multi-Map
Pfeil 4.13.2 Datenstrukturen aus Guava
Pfeil 4.13.3 Utility-Klassen von Guava
Pfeil 4.13.4 Prädikate
Pfeil 4.13.5 Transformationen
Pfeil 4.14 Die Klasse BitSet für Bitmengen *
Pfeil 4.14.1 Ein BitSet anlegen
Pfeil 4.14.2 BitSet füllen und Zustände erfragen
Pfeil 4.14.3 Mengenorientierte Operationen
Pfeil 4.14.4 Weitere Methoden von BitSet
Pfeil 4.14.5 Primzahlen in einem BitSet verwalten
Pfeil 4.15 Zum Weiterlesen
 
Zum Seitenanfang

4.14Die Klasse BitSet für Bitmengen * Zur vorigen ÜberschriftZur nächsten Überschrift

Die Klasse BitSet ist eine platzsparende und performante Alternative zu boolean-Arrays und bietet komfortable Möglichkeiten zur bitweisen Manipulation von Daten. Beliebig viele Bits lassen sich wie in anderen dynamischen Datenstrukturen hinzufügen und verwalten. Die Methoden von BitSet lesen und modifizieren die einzelnen Bits leicht und führen Mengenoperationen durch. Auch wenn der Klassenname auf »Set« endet, ist BitSet keine Implementierung der Set-Schnittstelle und sogar ein bisschen irreführend, da ein Set Elemente nur einmal enthalten kann, in BitSet aber natürlich beliebig viele Nullen und Einsen vorkommen können, indem die Reihenfolge auch eine elementare Rolle spielt.

Klassendiagramm von BitSet

Abbildung 4.7Klassendiagramm von BitSet

 
Zum Seitenanfang

4.14.1Ein BitSet anlegen Zur vorigen ÜberschriftZur nächsten Überschrift

Ein leeres BitSet wird mit dem Standard-Konstruktor angelegt. Ein weiterer Konstruktor erlaubt eine Startgröße, die ein Vergrößern der internen Datenstruktur aufschiebt.

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.

Weiterhin gibt es die statischen Methoden BitSet valueOf(long[])/valueOf(byte[])/valueOf(ByteBuffer)/valueOf(LongBuffer), um Bitmengen aus anderen Quellen zu importieren. Es exportieren dann das BitSet mit toByteArray() in ein byte[] und toLongArray() in ein long[].

 
Zum Seitenanfang

4.14.2BitSet füllen und Zustände erfragen Zur vorigen ÜberschriftZur nächsten Ü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 Bit 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.

[zB]Beispiel

Setze in einem BitSet das erste und das dritte Bit:

Listing 4.43com/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
class java.util.BitSet
implements Cloneable, Serializable
  • 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 aus false wird true.

  • void flip(int fromIndex, int toIndex)
    Setzt alle Bits im gegebenen Bereich auf das Komplement.

  • int nextSetBit(int fromIndex)/previousSetBit(int fromIndex)

  • int nextClearBit(int fromIndex)/previousClearBit(int fromIndex)
    Liefert den Index des nächsten/vorangehenden als true bzw. false gesetzten Bits ab fromIndex. Gibt es keine Position, ist die Rückgabe –1. Der Index ist inklusiv.

 
Zum Seitenanfang

4.14.3Mengenorientierte Operationen Zur vorigen ÜberschriftZur nächsten Ü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, den Durchschnitt und den symmetrischen Durchschnitt.

class java.util.BitSet
implements Cloneable, Serializable
  • 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.

 
Zum Seitenanfang

4.14.4Weitere Methoden von BitSet Zur vorigen ÜberschriftZur nächsten Überschrift

Über die Methode size() erfahren wir, wie viele Bits das BitSet zur internen Speicherung der Werte nutzt.[ 57 ](Es ist vergleichbar mit dem capacity()-Wert eines Vektors.) Die Methode length() liefert die Position des höchsten gesetzten Bits. Die Anzahl aller gesetzten Bits liefert cardinality().

[zB]Beispiel

Die Methoden size(), length() und cardinality() im Vergleich:

BitSet bs = BitSet.valueOf( new byte[]{ 0b011001 } );
System.out.println( bs.size() ); // 64
System.out.println( bs.length() ); // 5
System.out.println( bs.cardinality() ); // 3

Die sonstigen Methoden von BitSet sind überschaubar:

class java.util.BitSet
implements Cloneable, Serializable
  • int size()
    Liefert den Platzbedarf in Bits für dieses BitSet.

  • int cardinality()
    Liefert die Anzahl der Bits, die true sind.

  • int length()
    Liefert die »Größe« des BitSet, also den Index des höchsten gesetzten Bits.

  • boolean clear()
    Leert den Container, indem alle Bits auf false gesetzt werden.

  • boolean isEmpty()
    Liefert true, wenn keine Bits gesetzt sind.

  • boolean equals(Object o)
    Vergleicht sich mit einem anderen BitSet-Objekt o.

  • IntStream stream()
    Liefert einen Stream der Indexe mit gesetztem Bit, vom niedrigsten zum höchsten.

[zB]Beispiel

Gib alle Postionen gesetzter Bytes aus, und prüfe, ob auf allen geraden Indexen das Bit gesetzt ist:

boolean b = BitSet.valueOf( new byte[]{ 0b1010 } ).stream()
.peek( System.out::println )
.allMatch( i -> (i & 1) == 1 );

Die Ausgabe wird hier sein: 1, 3.

Implementierungsdetails

Intern legt die Implementierung von BitSet die Bit-Sammlungen in einem 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.

 
Zum Seitenanfang

4.14.5Primzahlen in einem BitSet verwalten Zur vorigen ÜberschriftZur nächsten Ü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 4.44com/tutego/insel/util/Primtest.java, main()

final int MAXPRIM = 1000;
final int ROOT = (int) Math.sqrt( MAXPRIM );
final BitSet nonPimes = new BitSet(); // Nicht-Primzahlen

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

for ( int i = 2; i <= MAXPRIM; i = nonPimes.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.

 


Ihre Meinung

Wie hat Ihnen das Openbook gefallen? Wir freuen uns immer über Ihre Rückmeldung. Schreiben Sie uns gerne Ihr Feedback als E-Mail an kommunikation@rheinwerk-verlag.de.

<< zurück
 Zum Rheinwerk-Shop
Zum Rheinwerk-Shop: Java SE 8 Standard-Bibliothek Java SE 8 Standard-Bibliothek
Jetzt Buch bestellen

 Buchempfehlungen
Zum Rheinwerk-Shop: Java ist auch eine Insel
Java ist auch eine Insel


Zum Rheinwerk-Shop: Professionell entwickeln mit Java EE 8
Professionell entwickeln mit Java EE 8


Zum Rheinwerk-Shop: Besser coden
Besser coden


Zum Rheinwerk-Shop: Entwurfsmuster
Entwurfsmuster


Zum Rheinwerk-Shop: IT-Projektmanagement
IT-Projektmanagement


 Lieferung
Versandkostenfrei bestellen in Deutschland, Österreich und der Schweiz
InfoInfo

 
 


Copyright © Rheinwerk Verlag GmbH 2018
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.

 
Nutzungsbestimmungen | Datenschutz | Impressum

Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de

Cookie-Einstellungen ändern