数据结构-位图（可对海量数据进行处理）

我会带着你远行 2022-06-04 06:51 328阅读 0赞

#### 在学习linux过程中，wait函数中的status参数的用法其实就如同位图，位图法就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在STL中有一个bitset容器，其实就是**位图法。** ####

--------------------

#### 一、先给一个很简单的情景来引入该结构。题目如下： ####

#### **加入给定40亿个无符号整数，要快速判断一个值是否在这其中，该怎么解决？** ####

##### 首先我们得了解内存中各个单位之间的转换： #####

![这里写图片描述][SouthEast]

--------------------

通过上面的图我们可以了解到**40个亿个整型在4G内存中如果都以整型的方式是存不下的！！**也就压根别想我们存到一个数组里，依次遍历一遍这种简单粗暴的办法了。这时候就可以利用位图来解决这个题。先简述一下位图的解决方法：我们可以给每一个不同的数字在开辟的数组中拿一个位表示它在或者不在（一个位的状态只有0或者1，刚好对应了题目中的存在或者不存在），这时候存40亿个整型就被我们转换成了存储40亿个位，再计算一下我们只需要差不多500M的空间就可以存下这40亿个数字的出现状态，最后再计算出该数字对应的那一位的状态，如果是1则表示存在，是0则不存在。

--------------------

##### 先给出实现代码再来一步步解释 #####

class MyBitMap
    {
    public:
        MyBitMap()
        {}
    
        MyBitMap(const int& range)
        {
            _a.resize((range >> 3) + 1);
        }
    
    
        void Set(const int& x)
        {
            int index = (x >> 3);
            int bit = x % 8;
            _a[index] |= (1 << bit);
        }
    
        void Reset(const int& x)
        {
            int index = (x >> 3);
            int bit = x % 8;
            _a[index] &= ~(1 << bit);
        }
    
        bool Test(const int& x)
        {
            int index = (x >> 3);
            int bit = x % 8;
            bool res = (_a[index] >> bit) & 1;
            return res;
        }
    
    private:
        vector<char> _a;
    };

--------------------

##### 简单的测试一下： #####

![这里写图片描述][SouthEast 1]

--------------------

#### **梳理过程：** ####

##### **开辟空间：**给定一个数值范围，开辟大小为rang / 8 +1的数组。+1的原因在于当范围小于8时，如果不加1则数组开辟大小就为0，那接下来的操作就会错误。 #####

##### **置1操作：**给定一个数值，计算出该数字在数组中对应的下标以及在该下标中对应的位，或上1左移bit位，就完成了将该位置1的操作； #####

##### **置0操作：**同上，只不过需要与上~(1 << bit)，就完成置0操作； #####

##### **取出结果：**算出对应的下标以及位后，取出该位的结果进行判断即可。 #####

--------------------

##### 将上面的测试用图示的方法梳理下： #####

![这里写图片描述][SouthEast 2]

--------------------

#### 二、再给个稍微复杂一点的情景：假如还是40亿个数字，我们现在要找出其中出现次数不少于三次的数字。有了上面的铺垫，这个题就很简单了。 ####

##### **思路：**第一题由于只需要表示存在或不存在，一个二进制位就可以表示了。在这个题中，不少于两次就需要使用两位来表示：00代表没出现过，01代表出现了一次，10表示出现了两次，11表示出现了不少于三次，也就是大于等于3。 #####

##### 实现代码： #####

class TwoBitMap
    {
    public:
        TwoBitMap()
        {}
    
        TwoBitMap(const int& range)
        {
            //range /4
            _a.resize((range >> 2) + 1);
        }
    
        void Set(const int& x)
        {
            int index = (x >> 2);
            int bit_start = x % 4 * 2;
            bool first = _a[index] & (1 << bit_start);
            bool second = _a[index] & (1 << (bit_start + 1));
    
            if (!(first && second))
                _a[index] += (1 << bit_start);
        }
    
        bool Test(const int& x)
        {
            int index = (x >> 2);
            int bit_start = x % 4 * 2;
            bool first = _a[index] & (1 << bit_start);
            bool second = _a[index] & (1 << (bit_start + 1));
    
            return first && second ? true : false;
        }
    
    
    private:
        vector<char> _a;
    };

##### 简单测试： #####

![这里写图片描述][SouthEast 3]

--------------------

#### 注意：位图用每一位来存放某种状态，但是只限于整数类型，所以当我们要想将其他信息使用位图来解决，就不太行了。例如存储字符串状态，就最好使用布隆过滤器。至于STL中的bitset的用法可参考[http://www.cplusplus.com/reference/bitset/bitset/?kw=bitset][http_www.cplusplus.com_reference_bitset_bitset_kw_bitset] ####

[SouthEast]: /images/20220604/18b3c50062104524a02d5c506bb5b4b2.png
[SouthEast 1]: /images/20220604/32d9228a09c446bba3bf534d6b82d600.png
[SouthEast 2]: /images/20220604/e7d98a5305da4c629920c309c8e0ecae.png
[SouthEast 3]: /images/20220604/3d3cd1ad3077489f9589eddca8579960.png
[http_www.cplusplus.com_reference_bitset_bitset_kw_bitset]: http://www.cplusplus.com/reference/bitset/bitset/?kw=bitset