C++ 哈希思想应用 位图 布隆过滤器 海量数据处理 |
您所在的位置：网站首页 › o里面有个c的符号 › C++ 哈希思想应用 位图 布隆过滤器 海量数据处理 |
|
文章目录
问题引入位图（附C++模拟实现源码）布隆过滤器（附C++模拟实现源码）
问题引入
问题： 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。 问题分析： 时间复杂度角度： 直接遍历，时间复杂度O(N)；以文件为单位进行归并排序(O(NlogN))+二分查找O(logN);利用位图解决，时间复杂度0(1); 空间复杂度角度：如果利用 unordered_set 去建立哈希映射关系，在空间上是不够的 40亿个数如果使用开散列为底层， 那么仅仅是计算所开 结点 的内存大小就为 (16 * 40亿)byte，换算一下约为72GB ，非常不合理。利用位图解决 位图（附C++模拟实现源码）什么是位图？ 位图，就是用每一bit位来存放某种状态，为1，代表存在，为0 代表不存在适，用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。利用位图处理该问题的思路就是压缩内存成本，是利用哈希思想建立映射的方案可行 位图能解决该问题的大概计算 只粗略计算主干：1 byte 可建立8个数的映射关系(闭散列)，那么40亿个数需要 40亿 / (1024 * 1024* 1024 * 8 ) 约等于0.5GB内存。 位图应用总结 快速查找某个数据是否在一个集合中排序 + 去重求两个集合的交集、并集等操作系统中磁盘块标记（暂时不了解）位图的模拟实现 注意点： 1.运算符优先级 2.运算逻辑的控制 在.h文件中： #pragma once #include #include #include using namespace std; namespace myBitSet { // 非类型模板参数特化的应用 N的含义为N个bit位的位图 template class bitset { private: //成员变量 std::vector _bits; public: bitset() { // 一个char占8个比特位 _bits.resize(N / 8 + 1, 0); } //大概理解为建立映射的功能 void set(size_t x) { // x 映射的比特位在第几个char对象 size_t i = x / 8; // x 在char的第几个比特位 size_t j = x % 8; //# 表示可能位0也可能为1 // 举例j = 3 // 原第i个char： ######## // (1 size_t i = x / 8; size_t j = x % 8; return _bits[i] & (1 size_t operator()(const string& s) { // BKDR size_t value = 0; for (auto ch : s) { value *= 31; value += ch; } return value; } }; struct APHash { size_t operator()(const string& s) { size_t hash = 0; for (long i = 0; i hash ^= ((hash 3)); } else { hash ^= (~((hash 5))); } } return hash; } }; struct DJBHash { size_t operator()(const string& s) { size_t hash = 5381; for (auto ch : s) { hash += (hash size_t hash = 1315423911; for (auto ch : s) { hash ^= ((hash 2)); } return hash; } }; template class BloomFilter // 关键字: Bloom 布隆过滤器 { private: //成员变量 bitset _bs; public: void Set(const K& key) { //如果这样写则会被认为是强制类型转换，类名() 是调用该类构造函数的格式 //size_t hash1 = HashFunc1(key) % M; //所以HashFunc1()是有个匿名对象的 size_t hash1 = HashFunc1()(key) % M; size_t hash2 = HashFunc2()(key) % M; size_t hash3 = HashFunc3()(key) % M; size_t hash4 = HashFunc4()(key) % M; _bs.set(hash1); _bs.set(hash2); _bs.set(hash3); /*_bs.set(hash4);*/ } bool Test(const K& key) { //这样逐个判断，只要有一个不符合就立马返回结果符合效率最高 size_t hash1 = HashFunc1()(key) % M; if (_bs.test(hash1) == false) { return false; } size_t hash2 = HashFunc2()(key) % M; if (_bs.test(hash2) == false) { return false; } size_t hash3 = HashFunc3()(key) % M; if (_bs.test(hash3) == false) { return false; } size_t hash4 = HashFunc4()(key) % M; if (_bs.test(hash4) == false) { return false; } return true; //如果判断为false，即不存在，结果是100%正确的 //结果为 true 存在误判的可能性 } //布隆过滤器不存在该选项，因为可能误删其他存在的映射关系 bool Reset(const K& key); void test_can_do() { BloomFilter bf; string a[] = { "苹果", "香蕉", "西瓜", "111111111", "eeeeeffff", "草莓", "休息", "继续", "查找", "set" }; for (auto& e : a) { bf.Set(e); } for (auto& e : a) { cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |