Java : Difference between a boolean array & BitSet? [duplicate]

Question

This question already has answers here:

boolean[] vs. BitSet: Which is more efficient? (8 answers)

Closed 8 years ago.

Java : Difference between a boolean array & BitSet?

As per the documentation of BitSet,

"This class implements a vector of bits that grows as needed. Each component of the bit set has a boolean value."

This makes me think, what is the difference between a BitSet() and a boolean[] array?

1) Is There any difference under the hood in the amount of space allocated in the memory?

What is the difference in memory allocation if I create both boolean Array & BitSet of size 10 million

2) which one is faster?

Answer 1

The documentation for a BitSet pretty clearly implies that the implementation isn't necessarily an actual boolean array. In particular:

Every bit set has a current size, which is the number of bits of space currently in use by the bit set. Note that the size is related to the implementation of a bit set, so it may change with implementation. The length of a bit set relates to logical length of a bit set and is defined independently of implementation.

The source for Java library classes is openly available and you can easily check this for yourself. In particular:

The internal field corresponding to the serialField "bits".
89 
90     private long[] words;

As for speed; profile it. It depends on what you are doing. In general, don't think about speed ahead of time; use whichever tool makes the most sense semantically and leads to the clearest code. Optimize only after observing that your performance requirements aren't being met and identifying the bottlenecks.

In any case, obviously, I'd presume that a direct access to a value in a boolean array is faster than finding the bit in a long array, but performing a bitwise OR on two long values is faster than performing a logical OR on 64 boolean values. Think about it a little. For example:

613     public boolean get(int bitIndex) {
614         if (bitIndex < 0)
615             throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
616 
617         checkInvariants();
618 
619         int wordIndex = wordIndex(bitIndex);
620         return (wordIndex < wordsInUse)
621             && ((words[wordIndex] & (1L << bitIndex)) != 0);
622     }

As for other differences, obviously the API is different. BitSet provides a number of bitwise operations that you may need to use. A boolean array is an array. The one that works best for you will depend on your specific application requirements.

Answer 2

The memory difference should be factor 8.

For your 2nd question: Faster doing what?