微信红包建设网站,百姓网二手车个人,广州竞价托管,百度网络推广一、哈希的应用#xff08;位图和布隆过滤器#xff09;
1、位图#xff08;bitset#xff09;
#xff08;1#xff09;位图概念
【题目】 给 40亿 个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这 40亿 个数中。…一、哈希的应用位图和布隆过滤器
1、位图bitset
1位图概念
【题目】 给 40亿 个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这 40亿 个数中。 遍历 40亿 个数时间复杂度为O(N)。先排序快排O(NlogN)再利用二分查找O(logN)。将 40亿 个数放进 set / unordered_set 中然后再查找 key 在不在。位图解决。 前面三种解法看似可行实际上有很大的问题内存消耗太大。 40亿 个整数要占用多少空间大约是 16GB。 1GB 1024 * 1024 * 1024 210 * 210 * 210 230 大约是 10 亿 byte4GB 4 * 230 232 byte大约是42亿9九千多万byte40亿 个 unsigned int 整数 40亿 * 4字节 160亿字节 16 * 10亿字节 ≈ 16GB a这 40亿 个数据是放在文件中的要对这 40亿 个整数进行排序 难道在内存中开一个 16GB 空间的数组存放这些数据吗显然不太现实内存消耗太大了。 b虽然归并排序可以对文件中的数据做外排序但是效率很低磁盘读写速度是很慢的即使在文件中对 40亿 个数据排完了序但是很难去算出数据的下标位置不能进行二分查找那意义也不大。 c把数据放进 set / unordered_set 中因为其底层是链式结构除了存数据还要存指针所以附带的内存消耗更大需要的空间比 16GB 还要大很多更不可行。 所以我们一定要从节省内存的角度出发去思考才能更好的解决问题。同时题目要求是快速判断。 这里是判断一个数在不在数据集中仔细想一想也并不需要把这个数存起来只需要有个标记去 标记某个数在不在就行了。就好比统计数组中数字的出现次数我们用数的数值作为下标在该下标处存储出现的次数也并没有把数存下来。标记一个数在不在最小的标记单位是比特位0 / 1我们用一个比特位标记一个数这样就节省空间了。 这里我们将采用第四种解法位图。
某个数是否在给定的数据集中有两种结果存在 / 不存在刚好是两种状态那么可以使用一个二进制比特位来代表某个数是否存在的信息比如二进制比特位为 1 代表存在为 0 代表不存在。
我们把数据集的所有数用直接定址法映射到一张二进制表中并用二进制值1 / 0标记其是否存在这样每个数都有唯一的映射位置不会出现哈希冲突。如果要判断某个数在不在数据集中时只需要找到这个数映射到表中的位置然后查看该位置的比特位为 1 还是 0。 我们是用每个无符号整数 unsigned int 的值来映射其哈希位置比如 25就映射到第 25 个二进制位 因为 unsigned int 的 取值范围 是 0 ~ 2³²-1所以一个无符号整数最小值为 0最大值为 2³² - 14,294,967,29542亿9千多万。所以我们要开有 232 个二进制位的表才能映射完所有的无符号整数但实际上只能开到有 2³²-1 个二进制位的表因为 size_t 最大为 0xffffffff也就是开 ( 2³²-1 ) / 8 个字节 ≈ 5亿多个字节 ≈ 0.5GB 512MB 的内存空间。 一个 bit 位标记一个 unsigned int 值512GB 的内存就可以标记完 42亿9千多万个整数的存在状态了极大的节省了内存。 注意位图并没有把整个数据集存储起来而是将所有数映射到哈希表中在映射的哈希位置上标记这个数在不在。 【位图概念】
面对判断一个数在不在海量数据中的问题红黑树和哈希表查找效率是挺高的但是我们光把海量数据存起来够呛同时红黑树和哈希表附带的内存消耗所需空间更大基于这样的原因提出了位图这种数据结构。 所谓位图bitset就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。在索引、数据压缩方面有很大的应用。 template size_t N class bitset;
位图是用数组实现的数组的每一个元素的每一个二进制位都表示一个数据0 表示该数据不存在1 表示该数据存在。
位图最大的特点就是快、节省空间因为它不需要存储数据集只是标记某个数在不在这个数据集中。 2位图的实现
a. 位图的底层结构
如图我们开一个数组数组的每个元素是一个 char8个 bit 位。如果是一个 int 32 个 bit 位也可以只是计算数据映射的比特位的方法略有差别。
这里的 0 ~ 7 是比特位的编号从右到左依次编号。 问如何计算这个数据映射在数组中第几个 char(字节) 中的第几个比特位上 字节位置 数据 / 8得出 x 映射在第几个 char 中。位位置 数据 % 8得出 x 映射在这个 char 中的第几个比特位上。注意如果数组的每个元素是一个 int改成除以 32 就好了。 比如数据 x 10则 字节位置 10 / 8 1说明 10 映射在第 1 个 char字节中。位位置 10 % 8 2说明 10 映射在第 1 个 char字节中的第 2 个比特位上。 // 位图的结构
namespace xyl
{templatesize_t N // N: 非类型模板参数表示至少需要开N个比特位的存储空间class bitset{public:// 构造有N个比特位的位图等价于要开N/8个字节(char)的空间// 为了防止N不是8的整数倍所以要1多开1个字节(char)的空间bitset() { _bits.resize(N / 8 1, 0); }// 把数据x映射的比特位设置成1表示数据x存在void set(size_t x);// 把数据x映射的比特位设置成0表示数据x不存在void reset(size_t x);// 检测数据x映射的比特位是否为1即数据x是否存在bool test(size_t x) const;private:vectorchar _bits; // 位数组};
} b. 位图的一些成员函数
① 位图的构造
默认构造函数 构造至少有 N 个比特位的位图等价于开 N / 8个字节char的空间 为了防止 N 不是 8 的整数倍所以要 1多开1个字节char的空间 bitset()
{_bits.resize(N / 8 1, 0);
} ② 位图的插入set
set 函数修改数据映射的比特位位置。位位置从最右边的位开始计数即从 0 位置开始计数。
// 把数据 x 映射的比特位设置成1表示数据x存在
void set(size_t x)
{// 计算出这个数据映射在数组中第几个char(字节)中的第几个比特位上size_t i x / 8; // 计算出x映射在第i个char(字节)中size_t j x % 8; // 计算出x映射在第i个char(字节)中的第j个比特位上// 把数组中第i个char的第j位设置成1其它位不受影响_bits[i] | (1 j);
}// 分析
// 比如: 数据5映射在第0个char的第5个比特位
// 现在要用set函数把数据5映射的第0个char的第5个比特位设置成1
0000 1111 - _bits[0] // 第0个char
0010 0000 - 1 5 // 将1左移5位// 将1左移5位后的结果按位或上 _bits[0]0010 0000 - 1 5
| 0000 1111 - _bits[0]
-----------------------0010 1111 - _bits[0] // 此时第0个char的第5个比特位已经被设置成1了 ③ 位图的删除reset
reset 函数修改数据映射的比特位位置。位位置从最右边的位开始计数即从 0 位置开始计数。
// 把数据x映射的比特位设置成0表示数据x不存在
void reset(size_t x)
{size_t i x / 8; // 映射在第i个char中size_t j x % 8; // 映射在第i个char中的第j个比特位上// 把数组中第i个char的第j位设置成0其它位不受影响_bits[i] (~(1 j));
}// 这里需要注意
_bits[i] ^ (1 j); // 不能用异或如果第 j 个比特位本身就是 0异或之后就变成 1 了。// 比如: 数据5映射在第0个char的第5个比特位
// 现在要用reset函数把数据5映射的第0个char的第5个比特位设置成0
0010 1111 - _bits[0] // 第0个char
0010 0000 - 1 5 // 将1左移5位// 将1左移5位后的结果按位取反然后按位与上 _bits[0]1101 1111 - ~(1 5)0010 1111 - _bits[0]
-----------------------0000 1111 - _bits[0] // 此时第0个char的第5个比特位已经被设置成0了 ④ 位图的查找test
test 函数检测数据 x 映射的比特位是否为 1即数据 x 是否存在。
// 检测数据 x 映射的比特位是否为1即数据x是否存在
// 是1返回true是0返回false
bool test(size_t x) const
{size_t i x / 8; // 映射在第i个char中size_t j x % 8; // 映射在第i个char中的第j个比特位上return _bits[i] (1 j);// 0000 1111 - _bits[0]// 0010 0000 - 1 5// ----------------------// 0000 0000 - 说明第0个char的第5个比特位是0数据x不存在
} c. 如何开出有42亿9千多万个比特位的位图呢
来映射42亿9千多万个无符号整型数标记其存在状态。
void test_bitset()
{// (size_t)4,294,967,295Ubitset-1 bs1; // 方式一bitset0xffffffff bs2; // 方式二
}
通过调试可以看到开了 512MB 的空间即 4,294,967,295U 个比特位 3位图的应用 快速查找某个数据是否在一个集合中。排序去重。求两个集合的交集、并集等。操作系统中磁盘块标记。 2、布隆过滤器bloomfilter
1布隆过滤器提出
我们在使用新闻客户端看新闻时它会不停地给我们推荐新的内容每次推荐时都要去重去掉那些我们已经看过的内容。那么问题来了新闻客户端推荐系统是如何实现推送去重的用服务器记录了用户看过的所有历史记录当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选过滤掉那些已经存在的记录。如何快速查找呢 用哈希表存储用户记录缺点浪费空间。用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理了。将哈希与位图结合即布隆过滤器。 【场景一】
现在有 1亿个 IP 地址字符串给你一个 IP需要快速判断这个 IP 在不在其中如何处理
1哈希切分。太慢了。2用一个字符串哈希算法把 IP 地址转换成可以取模的整型size_t然后映射到位图的某一个比特位中进行标记0 表示这个 IP 不存在1 表示这个 IP 存在。
问题是如果不同的 IP 地址映射的是同一个比特位会发生哈希冲突可能会存在误判 判断一个值是否在就是判断其映射的比特位是否为 1。判断结果是不准确的可能存在误判。判断一个值是否不在就是判断其映射的比特位是否为 0。判断结果一定是准确的。因为如果这个值在其映射的比特位一定是 1。 那该怎么办呢布隆发现想要判断一个值是否在变得一定是准确的几乎是不可能的。因为总会存在哈希冲突。虽然无法解决冲突但是可以缓解冲突。 对2的改进
一个 IP 映射位图中的一个比特位冲突概率大误判概率大。
那么我们对同一个 IP 使用不同的哈希算法让其映射多个比特位缓解冲突降低误判的概率。 虽然还是存在一定的误判但至少节省了空间。 【场景二】
判断一个人是不是这个学校的学生
1用姓名作为标识来表示一个人万一同姓名的人比较多就会导致误判。2用姓名、性别、出生年月作为标识来表示一个人同姓名的人比较多容易导致误判而同姓名同性别同出生年月的人可能有但是数量没有那么多这样就缓解了冲突降低误判概率。 核心思想一个值映射多个位。 2布隆过滤器概念 布隆过滤器是由布隆Burton Howard Bloom在 1970 年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询它的实现是一个很长的二进制向量位数组和一系列哈希函数。可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。 优点是空间效率和查询时间 O(1) 都比一般的算法要好的多。 缺点是有一定的误识别率和删除困难。 核心思想一个值映射多个位。 问哈希函数的个数需要权衡一下映射的位越多冲突的概率也越低但是消耗的空间的也越大但是映射的位少误判率就会变高那映射多少位是合理的呢
问布隆过滤器的底层就是一个位数组一次性开 0xffffffff 个位空间也没必要很浪费那如何控制开多少个位是合理的呢
如何选择哈希函数个数和布隆过滤器的长度并非官方测试结果 比如规定哈希函数个数 k 3布隆过滤器长度 m ( k / ln2 ) * n ≈ 4.2 * n大约是插入元素个数的 4.2 倍 。 3布隆过滤器的插入 向布隆过滤器中插入baidu void set(const K key) // 把键值key映射的几个比特位设置成 1
{// 对键值 Key 使用不同的哈希算法得到其映射的三个比特位的位置// 注意计算的比特位的位置可能超过了布隆过滤器的长度需要对长度 len 取模size_t index1 Hash1()(key) % len;size_t index2 Hash2()(key) % len;size_t index3 Hash3()(key) % len;// 把键值 key 映射的三个比特位设置成 1_bs.set(index1);_bs.set(index2);_bs.set(index3);
} 4布隆过滤器的查找 布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为 1。 所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。 比如在布隆过滤器中查找 alibaba 时假设 3 个哈希函数计算的哈希值为1、3、7刚好和其他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的。 bool test(const K key) // 检查键值key映射的几个比特位的值判断键值key在不在
{// 对键值 Key 使用不同的哈希算法得到其映射的三个比特位的位置// 注意计算的比特位的位置可能超过了布隆过滤器的长度需要对长度len取模size_t index1 Hash1()(key) % len;if (_bs.test(index1) false) {return false; // 检测该比特位的值是否为0若为0说明不在直接返回false}size_t index2 Hash2()(key) % len;if (_bs.test(index2) false){return false;}size_t index3 Hash3()(key) % len;if (_bs.test(index3) false){return false;}return true; // 注意当三个比特位的值都为1时可能存在误判
}void test_bloomfilter1()
{BloomFilter100 bf; // 最多向布隆过滤器中插入100个元素bf.set(alibaba);cout bf.test(alibaba) endl; // 输出1cout bf.test(alibaba) endl; // 输出0
} 【拓展】测试布隆过滤器的误判率 相似字符串的误判率测试发现哈希函数个数和插入元素个数确定情况下布隆过滤器长度越长误判率越低。 void test_bloomfilter()
{BloomFilter100 bf; // 最多向布隆过滤器中插入100个元素// 1、构造100个不同的字符串存放到 v1 中vectorstring v1;for (size_t i 0; i 100; i){string url https://www.bilibili.com/;url std::to_string(123 i); // 构造出100个不同的字符串v1.push_back(url);}// 把100个不同的字符串插入到布隆过滤器中for (const auto e : v1) bf.set(e);// 2、构造100个不同的相似字符串存放到 v2 中vectorstring v2;for (size_t i 0; i 100; i){string url https://www.bilibili.com/; // 用了相同的网址url std::to_string(456 i); // 构造出100个不同的相似字符串v2.push_back(url);}// 检测这100个不同的相似字符串是否在布隆过滤器中按理来说应该不在size_t count1 0;for (const auto e : v2){if (bf.test(e)) count1; // 如果判断在说明误判了// 统计出有多少个字符串误判了}cout 相似字符串的误判率 (double)count1 / (double)100 endl;
} 5布隆过滤器删除 一般情况下布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 比如删除上图中 hello 元素如果直接将该元素所对应的二进制比特位置 0world 元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。 一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器记录有多少个值映射到这个位了比如使用两个比特位来记录最多可以记录 3 个值插入元素时给 k 个计数器k 个哈希函数计算出的哈希地址加一删除元素时给 k 个计数器减一通过多占用几倍存储空间的代价来增加删除操作。 6布隆过滤器优点 增加和查询元素的时间复杂度为O(K)K 为哈希函数的个数一般比较小与数据量大小无关。哈希函数相互之间没有关系方便硬件并行运算。布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势。在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势。数据量很大时布隆过滤器可以表示全集其他数据结构不能。使用同一组散列函数的布隆过滤器可以进行交、并、差运算。 7布隆过滤器缺陷 有误判率即存在假阳性False Position即不能准确判断元素是否在集合中补救方法再建立一个白名单存储可能会误判的数据。不能获取元素本身。一般情况下不能从布隆过滤器中删除元素。如果采用计数方式删除可能会存在计数回绕问题。 8BloomFilter 的应用场景 布隆过滤器的应用场景在一些允许误判的地方。 【场景一】
假设这里有一个网站注册的时候需要每个用户取一个昵称要求昵称不能重复。用户在注册的时候输入一个昵称系统需要判断一下这个昵称是否已被注册。用户输入昵称点击提交后先到后台数据库中去查再返回判断这个昵称是否存在的结果。这种方式就太麻烦了。 问那能否当用户刚输入完昵称后还没有点提交切换到下一个输入框这个时候就会提示用户该昵称是否被占用呢 我们可以使用一个布隆过滤器标记所有使用过的昵称就能快速判断一个昵称是否被使用过。这里虽然会存在误判但在这种场景下误判的影响并不大因为判断一个昵称没被使用过一定是准确的。判断一个昵称被使用过可能存在误判但没什么影响大不了换一个昵称。 【场景二】 问如果要求判断在或不在的结果都要是准确的能否使用布隆过滤器呢 也是可以的比如验证一个手机号是否在系统中注册过要求验证结果是准确的。使用一个布隆过滤器标记所有注册过的手机号判断这个手机号在不在布隆过滤器中 如果不在直接返回结果未注册。如果在因为可能存在误判所以再去服务器的数据库中查询然后返回查询结果未注册 / 已注册。 虽然查询效率降低了但比起每次判断都去访问数据库还是要高效不少。有些服务器就会采用这种方式来提高效率。 【场景三】
比如判断垃圾邮件垃圾邮件的地址都会被标记映射到一个黑名单布隆过滤器中当有人给你发邮件时系统会快速判断出这个是否是垃圾邮件然后进行拦截或分类。
系统判断这个邮件不在黑名单中一定不会被拦截。系统判断这个邮件在黑名单中但这个邮件实际上可能不在黑名单中误判了把正常邮件拦截了但影响不大在垃圾箱还是能够找到这封正常邮件。 二、海量数据题目 海量数据处理一般不能用我们常见的数据结构去处理考验当常见数据结构都失效时该如何处理。 1、哈希切割
给一个超过 100G 大小的 log file日志文件log 中存着 IP 地址, 设计算法找到出现次数最多的 IP 地址与上面讲到的条件相同如何找到 top K 的 IP如何直接用 Linux 系统命令实现
此题不能用位图来处理了因为位图处理的是整数而 IP 地址是字符串比如192.0.0.1。这里就需要用到哈希切分大文件我们处理不了就想办法把它切分小文件处理。假设我们有 4G 内存我们就把这个大文件平均切分成 100 份小文件每一份 1G但这种平均切分实际上是不行的因为同一个 IP 可能进入了多份小文件中想要统计出每个 IP 最终出现的次数都是非常麻烦的更别说找到出现次数最多的那个 IP 地址了。那该怎么办呢 使用哈希切分。 切分操作
先创建 100 个小文件分别叫 0.txt、1.txt、2.txt、… 99.txt。然后读取 100G log file依次获取每个 IP 地址用字符串哈希算法把 IP 地址转换成可以取模的整型size_t比如使用 BKDR 算法size_t num BKDRHash(IP) % 100然后这个 IP 地址就放入映射到第 num.txt 号小文件。依次对所有 IP 进行处理进入映射到对应的小文件。如果运气好一点平均下来差不多每个小文件就是 1G 左右如果运气不好可能有些小文件是 512MB有些小文件是 2G但至少是相对可控的。
问如果最小的小文件 num.txt 还是过大该怎么办呢 我们可以限制一个大小在处理操作之前先检测一下当前小文件的大小如果超过 2G就换一个哈希算法把当前小文件再切小一些。 我们要找到出现次数最多的 IP 地址在最开始记录下当前小文件中出现次数最多的 IP 地址然后再读取后面小文件的过程中不断更新这个 IP 地址当最后一个小文件读取完就找到出现次数最多的 IP 地址了。 处理操作
依次读取每个小文件比如先读取 0.txt 中所有的 IP用 mapstring, int 统计所有 IP 出现的次数这里统计的 IP 出现次数就是这个 IP 最终出现的次数。我们记录下 0.txt 中出现次数最多的 IP。
问这里为什么用了 map 呢 因为是小文件内存消耗不大。然后再 clear() 掉 map 中的元素再读取 1.txt 中所有的 IP继续统计所有 IP 出现的次数不断走下去。 如果要找到 topK 的 IP 地址建立 K 个数的小堆即可。 这里采用哈希切分的关键是 相同的 IP 地址一定会进入编号相同的小文件。因为用字符串哈希算法同一个 IP 地址转换出来的哈希位置一定是相同的。 可以理解为这里就是 100 个存着文件指针的哈希桶。 2、位图应用只能处理整数
1给定 100 亿个整数设计算法找到只出现一次的整数
前面的题目是在没排过序的海量数据中快速判断一个数在不在其中是一个典型的 key 模型。
所以我们只需要用位图标记 2 种状态存在 / 不存在用一个比特位 1 / 0 来标记。
而这里是在海量数据中找到只出现一次的数不仅要判断这个数在不在还要知道这个数的出现次数。
错误思路 显然是不能把这 100亿 个整数存储在 map/unordered_map红黑树/哈希表 中。 正确思路 我们需要标记 3 种状态不存在 / 出现一次 / 出现多次则要用两个比特位来标记。因为两个比特位有 4 种表现形式 00 / 01 / 10 / 11。00表示这个数不存在01表示这个数只出现一次10表示这个数出现多次然后遍历位图找到所有 01 标记的位置此位置映射的就是只出现一次的整数。 问那这里需要消耗多少空间呢 这里要注意虽然有100亿个整数但并不是开 100亿 个比特位的表。这 100亿 个 unsigned int 整数的取值范围都是 0 ~ 2³²-1大约是42亿9千多万个整数如果每个整数映射一个比特位需要消耗 ( 2³²-1 ) / 8 个字节 ≈ 5亿多个字节 ≈ 0.5GB 的空间则每个整数映射两个比特位需要消耗 1GB 的空间。 具体做法
方法一用一个位图用 2 个连续的比特位标识一个数。需要修改 2 个不同位置的比特位的值不方便。 方法二封装两个位图用两个位图的同一个位置的 2 个比特位来标识一个数。
所以修改两个位图的同一个位置的比特位的值就好了还可以复用之前写的位图代码。 封装了两个位图找只出现一次的整数N非类型模板参数表示至少要开 N 个比特位的存储空间。 templatesize_t N
class FindOnceValSet
{
public: void set(size_t x) // 把数据 x 映射的比特位设置成 01表示数据 x 出现一次{bool flag1 _bs1.test(x); // 检测数据 x 在第1个位图中映射的比特位是否为 1bool flag2 _bs2.test(x); // 检测数据 x 在第2个位图中映射的比特位是否为 1// 两个比特位分别为 00说明数据 x 之前不存在if (flag1 false flag2 false){// 00 - 01标识成出现一次_bs2.set(x);}// 两个比特位分别为 01说明数据 x 之前已经出现一次else if (flag1 false flag2 true){// 01 - 10标识成出现多次_bs1.set(x); // 1_bs2.reset(x); // 0}// 两个比特位分别为 10说明数据 x 之前已经出现多次了不用处理// 10 - 10}void print_once_num() // 输出所有只出现一次的数据{// 遍历位图中的 N 个比特位for (size_t i 0; i N; i){// 检测两个位图的同一个位置的比特位是否分别为 0、1if (_bs1.test(i) false _bs2.test(i) true){cout i endl; // 输出此位置映射的数据 i}}}
private:bitsetN _bs1; // 位图1bitsetN _bs2; // 位图2
};void testFindOnceValSet()
{int a[] { 1,20,23,23,20,5,20,7,3,7 }; // 测试数据FindOnceValSet100 bs; // 开至少有100个比特位的位数组for (const auto e : a){bs.set(e); // 把数组a的每个元素的出现次数映射到位图bs中}bs.print_once_num(); // 输出所有只出现一次的数据
}
运行结果1 3 5 2给两个文件分别有 100 亿个整数我们只有 1G 内存如何找到两个文件交集
分析问题找到两个文件的交集只需要判断这个数是否分别在两个文件中是一个典型的 key 模型。 解决思路定义两个位图。 位图 1 标识第一个文件中所有数的存在状态1 存在、0 不存在。位图 2 标识第二个文件中所有数的存在状态1 存在、0 不存在。遍历位图中的 N 个比特位检测两个位图的同一个位置的比特位的值是否都为 1如果都为 1说明此位置映射的这个数就是交集。 需要消耗的内存 因为 unsigned int 整数的取值范围是 0 ~ 2³²-1大约是42亿9千多万个整数每个整数映射一个比特位需要消耗 ( 2³²-1 ) / 8 个字节 ≈ 5亿多个字节 ≈ 0.5GB 的空间这里开了两个位图需要消耗 1GB 的空间。 3位图应用变形1 个文件有 100 亿个 int1G 内存设计算法找到出现次数不超过 2 次的所有整数
和1类似。
解决思路封装两个位图用两个位图的同一个位置的 2 个比特位来标识一个数。 我们需要标记 4 种状态不存在 / 出现一次 / 出现两次 / 出现多次。 因为两个比特位有 4 种表现形式 00 / 01 / 10 / 11 所以 00 - 表示这个数不存在01 - 表示这个数只出现 1 次10 - 表示这个数出现 2 次11 - 表示这个数出现 2 次及以上 然后遍历位图找到所有不是 11 标记的位置此位置映射的就是出现次数不超过2次的整数。 4这里的位图问题也可以用哈希切分的思路来解决。但我们还是优先选择位图更优一些 3、布隆过滤器
1给两个文件分别有 100 亿个 query查询我们只有 1G 内存如何找到两个文件交集分别给出精确算法和近似算法
近似算法把第一个文件中的100亿个查询插入布隆过滤器再读取第二个文件看当前查询在不在布隆过滤器中。如果不在说明一定不是交集如果在说明可能是交集因为存在误判。精确算法哈希切分。
假设一个 query 平均 20 字节则 100 亿个 query 大约是 2000 亿字节则文件大约是 200 G。
第一步 先创建 200 个小文件分别叫 A0.txt、A1.txt、A2.txt、… A199.txt。 先创建 200 个小文件分别叫 B0.txt、B1.txt、B2.txt、… B199.txt。 第二步 依次读取 A 文件中的 query使用字符串哈希算法转成可以取模的整型 size_t i Hash( query ) % 200把这个 query 放入到映射到第 Ai.txt 号小文件中。 依次读取 B 文件中的 query使用字符串哈希算法转成可以取模的整型 size_t i Hash( query ) % 200把这个 query 放入到映射到第 Bi.txt 号小文件中。 注意平均下来每个小文件是 1G 左右可能有些文件大有些文件小。 第二步结束后文件中相同的 query 会分别进入编号相同的小文件只需要去编号相同的小文件中找交集即可。
第三步 第四步 i [0, 199]把 Ai.txt 读进 setA 中Bi.txt 读进 setB 中setA 和 setB 相同的 query 就是交集。 核心思想 原文件太大存在磁盘中直接读取去找交集效率太低先切分成一个一个的小文件然后再去读取小文件找交集。 2如何扩展 BloomFilter 使得它支持删除元素的操作。 一般情况下布隆过滤器不支持删除 reset 接口因为多个值可能会映射到同一个位有哈希冲突把该位置 0 可能会影响到其它值的状态。 如果想要支持删除 reset 接口呢 可以弄一个计数器记录有多少个值映射到这个位了比如使用两个比特位来记录最多可以记录 3 个值但是会付出更多空间消耗的代价。 4、其他
1哈希在加密中的应用 2哈希在存储中的应用 当我们存储量超级大的时候比如日常生活中使用的 QQ我们要把每个用户的用户数据、QQ 空间中相册等数据存储起来这是非常庞大的数据量需要用服务器存储起来一台服务器存不下就弄多台服务器每个服务器上存一部分这就是分布式然后对服务器进行集群管理通过监控程序监控所有服务器的状态。问题假设我有个好友发了一个朋友圈数据提交到某台服务器上我刷新朋友圈会显示他发的朋友圈但是怎么知道朋友圈数据是存在哪一台服务器上的呢每个用户都会有一个唯一 ID比如手机号身份证标识该用户一个用户的数据要存在哪台服务器上就可以使用哈希映射比如Hash( ID ) % 服务器台数。所以这种分布式存储是一定要用哈希的。但实际上远远比这复杂的多比如万一某台服务器坏了呢所以数据一般不会只存在一台服务器上而是建立多副本如果一台服务器坏了就会重新建立映射在其它服务器上建立新的副本。副本越多越稳定但空间消耗越大。还有比如新增或者减少了一些新服务器那原先用户数据映射的位置也会发生改变该如何解决呢这就需要用到一致性哈希了。
