Bitmap——位图

import java.util.ArrayList;
import java.util.List;

/**
 * Created by zw on 2019/4/16.
 * 使用位图存储1000万个正整数，节省内存
 */
public class Bitmap {

    //1000万个正整数
    private static final int N = 10000000;
    
    //使用int数组进行存储，每个元素代表32个数字
    private int num[] = new int[N / 32 + 1];

    public void addValue(int value) {
        //int i = value % 32
        int i = value & 0x1f;

        //int index = value / 32;
        int index = value >> 5;
        
        //将1左移i位，做与运算
        num[index] |= (1 << i);
    }

    public void display(int row) {
        System.out.println("BitMap位图展示");
        for (int i = 0; i < row; i++) {
            List<Integer> list = new ArrayList<>();
            int temp = num[i];
            for (int j = 0; j < 32; j++) {
                list.add(temp & 1);
                temp >>= 1;
            }
            System.out.println("a[" + i + "]" + list);
        }
    }

    // 判断所在的bit为是否为1
    public boolean exists(int value) {
        int index = value >> 5;
        int i = value & 0x1f;
        return (num[index] & (1 << i)) != 0;
    }

    public static void main(String[] args) {
        int num[] = {1231231, 5, 30, 32, 64, 56, 159, 120, 21, 17, 35, 45};
        Bitmap map = new Bitmap();
        for (int i : num) {
            map.addValue(i);
        }

        int temp = 5;
        if(map.exists(temp)){
            System.out.println("temp:" + temp + "has already exists");
        }
        map.display(5);
    }
}

main result:

temp:5has already exists
BitMap位图展示
a[0][0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
a[1][1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
a[2][1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
a[3][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
a[4][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

Bitmap有两个比较局限的地方：

1. 当样本分布极度不均匀的时候，Bitmap会造成很大空间上的浪费
   比如有10个数，分别是1、2、3、4、5、6、7、8、99999999999；那么你不得不用99999999999个bit位去实现你的Bitmap,而这个Bitmap的中间绝大多数位置都是0，并且永远不会用到。
2. 当元素不是整型的时候，Bitmap就不适用了