位图

发表于

定义

位图(bitmap),就是用每一位来存放某种状态，适用于数据规模大且状态不多的情况。通常是用来判断某个数据存不存在。
在STL中有一个bitset容器，其实就是位图。

优点

节省空间，比如用1bit代表一个unsigned int类型整数，相当用1bit表示32bit数据，存储空间缩小至1/32

缺点

  • 可读性差
    将数据抽象为bit不利于理解，尤其是用多个bit位来表示一个数时。
  • 存储离散数据空间利用率低
    Bitmap申请空间时要根据最大的数来决定申请的空间大小，如果数据是离散的，那空间的利用率就会非常低。
  • 不适合多状态
    一个bit只能表示两种状态，如果要表示更多的状态，就需要更多的状态位来实现。如果一个数字需要多个状态位来表示的话，Bitmap的优越性也会大打折扣，而且复杂度却在增加。
  • 位图元素虽然比一般做法多，但是存储的元素大小受限于存储空间大小。
    能够存储的元素的最大值受限于存储空间的元素的个数。比如1K字节内存，能够存储8K个值大小上限是8K的元素。要存储值为65535的数，就必须要65535/8 = 8K 字节的内存。
  • 位图对有符号类型数据的存储，需要2位表示一个有符号元素。折让位图能够存储的元素个数以及元素值大小上限减半。例如8K字节内存空间只能存储8K*4 = 32K个，元素值大小方位为-32K~32K

数据结构

unsigned int bit[N];
在这个数组里，可以存储Nsizeof(int)8个数据，最大的数是Nsizeof(int)8-1。假如我们要存储的数组范围是0-15，则我们只需要一个int就够了
20171217151348508344596.png

数据为5，1，7，15，0，4，6，10存入这个结构的情况是
20171217151348509565810.png

位图法与布隆过滤器

位图法可以快速判断一个整数是否存在于集合中。然而现实生活中我们用的更多的是字符串，位图无法处理字符串，于是引出了布隆过滤器

应用

海量数据排序

从最简单的情况说起，如果要对90个小于100的不重复的正整数排序。用位图的思想就是先申请一块100bit的空间，第一遍遍历所有的数，将出现的数字在位图中对应的位置置为1；第二遍遍历位图，依次输出值为1的位对应的数字。先且不说这种情况出现的频率不是很高，就仅这种情况，还是有很多其他的排序算法有它们自己的优势（不用额外占用空间之类）。但更进一步，如果我们把数字范围放大，对1000,000,000中的900,000,000个不重复的正整数排序，由于需要的内存非常大，其他算法在不分治的情况下就很难再处理这个问题。而用位图法只需要1000000000/(810241024)=119.2MB空间，对现在的计算机来说没有任何问题。

海量数据去重

使用位图法判断整数数组是否存在重复

遍历数组，一个一个放到bitmap中，并检查是否其在bitmap中出现过

有40亿个不重复的unsigned int的整数，没排序过，之后再给一个数，如何快速判断这个数是否存在在那40亿个数中

将这40亿个数字存储到bitmap中，然后对于给出的数，判断是否在bitmap中即可。
需要40亿/8 约等于 500M字节空间

在2.5亿个整数中找到不重复的整数(注意，内存不足以容纳2.5亿个整数)

方法1:
采用2-bitmap(每个数分配2bit,00表示不存在，01表示出现一次，10表示出现多次，11无意义)
需要2.5亿/4 = 62M 字节空间 前提元素大小小于等于2.5亿

方法2:
使用两个bitmap,第一个bitmap存储整数是否出现，第二个bitmap存储该数是否再次出现。

代码实现

C++STL中给出bitmap类，提供了很多方法

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
    class BitMap
{
public:
    BitMap()
    {}
    BitMap(size_t size)
    {
        //1一个字节8个bit，int4个字节，32个bit
        //所以_table中1一个元素可以表示32个数据
        _table.resize((size >> 5) + 1);
    }
    //置1
    void Set(int data)
    {
        //ByteNO是表示在table数组中那个元素
        size_t ByteNo = data >> 5; //相当于除以32
        //bitNo是表示在int字节32位bit中那个bit位。
        size_t BitNo = data % 32;
        _table[ByteNo] |= (1 << BitNo); //置1
    }
    //置0
    void ReSet(int data)
    {
        size_t ByteNo = data >> 5; //相当于除以32
        size_t BitNo = data % 32;
        _table[ByteNo] &= ~(1 << BitNo); //置0
    }
    //判断是否存在
    bool Test(int data)
    {
        size_t ByteNo = data >> 5; //相当于除以32
        size_t BitNo = data % 32;
        if (_table[ByteNo] & (1 << BitNo))
            return true;
        return false;
    }
private:
    vector<int> _table;
};

参考

大数据常用技巧之位图法
位图实现，处理大数据
数据结构:位图法