目录

bitmap

基本思想

所谓的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,名字叫highLowContainerhighLowContainer存储了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中。keysvalues通过下标一一对应。size则标示了当前包含的key-value pair的数量,即keysvalues中有效数据的数量。

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数据结构及原理