10m光纤做网站,电子商务网站建设和技术现状,周口 网站建设,做物流的网站有哪些功能位图、布隆过滤器以及海量数据面试题 1.位图1.1概念1.2实现1.3位图应用 2.布隆过滤器2.1布隆过滤器的提出2.2布隆过滤器的概念2.3布隆过滤器的查找2.4布隆过滤器的实现2.5布隆过滤器的删除2.6布隆过滤器的优点2.7布隆过滤器的缺点 3.海量数据面试题3.1哈希切分3.2位图应用3.3布… 位图、布隆过滤器以及海量数据面试题 1.位图1.1概念1.2实现1.3位图应用 2.布隆过滤器2.1布隆过滤器的提出2.2布隆过滤器的概念2.3布隆过滤器的查找2.4布隆过滤器的实现2.5布隆过滤器的删除2.6布隆过滤器的优点2.7布隆过滤器的缺点 3.海量数据面试题3.1哈希切分3.2位图应用3.3布隆过滤器 1.位图
1.1概念
引入给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。 1遍历 时间复杂度O(N) 2排序加二分时间复杂度O(N*logN) 其中 方法(2)是行不通的因为内存很难装下这么多数据(40亿整数大概为16G)。方法(1)可行但如果需要多次查询很耗时。 3位图数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。比如 方法3的优势的建立起这个位图后查找任一数据在不在时间复杂度均为O(1)而且只需要 16G / 32 0.5G(存储整形需要16G现在一个比特位就可代表一个整形有32个比特位)空间占用很小。概念 所谓位图就是用比特位来存放某种状态(哈希思想的体现)适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。 1.2实现
namespace mystd
{//叫bitset只是单纯和库里面统一而已接口命名也是//库里面bitset使用基本也是这几个接口templatesize_t N //N表示要表示整数的范围即比特位个数class bitset {public:bitset() {//初始化这里可能存在浪费但几个比特位而已_bits.resize(N / 32 1, 0);}void set(size_t x) //设置标记表示x存在{//给你x计算出x属于第几个整数整数中的第几个比特位int i x / 32; //第几个int j x % 32; //第几个比特位//把对应的_bits[i]的第[j]位修改为1即可方法是将1左移j位或运算即可_bits[i] | (1 j);}void reset(size_t x) //去标记表示x不存在{int i x / 32;int j x % 32;//把对应的_bits[i]的第[j]位修改为0即可方法(1)是将1左移j位 (2)取反(j位置为0其它位置为1) (3)进行与运算_bits[i] ~(1 j);}bool test(size_t x) //看x在不在{int i x / 32;int j x % 32;//取到_bits[i]的第j位即可return _bits[i] (1 j); //非0即真0即假}private:vectorint _bits;};
}1.3位图应用
快速查找某个数据是否在一个集合中排序 去重求两个集合的交集、并集等
代码
#includeiostream
#includebitset
using namespace std;
//位图的应用
//快速查找某个数据是否在一个集合中
void test1()
{vectorint a { 0, 1, 2, 3, 4, 8, 99, 100, 150 };bitset151 bit_set;for (auto e : a){bit_set.set(e);}int x 0;while (cin x){if (bit_set.test(x)){cout x 存在 endl;}else{cout x 不存在 endl;}}
}//排序 去重
void test2()
{int a[] {0, 1, 2, 3, 4, 8, 99, 99, 100, 100, 150};bitset151 bit_set;vectorint result;for (auto e : a){bit_set.set(e);}//实际中应该在建立位图的过程中找出最大最小值这里就不写了//min 0 max 150;for (int i 0; i 150; i) {if (bit_set.test(i)){result.push_back(i);}}for (auto e : result) cout e ;cout endl;
}//求两个集合的交集、并集等
void test3()
{int a1[] { 0, 1, 2, 3 };int a2[] { 0, 2, 2, 4, 5, 6 };//交集bitset7 bit_set1;bitset7 bit_set2;for (auto e : a1) bit_set1.set(e);cout 交集为;for (auto e : a2){if (bit_set1.test(e) bit_set2.test(e) false){bit_set2.set(e); //过滤掉多次出现的数据cout e ;}}cout endl;//并集cout 并集为;bitset7 bit_set3; //去掉a1中重复的部分for (auto e : a1){if (bit_set3.test(e) false){cout e ;bit_set3.set(e);}}for (auto e : a2){if (bit_set3.test(e) false) //把a2特有的提取出来{cout e ;}}cout endl;
}2.布隆过滤器
2.1布隆过滤器的提出
想要判断某个数据在不在
哈希表空间消耗大。位图空间消耗小只适用于整形。哈希位图相结合即布隆过滤器。可适用各种复杂数据只要能通过哈希函数转化出关键值即可。 2.2布隆过滤器的概念 布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。 图解 2.3布隆过滤器的查找
结合前面可知布隆过滤器的查找需要对多个位置进行判断都为1才认为存在有一个为0认为不存在。
布隆过滤器判断存在判断不准确。 布隆过滤器判断不在结果准确。
布隆过滤器存在误判为什么还要使用 以用户注册为例用户名等信息存储在服务器数据库每次注册新用户都要遍历所有数据消耗太大。这个时候可以考虑使用布隆过滤器对于判断不在的情况是准确的可以允许注册对于判断在的情况就需要去遍历数据。实际当中可以过滤掉大量的请求提高效率。 2.4布隆过滤器的实现
//三个字符串哈希函数
struct BKDRHash
{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}return hash;}
};struct APHash
{size_t operator()(const string key){size_t hash 0;for (size_t i 0; i key.size(); i){char ch key[i];if ((i 1) 0){hash ^ ((hash 7) ^ ch ^ (hash 3));}else{hash ^ (~((hash 11) ^ ch ^ (hash 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string key){size_t hash 5381;for (auto ch : key){hash (hash 5) ch;}return hash;}
};//布隆过滤器一般都是解决字符串
//关于布隆过滤器的长度len N * x一般x取三以上至于具体大小依据场景进行衡量
//1x过大空间浪费
//2x过小误判较多不在判断为在过滤效果不好
templatesize_t N, size_t x 5, class K string, class HashFun1 BKDRHash, class HashFun2 APHash, class HashFun3 DJBHash
class BloomFilter
{void set(const K key){//一次标记3个位置要让数值落在范围内部size_t len N * x;size_t hash1 HashFun1()(key) % len;size_t hash2 HashFun2()(key) % len;size_t hash3 HashFun3()(key) % len;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(const K key){//看三个位置有一个为0就返回falsesize_t len N * x;size_t hash1 HashFun1()(key) % len;if (_bs.test(hash1) false) return false;size_t hash2 HashFun2()(key) % len;if (_bs.test(hash2) false) return false;size_t hash3 HashFun3()(key) % len;if (_bs.test(hash3) false) return false;return true;}
private:bitsetN * x _bs;
};2.5布隆过滤器的删除
布隆过滤器一般不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 比如删除上图中腾讯元素如果直接将该元素所对应的二进制比特位置0“百度”元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。 了解一定要支持删除的话可以采用引用计数的方法 将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。 2.6布隆过滤器的优点
增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关哈希函数相互之间没有关系方便硬件并行运算布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势在能够承受一定的误判时布隆过滤器比其他数据结构相比有很大的空间优势数据量很大时布隆过滤器可以表示全集其他数据结构不能使用同一组散列函数的布隆过滤器可以进行交、并、差运算 2.7布隆过滤器的缺点
有误判率即存在假阳性(False Position)即判断元素在集合中不准确(补救方法再建立一个白名单存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素如果采用计数方式删除可能会存在计数回绕溢出了回滚到0问题 3.海量数据面试题
3.1哈希切分 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址
100G过大无法直接在内存中处理可以先切割成100个小文件。先将IP转化为整形key然后key % 100相同IP会分到一样的小文件。依此读取这100个文件找每个文件中出现次数最多然后找出最大的那个。利用哈希切分可能存在冲突如果某个小文件极大可以更换哈希函数对这个小文件再进行切分。 3.2位图应用
给定100亿个整数设计算法找到只出现一次的整数 解法一整形范围为40多亿位图需要的空间为0.5G存在出现多次的情况即三种状态故一个比特位不够可以增加一位即用两个位图实现。当结果为00时代表没有出现、为01时代表出现了一次、为11时代表出现了多次。 解法二哈希切分相同的数字一定会分到同个文件对每个文件做统计即可。给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 1先哈希切分key % 500文件一分出A0、A1、A2……A499文件二分出B0、B1、B2……B499。其中相同的部分交集会被分到相同标号的文件只需要A0对B0、A1对B1……A499对B499的两两找交集就行。 2小文件过大的情况更换哈希再次切分即可。位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数 1分析状态一、出现0次。二、出现1次。三、出现2次。四、出现2次以上。 2有四种状态用两个比特位即可表示即使用两个位图。当结果为00、01、10时都属于没超过2次当结果为11时代表结果超过了两次。 3.3布隆过滤器
给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法 1近似算法先读取文件一建立布隆过滤器。然后读取文件二依次判断是否在布隆过滤器中近似算法存在误判。 2精确算法对两个大文件进行哈希切分两两小文件找交集即可。如何扩展BloomFilter使得它支持删除元素的操作 1数据量不大可以用几个位图实现。 2数据量大一个哈希值对应的就不是一比特位了而是一个整形。
