What is a Java BitSet?
A Java BitSet is an implementation of the bitset data structure for the Java programming language. But what are Java BitSets exactly, and how do Java BitSets work?
What are Java BitSets?
In computer science, a bit set (also known as a bit array) is a highly compact way of storing information. A bit set consists of a length of values that take on either 0 or 1. These values represent some binary relationship, such as seen/unseen, absent/present, etc.
For example, suppose that we have a list of natural numbers and we want to know which of these integers are present in the list. First, we could create a bit set and initialize all of the values to false. Then, while iterating through the list, for each number that we find in the list, we change the corresponding bit in the bit set to true. At the end of the iteration, we can use the bit set as an easy way to check whether a given number is in the list. (Note that this requires a bit set whose size is at least as large as the largest number in the list.)
The benefit of a bit set is that it is extremely space-efficient, requiring only a single bit for each piece of information. Bit sets have a much smaller memory footprint than alternatives such as an array of boolean values, where each value consumes a byte of space (8 bits) instead of a single bit.
Java implements bit sets using the java.util.BitSet class. According to the Java documentation, a Java BitSet “implements a vector of bits that grows as needed. Each component of the bit set has a boolean value… By default, all bits in the set initially have the value false.”
How do Java BitSets work?
The java.util.BitSet class defines the methods that developers need to know when working with BitSets in Java. Below are some of the most important methods of Java BitSets:
- and():Given two BitSets, returns the logical AND operation of combining both BitSets.
- cardinality():Returns the number of bits in the BitSet that are currently set to true.
- clear():Sets all of the bits in the BitSet to false.
- clone(): Given a BitSet, creates a new identical copy of the original BitSet.
- flip(): Switches the value of the given bit (e.g. false to true or vice versa).
- get(): Given an index, returns the value of the bit at that index in the BitSet.
- isEmpty(): Returns true if all of the bits in the BitSet are set to false.
- nextClearBit(): Given an index, returns the index of the next bit in the BitSet that is set to false.
- nextSetBit(): Given an index, returns the index of the next bit in the BitSet that is set to true.
- or(): Given two BitSets, returns the logical OR operation of combining both BitSets.
- set(): Given an index and a boolean value, sets the value at that index in the BitSet.
- size(): Returns the number of bits of space used by the given BitSet.
Java BitSets in Redis
Redis is an open-source, in-memory data structure store that is used to implement NoSQL key-value databases, caches, and message brokers. There are several built-in data types in Redis, including lists, sets, sorted sets, strings, and hashes.
Bit sets in Redis are typically implemented using the string data type. Each character in the string is set to either 0 or 1. The maximum length of a string in Redis is 512 megabytes (2^32 bits), which puts an upper limit on the possible size of Redis bit sets.
Java developers who are used to the richness of the Java standard library may find this approach a bit challenging. For this reason, many developers choose to install a third-party Redis Java client such as Redisson.
Redisson includes many familiar Java objects, collections, and constructs for Java developers working with Redis. This includes Java BitSets, which are implemented in Redisson using the RBitSet interface. Below is a simple example demonstrating how to use RBitSet in order to work with Java BitSets in Redis:
RBitSet set = redisson.getBitSet("simpleBitset");
set.set(0, true);
set.set(1812, false);
set.clear(0);
set.addAsync("e");
set.xor("anotherBitset");
As in Redis itself, the size of a Redisson RBitSet object is limited to 2^32 bits (512 megabytes). RBitSet also comes with Async, Reactive, and RxJava2 interfaces so that you can choose the programming model that works best for you.