bitmap

summarize

BitMap (BitMap) using binary bits to indicate the existence of a number, such as a byte accounted for 8 bits, so that the byte can be used to indicate 1-8, the corresponding bit 1 means that the corresponding number exists, 0 does not exist, a significant saving of storage space

Java Implementation of Bitmaps

There is an official bitmap implementation of BitSet in the package, or we can implement our own.

Java uses byte[] byte arrays to store bit data. For bit i in the bit data, a 1 means true that the data exists; a 0 means false that the data does not exist

The data structure of a bitmap is as follows, stored in bits

public class Bitmap {

  private byte[] bytes;
  // length is the length of the bitmap
  private int length;
  
  public Bitmap(int length) {
     = length;
    bytes = new byte[length % 8 == 0 ? length / 8 : length / 8+1];
  }
}

Assuming the value to be queried is val, the query operation using a bitmap is as follows:

1. Get the byte where the target bit is located by val/8 arrayIndex
2. Get the position of the target bit in this byte by val%8 bitIndex
3. bytes[arrayIndex] & (1<<bitIndex) set all the bits corresponding to the target bit to 0 and get the final value, if the final value is 0 then it means false, otherwise it means true

public boolean get(int val) {
  int arrayIndex = val /8;
  int bitIndex = val % 8;
  if((bytes[arrayIndex] & (1 << bitIndex)) != 0) {
    return true;
  }
  return false;
}

Assuming the value to be modified is val, the modification operation using a bitmap is as follows:

1. Find the target where val is located along the lines of the query
2. If val is modified to be the presence of data and the target bit is orchestrated with 1, you need to construct an operand with 1 in the target bit and 0 in the other bits.
3. If val is changed to data that does not exist and the target bit is summed to 0, you need to construct an operand with the target bit as 0 and the other bits as 1.

public void set(boolean flag, int val) {
  int arrayIndex = val /8;
  int bitIndex = val % 8;
  if(flag) {
    bytes[arrayIndex] |= 1 << bitIndex;
  } else {
    bytes[arrayIndex] &= ~(1 << bitIndex);
  }
}