数据结构之BITMAP

淩亂°似流年 2022-06-12 14:44 164阅读 0赞

我们先给出之前我看过的腾讯公司的一道笔试题，引出位图BitMap。

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

这个问题怎么解决呢？

1）将40亿数据保存起来（保存在数组、链表、树中），再和该数判断是否相等。

那我们思考一下需要多少内存：

[![技术分享][wKioL1c1du-CIGvrAABXJBMCxrU651.png]][wKioL1c1du-CIGvrAABXJBMCxrU651.png]

![技术分享][wKiom1c1de7B09ciAABXJBMCxrU543.png]

2）借助位图BitMap解决。

位图（BitMap）

是用一个数组中的每个数据的每个二进制位表示一个数是否存在。1表示存在，0表示不存在。

相当于把数组分成很多块的空间，每一块是32个比特位。

原来32个比特位放一个数据，现在一个位就可以放一个数据。16GB/32=0.5GB=512MB。

位图的实现：

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

#ifndef __BITMAP_H__
    #define __BITMAP_H__
    #include<iostream>
    using namespace std;
    
    #include<vector>
    
    class BitMap
    {
    public:
        BitMap(size_t size = 0)
            :_size(0)
        {
            //_a开辟多一个空间，如size=36/32=1,需要两块空间才能放下
            _a.resize((size >> 5) + 1);
        }
    
    
        void Set(size_t x)
        {
            //size_t index = x / 32;
            size_t index = (x >> 5);
            size_t num = x % 32;
    
            //if(!(_a[index] & (1 << num))表示该二进制位不存在，则该位二进制置成1
            if (!(_a[index] & (1 << num)))
            {
                _a[index] |= (1 << num);
                ++_size;
            }
        }
    
    
        void Reset(size_t x)
        {
            //size_t index = x / 32;
            size_t index = x >> 5;
            size_t num = x % 32;
    
            //该位存在则将该位二进制置为0
            if (_a[index] & (1 << num))
            {
                _a[index] &= ~(1 << num);
                --_size;
            }
        }
    
    
        bool Test(size_t x)
        {
            //size_t index = x / 32;
            size_t index = x >> 5;//获取索引值
            size_t num = x % 32;//获取索引值内的位置
            if (_a[index] & (1 << num))//某一位是否存在 0代表不存在  1代表存在
            {
                return true;
            }
            return false;
        }
    
    
        void Resize(size_t size)
        {
            _a.resize(size);
        }
    private:
        vector<size_t> _a;
        size_t _size;
    };
    
    #endif //__BITMAP_H__

[wKioL1c1du-CIGvrAABXJBMCxrU651.png]: /images/20220612/73464e8426d84141bf475191e6dede3f.png
[wKiom1c1de7B09ciAABXJBMCxrU543.png]: /images/20220612/4fedc8c2b194460ea8481c1c4d4e2d1a.png