当前位置：首页 > article >正文

数据结构——位图

article 2025/3/1 11:24:10

位图概念

位图可以用来快速判断某个数在不在，它的本质也是一种哈希结构，不过位图更节省空间。位图是用比特位来存储数据的。

我们知道一个整形有32个比特位，我们可以用1个整形存储32个数据，如果我们要查找15这个数在不在，只用判定这个整形的第15个比特位是0还是1，是0，说明不在，是1说明在，如果我们要插入17，只用把这个整形的第17个比特位置设置为1即可。

因为C++没有一个比特的数据类型，因此这个地方我们用char或者int都是可以的，区别在于不同类型存储的比特位个数不同，这个地方我们就用整形了。

那如果我们要插入一个数是99呢？一个整形只有32个比特位呀，那我们搞一个整形数组即可。我们可以用99 / 32计算这个数在数组的哪一个下标，然后用99 % 32计算在该下标所对应整形的第几个比特位。99/32=3，因此对应下标为3的整形，99%32=3，因此映射到了该整形的第3个比特位。

位图

位图的底层我们可以直接用一个vector数组来实现，位图也是一种哈希，因此我们要提前给位图开好空间。并且位图是不可以动态扩容的，需要我们一次就把空间开好，当然也可以动态扩容，但是扩容之后可能会导致索引发生变化，还是很麻烦的，因此最后直接一次开好就行。

// 非类型模版参数
template <size_t N>
class bitset
{
public:
    // 构造函数
    bitset()
    {
        _bits.resize(N / 32 + 1, 0);
    }
 
private:
    vector<int> _bits; // 位图;
};

我们可以通过模版参数的方式来给位图开空间，模版参数传递这个位图需要存储的最大值，因为1个整形可以存32个数，因此我们实际上并不需要开N个空间，只需要N / 32 + 1个空间即可，因为有可能N不是32的倍数除不尽，因此要多开一个空间给那些余数。

设置位（插入）

当要插入一个数的时候，只需要计算出该位所在的整形以及所在的比特位，计算所在的整形直接 / 32即可，计算在哪个比特位 % 32即可，然后把该位设置为1即可。

    // 设置位
    void set(size_t x)
    {
        // 计算出在第i个整形的第j位
        int i = x / 32;
        int j = x % 32;
        _bit[i] |= (1 << j); // 将该位设置为1，不影响其它位
    }

清除位（删除）

当要把一个数从位图删除，同样计算出在哪个整形哪个比特位，然后将该位置0即可

    // 清除位
    void reset(size_t x)
    {
        // 计算出在第i个整形的第j位
        int i = x / 32;
        int j = x % 32;
        _bit[i] &= (~(1 << j)); // 将该位设置为0，不影响其它位
    }

获取位是0还是1（查找）

    // 获取位的状态
    bool test(size_t pos)
    {
        int i = pos / 32;
        int j = pos % 32;
        if(_bits[i] & (1 << j)) // 该位被设置
            return true;
        else
            return false;
    }

但是现在有一个问题，位图的确可以解决一个数存在不存在，但如果我这个数是负数呢？如果一个数是负数我们其实可以通过映射等方法将其转成一个整数在进行映射，但是用到的不多。

但是如果我们要快速查询一个字符串在不在呢？现在的位图是解决不了的，这就需要引入下一个数据结构叫做布隆过滤器，布隆过滤器可以快速判断字符串在不在，并且也是采用位图的形式。

查看全文

http://www.kler.cn/a/565863.html