迦南地
所有文章 标签 分类 实验室 关于
迦南地

目录

bitmap

 收录于 技术
   约 7024 字   预计阅读 15 分钟    次阅读  

基本思想

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。

要表示8个数，我们就只需要8个Bit（1Byte），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0 然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作 (i/8)|(1«(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为1。

然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1。然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。 其实就是把计数排序用的统计数组的每个单位缩小成bit级别的布尔数组

以上内容引用自《编程珠玑》

原理剖析

假设现在有一个文件中的数据，该文件存储了N=1000000个无序的整数，需要把这些整数读取到内存并排序再重新写回文件中该如何解决？

我们知道一个int型的数有4个字节，也就是32位，那么我们可以用N/32个int型数组来表示这N个数：

1
2
3
4

a[0]表示第1~32个数（0~31）
a[1]表示第33~64个数（32~63）
a[2]表示第65~96个数（64~95）
...... 以此类推

这样，每当输入一个数字m，我们应该先找到该数字在数组的第？个元素，也就是a[?]，然后再确定在这个元素的第几个bit位，找到后设置为1，代表存在该数字。举个例子来说，比如输入40，那么40/32为1余8，则应该将a[1]元素值的第9个bit位置为1(1的二进制左移8位后就是第9个位置)，表示该数字存在。

大概明白了位向量表示方式后，上述过程的计算方式，通过以下方式可以计算该数存储在数组的第?个元素和元素中第?个bit位置,为了演示方便，我们这里假设整第?个元素中的?为p，余值设置s，数组int[] a, 待排序的整数为m。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

//m 除以2^n 的余数(s)表示为 m & (2^n-1) 
//等同于： m % 2^5 取余数 即：40 % 32 = 8

//m=40的二进制
00000000 00000000 00000000 00101000

//2^n-1（31）的二进制
00000000 00000000 00000000 00011111

// m & (2^n-1) 即40与31进行与操作得出余数 即 s=8
00000000 00000000 00000000 00001000 

//下面是将a[1]元素值的第(8+1)个bit设置为1，为什么是(8+1)不是8？因为1左移8位就在第9个bit位了，过程如下：

//1的二进制如下：
00000000 00000000 00000000 00000001

//1 << 8 利用余数8对1进行左移动
00000000 00000000 00000001 0000000 

//然后再与a[1]执行或操作后就可以将对应的bit位设置为1
//a[p] |= 1 << S 见下述java实现的代码

1
2
3
4
5
6
7
8
9

int 有32位，也即2^5个bit
p = i >> 5
s = i & (2^5 -1)
// 将i设置到数组a
  a[p] |= 1 << s
// 将i从数组a上清除
  a[p] &= ~(1 << s)
// i在数组a上的bit值，1表示存在元素i，0表示不存在元素i,可以借助Integer.bitCount()方法，Integer.bitCount()是返回指定 int 值的二进制补码(计算机数字的二进制表示法都是使用补码表示的)表示形式的 1 位的数量。
	int num = Integer.bitCount();

示例代码

对1000以内的随机数(1000次随机并去重)排序

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

package com.eh.ftd.bitmap;

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

/**
 * todo
 *
 * @author David Li
 * @create 2020/08/05
 */
public class BitMap {

    private int maxNum; // 最大值
    private int[] a; // bitmap数组
    private int BIT_LENGTH = 32;
    private int MASK = 0x1F; // 2^5 -1
    private int SHIFT = 5; // Integer的位数32，2^5中的5

    // 初始化位向量，实际使用时最大值需要自己遍历获取
    public BitMap(int maxNum) {
        this.maxNum = maxNum;
        a = new int[(maxNum - 1) / BIT_LENGTH + 1]; // 最大值32需要2个Integer表示，因为0-32共33个元素
        init();
    }

    // 将数组中元素bit位都设置成0
    public void init() {
        for (int i = 0; i <= maxNum; i++) {
            clear(i);
        }
    }

    // 设置元素，置位操作
    public void set(int i) {
        a[i >> SHIFT] |= 1 << (i & MASK);
    }

    // 清除元素, 置0操作
    public void clear(int i) {
        a[i >> SHIFT] &= ~(1 << (i & MASK));
    }

    // 读取元素所在位置的bit位值
    public int get(int i) {
        return Integer.bitCount(a[i >> SHIFT] & (1 << (i & MASK)));
    }

    public static void main(String[] args) {
        int count = (int) Math.pow(10, 3);
        int maxNum = (int) Math.pow(10, 3);

        // 构造测试元素集合
        List<Integer> list = getRandomsList(count, maxNum);
        // 排序
        long start = System.currentTimeMillis();
        BitMap bitMap = new BitMap(maxNum);

        list.forEach(bitMap::set);
        System.out.println(System.currentTimeMillis() - start);
        // 输出
        for (int i = 0; i <= maxNum; i++) {
            if (bitMap.get(i) == 1) {
                System.out.println(i);
            }
        }
    }

    private static List<Integer> getRandomsList(int count, int maxNum) {
        Random random = new Random();
        List<Integer> randomsList = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            int element = random.nextInt(maxNum); //element ∈  [1,count)
            if (!randomsList.contains(element)) {
                randomsList.add(element);
            }
        }
        return randomsList;
    }
}

应用场景

  1. 快速排序

  2. 快速查询

    先对所有数字进行一次遍历(相当于一趟一趟快速排序)。遍历完以后就是查询，由于我们的Bit-map采取的是连续存储（整型数组形式，一个数组元素对应32bits），我们实际上是采用了一种分桶的思想。一个数组元素可以存储32个状态位，那将待查询的数字除以32，定位到对应的数组元素（桶），然后再求余（%32），就可以定位到相应的状态位。如果为1，则代表改数字存在；否则，该数字不存在。

  3. 快速去重

    在3亿个整数中找出不重复的整数，限制内存不足以容纳3亿个整数。

    对于这种场景我可以采用2-BitMap来解决，即为每个整数分配2bit，用不同的0、1组合来标识特殊意思，如00表示此整数没有出现过，01表示出现一次，11表示出现过多次，就可以找出重复的整数了，其需要的内存空间是正常BitMap的2倍，为：3亿*2/8/1024/1024=71.5MB。

    具体的过程如下：

    扫描着3亿个整数，组BitMap，先查看BitMap中的对应位置，如果00则变成01，是01则变成11，是11则保持不变，当将3亿个整数扫描完之后也就是说整个BitMap已经组装完毕。最后查看BitMap将对应位为01的整数输出即可。

  4. 统计不同号码的个数

    已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数

    8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）

  5. REDIS bitmap相关应用

    edis提供了类似的命令，最大可以存放2的32次方，即21亿多的数字，主要有以下几个：SETBIT， GETBIT， BITCOUNT， BITOP， BITPOS，BITFIELD

    主要用来做活跃用户在线状态、活跃用户统计、用户签到等场景，特别适合大量用户，几千万上亿级别，当然你用传统数据库也能做，但是redis做起来更简单，更节省空间！

    下面举一个用户签到的功能设计案例：

    很多App都有一个签到功能，比如说连续签到7天或者30天给一些奖励，需求十分简单！

    作为后端，我们需要提供一个签到接口，然后记录用户签到的信息，比如用户uid，签到时间！

    如果使用传统关系型数据库，我们可能需要建一张签到表，大概有id、uid、createdTime等几个字段，当用户签到的时候新增一条记录就行！这种做法肯定是没问题的，但是如果网站每天有千万用户签到，那么这张表每天都会有千万条记录产生，数据的存储是问题！分库分表必不可少！

    假如使用redis的bit操作，我们可以使用setbit，SETBIT key offset value 对指定的key的value的指定偏移(offset)的位置1或0, 其中key我们可以设置为当天的年月日，offset是用户uid（这里暂时只考虑uid是纯数字的情况）,value的话1表示已签到。比如说用户uid位12500的用户在20190501签到了，我们可以执行SETBIT 20190501 12500 1,其它用户依此论推！

    如果我们需要查询用户某天是否签到，只需要使用GETBIT 20190501 12500，返回1表示已签到，0未签到。

    如果需要查询某天有多少人签到，可以使用BITCOUNT 20190501。

    如果要统计连续7天签到的总人数的话可以使用bitop命令，比如bitop AND 7_dasy_sign 20190501 20190502 20190503 ... 20190507。

    对一个或多个保存二进制位的字符串key进行位元操作，并将结果保存到destkey上。

    operation可以是AND、OR、NOT、XOR这四种操作中的任意一种。 　　BITOP AND destkey key [key …] ，对一个或多个key求逻辑并，并将结果保存到destkey 　　BITOP OR destkey key [key …] ，对一个或多个key求逻辑或，并将结果保存到destkey 　　BITOP XOR destkey key [key …] ，对一个或多个key求逻辑异或，并将结果保存到destkey 　　BITOP NOT destkey key ，对给定key求逻辑非，并将结果保存到destkey 除了NOT操作外，其他操作都可以接受一个或多个key作为输入 当BITOP处理不同长度的字符串时，较短的那个字符串所缺少的部分会被看做0 空的key也被看作是包含0的字符串序列

    理论上讲，setbit的大小在0到2的32次方（最大使用512M内存）之间，即0~4294967296之间，也就说最多可以存储42亿用户的签到情况。和数据库相比，这种方式查询的效率非常高，并不会因为数据大而变慢，而且比较节省内存，操作上也不是太复杂！

扩展

问题

数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。

数据稀疏。又比如要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。

Bloom Filter

概念

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

原理

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。

https://gitee.com/lienhui68/picStore/raw/master/null/20200805095525.png

缺点

bloom filter之所以能做到在时间和空间上的效率比较高，是因为牺牲了判断的准确率、删除的便利性

  • 存在误判，可能要查到的元素并没有在容器中，但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。

  • 删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。可以采用Counting Bloom Filter

应用

常见的几个应用场景：

  • cerberus在收集监控数据的时候, 有的系统的监控项量会很大, 需要检查一个监控项的名字是否已经被记录到db过了, 如果没有的话就需要写入db.

  • 爬虫过滤已抓到的url就不再抓，可用bloom filter过滤

  • 垃圾邮件过滤。如果用哈希表，每存储一亿个 email地址，就需要 1.6GB的内存（用哈希表实现的具体办法是将每一个 email地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email地址需要占用十六个字节。一亿个地址大约要 1.6GB，即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB的内存。而Bloom Filter只需要哈希表 1/8到 1/4 的大小就能解决同样的问题。

Roaring BitMap

概念

为了解决位图不适应稀疏存储的问题，大佬们提出了多种算法对稀疏位图进行压缩，减少内存占用并提高效率。比较有代表性的有WAH、EWAH、Concise，以及RoaringBitmap。前三种算法都是基于行程长度编码（Run-length encoding, RLE）做压缩的，而RoaringBitmap算是它们的改进版，更加优秀。

https://gitee.com/lienhui68/picStore/raw/master/null/20200805100559.png

每个RoaringBitmap(GitHub链接)中都包含一个RoaringArray，名字叫highLowContainer。 highLowContainer存储了RoaringBitmap中的全部数据。

1

RoaringArray highLowContainer;1

这个名字意味着，会将32位的整形（int）拆分成高16位和低16位两部分（两个short）来处理。

RoaringArray的数据结构很简单，核心为以下三个成员：

1
2
3

short[] keys;
Container[] values;
int size;123

每个32位的整形，高16位会被作为key存储到short[] keys中，低16位则被看做value，存储到Container[] values中的某个Container中。keys和values通过下标一一对应。size则标示了当前包含的key-value pair的数量，即keys和values中有效数据的数量。

keys数组永远保持有序，方便二分查找。

三种Container

下面介绍到的是RoaringBitmap的核心，三种Container。

通过上面的介绍我们知道，每个32位整形的高16位已经作为key存储在RoaringArray中了，那么Container只需要处理低16位的数据。

ArrayContainer

1
2
3

static final int DEFAULT_MAX_SIZE = 4096

short[] content;123

结构很简单，只有一个short[] content，将16位value直接存储。

short[] content始终保持有序，方便使用二分查找，且不会存储重复数值。

因为这种Container存储数据没有任何压缩，因此只适合存储少量数据。

ArrayContainer占用的空间大小与存储的数据量为线性关系，每个short为2字节，因此存储了N个数据的ArrayContainer占用空间大致为2N字节。存储一个数据占用2字节，存储4096个数据占用8kb。

根据源码可以看出，常量DEFAULT_MAX_SIZE值为4096，当容量超过这个值的时候会将当前Container替换为BitmapContainer。

BitmapContainer

1

final long[] bitmap;1

这种Container使用long[]存储位图数据。我们知道，每个Container处理16位整形的数据，也就是0~65535，因此根据位图的原理，需要65536个比特来存储数据，每个比特位用1来表示有，0来表示无。每个long有64位，因此需要1024个long来提供65536个比特。

因此，每个BitmapContainer在构建时就会初始化长度为1024的long[]。这就意味着，不管一个BitmapContainer中只存储了1个数据还是存储了65536个数据，占用的空间都是同样的8kb。

RunContainer

1
2
3

private short[] valueslength;

int nbrruns = 0;123

RunContainer中的Run指的是行程长度压缩算法(Run Length Encoding)，对连续数据有比较好的压缩效果。

它的原理是，对于连续出现的数字，只记录初始数字和后续数量。即：

  • 对于数列11，它会压缩为11,0；
  • 对于数列11,12,13,14,15，它会压缩为11,4；
  • 对于数列11,12,13,14,15,21,22，它会压缩为11,4,21,1；

源码中的short[] valueslength中存储的就是压缩后的数据。

这种压缩算法的性能和数据的连续性（紧凑性）关系极为密切，对于连续的100个short，它能从200字节压缩为4字节，但对于完全不连续的100个short，编码完之后反而会从200字节变为400字节。

如果要分析RunContainer的容量，我们可以做下面两种极端的假设：

  • 最好情况，即只存在一个数据或只存在一串连续数字，那么只会存储2个short，占用4字节
  • 最坏情况，0~65535的范围内填充所有的奇数位（或所有偶数位），需要存储65536个short，128kb

RoaringBitmap针对Container的优化策略

创建时：

  • 创建包含单个值的Container时，选用ArrayContainer
  • 创建包含一串连续值的Container时，比较ArrayContainer和RunContainer，选取空间占用较少的

转换：

针对ArrayContainer：

  • 如果插入值后容量超过4096，则自动转换为BitmapContainer。因此正常使用的情况下不会出现容量超过4096的ArrayContainer。
  • 调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。

针对BitmapContainer：

  • 如果删除某值后容量低至4096，则会自动转换为ArrayContainer。因此正常使用的情况下不会出现容量小于4096的BitmapContainer。
  • 调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。

针对RunContainer：

  • 只有在调用runOptimize()方法才会发生转换，会分别和ArrayContainer、BitmapContainer比较空间占用大小，然后选择是否转换。

参考

大数据量下的集合过滤—Bloom Filter

RoaringBitmap数据结构及原理

更新于 2020-06-12
 数据结构与算法基础, 数据结构
返回 | 主页