• 数据结构之位图【原理与实现】



    前言

    bitmap意为位图,它的每一位用于存放状态,适用于大规模并且不重复的数据,判断某个数据是否存在于位图之中。bitmap在数据稠密的时候,非常节省空间,但是在数据稀疏的时候,会有极大的浪费

    一、位图bitap是什么?

    个int类型占4个字节,也就是32bit,我们用一个int数组来表示时 new int[32],总计占用内存大概32*32bit,如果说我们存放的海量数据,亿万级非常大,那么这些基本数据类型都不够用的,则可以用int字节码的每一位表示一个数字,比如int类型32位,可以存放0-31共32个数值,那么32个数字只需要一个int类型所占内存空间大小就够了,这样在大数据量的情况下会节省很多内存。

    就是通过定义一个整形数值后,将原本只表示1个数值的情况下,扩大了可以存放几十个数及以上的结构,比如我们要存放0-63的数,共64个数,那么我们就定义一个long型变量,有8个字节,64位,二进制就是64位,那么每一位从左到右就可以表示0,1,2…,63,如果有数则可以赋值1 没有则表示0 比如保存1,那么就是第二位赋值1 ,以此类推
    下面我们演示下,传递一个数值,保存到一个long[] arr数组中,简单了解下:
    arr[0]存放的值: 0 - 63
    arr[1]存放的值: 64 - 127
    arr[2]存放的值: 128 - 191
    举例num =4 存放的位置就是 arr[0] 第一个元素 因为 num /64 = 0 ,元素二进制 00…10000 第五位赋值1
    在这里插入图片描述

    二、位图的引用场景

    所以位图bitmap的作用是:
    存放海量数据,节省存储空间有明显优势在这里插入代码片

    1、查询统计、定位查询,排序,去重

    **查询统计:**假设有一个包含1000万个整数的数据集,我们想要知道其中有多少个整数大于等于100。我们可以使用一个位图,位图的长度为100000000(即整数范围),每个位置代表一个整数,如果对应位置的位为1,则表示该整数存在;否则,表示不存在。对于大于等于100的整数,将对应的位置设置为1,其他位置默认为0。最后,通过统计位图中值为1的位的数量,就可以得到大于等于100的整数的数量。

    **定位查询:**假设有一个存储用户标签信息的位图,其中每个位置代表一个标签,如果对应位置的位为1,则表示该用户拥有该标签;否则,表示不拥有。当需要查找拥有指定标签的用户时,只需要检查位图中对应位置的位是否为1即可快速定位到拥有该标签的用户。

    **去重:**假设有一个包含大量重复元素的数据集,我们需要对这些元素进行去重操作。我们可以使用一个位图,将数据集中的每个元素映射到位图的对应位置,如果对应位置的位为0,则表示该元素不存在;否则,表示已经存在。当遍历数据集时,可以根据位图来判断某个元素是否已经存在,从而实现去重操作。

    2、取两个集合的交集,并集等

    取两个集合的交集:
    对两个位图进行按位与运算,得到新的位图,其中被设置为1的位表示两个集合都包含的元素。

    取两个集合的并集:
    对两个位图进行按位或运算,得到新的位图,其中被设置为1的位表示两个集合中任意一个集合包含的元素。

    在这里插入图片描述

    三、位图C++实现

    位图实现的包含以下功能:

    • 构造函数:接受一个范围参数 range,创建一个大小适合存储范围内元素的位图。
    • 析构函数:释放位图占用的内存。
    • 初始化函数:将位图中的所有位都设置为0。
    • 增加函数:将给定的数字 num 添加到位图中。这里假设数字的范围在位图的有效范围内。
    • 删除函数:从位图中删除给定的数字 num
    • 查找函数:在位图中查找给定的数字 num,如果存在则返回 true,否则返回 false

    注意事项:

    • 位图使用一个 unsigned int 数组来存储位的信息,每个 unsigned int 可以存储 32 个位。
    • 位图的大小由范围参数 range 决定,使用 range / 32 + 1 计算出所需的 unsigned int 数组的大小。
    • 数字 num 在位图中的索引位置由 num / 32 计算得到,表示在哪个 unsigned int 数组上。
    • 数字 num 在位图中的具体位索引由 num % 32 计算得到,表示在该 unsigned int 上的哪个位上。
    #pragma once
     
    #include 
     
    class BitMap
    {
    public:
        //构造函数
        BitMap(const size_t & range) {
            assert(range >= 0);
            if (bits != nullptr) {
                delete[] bits;
            }
            count = range;
            size = range / 32 + 1;
            bits = new unsigned int[size];
        }
        //析构函数
        ~BitMap() {
            delete[] bits;
        }
        //初始化数据,把所有数据置0
        void init() {
            for (int i = 0; i < size; i++)
                bits[i] = 0;
        }
        //增加数据到位图
        void add(const size_t & num) {
            assert(count > num);
            int index = num / 32;
            int bit_index = num % 32;
            bits[index] |= 1 << bit_index;
        }
        //删除数据到位图
        void remove(const size_t & num){
            assert(count > num );
            int index = num / 32;
            int bit_index = num % 32;
            bits[index] &= ~(1 << bit_index);
        }
        //查找数据到位图
        bool find(const size_t & num) {
            assert(count > num);
            int index = num / 32;
            int bit_index = num % 32;
            return (bits[index] >> bit_index) & 1;
        }
    //位图相关数据
    private:
        unsigned int* bits=nullptr;
        int size;
        int count;
    };
    
    • 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
  • 相关阅读:
    MinIO图片正常上传不可查看,MinIO通过页面无法设置桶为public
    创建Prism项目
    敲电子木鱼微信小程序源码下载+搭建教程
    改了函数以后,一个数字都不显示了
    Web应用基础
    tensorflow的数据类型
    [联邦学习TFF]构建自己的联邦学习模型
    游戏开发37课 狙击枪 视野问题
    Kafka使用Java管理主题和分区
    【数据分享】全国县市2000-2020年医疗卫生机构床位数数据(excel和shp格式)
  • 原文地址:https://blog.csdn.net/weixin_44545838/article/details/132831134