BitArrayBin is class from ActiveMQ and is used to set true/false against some long index. This is useful if we want to know whether some sequence ID is duplicated. In case of ActiveMQ, it is used it to find out whether a message is duplicated.The trick would be to minimize the memory consumption. Since each boolean uses a byte, it would be a wastage of memory if we use a boolean array. We need to see how we can store a boolean value in a bit.
If we somehow map a long value into an int index, we can store that index in a long variable using masking.
If y is the long index, it can be shown as x * 64 + x‘ where x is the bin index and x‘ is the offset into the bin.
This helps us to map a long value into a bin and subsequently an offset into it.
Now we shall use masking to set the bit, and then, get it’s value.
The bit’s value will initially be 0.
- Assuming offset value is 2, and we want to set it to true, the stored bits would be 0 | 10 = 10 = 10
- If offset value is 16, and we want to set the bit to true, the stored bits would be 10 | 10000 = 10010
- If want to find the old value at index 2, we will do an AND operation, old value = bits & 10 = 10010 & 10 = 10. The result is true as it is a not null.
- If offset value is 16, and we want to set the bit to false, bits = 10010 & 101111 = 10. This is nothing but bits = bits & ~(10000)
Below diagram shows a BitArrayBin which is nothing but a holder for many bins where the size can be defined during its construction. Each bin contains a long variable to store the bits so so it can store up to 64 boolean values.