江苏省建设考试信息管理系统网站,腾讯企业邮箱,郑州妇科医院前十强排名,etsy网站文章目录一、位图1.1 位图概念1.2 位图实现1.2.1 把x对应比特位0置11.2.2 把x对应比特位1置01.2.1 查看x对应比特位1.3 位图源码1.4 位图的应用二、哈希切割#xff08;处理海量数据#xff09;三、布隆过滤器3.1 布隆过滤器的概念3.2 布隆过滤器的应用场景3.3 布隆过滤器的实…
文章目录一、位图1.1 位图概念1.2 位图实现1.2.1 把x对应比特位0置11.2.2 把x对应比特位1置01.2.1 查看x对应比特位1.3 位图源码1.4 位图的应用二、哈希切割处理海量数据三、布隆过滤器3.1 布隆过滤器的概念3.2 布隆过滤器的应用场景3.3 布隆过滤器的实现3.3.1 布隆过滤器长度的设置3.3.2 插入操作3.3.3 查找操作3.3.4 误判测试3.3.5 布隆过滤器删除3.4 布隆过滤器的应用一、位图
先看一道例题 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中 首先要知道1G约等于10亿字节那么40亿个整形就是160亿个字节约等于16G。 【遍历或者排序二分】 他们都需要存入数组中但是内存没有空间能够创建16G大小的数组。❌ 【红黑树和哈希】 红黑树不仅要存放数字还得存放指针。❌ 而哈希表也要存放指针和负载因子。❌ 1.1 位图概念 【位图】 数据是否在给定的整形数据中结果是在或者不在刚好是两种状态我只需要判断在还是不在即可。那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。✔ 我们知道无符号整数的范围是0 ~ 2^32 - 1所以我们开一个2^32大小的数组。也就是2^32个比特位因为一个整形是32个比特位所以用位图开出的空间大小为16G/32 0.5G 512M。
接下来我们就可以使用直接定址法是几就在第几个位置把该比特位置为1。
而我们开int类型和char类型都无所谓如果是char就是8个比特位第一个元素就可以表示0 ~ 7第二个元素则表示8 ~ 15。如果是int类型就是32个比特位第一个元素就可以表示0 ~ 31第二个元素则表示32 ~ 63。
当我们要查找一个值x的时候我们需要知道它在第几个元素的第几个比特位上怎么办呢 【char】在第x/8个元素上。在该元素的第x%8个比特位上。 【int】在第x/32个元素上。在该元素的第x%32个比特位上。
1.2 位图实现
这里我们使用vectorchar类型的位图。 那么我们首先就要初始化好把每个比特位都置为0那么vector开多大呢 我们可以使用非类型模板参数template size_t N那么我们就要开N / 8 1大小的空间。 template size_t N
class BitSet
{
public:BitSet(){_bits.resize(N / 8 1, 0);}
private:vectorchar _bits;
};1.2.1 把x对应比特位0置1
我们按照上面说的/8和%8获得具体位置加下来我们需要把这个位置置为1其他位置不变我们可以把1左移然后|运算。 有人可能会如果是int类型就跟大小端有关系其实不管是大端还是小端。 左移是向高位移动 右移是向低位移动 void set(size_t x)
{size_t i x / 8;size_t j x % 8;_bits[i] | (1 j);
}1.2.2 把x对应比特位1置0
我们只能把x对应的比特位变成0其他位置不能变那么我们可以先用上面的方法找到位置然后将1左移然后先取反再运算
void reset(size_t x)
{size_t i x / 8;size_t j x % 8;_bits[i] (~(1 j));
}1.2.1 查看x对应比特位
还是按照上面的方法找到具体位置后把1左移到该位置返回两个的结果。
bool search(int x)
{size_t i x / 8;size_t j x % 8;return _bits[i] (1 j);
}1.3 位图源码
namespace yyh
{template size_t Nclass BitSet{public:BitSet(){_bits.resize(N / 8 1, 0);}void set(size_t x){size_t i x / 8;size_t j x % 8;_bits[i] | (1 j);}void reset(size_t x){size_t i x / 8;size_t j x % 8;_bits[i] (~(1 j));}bool search(int x){size_t i x / 8;size_t j x % 8;return _bits[i] (1 j);}private:std::vectorchar _bits;};
}上面就是为了开辟42亿个比特的大小因为-1的无符号数字就是2^32 - 1当然也可以写成0xffffffff。 验证一下所占内存大小
1.4 位图的应用
【第一题】 给定100亿个整数设计算法找到只出现一次的整数 这里的关键是注意到只出现一次这样我们就可以列出三种状态 1️⃣ 出现0次 2️⃣ 出现1次 3️⃣ 出现1次以上 我们只需要两个比特位就可以表示出三个状态。 上面的位图是用一个位图中的一个比特位标定一个数字出没出现那么这里我们可以用两个位图的两个比特位标定一个数字出现次数。 假如现在是看0这个数字 template size_t N
class TwoBitSet
{
public:void set(size_t x){if (!_b1.search(x) !_b2.search(x))// 00{_b2.set(x);// 01}else if (!_b1.search(x) _b2.search(x))// 01{_b1.set(x);_b2.reset(x);// 10}// 10不变}void PrintOnce(){for (size_t i 0; i N; i){if (!_b1.search(i) _b2.search(i))std::cout i std::endl;}}private:BitSetN _b1;BitSetN _b2;
};【第二题】 给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 思路一 先把一个位图中的数据放入位图中然后遍历另一个文件寻找找出交集。 但是有可能会出现重复元素要注意去重。 思路二 两个文件的元素放进两个位图中放进去的过程就各自去重了然后两个运算即可判断是否有交集。 【第三题】 1 个文件有 100 亿个 int1G内存设计算法找到出现次数不超过2次的所有整数 这个题跟第一题类似可以分为四种状态 1️⃣ 出现0次 2️⃣ 出现1次 3️⃣ 出现2次 4️⃣ 出现3次以上 所以一样可以用两个位图表示四种状态。 【第四题】 给一个超过100G大小的log filelog中存着IP地址设计算法找到出现次数最多的IP地址 这里就不能用位图了因为位图的作用是统计在不在统计次数还得使用map。 我们可以把文件切分成多个小文件这里的切分也是有讲究的如果平均切分在每个小文件统计的话结果不正确因为可能一个IP有多份分在多个文件。而我们map统计完一个小文件就要清空再统计下一个文件不然内存不够用。 所以这里我们需要使用哈希切割。 二、哈希切割处理海量数据
前面我们学过为了实现哈希映射我们需要一个哈希函数这里我们也可以使用哈希函数把IP转为整型。比方说我们分成了100份小文件idx HashFunc(IP) % 100idx是几就把它放进几号文件中。
我们可以把每个小文件理解为一个哈希桶。 这样不一样的IP可能分进同一个小文件中但是同一个IP一定会分进同一个小文件。
这里还可能出现一个情况其中一个小文件的大小可能超过1G假设超过1G就不够了。 而超过了1G也有有两种情况 1️⃣ 不重复的IP很多map需要很多节点统计不下。 2️⃣ 重复的IP很多map不需要很多节点统计的下。 针对第一种情况我们可以换个哈希函数递归切分。 但是这种方法对情况二无效因为相同的IP太多照样会切分超过1G。
所以综合考虑可以这样统计 不管是啥情况都直接用map统计如果是第二种情况就直接统计完成了。如果是第一种情况会insert失败我们可以捕获异常此时再去换个哈希函数递归切分。 三、布隆过滤器
通过上面的讲解我们可以看出 位图的优点是节省空间和效率高 缺点是要求范围相对集中而且只能是整型。
而如果是字符串我们想使用位图就可以使用哈希函数转成整型。 这里就会有一种情况不同的字符串可能转换成同一个整型。 会导致误判。 存在是不准确的如果只有str1和str2而str3映射的位置跟str2重了就会导致原本不在的元素误判成在。 那我们如何降低误判率呢答案是使用布隆过滤器。
3.1 布隆过滤器的概念
它的主要思想是让一个值映射多个位置。我们可以使用多个哈希函数多映射几个位置这里假设有两个哈希函数映射两个位置。 这样我们要看str2是否存在必须要同时指向红色和绿色才能判断为存在。
所以布隆过滤器的作用就是降低误判率。映射的位置越多误判率越低。 但是这里映射的位置也不能太多映射的多占的空间也多找的次数也多我们使用位图这样的方式就是为了提高效率并且节省空间。映射的多了也就没那么节省空间了。
3.2 布隆过滤器的应用场景
【场景一】 当我们要写一个注册系统的时候我们注册昵称的时候不能跟别人重复此时我们就可以采用布隆过滤器如果不在那么就是准确的一定不存在。但是如果显示存在则有可能是误判。因为布隆过滤器中如果存在可能会误判可以到数据库中再次查询昵称号码存不存在。 有人可能问这有必要加一个布隆过滤器吗 假设现在来了100不存在的值大部分都会显示不存在只有很小一部分会误判为存在这样没有误判的大部分效率大大提高。 【场景二】 我们在访问网站的时候有时候会出现风险网站。我们可以把这些网页加入黑名单在我们访问网站之前就先经过布隆过滤器有风险就可以快速的判断。
3.3 布隆过滤器的实现
布隆过滤器最常见的是string类型。 这里要给一个非类型模板参数N以确定开的空间有多大这里我们写三个哈希函数。而字符串转整型的哈希函数有很多 各种字符串Hash函数
这里我们就取里面效率较高的三个
struct BKDRHash
{size_t operator()(const std::string s){size_t value 0;for (auto ch : s){value * 31;value ch;}return value;}
};struct APHash
{size_t operator()(const std::string s){size_t hash 0;for (long i 0; i s.size(); i){if ((i 1) 0){hash ^ ((hash 7) ^ s[i] ^ (hash 3));}else{hash ^ (~((hash 11) ^ s[i] ^ (hash 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const std::string s){size_t hash 5381;for (auto ch : s){hash (hash 5) ch;}return hash;}
};3.3.1 布隆过滤器长度的设置
关于长度的问题这里有专门的文章进行讲述 详解布隆过滤器的原理 里面有一个公式 这里n我们是知道的假设k是3ln2约等于0.7最后得到m4.2*n所以布隆过滤器多一个数据要开大约4.2个比特位我们直接按加入一个数据开5个比特位算。
templatesize_t N,
class K std::string,
class HashFunc1 BKDRHash,
class HashFunc2 APHash,
class HashFunc3 DJBHash
class BloomFilter
{
public:
private:std::bitsetN * 5 _bs;
};3.3.2 插入操作
大致思路跟我们上面的位图一样这里我们使用库里的函数bitset头文件#include bitset而set函数库里面已经帮我们实现好了
void set(const K x)
{size_t idx1 HashFunc1()(x) % (5 * N);size_t idx2 HashFunc2()(x) % (5 * N);size_t idx3 HashFunc3()(x) % (5 * N);_bs.set(idx1);_bs.set(idx2);_bs.set(idx3);
}3.3.3 查找操作
这里只要有一处不在那么就返回false全部都在才能返回true。
bool test(const K x)
{size_t idx1 HashFunc1()(x) % (5 * N);if (!_bs.test(idx1)){return false;}size_t idx2 HashFunc2()(x) % (5 * N);if (!_bs.test(idx2)){return false;}size_t idx3 HashFunc3()(x) % (5 * N);if (!_bs.test(idx3)){return false;}return true;
}3.3.4 误判测试
std::string arr[] { 北京, 武汉, 广州, 上海, 北京, 北京, 广州,上海, 上海 };BloomFilter10 bs;for (auto e : arr){bs.set(e);}for (auto e : arr){std::cout bs.test(e) std::endl;}std::cout std::endl;结果没有问题接下来我们测试误判加上
// 测试误判
srand(time(0));
for (auto e : arr)
{std::cout bs.test(e std::to_string(rand())) std::endl;
}可以看到出现了误判。
3.3.5 布隆过滤器删除
布隆过滤器一般不能支持删除因为一个位置可能被多个值映射删除以后可能把别人的也删掉了。
那么我们能不能强制支持删除呢 我们可以去计数有几个值映射计数器就是几删除了就让当前位置的计数器--。 但是使用计数又会有问题因为不知道计数器的范围所以不能开的太小的比特位导致使用过多内存。 3.4 布隆过滤器的应用
【第一题】 给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和 近似算法。query就是sql语句可以理解为一个字符串。也可能是网络请求url也就是网址 近似算法我们直接使用布隆过滤器将一个文件的query语句放进布隆过滤器里然后另一个文件查找在不在就是交集。虽然有误判不存在的也被当做交集。但是作为近似算法还是可行的。 而精确算法就得用到前面的哈希切割。同时把两个文件都切分成数个小文件在编号相同的小文件查看交集即可最后注意去重。
