一、位图1.1位图概念一道面试题给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中【腾讯】解决思路1. 遍历时间复杂度O(N)---不行2. 排序(O(NlogN))利用二分查找: logN---不行3. 位图解决---可以数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。比如位图概念所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。1.2位图实现#pragma once #includevector #includeiostream #includestdbool.h namespace BitSet { templatesize_t N class bitset { public: bitset() { _a.resize(N / 32 1);//向上取整一下 } //set将x映射的位标记为1 void set(size_t x) { //找到第几个整形 size_t i x / 32; //找到整形中的第几个 size_t j x % 32; //将这一位标记为设置成1 _a[i] | (1 j); } //reset将x映射的位标记为0 void reset(size_t x) { //找到第几个整形 size_t i x / 32; //找到整形中的第几个 size_t j x % 32; //将这一位标记为设置成0 _a[i] (~(1 j)); } //检测某个值在不在(判断该位为1还是0) bool test(size_t x) { //找到第几个整形 size_t i x / 32; //找到整形中的第几个 size_t j x % 32; return _a[i] (1 j); } private: std::vectorint _a; }; }1.4位图的测试int main() { BitSet::bitset1000 bs1; bs1.set(1); bs1.set(100); bs1.set(134); std::cout bs1.test(134) std::endl; std::cout bs1.test(100) std::endl; std::cout bs1.test(23) std::endl; bs1.reset(100); std::cout bs1.test(100) std::endl; return 0; }1.5通过使用位图完成上述1.1中的面试题int main() { BitSet::bitset-1 bs1; //除了上述开42亿的方法还有以下方法 BitSet::bitset0xffffffff bs2; return 0; }1.6位图的应用1. 快速查找某个数据是否在一个集合中2. 排序 去重3. 求两个集合的交集、并集等4. 操作系统中磁盘块标记5.给定100亿个数设计算法找到只出现一次的整数第五题思路使用两个位图来表示一个数字出现的次数00表示0次01表示1次10表示两次及以上templatesize_t N class solution { public: void set(size_t x) { if (!_a.test(x) !_b.test(x)) { //本身00则变01 _b.set(x); } else if (!_a.test(x) _b.test(x)) { //本身是01则变10 _a.set(x); _b.reset(x); } else if (_a.test(x) !_b.test(x)) { //本身是10的就表示出现两次以上了不用变了 } } bool Is_once(size_t x) { //第一个是0且第二个是1就是出现一次的 return !_a.test(x) _b.test(x); } private: std::bitsetN _a; std::bitsetN _b; }; int main() { int a[] { 1,2,3,3,4,4,4,4,4,2,3,6,3,1,5,5,8,9}; solution10000 tbs; for (auto e : a) { tbs.set(e); } for (auto e : a) { if (tbs.Is_once(e)) { std::cout e ; } } std::cout std::endl; return 0; }6.给两个文件分别有100亿个数但我们只有1GB的内存如何找两个文件的交集思路两个文件对应到两个位图对应的位置与一下int main() { //用两个数组模拟 int a[] { 1,2,3,3,4,4,4,4,4,2,3,6,3,1,5,5,8,9 }; int b[] { 1,3,34,23,12,34,54,65,4,4,5,6,7,3,9}; std::bitset1000 bs1; std::bitset1000 bs2; for (auto e : a) { bs1.set(e); } for (auto e : b) { bs1.set(e); } //遍历看是否都在位图里面 for (size_t i 0; i 100; i) { if (bs1.test(i) bs2.test(i)) { std::cout i ; } } std::cout std::endl; return 0; }7.1个文件有100亿个int1G内存设计算法找到出现次数不超过两次的所有整数思路依旧两个位图用两位来表示这个数字然后00、01、10都是不超过两次的而11则表示超过两次的1.7C库中的bitset二、布隆过滤器2.1布隆过滤器提出我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉那些已经看过的内容。问题来了新闻客户端推荐系统如何实现推送去重的 用服务器记录了用户看过的所有历史记录当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选过滤掉那些已经存在的记录。 如何快速查找呢1. 用哈希表存储用户记录缺点浪费空间2. 用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理了。3. 将哈希与位图结合即布隆过滤器2.2布隆过滤器概念布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。2.3布隆过滤器的实现#pragma once #includeiostream #includevector #includebitset #includestring class BKDRHash { public: size_t operator()(const std::string str) { register int hash 0; for (auto element : str) { hash hash * 131 element; } return hash; } }; class APHash { public: size_t operator()(const std::string str) { size_t hash 0; for (size_t i 0; i str.size(); i) { if ((i 1) 0) { hash ^ ((hash 7) ^ str[i] ^ (hash 3)); } else { hash ^ (~((hash 11) ^ str[i] ^ (hash 5))); } } return hash; } }; class DJBHash { public: size_t operator()(const std::string str) { size_t hash 5381; for (auto ch : str) { hash (hash 5) ch; } return hash; } }; templatesize_t N, class K std::string, class Hash1 BKDRHash, class Hash2 APHash, class Hash3 DJBHash class BloomFilter { public: bool set(const K key) { size_t hash1 Hash1()(key) % N; _bs.set(hash1); size_t hash2 Hash2()(key) % N; _bs.set(hash2); size_t hash3 Hash3()(key) % N; _bs.set(hash3); return true; } bool test(const K key) { size_t hash1 Hash1()(key) % N; if (_bs.test(hash1) false) { return false; } size_t hash2 Hash2()(key) % N; if (_bs.test(hash2) false) { return false; } size_t hash3 Hash3()(key) % N; if (_bs.test(hash3) false) { return false; } return true;//不保真 } private: std::bitsetN _bs; };注意布隆过滤器一般不支持删除删除一个值可能会影响其他值2.4布隆过滤器的测试int main() { BloomFilter1000 bf; bf.set(孙悟空); bf.set(猪八戒); bf.set(唐僧); std::cout bf.test(孙悟空) std::endl; std::cout bf.test(孙尚香) std::endl; return 0; }2.5布隆过滤器优点1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关2. 哈希函数相互之间没有关系方便硬件并行运算3. 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势4. 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势5. 数据量很大时布隆过滤器可以表示全集其他数据结构不能6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算2.6布隆过滤器缺陷1. 有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据)2. 不能获取元素本身3. 一般情况下不能从布隆过滤器中删除元素4. 如果采用计数方式删除可能会存在计数回绕问题2.7布隆过滤器的删除布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。一种支持删除的方法使用引用计数将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。该方法的缺陷1. 无法确认元素是否真正在布隆过滤器中2. 存在计数回绕2.8布隆过滤器的应用哈希切割2.8.1给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法思路假设一个query是30字节1G就是10亿字节那么100亿个query就是3000亿字节那么就是300G 将文件进行切割然后使用i Hash(query) % 1000对于两个文件中i是多少就进几号文件然后对应编号相同的找交集就可以了两个场景比如Ai有5G1、4G都是相同query1G冲突2、大多数都是冲突解决方案 :1、先把Ai的query读到一个set如果set的insert报错抛异常(bad alloc)那么就说明是大多数query都是冲突。如果能够全部读出来insert到set里面那么说明Ai有大量相同的query2、如果抛异常说明有大量冲突再换一个哈希函数再进行二次切分。2.8.2给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址思路进行哈希切割然后对进入了相同小文件的ip放进map里面统计次数