BitMap原理&Redis和Java中的位图实现

/ 默认分类 / 0 条评论 / 1107浏览

BitMap

1.简介

bitmap是一种数据结构，可以用来对数据进行压缩存储，另外还可以用来对大规模数据进行相关操作处理。他的原来很简单，就是用二进制数据位来表示一个数，如果第n个位上的数是1则表示n这个数存在，如果第m个位上的数是0，则表示m这个数不存在。 以Java语言为例，如果现在需要存储1亿个不同的整数(最大数就是1亿),那么占用的空间为：

100000000*4/1024/1024≈381M

但是如果使用bitMap存储，占用内存为

100000000/32*4/1024/1024≈11.9M

可以看到,大约节省了原来97%的空间

2.存储原理

假设一个int整形数据类型占用1个字节,那么也就是8位,那么一个整形数据就可以表示[0,7]这个区间的八个整数,比如下面的存储就可以表示2和7存在,其他数不存在

image-20220221192102895

所以,如果数很大,超出了8位可以表示的范围,那么可以再加一个int(这里先假设int是1个字节),那么

image-20220221192809682 不难看出,这样就等于是一个二维数组了.

3. 操作方式

现在我们弄明白了bitmap的存储原理,那么我们要怎样将数据存储到指定的位上? 前面说过了,整个bitmap结构就是一个二维数组,所以,当我们需要存储的最大数字是N,假设一个int占1个字节,那么我们需要开辟的int数据的数目(也就是二维数组的第一个维度大小)就是:

len1 = N/8

数组的第二个维度大小就是:

len2 = N % 8

下面是一个实际的例子:

image-20220221194431570

但实际上,一个int数据就可以看作为一个bit数组,所以如果我们需要用bitmap表示一个最大数为N的数据集,那么可以开辟了一个int数组如下:

int[] bitmap = new int[N/8]
bitmap[N/8] = bitmap[N/8] | (1 << bitmap[N%8])

4. 实现一个简单的BitMap

上面我们是假设一个int占用1个字节,下面我们按照这样的逻辑,以java语言为例,编写一个简单的BitMap

/**
 * @author hi@54zh.cn
 * @date 2022/2/21
 */
public class BitMap {

    //使用int数组来作为存储的底层结构,也就是相当于每一个一维数组可以表示32个不同的数
    private int[] data;
    private static final int LEN = 32;
    private static final int NUM = 1;

    //这里我们简单点,就是指定当前二维数组的二维长度
    public BitMap(int length) {
        data = new int[length];
    }

    //按照存储的最大数字来创建bitmap
    public BitMap(long max) {
        data = new int[(int)max/LEN];
    }

    public void insert(int num){
        int arrIndex = num / LEN;
        int bitIndex = num % LEN;
        data[arrIndex] = data[arrIndex] | NUM << bitIndex;
    }

    public void insert(int... nums){
        for (int num : nums) {
            int arrIndex = num / LEN;
            int bitIndex = num % LEN;
            data[arrIndex] = data[arrIndex] | NUM << bitIndex;
        }
    }

    public void remove(int... nums){
        for (int num : nums) {
            int arrIndex = num / LEN;
            int bitIndex = num % LEN;
            data[arrIndex] = data[arrIndex] & ~(NUM << bitIndex);
        }
    }

    //取反之后，目标位是0，其他位都为1，所以与原数且运算，可以保证原数其他位上的数不变，目标位变为0，达到删除的目的
    public void remove(int num){
        int arrIndex = num / LEN;
        int bitIndex = num % LEN;
        data[arrIndex] = data[arrIndex] & ~(NUM << bitIndex);
    }

    //左移之后的数因为只有目标为上是1，其他都为0，所以与原数&运算后，如果不存在，则目标位就是0&1=0,否则是1&1=1
    public boolean exist(int num){
        int arrIndex = num / LEN;
        int bitIndex = num % LEN;
        return (data[arrIndex] & (NUM << bitIndex)) != 0;
    }

    public void print(){
        for (int num : data) {
            System.out.println(Integer.toBinaryString(num));
        }
    }
    
}

下面来测试一下：

public class Test {

    public static void main(String[] args) throws IOException, InterruptedException {
        BitMap bitMap = new BitMap(3);
        bitMap.print();
        System.out.println("----------");
        bitMap.insert(5,21,26,31,40,63,84,95);
        bitMap.print();
        System.out.println("----------");
        try{
            bitMap.insert(96);
        }catch(Exception e)
        {
            e.printStackTrace();
        }
        System.out.println("----------");
        bitMap.remove(5);
        bitMap.print();
        System.out.println("----------");
        bitMap.remove(84,95);
        bitMap.print();
        System.out.println("----------");
        System.out.println("5 does" + (bitMap.exist(5) ? "" : " not") + " exist");
        System.out.println("26 does" + (bitMap.exist(26) ? "" : " not") + " exist");
    }

}

运行结果如下:

0
0
0
----------
10000100001000000000000000100000
10000000000000000000000100000000
10000000000100000000000000000000
----------
java.lang.ArrayIndexOutOfBoundsException: 3
	at cn.zuo.BitMap.insert(BitMap.java:28)
	at cn.zuo.Test.main(Test.java:20)
----------
10000100001000000000000000000000
10000000000000000000000100000000
10000000000100000000000000000000
----------
10000100001000000000000000000000
10000000000000000000000100000000
0
----------
5 does not exist
26 does exist

可以看到,我们已经实现了简单的bitmap用来存储数据.

针对以上特性,bitmap可以用于排序和去重,以及快速查找定位元素是否存在.

bitmap中的数据插入后就已经是有序的了，并且数据也是去重后的，所以可以将需要排序或者需要去重的一组数据放入bitmap中，这样便利输出出来的一组数据就是有序不重复的。

可以添加以下方法:

	public List<Integer> outputNum(){
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < LEN; j++) {
                if((data[i] & 1 << j) != 0){
                    list.add(i*32 + j);
                }
            }
        }
        return list;
    }

测试:

    public static void main(String[] args)  {
        BitMap bitMap = new BitMap(3);
        bitMap.insert(5,45,32,7,4,45,32,95,87,82,87);
        List<Integer> list = bitMap.outputNum();
        System.out.println(list);
    }

结果:

[4, 5, 7, 32, 45, 82, 87, 95]

5. 解析几个典型的实现

5.1 redis中的bitmap

redis中支持使用bitmap进行数据存储，相关功能的命令如下：

SETBIT key offset value
GETBIT key offset
BITCOUNT key [start] [end]
BITOP operation destkey key [key ...]

关于这些命令的解释可以参考下面的文档： redis官方文档
国内总结文档

利用redis的这个功能，就可以实现使用 bitmap 实现用户上线次数统计 假设现在我们希望记录自己网站上的用户的上线频率，比如说，计算用户 A 上线了多少天，用户 B 上线了多少天，诸如此类，以此作为数据，从而决定让哪些用户参加 beta 测试等活动 —— 这个模式可以使用 SETBIT 和 BITCOUNT 来实现。 比如说，每当用户在某一天上线的时候，我们就使用 SETBIT ，以用户名作为 key ，将那天所代表的网站的上线日作为 offset 参数，并将这个 offset 上的为设置为 1 。 举个例子，如果今天是网站上线的第 100 天，而用户 peter 在今天阅览过网站，那么执行命令 SETBIT peter 100 1 ；如果明天 peter 也继续阅览网站，那么执行命令 SETBIT peter 101 1 ，以此类推。 当要计算 peter 总共以来的上线次数时，就使用 BITCOUNT 命令：执行 BITCOUNT peter ，得出的结果就是 peter 上线的总天数。(该方案摘自doc.redisfans.com)

5.2 java中的BitSet

Java中也有完善的BitMap的实现，也就是BitSet,下面简单看下BitSet的实现

public class BitSet implements Cloneable, java.io.Serializable {
    /*
     * BitSets are packed into arrays of "words."  Currently a word is
     * a long, which consists of 64 bits, requiring 6 address bits.
     * The choice of word size is determined purely by performance concerns.
     */
    private final static int ADDRESS_BITS_PER_WORD = 6;
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
    private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
    
    private long[] words;
    
    private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }
    
..........

上面是我截取的jdk中的BitSet的部分源码，可以看出，BitSet中使用的是long数组存储的，而我们上面实现的BitMap是byte数组存储的，但是其他的插入等操作都是同样的道理，这里主要解析下set方法：

 public void set(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);
        expandTo(wordIndex);

        words[wordIndex] |= (1L << bitIndex); // Restores invariants

        checkInvariants();
    }

首先，wordIndex方法就等同于我们上面实现的BitMap中的int arrIndex = num / LEN;，除以数组长度来得到第一维度的索引，这里bitIndex >> 6，其实也就是除以64，所以我们上面的BitMap也可以直接修改位位运算来提高运算效率

另外，这里需要注意的一点是，在前面我们自己实现的BitMap中，我们通过取余操作得到需要左移的位数，但是这里直接左移bitIndex，没有和64进行取余，原因很简单，java中的移位操作会按照是否超出数据类型的大小范围自动取余进行移位。这一点和python中是不一样的，因为python在3.0之后，默认int就是long int，可以是无限大小的整数，所以不存在数据类型大小的限制，所以移位不会取余。


System.out.println(1<<31);
//打印结果：-2147483648

System.out.println(1<<32);//也就是2^(32%32)=2^0
//打印结果： 1

System.out.println(1<<33);//也就是2^(33%32)=2^1
//打印结果： 2

但是py中：

print(1<<32)
//4294967296

print(1<<100)
//1267650600228229401496703205376

理解了上面这几点，BitSet就很容易弄清楚原理了，其实和我们最上面实现的BitMap的原理都是一样的。

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2022/05/05 10:41