CODEWITHSUNDEEP
javacollectionsbitset
mR_fr0g
mR_fr0g

Reputation: 8722

Alternative to java.util.BitSet for small sizes?

java.util.BitSet is backed by a long[] so the minimum size is 64 bits. I require to cache lots (~2M) of objects that each require a BitSet of size 23. Is there an alternative to BitSet that is more space efficient for small sizes? For example is there a BitSet type data structure that is backed by a byte[] instead of a long[]? This would allow me to store my 23 bits in 3 bytes instead of 8.

Upvotes: 2

Views: 1249

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

The java.util.BitSet class is designed for larger bit sets. When you need bit sets of size 23, even a bit set based ob 3 bytes would use too much memory, because an array of any size uses an additional reference for the array itself, which is most likely four to eight bytes.

The most economical solution in terms of memory is using ints instead of bit sets, and writing your own implementations of the bit set operations that you need. Since operations on bit sets are for the most part copied from bitwise operations, you should have no problem implementing them:

boolean get(int mySet, int index) {
    return (mySet & (1<<index)) != 0;
}
int set(int mySet, int index) {
    return mySet | (1<<index);
}
int clear(int mySet, int index) {
    return mySet & (1<<index);
}

...and so on.

Upvotes: 9

Alexei Kaigorodov
Alexei Kaigorodov

Reputation: 13525

First, byte array of length 3 takes much more than 3 bytes. Any object instance in Java has memory overhead, including BitSet.

To keep memory consumption low, try to use elements of int array for bit set. Such element cannot be represented as an object, so you have to develop procedure interface rather than object-oriented. Tell us what operations on bitsets you need and we'll make more detailed advice.

Upvotes: 0

Related Questions