利用位图(BitMap)查找数据 原创 C++开发 2022年3月31日 17:37 夏至未至 1236 当前内容 1886 字，在路上，马上到，马上到 ### 目录 [TOC] ### 题目要求 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。 ### 题目分析 思路：如果内存够的话，40亿个整型使用位图存储需要500M左右的空间。 分析：位图只适合判断，查找数据是否存在！ 如图  在代码中，使用的是无符号整型数据，32个二进制位，开辟数组时，一个数组元素是一个32位的整型数据，位图的思想，则这32位二进制位就可以表示32位数，原本一个数组元素只能存一个数据，40亿个数，内存将会吃不消，查找也相当困难，位图使得一个数据用一个二进制位表示，一个无符号整型的数组元素就可以表示32个数据，40亿个数据，有位图的方式存，会很节省空间，同时查找效率也会得到提高！ ### 代码实现 #ifndef _BIT_MAP_H #define _BIT_MAP_H #include<iostream> #include<vector> using namespace std; /* *一个数据32位，40亿个整数，每个整数需用一位表示，40亿位就完事 */ class BitMap { public: BitMap() :_size(0) {} BitMap(size_t size) :_size(0) { _array.resize((size>>5)+1); //多少个数据，一个数据占32位，加一是至少一个数据 } bool Set(size_t num) { size_t index = num >> 5; //计算在哪个数据上 size_t n = num % 32; if (_array[index] & (1 << (31 - n))) //移位问题 { cout << "有数据" << endl; return false; } else { size_t a = 1 << (31 - n); _array[index] |= a; ++_size; return true; } } bool ReSet(size_t num) //删除一个数 之后重置 { size_t index = num >> 5; size_t n = num % 32; if (_array[index] & (1 << (31 - n))) //数存在 删除 { _array[index] &= (~(1 << (31 - n))); --_size; return true; } else { return false; //不存在这个数 } } private: vector<size_t> _array; //数组 size_t _size; //位图中数据个数 }; #endif void Test() { BitMap bm(65); for (int i = 0; i < 32; ++i) { bm.Set(i); } bm.ReSet(0); } 本文标题： 利用位图(BitMap)查找数据 本文作者： 夏至未至 发布时间： 2022年3月31日 17:37 最近更新： 2022年3月31日 17:37 原文链接： 许可协议： 署名-非商业性-禁止演绎 4.0 国际(CC BY-NC-ND 4.0) 请按协议转载并保留原文链接及作者 布隆过滤器(2) 位图(1) 上一个 变长数组-变量也可做特殊数组的长度 下一个 Linux下线程间同步-条件变量 当前文章评论暂未开放,请移步至留言处留言。
