茂名网站建设系统,公司logo制作,海南响应式网页建设找哪家,在线制作带字图片哈希的应用
一、位图
情景#xff1a;给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这40亿个数中#xff1f;#xff1f;#xff1f;
看到查找元素的范围#xff0c;暴力肯定是过不了的#xff0c;我们要么…哈希的应用
一、位图
情景给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中
看到查找元素的范围暴力肯定是过不了的我们要么二分要么哈希但是二分要求排序题目说没排过序只剩下哈希但是如果用正常的哈希表肯定不行数据量太大了(可以算一下大概15G)根本加载不进内存更别谈放到哈希表中了那怎么办
这时候就需要用到位图---本质就是状态压缩版的哈希表用一个比特位表示一个数字大大压缩了数据量(整形是4字节如果是哈希表只能用来表示一个数字但是位图可以用来表示4*832个数)数据量缩小了32倍大概0.5G具体的实现如下
namespace zxws
{template size_t N100class bitset{public:bitset(){bit.resize(N/321);}void set(size_t x)//增{size_t i x / 32;size_t j x % 32;bit[i] | (1u j);//1u代表unsigned int类型的1}void reset(size_t x)//删{size_t i x / 32;size_t j x % 32;bit[i] ~(1u j);}bool test(size_t x)//查{size_t i x / 32;size_t j x % 32;return (bit[i] j) 1u;}private:vectorintbit;};
}
模拟实现没啥难度就是要了解位运算当然这只是位图的最重要的几个函数还有一些其他的不常用的就不模拟实现了有兴趣大家可以去查看文档 那么了解了位图的实现原理我们再来看看下面的几个题 1. 给定100亿个整数设计算法找到只出现一次的整数 2. 给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 3. 位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数 题1正常用一个位图不好做因为一个数字对应一个比特位而一个比特位只有0 / 1两个状态无法表示没出现出现1次和出现多次这3个状态那怎么办既然一个比特位无法表示那两个比特位呢共有00011011四个状态绰绰有余实现如下 namespace zxws
{template size_t N 100class twobitset{public:void set(size_t x){size_t i x / 32;size_t j x % 32;if (bs1.test(x) false bs2.test(x) false)//00-01{bs1.set(x);}else if (bs1.test(x) true bs2.test(x) false)//01-10{bs1.reset(x);bs2.set(x);}}void test(size_t x){return bs1.test(x) true bs2.test(x) false;//01--代表只出现一次}private:bitsetNbs1;bitsetNbs2;};
} 题2找文件交集这个就很明显了两个位图分别存放两个文件中的数字然后比特位之间一下比特位上为1的就是交集 题3这题其实和第1题一样都是查看数字出现次数要求不出现两次即有没出现出现1次出现2次和出现2次以上四个状态两个位图正好够了实现同题1 二、布隆过滤器 布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间 实现原理图 一般来说用三个哈希函数就差不多了 上图是网上的研究数据显示结果仅供参考(kmn满足上诉关系时不容易发生哈希冲突) 布隆过滤器的作用范围还是很广泛的尤其是在不怎么关心某一个东西是否真的存在的场景下举个例子比如说取用户ID当你取的id没人用时OK你创建成功当你取的id显示有人用时如果是真的有人用了那我们就换一个如果没人用它误判了那我们也就是不能用这个id而已没有啥太大影响这时布隆过滤器就非常合适 当然如果说用户投诉说明明没人用这个id却不让用要求我们修复bug这时我们只要让在布隆过滤器过滤后显示为存在的数据再去数据库中校验一下即可 当然也有人会觉得反正都要去数据库校验还要布隆过滤器干嘛注意1.布隆过滤器它为啥叫过滤器关键就是它只能确定不存在的数据不能确定存在的数据。2.网络上通讯会比较耗时如果每一个id的确认都需要与服务器上的数据库校验就会浪费时间 实现如下 //哈希函数就自行去网上找哪些不容易产生哈希冲突的就行
template size_t N, class Kstring, class HashFunc1HashFunK, class HashFunc2DGBHashK, class HashFunc3APHashK
class BloomFiler {
public:void set(const K key){size_t hash1 HashFunc1()(key) % N;size_t hash2 HashFunc2()(key) % N;size_t hash3 HashFunc3()(key) % N;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(const K key){size_t hash1 HashFunc1()(key) % N;size_t hash2 HashFunc2()(key) % N;size_t hash3 HashFunc3()(key) % N;if (_bs.test(hash1) false|| _bs.test(hash2) false|| _bs.test(hash3) false)return false;return true;}
private:bitsetN*5_bs;
}; 两个问题 1. 给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法(具体下面一个专题讲) 2. 如何扩展BloomFilter使得它支持删除元素的操作一般来说是不能支持的因为删除一个元素的映射会影响其他元素的哈希映射(因为它们会出现冲突)但是我们可以给它们加一个引用计数这样就能在删除它的同时不影响其他元素的映射 优点 1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关 2. 哈希函数相互之间没有关系方便硬件并行运算 3. 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 4. 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势 5. 数据量很大时布隆过滤器可以表示全集其他数据结构不能 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 三、哈希分割---哈希思想的扩展 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址如何找到top K的IP 100G的file很显然太大我们的想法是将它分割成一个个小文件然后在小文件中计数我们将文件按Hash(id) % 100得到100个1G的小文件(理想情况)然后我们就可以在小文件中统计每个id出现的次数(因为同一个id经过哈希映射会在同一个小文件中)但是上面的只是理想情况如果某一个小文件的大小为10G也就是分完之后还是太大了我们又该怎么办 出现上诉情况共分两种可能 1.相同的id太多2.哈希冲突太多导致多个不同的id都放在了同一个小文件中 如果是情况一我们不用管map中只会插入一次这个id空间足够 如果是情况二会报内存错误这时我们就对这个小文件进行二次哈希分割即可 top K问题用堆实现就行之前再二叉树数据结构中讲过的 下面我们回过头去看看 给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法 近似算法就是用布隆过滤器但是精确的算法呢 这个query的大小也要考虑到假设query的大小为50字节那么一共5000亿字节约等于500G很明显了哈希切割当然我们得先将query转成整数Hash(query)%500两个文件各自分成500个1G的小文件(理想情况)这样两个文件中相同的query会分别放在同一个余数的两个小文件中如下图 当然它也会出现小文件太大的情况处理方法同上注意这个不能用位图的原因是query里面存的不一定是整数这样不同的query查询也有可能映射到用一个比特位(这也是布隆过滤器不准确的原因之一)就不精确了 如果上诉内容对你理解哈希有帮助的话不要忘记点赞评论哟
