Bitmap

简介

Bit-map就是用一个bit位来标记某个元素对应的Value（若元素存在bit位置为1，不存在则置为0）。可创建一个整型数组（如byte数组，int数组，long数组）来表示。可以使用redis的api来实现对bitmap的运用

代码实现bitmap

BitmapUtil
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package com.cc.bitmap;

public class BitmapUtil {

    private static int capacity;

    private static int maxValue;

    private static byte[] byteBits;

    public BitmapUtil(int maxValue) {
        this.maxValue = maxValue;
        this.capacity = maxValue / 8 + 1;
        byteBits = new byte[capacity];
    }
	
	//存储元素
    public void add(int x) {
        int index = x / 8;
        int location = x % 8;
        byteBits[index] |= 1 << location;
    }
	
	//判断是否包含某个元素
    public boolean find(int x) {
        int index = x / 8;
        int location = x % 8;
        int temp = byteBits[index] & (1 << location);
        if (temp != 0) {
           return true;
        }
        return false;
    }
}

测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package com.cc.bitmap;

public class Test {

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 5, 7, 8, 10};

        int maxvalue = 0;
        for (int it : arr) {
            maxvalue = Math.max(maxvalue, it);
        }

        BitmapUtil bitmapUtil = new BitmapUtil(maxvalue);


        for(int i = 0; i < arr.length; i ++) {
            bitmapUtil.add(arr[i]);
        }

        for(int i = 1; i <= 10; i ++) {
            boolean ans = bitmapUtil.find(i);
            if (!ans) {
                System.out.println("ans = " + ans + "---" + i + "不存在");
            }
        }
    }
}

测试结果
1
2
3
ans = false---2不存在
ans = false---6不存在
ans = false---9不存在