-1

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?

Rajesh Pantula
  • 10,061
  • 9
  • 43
  • 52
  • 2
    This question asked earlier...http://stackoverflow.com/questions/605226/boolean-vs-bitset-which-is-more-efficient – Kuldeep Nov 05 '13 at 11:56
  • The difference between a boolean array and a BitSet is essentially the same as the difference between an array of object references and a List. – Hot Licks Nov 05 '13 at 11:59
  • 1
    @Kuldeep They're both pretty terrible questions. Questions like this that ask about speed generally show that the OP thinks they care about efficiency but wasn't willing to profile and didn't define performance requirements. Under the surface, that's usually a red flag that the OP is headed down the wrong path. – Jason C Nov 05 '13 at 12:10
  • Guys, I know this question was asked previously in SO, and I also know the difference between an array and a list. The sole purpose of asking the questions was if somebody can provide more insights at the bit level. Also these days I notice lot of people on SO, just paste a link to previous questions which does not provide satisfying answers. The quality of SO is seriously going down. Just be patient rather than pasting a link to some previous post and wait if somebody can provide better answer than you. – Rajesh Pantula Nov 06 '13 at 13:30

2 Answers2

3

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.

Jason C
  • 38,729
  • 14
  • 126
  • 182
  • +1 excellet answer, to which I only want to add that it may be(!) that loading a boolean (byte) from an odd addreess is slower than loading a long from an address divisible by 8, on 64bit CPUs anyway. Thus, not even the amortized direct access is *necessarily* faster. – Ingo Nov 05 '13 at 12:17
  • Platform-specific native address alignment isn't something that you even want to *begin* to think about when coding in Java, nor is it something you have enough information about to make even the most general statements on. Let hotspot do the work there, and in any case thinking about micro-optimizations that low level during design is certainly a mistake! – Jason C Nov 05 '13 at 12:27
  • Sure, I say that precisely because I have often seen newbees ask such questions that seem to imply that they think "byte is faster" (or some such along the lines). Thus, first, Thou shalst not think about µ-optimization! and second, The way modern systems work is often counter your intiution. – Ingo Nov 05 '13 at 12:58
0

The memory difference should be factor 8.

For your 2nd question: Faster doing what?

Ingo
  • 36,037
  • 5
  • 53
  • 100