关键词：
目录
前言
海量数据处理，顾名思义。就是数据两很大，内存不足以保存这么多数据的问题该如何解决。
一般可以使用位图(整形)，布隆过滤器(非整形)，哈希切割的方法。
一.位图应用
- 给定100亿个整数，设计算法找到知出现一次的整数？
首先估算，100亿整数保存需要多少空间？1个整数4字节，100亿整数400亿字节。1G10亿字节，所以这里差不多要10G。内存无法将数据全部保存，只能将数据保存在硬盘中。
这里该如何计算呢？
方案一：我们可以使用位图，一般的位图用一位来表示一个数组是否存在。但是这里需要找出知出现一次的整数。这里仔细分析，有三种状态，存在，存在只出现一次和存在出现多次。我们可以在位图种用两个位来表示一个整数的状态，(00表示不存在，01表示存在且只出现一次，11表示存在且出现多次)。无符号整形的最大范围为2^32-1(42亿多)，100亿个整数，肯定有很大重复的值。位图只需要开空间2*(2^32-1)个位，差不多1G空间。
方案二：还是用上面的思想，但是不是在一个位图种。定义两个位图，它们的哈希函数一样，两位图同一位置，一个位图是高位，一个位图是低位。依旧是00表示不存在，01表示存在且只出现一次，11表示存在且出现多次。
- 给定100亿个整数，1G内存，设计算法找到知出现不超过两次的整数？
上面题目的变形，情况相同还是用两位状态00表示不存在，01表示存在一次，10表示存在两次，11表示存在两次以上。
- 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？
方案一：假设两个文件一个是文件A，一个是文件B。将文件A数据映射到位图种，需要消耗500M内存。读取文件B中的数据，在位图中找存不存在。
方案二：将文件A映射到位图中，将文件B映射到位图中。然后将两位图按位&，得到的位图，再按照哈希函数反推到交集数据。
位图保存的是整形，是直接定址法，不会有哈希冲突。
二.布隆过滤器
- 给两个文件，分别由100亿个query(query是sql的查询语句或者是网络请求url，一般是字符串)，我们只有1G内存，如何找到交集？给出精确算法和近似算法。
首先由于query是字符串，不能使用位图，得使用布隆过滤器。
分析一个100亿个query占多少空间？一般一个query占30~60字节，100亿query大概占用300~600G内空间。内存无法保存。
方案一(近似算法)：假设两个文件分别是文件A和文件B，用一个布隆过滤器保存文件A的数据，字符串转换函数将字符串转为整形，整形最多大范围也只有42亿多，所以布隆过滤器只需要开500M左右空间。再将文件B保存到布隆过滤器中，两布隆过滤器按位&，得到交集。
但是这样会有一个缺陷：就是不同的query通过几个字符串转换函数可能会得到相同的值，会导致交集里出现不是交集的query。交集数据不准确。
方案二(精确算法)：利用分割 + 红黑树
首先将文件A和文件B分割成n个内存可以放下的文件。比如上面大概占用300G~600G，将文件A和文件B分割成1000个小文件，每一个小文件大概占用300~600M，可以保存在内存中。
再将文件A中的一个小文件中保存到set或者unordered_set中，再将文件B中的每一个小文件与set或者unordered_set中的数据比较，找交集。再保存文件A中的另一个小文件保存到set或者unordered_set中，再将文件B中的每一个小文件与set或者unordered_set中的数据比较，找交集。如此，可以得到交集。
此时需要文件A的一个小文件，都和文件B的每一个小文件比较。
方案三(精确算法)：利用哈希分割 + 红黑树
依旧是将文件A和文件B分割成n个小文件，这里分割成1000个小文件。每个文件就是300~600M。
利用哈希分割：利用哈希字符串转整形函数：i = hashstr(query) % n，hashstr是字符串转整形函数，query是文件A和文件B中的query。n是文件个数，这里是1000。求出来的i是将对应的query保存到对应第i个文件中。
文件A和文件B求query放到哪个文件的hashstr用的是同一个。这时通过hashstr求出来的相同的值一定在A和B同一个编号小文件中，也就是Ai和Bi中。
文件A和文件B的交集一定都保存到了同样编号的小文件中，其中可能也保存了不是交集的值。
此时将小文件Ai保存到set中，只需要和对应小文件Bi比较皆可，不需要和文件B的每一个小文件比较。
- 如何扩展布隆过滤器使它支持删除操作？
通过使用计数器，使用多个位来表示一个计数器。1个位可以表示0和1，2个位表示0~3，3个位表示0~7.....
但是使用空间过小，如使用一字节最多表示256个数，当多余256时，就溢出了。但是使用空间过大，布隆过滤器就没有优势了。
使用多少位取决于会重复多少数据。建议使用两个字节大小，也就是16个位。
三.哈希切割
- 给一个超过100G的log file(日志文件)，log里保存着IP地址，设计一算法找出出现次数最多的IP？与上题想同找到top K IP?
利用哈希切割，先将log file分割成多个小文件。分割的小文件只要可以保存到内存即可。假设我这里分割成1000个小文件，每个文件最小100M。
在将每个小文件的IP保存到map<string，int>中来进行计数，设置一个遍历pair<string，int> max，来保存每个小文件中出现次数最多的键值对。就可以得到出现次数最多的IP。
海量数据处理面试题(代码片段)
...位图相关二、布隆过滤器相关三、哈希切割相关前言海量数据处理是指基于海量数据的存储和处理，正因为数据量太大，所以导致要么无法在短时间内迅速处理，要么无法一次性装入内存。对于时间问题，就可以... 查看详情
手撕stlbitset（位图）布隆过滤器(代码片段)
位图位图的实现位图的应用哈希切割布隆过滤器布隆过滤器优点布隆过滤器缺陷布隆过滤器的应用场景布隆过滤器实现布隆过滤器删除如何选择哈希函数个数和布隆过滤器长度代码实现：相关面试题位图，就是用每一位... 查看详情
手撕stlbitset（位图）布隆过滤器(代码片段)
位图位图的实现位图的应用哈希切割布隆过滤器布隆过滤器优点布隆过滤器缺陷布隆过滤器的应用场景布隆过滤器实现布隆过滤器删除如何选择哈希函数个数和布隆过滤器长度代码实现：相关面试题位图，就是用每一位... 查看详情
[c++]位图-布隆过滤器-海量数据的处理问题(代码片段)
...位图2.3使用过程2.4位图的应用2.5位图相关问题解决3.布隆过滤器3.1为什么使用布隆过滤器？3.2原理3.3插入、查找与删除3.3.1插入3.3.2查找3.3.3删除3.4优缺点3.5问题4.代码模拟4.1位图4.2布隆过滤器1.哈希切割 现在有一个100 查看详情
[c++]位图-布隆过滤器-海量数据的处理问题(代码片段)
...位图2.3使用过程2.4位图的应用2.5位图相关问题解决3.布隆过滤器3.1为什么使用布隆过滤器？3.2原理3.3插入、查找与删除3.3.1插入3.3.2查找3.3.3删除3.4优缺点3.5问题4.代码模拟4.1位图4.2布隆过滤器1.哈希切割 现在有一个100 查看详情
[c++]位图-布隆过滤器-海量数据的处理问题(代码片段)
...位图2.3使用过程2.4位图的应用2.5位图相关问题解决3.布隆过滤器3.1为什么使用布隆过滤器？3.2原理3.3插入、查找与删除3.3.1插入3.3.2查找3.3.3删除3.4优缺点3.5问题4.代码模拟4.1位图4.2布隆过滤器1.哈希切割 现在有一个100G的大... 查看详情
手撕stlbitset（位图）布隆过滤器(代码片段)
位图位图的实现位图的应用哈希切割布隆过滤器布隆过滤器优点布隆过滤器缺陷布隆过滤器的应用场景布隆过滤器实现布隆过滤器删除如何选择哈希函数个数和布隆过滤器长度代码实现：相关面试题位图，就是用每一位... 查看详情
数据结构----哈希(代码片段)
...散列(模拟实现)比较哈希应用位图模拟实现位图题目布隆过滤器模拟实现布隆过滤器的误判对于布隆过滤器的删除总结拓展问题(利用哈希切分)其他哈希切割一致性哈希(解决分布式缓存问题)（MARK以后看Linux服务器模拟）... 查看详情
哈希表应用(位图和布隆过滤器)(代码片段)
... 1.2位图的应用 1.3位图的实现 二.布隆过滤器 2.1布隆过滤器的概念 2.2布隆过滤器的优缺点 2.3实现一.位图 1.1位图概念 位图，是用比特位来表示某种状态。一个位有两种状态0和1... 查看详情
位图及布隆过滤器的模拟实现与面试题(代码片段)
位图模拟实现namespaceyyqtemplate<size_tN>classbitsetpublic:bitset()_bits.resize(N/8+1,0);//_bits.resize((N>>3)+1,0);voidset(size_tx)//将某位做标记size_ti=x/8;//第几个char对象size_tj=x%8;//这个char对象的第几个比特位_bits[i]|=(1<<j);//... 查看详情
bingc++（mapset树哈希位图布隆过滤器）(代码片段)
...列开散列的应用--unordermap、unorderset位图位图的应用布隆过滤器常见面试题前言底层为红黑树结构C++98二叉搜索树＋平衡限制map:K-V–键值对—key 查看详情
布隆过滤器
1、布隆过滤器的概念布隆过滤器(BloomFilter)是一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你某样东西一定不存在或者可能存在，它是用多个哈希函数，将一个数据映射到位图结构中。此... 查看详情
位图与布隆过滤器简明介绍
...某个位表示某个数字。这就是位图消耗大小：约120M布隆过滤器不过位图有个问题，想想看，如果数的范围是1到100亿呢，那位图消耗的大小就是1.2G了！！，相对于散列表，不降反升。这个时候，总算轮到今天的主角：布隆过滤器... 查看详情
算法初级面试题05——哈希函数/表生成多个哈希函数哈希扩容利用哈希分流找出大文件的重复内容设计randompool结构布隆过滤器一致性哈希并查集岛问题(代码片段)
今天主要讨论：哈希函数、哈希表、布隆过滤器、一致性哈希、并查集的介绍和应用。 题目一认识哈希函数和哈希表1、输入无限大2、输出有限的S集合3、输入什么就输出什么4、会发生哈希碰撞5、会均匀分布，哈希函数的离... 查看详情
bingc++（mapset树哈希位图布隆过滤器）(代码片段)
...列开散列的应用--unordermap、unorderset位图位图的应用布隆过滤器常见面试题前言底层为红黑树结构C++98二叉搜索树＋平衡限制map:K-V–键值对—key必须唯一set:K—key必须唯一multimap:K-V–键伯对—key是可以重复multisetK----key是... 查看详情
bingc++（mapset树哈希位图布隆过滤器）(代码片段)
...列开散列的应用--unordermap、unorderset位图位图的应用布隆过滤器常见面试题前言底层为红黑树结构C++98二叉搜索树＋平衡限制map:K-V–键值对—key必须唯一set:K—key必须唯一multimap:K-V–键伯对—key是可以重复multisetK----key是... 查看详情
布隆过滤器详解
参考技术A布隆过滤器（英语：BloomFilter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。通常我们会遇到很多要判断一个元素是否在某个集合中的业... 查看详情
解释一下布隆过滤器原理
...获取你想要的,接下来的是今日的面试题：1.解释一下布隆过滤器原理在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要... 查看详情