位图

概念

题目

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何判断一个数是否在这40亿个整数中

1.遍历，时间复杂度O(N)
2.二分查找，需要先排序，排序(N*logN)，二分查找，logN。1个g大约存储10g字节，40亿个整数就需要160g字节，需要16个g的连续空间，内存中无法开出这么大的容量。
3.位图。判断一个数在不在的最小单位可以是位，将整数的范围全部做一个映射，有的值设置为1，没有就设置为0。这样，需要的空间就是42亿个位，0.5个g就可以存下

上面是3个字节的值，一个字节32位，可以表示的数的范围。计算一个值在第几个字节，在这个字节的第几个位。将一个数除以32就知道在第几个字节，取模就知道在第几个位，比如40，在第1个字节里，在第8位

位图概念

用每一位存放某种状态，适用于海量数据，数据无重复的场景，判断某个数据村部还存在的

实现

成员函数

可以用内置数组，这里直接用vector，成员类型是int

构造

为vector开辟需要的空间，每一位代表一个值，看需要多大的值，用非类型模板参数传入值。传入的是位，除以32再补上去的余数的一位，就是开辟多大整形的空间

set

将这个数据映射的值设为1。计算出数据所在的位，设置为1。i和j分别计算在第几个字节和第几位，让一个数的一位变为1，其他位不变化，可以或一个数，这个数这一位为1，其他位为0。可以将1左移j位就有了这个数

内存有大端和小端存储，左移都是往高位移动

reset

将这个数据清除，变为0。计算出i和j，让某一位变为0，可以与一个数，这个数这一位为0，其他都为1。1左移j位然后取反

test

查询一个数是否存在。1左移j位，与操作

全

#pragma once
#include <vector>//N是需要多少位
template <size_t N>
class bitset
{
public:bitset(){//多开一个防止不够_bit.resize(N / 32 + 1, 0);//_bit.resize( (N >> 5) + 1, 0)}void set(size_t x){int i = x / 32;int j = x % 32;_bit[i] = _bit[i] | (1 << j);}void reset(size_t x){int i = x / 32;int j = x % 32;_bit[i] = _bit[i] & ~(1 << j);}bool test(size_t x){int i = x / 32;int j = x % 32;return _bit[i] & (1 << j);}
public:std::vector<int> _bit;
};

测试

40亿的整数需要开辟的空间必须是无符号的整形大小，int是有符号的，所以用0xffffffff或-1

bitset<0xffffffff> bs;
bs.set(39256);
bs.set(43450);
bs.reset(40);cout << bs.test(24515) << endl;
cout << bs.test(32329) << endl;
cout << bs.test(39256) << endl;
cout << bs.test(2314) << endl;
cout << bs.test(43450) << endl;

应用

1.快速查找某个数据是否在一个集合中
2.排序+去重
3.求两个集合的交集、并集等
4.操作系统重磁盘块标记

题目

1.给定100亿个整数，设计算法找到只出现一次的整数
位图用一个位标识两种状态，存在和不在，找到出现一次的数需要第三种状态，可以用两个位来保存一个数。也可以复用前面的位图，用一个结构，成员两个位图。set时，当两个位图表示的是00的时候，就设置为01,01就设置为10,10就不做任何改变。打印的时候打印出01状态的数字

template <size_t N>
class twobitset
{
public:void set(size_t x){//00 0次//01 1次//10 2次或以上int i = x / 32;int j = x % 32;if (_bs1.test(x) == false && _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false && _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}}void printOne(){for (size_t i = 0; i < N; i++){if (_bs1.test(i) == false && _bs2.test(i) == true){printf("%d ", i);}}printf("\r\n");}public:bitset<N> _bs1;bitset<N> _bs2;
};

2.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集

和上面的方法一样，无论多少整数，还是申请42亿，两个位图里都有的就是交集

3.位图变形，一个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

还是上面的类型，稍微修改，set函数10的时候变为11,11不变

template <size_t N>
class twobitset
{
public:void set(size_t x){//00 0次//01 1次//10 2次或以上int i = x / 32;int j = x % 32;if (_bs1.test(x) == false && _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false && _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}else if (_bs1.test(x) == true && _bs2.test(x) == false){_bs1.set(x);_bs2.set(x);}}void printOne(){for (size_t i = 0; i < N; i++){if (_bs1.test(i) == false && _bs2.test(i) == true){printf("一次%d ", i);}else if (_bs1.test(i) == true && _bs2.test(i) == false){printf("两次%d ", i);}}printf("\r\n");}public:bitset<N> _bs1;bitset<N> _bs2;
};

布隆过滤器

提出

每次看新闻时，会不断推荐新的内容，去掉已经看过的内容。问题来了，如何实现推送去重的，用服务器记录所有看过的记录，当推荐系统推荐新闻时从每个用户的历史记录里筛选，过滤掉已经存在的记录，怎么快速查找

目前搜索采用的各种方法
1.暴力查找，数据量太大了，效率就低
2.排序+二分查找，问题a:排序有代价 问题b:数组不方便增删
3.搜索树，avl树+红黑树
上面的数据结构对空间消耗的都很高，如果面对数据量很大的
5.[整形]，在不在及其扩展问题，位图和变形，节省空间
6.[其他类型] 在不在，哈希和位图结合，布隆过滤器

概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率性数据结构，特点是高效的插入和查询，可以判断一个东西一定不在或可能在，是用多个哈希函数，将一个数据映射到位图结构中，此种方式不仅可以提升查询效率，也可以节省大量的内存空间

一个值映射一个比特位，冲突的概率很大，两个不同的字符串正好映射在一个比特位，这时判断的存在就是错误的。为了降低误判的概率，多映射几个比特位，映射的越多，消耗的空间就越多

插入

上图中，当k3个时，100m数据误判率0.01已经很低了

按公式计算：

3个哈希函数，n和m的关系是4.3，约为4倍容量

查找

将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置比特位一定为1.所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个零，代表该元素一定不在哈希表中，否则可能在哈希表中

注意：布隆过滤器如果说某个元素不存在时，一定不存在，如果该元素存在时，可能存在，因为存在一定的误判

删除

不能直接支持删除操作，因为在删除一个元素时，可能影响到其他元素
比如：删除上图的"tecent”元素，如果直接将该元素对应的二进制比特位置置为0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算的比特位有重叠

一种支持删除的方法：将布隆罗氯气每个比特位扩展成一个小的计数器，插入元素时给k个计数器（k个哈希函数计算出的哈希地址）加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。如果引用计数最大为255时，映射的单位就必须扩展为8位

缺陷：
1.无法确认元素是否真正在布隆过滤器中
2.存在计数回绕

实现

#pragma once
#include <bitset>struct BKDRHash
{size_t operator()(const std::string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};struct APHash
{size_t operator()(const std::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 std::string& key){size_t hash = 5381;for (auto ch : key){hash += (hash << 5) + ch;}return hash;}
};template <size_t N, class K = std::string,class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJBHash>
class BloomFilter
{
public:void set(const std::string& key){size_t hashi1 = HashFunc1()(key) % N;size_t hashi2 = HashFunc2()(key) % N;size_t hashi3 = HashFunc3()(key) % N;_bs.set(hashi1);_bs.set(hashi2);_bs.set(hashi3);}// 一般不支持删除，删除一个值可能会影响其他值// 非要支持删除，也是可以的，用多个位标记一个值，存引用计数// 但是这样话，空间消耗的就变大了void Reset(const K& key);bool test(const std::string& key){size_t hashi1 = HashFunc1()(key) % N;if (_bs.test(hashi1) == false)return false;size_t hashi2 = HashFunc2()(key) % N;if (_bs.test(hashi2) == false)return false;size_t hashi3 = HashFunc3()(key) % N;if (_bs.test(hashi3) == false)return false;return true;}private:std::bitset<N> _bs;
};

测试

#include <time.h>
#include <vector>
#include <iostream>
#include <string>
#include "bloom.h"int main()
{srand(time(0));const size_t N = 100000;BloomFilter<N * 4> bf;std::vector<std::string> v1;//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";std::string url = "猪八戒";for (size_t i = 0; i < N; ++i){v1.push_back(url + std::to_string(i));}for (auto& str : v1){bf.set(str);}// v2跟v1是相似字符串集（前缀一样），但是不一样std::vector<std::string> v2;for (size_t i = 0; i < N; ++i){std::string urlstr = url;urlstr += std::to_string(9999999 + i);v2.push_back(urlstr);}size_t n2 = 0;for (auto& str : v2){if (bf.test(str)) // 误判{++n2;}}std::cout << "相似字符串误判率:" << (double)n2 / (double)N << std::endl;// 不相似字符串集std::vector<std::string> v3;for (size_t i = 0; i < N; ++i){//string url = "zhihu.com";std::string url = "孙悟空";url += std::to_string(i + rand());v3.push_back(url);}size_t n3 = 0;for (auto& str : v3){if (bf.test(str)){++n3;}}std::cout << "不相似字符串误判率:" << (double)n3 / (double)N << std::endl;return 0;
}

优点

1.增加和查询元素的时间复杂度为：O(K),（k为哈希函数个数，一般比较小），与数据数量无关
2.哈希函数相互之间没有关系，方便硬件并行计算
3.布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4.能够承受一定的误判时，布隆过滤器比其他数据结构有很大的空间优势
5.数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6.使用同一组散列函数的布隆过滤器可以进行交、并、差运算

例如网页注册时，判断用户名存不存在。如果需要更进一步正确，可以将判断为存在的和数据库对比

缺陷

1.有误判率，即存在假阳性（False Position），即不能准确判断元素是否在集合中（补救方法：再建立一个白名单，存在可能会误判的数据）
2.不能获取元素本身
3.一般情况下不能从布隆过滤器中删除元素
4.如果采用计数方式删除，可能会存在计数回绕问题

哈希切割

1. 给定两个文件，分别有100亿个query（字符串），只有1G内存，找到文件交集，精确算法和近似算法

近似算法就是上面的布隆过滤器
精确算法：
假设一个query有50个字节，100亿数据就需要500G，内存存不下，可以用哈希切分
读取每个query，计算i=Hash(query)%500，i是几，query就进入Ai小文件

A和B相同的字符串会进入相同编号的块里，只需要比较两个相同编号的块，就能找到交集
如果切分的某个文件大于10G，还是无法加载到内存里？
1.这个小文件大多数都是1个query
2.这个小文件，有很多不同的query

不管文件大小，直接读到内存插入set，如果是情况1，文件有很多重复，会去重
如果是情况2，插入后就会内存不足，抛异常，换一个哈希函数，二次划分，再找交集

2. 给一个超过100G大小的logfile，存ip地址，设计找出次数最多的ip地址

还是用哈希切分，相同的ip就进入了同一个小文件，然后用map统计次数。如果找topk，也可以用堆来解决