Un guide de BitSet en Java

1. Vue d'ensemble

Dans ce tutoriel, nous allons voir comment nous pouvons utiliser des BitSet pour représenter un vecteur de bits.

Tout d'abord, nous allons commencer par la justification de ne pas utiliser le booléen [] . Ensuite, après nous être familiarisés avec les composants internes de BitSet , nous examinerons de plus près son API.

2. Tableau de bits

Pour stocker et manipuler des tableaux de bits, on pourrait dire que nous devrions utiliser boolean [] comme structure de données. À première vue, cela peut sembler une suggestion raisonnable.

Cependant, chaque membre booléen d'un booléen [] consomme généralement un octet au lieu d'un seul bit . Ainsi, lorsque nous avons des besoins en mémoire serrés, ou que nous visons simplement une empreinte mémoire réduite, les booléens [] sont loin d'être idéaux.

Pour rendre les choses plus concrètes, voyons combien d'espace un booléen [] avec 1024 éléments consomme:

boolean[] bits = new boolean[1024]; System.out.println(ClassLayout.parseInstance(bits).toPrintable());

Idéalement, nous nous attendons à une empreinte mémoire de 1024 bits de ce tableau. Cependant, la mise en page d'objets Java (JOL) révèle une réalité entièrement différente:

[Z object internals: OFFSET SIZE TYPE DESCRIPTION VALUE 0 4 (object header) 01 00 00 00 (00000001 00000000 00000000 00000000) (1) 4 4 (object header) 00 00 00 00 (00000000 00000000 00000000 00000000) (0) 8 4 (object header) 7b 12 07 00 (01111011 00010010 00000111 00000000) (463483) 12 4 (object header) 00 04 00 00 (00000000 00000100 00000000 00000000) (1024) 16 1024 boolean [Z. N/A Instance size: 1040 bytes

Si nous ignorons la surcharge de l'en-tête d'objet, les éléments du tableau consomment 1024 octets, au lieu des 1024 bits attendus. C'est 700% de mémoire en plus que ce à quoi nous nous attendions.

Les problèmes d'adressabilité et le déchirement des mots sont les principales raisons pour lesquelles les booléens sont plus qu'un simple bit.

Pour résoudre ce problème, nous pouvons utiliser une combinaison de types de données numériques (tels que long ) et d'opérations par bit. C'est là que le BitSet entre en jeu.

3. Comment BitSet Works

Comme nous l'avons mentionné précédemment, pour atteindre l'utilisation de la mémoire d'un bit par indicateur, l' API BitSet utilise une combinaison de types de données numériques de base et d'opérations par bit.

Par souci de simplicité, supposons que nous allons représenter huit indicateurs avec un octet . Dans un premier temps, nous initialisons tous les bits de cet octet unique avec zéro:

Maintenant, si nous voulons définir le bit en position trois sur true , nous devons d'abord décaler le nombre 1 à gauche de trois:

Et puis ou son résultat avec la valeur d' octet actuelle :

Le même processus se produira si vous décidez de définir le bit à l'index sept:

Comme indiqué ci-dessus, nous effectuons un décalage vers la gauche de sept bits et combinons le résultat avec la valeur d' octet précédente à l'aide de l' opérateur ou .

3.1. Obtenir un index de bits

Pour vérifier si un index de bit particulier est défini sur true ou non, nous utiliserons l' opérateur and . Par exemple, voici comment nous vérifions si l'index trois est défini:

  1. Effectuer un décalage vers la gauche de trois bits sur la valeur un
  2. Anding le résultat avec la valeur d' octet actuelle
  3. Si le résultat est supérieur à zéro, nous avons trouvé une correspondance et cet index de bits est en fait défini. Sinon, l'index demandé est clair ou est égal à faux

Le diagramme ci-dessus montre les étapes de l'opération d'obtention pour l'index trois. Si nous nous renseignons sur un index clair, cependant, le résultat sera différent:

Puisque le résultat et est égal à zéro, l'index quatre est clair.

3.2. Augmenter le stockage

Actuellement, nous ne pouvons stocker qu'un vecteur de 8 bits. Pour aller au-delà de cette limitation, il suffit d'utiliser un tableau d' octets , au lieu d'un seul octet , c'est tout!

Maintenant, chaque fois que nous devons définir, obtenir ou effacer un index spécifique, nous devons d'abord trouver l'élément de tableau correspondant. Par exemple, supposons que nous allons définir l'index 14:

Comme indiqué dans le diagramme ci-dessus, après avoir trouvé le bon élément de tableau, nous avons défini l'index approprié.

De plus, si nous voulons définir ici un index au-delà de 15, le BitSet étendra d'abord son tableau interne. Ce n'est qu'après avoir développé le tableau et copié les éléments que le bit demandé sera défini. Ceci est quelque peu similaire à la façon dont ArrayList fonctionne en interne.

Jusqu'à présent, nous avons utilisé le type de données byte par souci de simplicité. Le BitSet cependant, API, utilise un tableau de longues valeurs internes .

4. L' API BitSet

Maintenant que nous en savons suffisamment sur la théorie, il est temps de voir à quoi ressemble l'API BitSet .

Pour commencer, comparons l'empreinte mémoire d'une instance de BitSet avec 1024 bits avec le booléen [] que nous avons vu précédemment:

BitSet bitSet = new BitSet(1024); System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());

Cela affichera à la fois la taille superficielle de l' instance BitSet et la taille de son tableau interne:

[email protected] object externals: ADDRESS SIZE TYPE PATH VALUE 70f97d208 24 java.util.BitSet (object) 70f97d220 144 [J .words [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Comme indiqué ci-dessus, il utilise un long [] avec 16 éléments (16 * 64 bits = 1024 bits) en interne. Quoi qu'il en soit, cette instance utilise 168 octets au total, tandis que le booléen [] utilisait 1024 octets .

The more bits we have, the more the footprint difference increases. For example, to store 1024 * 1024 bits, the boolean[] consumes 1 MB, and the BitSet instance consumes around 130 KB.

4.1. Constructing BitSets

The simplest way to create a BitSet instance is to use the no-arg constructor:

BitSet bitSet = new BitSet();

This will create a BitSet instance with a long[] of size one. Of course, it can automatically grow this array if needed.

It's also possible to create a BitSet with an initial number of bits:

BitSet bitSet = new BitSet(100_000);

Here, the internal array will have enough elements to hold 100,000 bits. This constructor comes in handy when we already have a reasonable estimate on the number of bits to store. In such use cases, it can prevent or decrease the unnecessary copying of array elements while growing it.

It's even possible to create a BitSet from an existing long[], byte[], LongBuffer, and ByteBuffer. For instance, here we're creating a BitSet instance from a given long[]:

BitSet bitSet = BitSet.valueOf(new long[] { 42, 12 });

There are three more overloaded versions of the valueOf() static factory method to support the other mentioned types.

4.2. Setting Bits

We can set the value of a particular index to true using the set(index) method:

BitSet bitSet = new BitSet(); bitSet.set(10); assertThat(bitSet.get(10)).isTrue();

As usual, the indices are zero-based. It's even possible to set a range of bits to true using the set(fromInclusive, toExclusive) method:

bitSet.set(20, 30); for (int i = 20; i <= 29; i++) { assertThat(bitSet.get(i)).isTrue(); } assertThat(bitSet.get(30)).isFalse();

As is evident from the method signature, the beginning index is inclusive, and the ending one is exclusive.

When we say setting an index, we usually mean setting it to true. Despite this terminology, we can set a particular bit index to false using the set(index, boolean) method:

bitSet.set(10, false); assertThat(bitSet.get(10)).isFalse();

This version also supports setting a range of values:

bitSet.set(20, 30, false); for (int i = 20; i <= 29; i++) { assertThat(bitSet.get(i)).isFalse(); }

4.3. Clearing Bits

Instead of setting a specific bit index to false, we can simply clear it using the clear(index) method:

bitSet.set(42); assertThat(bitSet.get(42)).isTrue(); bitSet.clear(42); assertThat(bitSet.get(42)).isFalse();

Moreover, we can also clear a range of bits with the clear(fromInclusive, toExclusive) overloaded version:

bitSet.set(10, 20); for (int i = 10; i < 20; i++) { assertThat(bitSet.get(i)).isTrue(); } bitSet.clear(10, 20); for (int i = 10; i < 20; i++) { assertThat(bitSet.get(i)).isFalse(); }

Interestingly, if we call this method without passing any arguments, it'll clear all the set bits:

bitSet.set(10, 20); bitSet.clear(); for (int i = 0; i < 100; i++) { assertThat(bitSet.get(i)).isFalse(); }

As shown above, after calling the clear() method, all bits are set to zero.

4.4. Getting Bits

So far, we used the get(index) method quite extensively. When the requested bit index is set, then this method will return true. Otherwise, it'll return false:

bitSet.set(42); assertThat(bitSet.get(42)).isTrue(); assertThat(bitSet.get(43)).isFalse();

Similar to set and clear, we can get a range of bit indices using the get(fromInclusive, toExclusive) method:

bitSet.set(10, 20); BitSet newBitSet = bitSet.get(10, 20); for (int i = 0; i < 10; i++) { assertThat(newBitSet.get(i)).isTrue(); }

As shown above, this method returns another BitSet in the [20, 30) range of the current one. That is, index 20 of the bitSet variable is equivalent to index zero of the newBitSet variable.

4.5. Flipping Bits

To negate the current bit index value, we can use the flip(index) method. That is, it'll turn true values to false and vice versa:

bitSet.set(42); bitSet.flip(42); assertThat(bitSet.get(42)).isFalse(); bitSet.flip(12); assertThat(bitSet.get(12)).isTrue();

Similarly, we can achieve the same thing for a range of values using the flip(fromInclusive, toExclusive) method:

bitSet.flip(30, 40); for (int i = 30; i < 40; i++) { assertThat(bitSet.get(i)).isTrue(); }

4.6. Length

There are three length-like methods for a BitSet. The size() method returns the number of bits the internal array can represent. For instance, since the no-arg constructor allocates a long[] array with one element, then the size() will return 64 for it:

BitSet defaultBitSet = new BitSet(); assertThat(defaultBitSet.size()).isEqualTo(64);

With one 64-bit number, we can only represent 64 bits. Of course, this will change if we pass the number of bits explicitly:

BitSet bitSet = new BitSet(1024); assertThat(bitSet.size()).isEqualTo(1024);

Moreover, the cardinality() method represents the number of set bits in a BitSet:

assertThat(bitSet.cardinality()).isEqualTo(0); bitSet.set(10, 30); assertThat(bitSet.cardinality()).isEqualTo(30 - 10);

At first, this method returns zero as all bits are false. After setting the [10, 30) range to true, then the cardinality() method call returns 20.

Also, the length() method returns the one index after the index of the last set bit:

assertThat(bitSet.length()).isEqualTo(30); bitSet.set(100); assertThat(bitSet.length()).isEqualTo(101);

At first, the last set index is 29, so this method returns 30. When we set the index 100 to true, then the length() method returns 101. It's also worth mentioning that this method will return zero if all bits are clear.

Finally, the isEmpty() method returns false when there is at least one set bit in the BitSet. Otherwise, it'll return true:

assertThat(bitSet.isEmpty()).isFalse(); bitSet.clear(); assertThat(bitSet.isEmpty()).isTrue();

4.7. Combining With Other BitSets

The intersects(BitSet) method takes another BitSet and returns true when two BitSets have something in common. That is, they have at least one set bit in the same index:

BitSet first = new BitSet(); first.set(5, 10); BitSet second = new BitSet(); second.set(7, 15); assertThat(first.intersects(second)).isTrue();

The [7, 9] range is set in both BitSets, so this method returns true.

It's also possible to perform the logical and operation on two BitSets:

first.and(second); assertThat(first.get(7)).isTrue(); assertThat(first.get(8)).isTrue(); assertThat(first.get(9)).isTrue(); assertThat(first.get(10)).isFalse();

This will perform a logical and between the two BitSets and modifies the first variable with the result. Similarly, we can perform a logical xor on two BitSets, too:

first.clear(); first.set(5, 10); first.xor(second); for (int i = 5; i < 7; i++) { assertThat(first.get(i)).isTrue(); } for (int i = 10; i < 15; i++) { assertThat(first.get(i)).isTrue(); }

There are other methods such as the andNot(BitSet) or the or(BitSet),which can perform other logical operations on two BitSets.

4.8. Miscellaneous

As of Java 8, there is a stream() method to stream all set bits of a BitSet. For instance:

BitSet bitSet = new BitSet(); bitSet.set(15, 25); bitSet.stream().forEach(System.out::println);

This will print all set bits to the console. Since this will return an IntStream, we can perform common numerical operations such as summation, average, counting, and so on. For instance, here we're counting the number of set bits:

assertThat(bitSet.stream().count()).isEqualTo(10);

Also, the nextSetBit(fromIndex) method will return the next set bit index starting from the fromIndex:

assertThat(bitSet.nextSetBit(13)).isEqualTo(15);

The fromIndex itself is included in this calculation. When there isn't any true bit left in the BitSet, it'll return -1:

assertThat(bitSet.nextSetBit(25)).isEqualTo(-1);

Similarly, the nextClearBit(fromIndex) returns the next clear index starting from the fromIndex:

assertThat(bitSet.nextClearBit(23)).isEqualTo(25);

On the other hand, the previousClearBit(fromIndex) returns the index of the nearest clear index in the opposite direction:

assertThat(bitSet.previousClearBit(24)).isEqualTo(14);

Same is true for previousSetBit(fromIndex):

assertThat(bitSet.previousSetBit(29)).isEqualTo(24); assertThat(bitSet.previousSetBit(14)).isEqualTo(-1);

Moreover, we can convert a BitSet to a byte[] or a long[] using the toByteArray() or toLongArray() methods, respectively:

byte[] bytes = bitSet.toByteArray(); long[] longs = bitSet.toLongArray();

5. Conclusion

Dans ce tutoriel, nous avons vu comment nous pouvons utiliser des BitSet pour représenter un vecteur de bits.

Au début, nous nous sommes familiarisés avec la justification de ne pas utiliser booléen [] pour représenter un vecteur de bits. Ensuite, nous avons vu comment un BitSet fonctionne en interne et à quoi ressemble son API.

Comme d'habitude, tous les exemples sont disponibles sur over sur GitHub.