哪里做网站需求,农药放行单在哪个网站做,移动电商网站开发需求文档,购物商城有哪些目录
一、位图
1、位图的概念
2、位图的实现 ①、基本结构
②、set
③、reset#xff1a;
④、test
⑤、问题#xff1a;
⑥、位图优缺点及应用#xff1a;
⑦、完整代码及测试
二、布隆过滤器
1、布隆过滤器的提出
2、布隆过滤器的实现
①、基本结构
②…
目录
一、位图
1、位图的概念
2、位图的实现 ①、基本结构
②、set
③、reset
④、test
⑤、问题
⑥、位图优缺点及应用
⑦、完整代码及测试
二、布隆过滤器
1、布隆过滤器的提出
2、布隆过滤器的实现
①、基本结构
②、三个Hash仿函数实现
③、 set
④、 test
⑤、 删除 ⑥、完整代码及测试
⑦、 优缺点 一、位图
1、位图的概念 1. 面试题 给 40 亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在 这 40 亿个数中。【腾讯】 查找一个数在不在其实就是key模型那常见的几种解法如下 1. 遍历时间复杂度O(N) 2. 排序(O(NlogN))利用二分查找: logN 3. 位图解决 前两个方案的问题数据量太大放不到内存中。 我们可以先考虑40亿个不重复的无符号整数占多少空间 10亿个字节是1个G而40亿个整数一个整数4个字节即需要160亿9个0个字节即需要16G这些数据太占空间了内存根本存不下。 位图是如何解决的呢 所谓位图就是用每一bit位来存放某种状态适用于海量数据数据无重复的场景。通常是用 来判断某个数据存不存在的。数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一 个二进制比特位来代表数据是否存在的信息如果二进制比特位为 1 代表存在为0 代表不存在。位图是直接定址法的一种 而40亿个数据我们起码要开42亿个空间为什么假如有一个数是4200000000你要映射到哪个位置我们开空间是要开数据的范围才能满足全部映射进去。 那我们直接开2^32个空间这里说的每个位置就是比特位2^32≈42亿9千万因为位图就是每个位置存的bit位来对所有数直接定址法建立映射关系即我们开辟42亿9千万个bit位先把42亿9千万看成字节则其≈4G而4G≈4000M或者MB而这里是比特位故要除以84000/8500M故位图存储占用500M即可这既节省了空间效率又很高效率高因为直接定址法没哈希冲突 2、位图的实现 ①、基本结构 位图的初始化应该是开多少个比特位因为位图就是利用存比特位来节省的空间你传的N也是比特位其次是vector的类型是int因为类型不支持是比特位的 class bitset
{
public:bitset(size_t N){//N代表要开多少比特位简称位_bits.resize(N / 32 1, 0);_num N;}private://int* _bits;std::vectorint _bits;size_t _num; //表示存了多少个比特位映射存储的多少个数据
};
_bits.resize(N / 32 1, 0); 为什么要N / 32 1 呢 因为vector的resize开空间是以整形为单位的而位图的每个位置存的都是一个比特位而一个整形32个比特位N代表的是比特位的位数则N/32得到的是整形的个数但是还需1为什么比如N100100/323那意思就是开3个整形即32*396个位但是100还是没位置放你就开了96个位同理97,98...都没位置为了避免这个问题我们会1即多开一个整形那最多只会浪费31个位 ②、set 功能把第x个位设置为1表示这个位存在 void set(size_t x)
{//把第x位设置为1表示此位置存在size_t index x / 32; //算出映射的位置在第几个整数size_t pos x % 32; //算出x在整数的第几个位_bits[index] | (1 pos); //对于这个整数第pos的位置或1//1pos表示先把1移动到和pos相同位置的比特位上因为pos几1就会左移几位//|表示是或即除了pos位置的位要变成1其余位置都不受影响
} 其实就是考察怎么把一个整数的某个位变成1还不影响其他的31位 小端机的左移是向左 大端机的左移是向右 这是c语言设计的bug历史遗留问题易让人误导计算机技术发展百花齐放再融合统一 ③、reset 功能把第x个位置成0表示这个位不存在 void reset(size_t x)
{//把第x位设置为0表示此位置不存在size_t index x / 32; //算出映射的位置在第几个整数size_t pos x % 32; //算出x在整数的第几个位_bits[index] ~(1 pos); //对于这个整数第pos的位置与0
} ④、test 功能判断第x位在不在即判断x所映射的位是否为1 //判断x在不在也就是说x映射的位是否为1
bool test(size_t x)
{size_t index x / 32; //算出映射的位置在第几个整数size_t pos x % 32; //算出x在整数的第几个位return _bits[index] (1 pos); //结果非0为真0则为假
} ⑤、问题 理论上这40亿个数不可能存在内存当中应该存在文件中那我们就要去读文件40亿个数因为要按范围开故要开42亿9千万的空间怎么开这么大的空间常见方法如下 ①、bitset bs(-1); //因为位图的构造函数参数是size_t那-1若看为无符号数就是整形的最大值 ②、bitset bs(0xffffffff); ⑥、位图优缺点及应用 优点节省空间、效率高 缺点只能处理整形 应用 快速查找某个数据是否在一个集合中 排序 去重 求两个集合的交集、并集等 操作系统中磁盘块标记 ⑦、完整代码及测试
#pragma once
#includeiostream
#includevectornamespace mz
{class bitset{public:bitset(size_t N){//N代表要开多少比特位简称位_bits.resize(N / 32 1, 0);_num N;}void set(size_t x){//把第x位设置为1表示此位置存在size_t index x / 32; //算出映射的位置在第几个整数size_t pos x % 32; //算出x在整数的第几个位_bits[index] | (1 pos); //对于这个整数第pos的位置或1//1pos表示先把1移动到和pos相同位置的比特位上因为pos几1就会左移几位//|表示是或即除了pos位置的位要变成1_num;}void reset(size_t x){//把第x位设置为0表示此位置不存在size_t index x / 32; //算出映射的位置在第几个整数size_t pos x % 32; //算出x在整数的第几个位_bits[index] ~(1 pos); //对于这个整数第pos的位置与0--_num;}//判断x在不在也就是说x映射的位是否为1bool test(size_t x){size_t index x / 32; //算出映射的位置在第几个整数size_t pos x % 32; //算出x在整数的第几个位return _bits[index] (1 pos); //结果非0为真0则为假}private://int* _bits;std::vectorint _bits;size_t _num; //表示存了多少个比特位映射存储的多少个数据};void test_bitset(){bitset bs(100);bs.set(99);bs.set(98);bs.set(97);bs.reset(98);for (size_t i 0; i 100; i){printf([%d]:%d\n, i, bs.test(i));}}}
部分测试结果如下 二、布隆过滤器
1、布隆过滤器的提出 我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉 那些已经看过的内容。问题来了新闻客户端推荐系统如何实现推送去重的 用服务器记录了用 户看过的所有历史记录当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选过滤掉那 些已经存在的记录。 如何快速查找呢 1. 用哈希表存储用户记录缺点浪费空间 2. 用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理了3. 将哈希与位图结合即布隆过滤器 布隆过滤器是 由布隆 Burton Howard Bloom 在 1970 年提出的 一种紧凑型的、比较巧妙的 概 率型数据结构 特点是 高效地插入和查询可以用来告诉你 “ 某样东西一定不存在或者可能存 在 ” 它是用多个哈希函数将一个数据映射到位图结构中。此种方式 不仅可以提升查询效率也 可以节省大量的内存空间 。 2、布隆过滤器的实现
①、基本结构 一般布隆过滤器存的是字符串或结构体等一般不会是整形因为整形就用位图来存了 布隆过滤器底层就是用位图实现的因为字符串比较常用故我们直接把字符串作为默认模板参数其他三个Hash模板参数表示的是用三个位置来映射一个值 构造函数开多少个空间 有大佬已经计算过了10个元素就需要长度为43位那我们干脆初始开个5倍 templateclass K string, class Hash1 HashStr1, class Hash2 HashStr2, class Hash3 HashStr3
class bloomfilter
{
public://直接上来开满会有问题因为可能我本身可能就没映射几个值//那就根据你大概会存多少个数据来对应开空间//到底开多少比较好有人算过即你存多少个值就要映射到多少个位bloomfilter(size_t num):_bs(5 * num),_N(5 * num){}private:bitset _bs; //底层是一个位图size_t _N;
}; ②、三个Hash仿函数实现 因为要用三个映射位置来映射一个值故要写三个字符串转为整形的函数而又因为string类型比较常用这三个仿函数会作为默认模板参数 下面是能降低哈希冲突的字符串算法我们下面三个仿函数就选用下面三个算法 struct HashStr1
{size_t operator()(const string str){ //运用BKDRHashsize_t hash 0;for (size_t i 0; i str.size(); i){hash * 131;hash str[i];}return hash;}
};struct HashStr2
{size_t operator()(const string str){ //运用RSHashsize_t hash 0;size_t magic 63689; //魔数for (size_t i 0; i str.size(); i){hash * magic;hash str[i];magic * 378551;}return hash;}
};struct HashStr3
{size_t operator()(const string str){ //运用SDBMHashsize_t hash 0;for (size_t i 0; i str.size(); i){hash * 65599;hash str[i];}return hash;}
}; ③、 set 函数是想把key这个数标志为存在而我们说了要用三个位置来映射这个key值则调用Hash仿函数先计算出字符串的映射位置%_N是因为我们刚开始给位图就开了_N个比特位你算出的映射位置很可能大于_N故都%_N既能存储也能统一则一个key值就能用三个映射位置来表示了 注Hash1是仿函数类型Hash1()是仿函数对象当然你也可以写为Hash1 hs1; hs1(key) % _N;但是明显更麻烦 void set(const K key)
{size_t index1 Hash1()(key) % _N;//利用Hash1类型的匿名对象size_t index2 Hash2()(key) % _N;size_t index3 Hash3()(key) % _N;_bs.set(index1);//表示index1这个位置存在_bs.set(index2);_bs.set(index3);
} ④、 test 功能判断key值存不存在 因为一个值用了三个映射位置故我们判断计算出key的三个映射位置在位图中是否同时存在同时存在key值才存在反之有一个不存在就肯定不存在 bool test(const K key)
{size_t index1 Hash1()(key) % _N;if (_bs.test(index1) false)return false;size_t index2 Hash2()(key) % _N;if (_bs.test(index2) false)return false;size_t index3 Hash3()(key) % _N;if (_bs.test(index3) false)return false;return true; //但这里也不一定是真的在还是可能存在误判//判断在是不准确的可能存在误判//判断不在是准确的
} ⑤、 删除 布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给 k个计 数器 (k 个哈希函数计算出的哈希地址 ) 加一删除元素时给 k个计数器减一通过多占用几倍存储 空间的代价来增加删除操作。 缺陷 1. 无法确认元素是否真正在布隆过滤器中 2. 存在计数回绕 void reset(const K key)
{//将映射的位置给置0就可以//不支持删除可能会存在误删故布隆过滤器一般不支持删除
} ⑥、完整代码及测试
#pragma once
#includebitset.h
#includestringusing std::string;
using std::cout;
using std::endl;namespace mz
{struct HashStr1{size_t operator()(const string str){ //运用BKDRHashsize_t hash 0;for (size_t i 0; i str.size(); i){hash * 131;hash str[i];}return hash;}};struct HashStr2{size_t operator()(const string str){ //运用RSHashsize_t hash 0;size_t magic 63689; //魔数for (size_t i 0; i str.size(); i){hash * magic;hash str[i];magic * 378551;}return hash;}};struct HashStr3{size_t operator()(const string str){ //运用SDBMHashsize_t hash 0;for (size_t i 0; i str.size(); i){hash * 65599;hash str[i];}return hash;}};templateclass K string, class Hash1 HashStr1, class Hash2 HashStr2, class Hash3 HashStr3class bloomfilter{public://直接上来开满会有问题因为可能我本身可能就没映射几个值//那就根据你大概会存多少个数据来对应开空间//到底开多少比较好有人算过即你存多少个值就要映射到多少个位bloomfilter(size_t num):_bs(5 * num),_N(5 * num){}void set(const K key){size_t index1 Hash1()(key) % _N;//利用Hash1类型的匿名对象size_t index2 Hash2()(key) % _N;size_t index3 Hash3()(key) % _N;_bs.set(index1);_bs.set(index2);_bs.set(index3);}bool test(const K key){size_t index1 Hash1()(key) % _N;if (_bs.test(index1) false)return false;size_t index2 Hash2()(key) % _N;if (_bs.test(index2) false)return false;size_t index3 Hash3()(key) % _N;if (_bs.test(index3) false)return false;return true; //但这里也不一定是真的在还是可能存在误判//判断在是不准确的可能存在误判//判断不在是准确的}void reset(const K key){//将映射的位置给置0就可以//不支持删除可能会存在误删故布隆过滤器一般不支持删除}private:bitset _bs; //底层是一个位图size_t _N;};void test_bloomfilter(){bloomfilterstring bf(100); //这里不给string直接用也行因为string是默认的bf.set(abcd);bf.set(aadd);bf.set(bcad);cout bf.test(abcd) endl;cout bf.test(aadd) endl;cout bf.test(bcad) endl;cout bf.test(cbad) endl;}
} ⑦、 优缺点 布隆过滤器优点 1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无 关 2. 哈希函数相互之间没有关系方便硬件并行运算 3. 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 4. 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势 5. 数据量很大时布隆过滤器可以表示全集其他数据结构不能 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 布隆过滤器缺陷 1. 有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再 建立一个白名单存储可能会误判的数据) 2. 不能获取元素本身 3. 一般情况下不能从布隆过滤器中删除元素 4. 如果采用计数方式删除可能会存在计数回绕问题
