哈希思想及其应用

1.unordered系列容器

1.1简介

1.2接口 (只对效果进行描述，具体可以自行参考文档)

1.2.1构造

1.2.2容量

1.2.3迭代器

1.2.4访问

1.2.5查询

1.2.6修改

1.2.7桶操作

2.哈希

2.1概念

2.2哈希冲突

2.2.1闭散列

2.2.2开散列

2.2.2.1哈希文件

2.2.2.2unordered_map模拟

2.2.2.3unordered_set模拟

3.位图

模拟

应用

4.布隆过滤器

模拟

优点：

缺陷：

应用

首先要说明的是unordered系列的容器，但是使用上unordered_map、unordered_set跟map、set区别不大，我这里不会再详细的介绍每个接口

1.unordered系列容器

1.1简介

set和unordered_set的区别,效率上unordered_set只是略微胜出一点，跟下面unordered_map和map的区别是差不多的，都是底层实现不同，所以不多赘述。详情可自行参考文档

unordered_map跟map的区别

1.unordered_map内部存储不会排序，为了能够常数级别访问，会有个哈希值，且把哈希值相同的放在同样的桶中（哈希值是什么，看下面具体哈希的内容，这里只是对容器做个说明）

unordered_map访问单个元素，比map快，但是遍历元素方面效率较低。

2.只有单向迭代器，没有反向迭代器。

1.2接口 (只对效果进行描述，具体可以自行参考文档)

1.2.1构造

unordered_map<int>has

1.2.2容量

empty()检测容器是否为空。

size获取容器有效元素个数

1.2.3迭代器

begin(),end(),cbegin(),cend().

1.2.4访问

has[3]。支持括号访问

原理跟map的括号一样，都是调用插入操作。

1.2.5查询

find(),返回key在哈希桶中的位置

count返回哈希桶中关键码为key的键值对的个数(unordered_map里面key不能重复，所以unordered_map的count只能返回1或0)

1.2.6修改

insert()插入，erase删除，clear清空，swap(unordered_map &)交换两个容器的元素

1.2.7桶操作

bucket count() 返回哈希中桶的总个数

bucket size(size_t n) 返回n号桶中有效元素的总个数

bucket(const K&key)返回元素key所在的桶号

2.哈希

2.1概念

顺序结构以及AVL树种，元素关键码与其存储位置之间没有对应的关系，因此在查找在查找一个元素的时候，必须经过关键码的多次比较，顺序查找时间复杂度O（n），AVL树是为树的高度，即O(log n)，搜索效率取决于搜索过程中元素的比较次数.

理想情况：不经过任何比较，一次直接获得要搜索的元素，即常数级别。

因此，哈希这种元素存储位置与关键码有映射关系的结构就出现了。

哈希：
根据插入元素的关键码，通过哈希函数获得对应存储位置，然后进行存放查找。

若查找的话，就是根据搜索元素的关键码通过哈希函数获得位置，然后与此位置的关键码进行比较。相等则成功。

在思想上跟桶排序有很大的关系，但是桶排序的空间浪费很大，所以这里不能直接通过下标确定位置。

哈希函数就是：hash(key)=key%capacity capacity就是存储元素空间的总大小。

负载因子：对于闭散列，基本都是0.几，而开散列，可以到1。负载因子就是有效数据占容器容量的比例。

2.2哈希冲突

但是有哈希冲突，就是有可能不同的关键码，获得的存储位置确实一模一样的，这就是冲洗冲突或哈希相撞

哈希函数的设定方式有很多种，上面只是一种。

直接定址法、除留余数、平方取中、折叠法、随机数法、数学分析法。

而解放方式常见的：闭散列、开散列。

2.2.1闭散列

也叫开放定址法，发生哈希冲突时，如哈希表未满，则一定还有位置，那就把key放在冲突位置的下一个空位置去。注意，哈希结构我们人为的限制不能装满，有一个负载因子\载荷因子做评估，实际元素个数/总空间大小，闭散列一般是0.7，因为如果满了的话，查找效率是O(n)。所以对于元素存储个数达到限制后，一般就直接空间扩容，用空间换取效率

线性探测：

从发生冲突的位置开始，依次向后探测，如果找到的最后一个位置，则跳到空间的开头，直到找到一个空位置。

插入：通过哈希函数获取元素的在哈希表的位置，如果该位置没有元素直接插入，有元素的话利用线性探测获取下一个空位置的地址，然后把该值放进去。

搜索：如果该位置元素不相等，则线性往后找，直到找到\遇到空

删除：闭散列删除的时候，不能直接删,因为我们搜索的逻辑是从直接获得地址开始往后找，这样的话，如果前面一个元素已经被删了，但是我们要查找的元素在后面，这样遇到空就不会继续找，也就不会找到我们要的元素而且我们如何确定删除的状态呢？。所以要采取标记的伪删除法来删除一个元素。

实现代码:

#pragma once
#include<vector>
enum State {EMPTY,EXIST,DELETE
};
template<class K, class V>
struct HashData {pair<K, V> _kv;State _state=EMPTY;//标记该位置状态
};//对于非整数的key，默认采用强转的方式
template<class K>
struct HashFunc {size_t operator()(const K& key){return (size_t)key;}
};
//如果不能通过强制的类型，则单独写个仿函数
//自己写的类，也可以这样。日期类就可以把年月日加起来，中间*权值
//不一定都是成员加起来，像是个人信息，就可以单独把身份证号的ASCII码加起来，中间*权值
//核心就是把非唯一的值尽量拼起来，然后以拼起来的值（中间可以*权值），作为key
//struct HashFuncString {
//	size_t operator()(const string& s) {
//		size_t hash = 0;
//		for (auto e : s)
//		{
//			hash += e;
//			hash *= 131;//权值，否则的话，abcd==dcba,太容易冲突了
//		}
//		return hash;
//	}
//};//一般来说，string经常用，所以直接特化(库里也是这样的，但自己写的类，还是要自己传仿函数)
//而且库里还有一个仿函数，是用来比较两个key是否相等的仿函数
template<>
struct HashFunc<string> {size_t operator()(const string& s) {size_t hash = 0;for (auto e : s){hash += e;hash *= 131;//权值，否则的话，abcd==dcba,太容易冲突了}return hash;}
};
template<class K,class V, class Hash=HashFunc<K>>
class HashTable {
public:HashTable(size_t size=10) {_tables.resize(size);}HashData<K,V>* Find(const K&key){Hash hs;//线性探测size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state!=EMPTY){if (key == _tables[hashi]._kv.first && _tables[hashi]._state == EXIST){return &_tables[hashi];}hashi++;hashi %= _tables.size();}return nullptr;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//如果负载因子大于等于0.7要扩容if (_n*10 / _tables.size() >= 7){HashTable<K, V,Hash>newHT(_tables.size() * 2);//遍历旧表，插入新表for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}//最后交换，旧表在newHT出了作用域之后，//newHT会自动调用析构//这里也不用特意写析构，因为默认生成的析构足够了//vector会调用vector的析构函数，int类型内置类型_tables.swap(newHT._tables);}Hash hs;//线性探测size_t hashi = hs(kv.first)%_tables.size();while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){_n--;ret->_state = DELETE;return true;}else{return false;}}
private:vector<HashData< K,V>>_tables;size_t _n;//实际存储的数据个数
};void TestHT1() {int a[] = { 1,4,24,34,45,7,44,17,37 };HashTable<int, int>ht;for (auto& e : a){ht.Insert(make_pair(e, e));}for (auto& e : a){auto ret = ht.Find(e);cout << ret->_kv.first << ":" << ret->_state << endl;}ht.Erase(34);ht.Erase(4);cout << endl;for (auto& e : a){auto ret = ht.Find(e);if (ret)cout << ret->_kv.first << ": EXIST" << endl;else cout << e << ": DELETE" << endl;}}
void TestHT2() {HashTable<string,string>ht;ht.Insert(make_pair("dwadwa", "dwadwa"));ht.Insert(make_pair("dsxzdwa", "dwadwa"));
}

二次探测：在线性探测的基础上，每次跨越的步伐更加大些。

线性探测是：hashi+i,i>=0,二次探测就是hashi+i^2,i>=0

让整个空间的存放更加均匀，而不是挤在某一块

结论：

在闭散列的结构下，这些探测本质还是一种互相挤占空间的方式，近似恶意循环。

2.2.2开散列

相对于闭散列，开散列不将冲突的值放其他位置，开散列下，每个空间都是一个链表，这个链表里存哈希值相同的元素

结构很清晰，就是利用链式结构。

2.2.2.1哈希文件

这是底层头文件，后面的unordered_map和unordered_set模拟，都是在这个头文件的基础上封装的

#pragma once
#include<vector>
//对于非整数的key，默认采用强转的方式
template<class K>
struct HashFunc {size_t operator()(const K& key){return (size_t)key;}
};
//如果不能通过强制的类型，则单独写个仿函数
//自己写的类，也可以这样。日期类就可以把年月日加起来，中间*权值
//不一定都是成员加起来，像是个人信息，就可以单独把身份证号的ASCII码加起来，中间*权值
//核心就是把非唯一的值尽量拼起来，然后以拼起来的值（中间可以*权值），作为key
//struct HashFuncString {
//	size_t operator()(const string& s) {
//		size_t hash = 0;
//		for (auto e : s)
//		{
//			hash += e;
//			hash *= 131;//权值，否则的话，abcd==dcba,太容易冲突了
//		}
//		return hash;
//	}
//};//一般来说，string经常用，所以直接特化(库里也是这样的，但自己写的类，还是要自己传仿函数)
//而且库里还有一个仿函数，是用来比较两个key是否相等的仿函数
template<>
struct HashFunc<string> {size_t operator()(const string& s) {size_t hash = 0;for (auto e : s){hash += e;hash *= 131;//权值，否则的话，abcd==dcba,太容易冲突了}return hash;}
};
namespace openadress {enum State {EMPTY,EXIST,DELETE};template<class K, class V>struct HashData {pair<K, V> _kv;State _state = EMPTY;//标记该位置状态};template<class K, class V, class Hash = HashFunc<K>>class HashTable {public:HashTable(size_t size = 10) {_tables.resize(size);}HashData<K, V>* Find(const K& key){Hash hs;//线性探测size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (key == _tables[hashi]._kv.first && _tables[hashi]._state == EXIST){return &_tables[hashi];}hashi++;hashi %= _tables.size();}return nullptr;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//如果负载因子大于等于0.7要扩容if (_n * 10 / _tables.size() >= 7){HashTable<K, V, Hash>newHT(_tables.size() * 2);//遍历旧表，插入新表for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}//最后交换，旧表在newHT出了作用域之后，//newHT会自动调用析构//这里也不用特意写析构，因为默认生成的析构足够了//vector会调用vector的析构函数，int类型内置类型_tables.swap(newHT._tables);}Hash hs;//线性探测size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){_n--;ret->_state = DELETE;return true;}else{return false;}}private:vector<HashData< K, V>>_tables;size_t _n;//实际存储的数据个数};
}
namespace hash_bucket {//数据量很大的时候，table的每个位置，可以不挂单链表，而是直接挂红黑树。//这样就算遇到极端情况，查找效率也很高。//从复用角度看，如果不想自己手搓，可以直接让Node//里面分别放list(),set(),当前桶里元素个数超过8个，遍历放入set里。//然后list.clear(),反之，放入list(),set.clear();template<class T>struct HashNode {HashNode<T>* _next;T _data;HashNode(const T&data):_next(nullptr), _data(data){}};//前置声明，因为下面迭代器类typedef了哈希表类，但是哈希表类下迭代器类的下面。//编译器找不到，也就识别不了迭代器类里的哈希表//但单纯两者对换也不行，因为哈希表类里也typedef了迭代器类//这样的话，互相引用。解决方法就是把处于下面的哈希表类进行前置声明//这样编译器就能识别了template<class K, class T, class KeyOfT, class Hash>class HashTable;template<class K, class T, class KeyOfT, class Hash>struct _HTIterator {size_t hti;typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef _HTIterator<K, T, KeyOfT, Hash> Self;HT* _ht;Node* _node;_HTIterator(Node* node, HT* ht):_node(node), _ht(ht){}T& operator*() {return _node->_data;}T* operator->() {return &_node->_data;}Self& operator++() {if (_node->_next){//当前桶没有走完_node = _node->_next;}else{//当前桶走完了，找下一个KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();hashi++;//找下一个桶while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}hashi++;}//后面没有桶了if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}bool operator!=(const Self& s){return _node != s._node;}};template<class K, class T, class KeyOfT,class Hash>class HashTable {template<class K, class T, class KeyOfT, class Hash>friend struct _HTIterator;typedef HashNode<T> Node;public:typedef _HTIterator<K, T, KeyOfT, Hash> iterator;iterator begin() {for (size_t i = 0; i < _tables.size(); i++){//从左往右，第一个桶if (_tables[i]){return iterator(_tables[i], this);}}return end();}iterator end() {return iterator(nullptr, this);}//素数大小的容器，没有定论，vs下没有这样int GetNextPrimer(size_t val) {const int prime[28] = { 53,97,193,389,769,1543,3079,6151,12289,24593,49157,98317,196613,393241,786433,1572869,3145739,6291469,12582917,25165843,50331653,100663319,201326611,402653189,805306457,1610612741,3221225473,4294967291 };for (int i = 0; i < 28; i++){if (prime[i] > val)return prime[i];}return prime[27];}HashTable() {_tables.resize(GetNextPrimer(1), nullptr);_n = 0;}~HashTable() {//一个个桶找过来，诶个释放for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}//为了用[]的结构pair<iterator,bool> Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it!=end()){return make_pair(it,false);}Hash hs;if (_n == _tables.size()){//这里不复用insert，是vector里的每个地址指向的空间//在复用的时候，都要经历new n个节点，析构n个节点。//消耗很大vector<Node*>newTables(GetNextPrimer(_n), nullptr);//遍历旧表，头插新表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);//头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode,this),true);}iterator Find(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){//这里其实还要再配一个比较的仿函数的if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return end();}iterator Erase(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev){prev->_next = cur->_next;delete cur;--_n;if(prev->_next)return iterator(prev->_next,this);else{for (size_t i = hashi+1; i < _tables.size(); i++){//从左往右，第一个桶if (_tables[i]){return iterator(_tables[i], this);}}return end();}}else{_tables[hashi] = cur->_next;delete cur;--_n;if(_tables[hashi])return iterator(_tables[hashi], this);else{for (size_t i = hashi+1; i < _tables.size(); i++){//从左往右，第一个桶if (_tables[i]){return iterator(_tables[i], this);}}return end();}}}prev = cur;cur = cur->_next;}return end();}private://vector<list<pair<K,V>>>_tables;可行，但自己写个也不错vector<Node*>_tables;//指针数组size_t _n;};}

2.2.2.2unordered_map模拟

#pragma once
#include"newHashTable.h"namespace bit {template<class K, class V,class Hash=HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;iterator begin() {return _ht.begin();}iterator end() {return _ht.end();}pair<iterator, bool> Insert(const pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = Insert(make_pair(key, V()));return ret.first->second;}iterator Find(const K& key){return _ht.Find(key);}iterator erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT,Hash>_ht;};
}

2.2.2.3unordered_set模拟

#pragma once
#include"newHashTable.h"namespace bit {template<class K,class Hash=HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;iterator begin() {return _ht.begin();}iterator end() {return _ht.end();}pair<iterator,bool> Insert(const K& key){return _ht.Insert(key);}iterator Find(const K& key){return _ht.Find(key);}iterator erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT,Hash>_ht;};void test_set1() {unordered_set<int>us;for (int i = 0; i < 200; i++)us.Insert(i);unordered_set<int>::iterator it = us.begin();while (it != us.end()){cout << (*it) << endl;++it;}}
}

3.位图

位图，就是每一位用来存放状态，适用于海量数据，数据不重复。一般是查找数据在不在。思想也是用哈希实现。库里也有实现，是bitset。

这里是用的直接定址法。所以开多大取决于数据范围，而不是数据量

位图可以用在什么地方？

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

接下来是具体的模拟，附带几道变形题

模拟

#pragma once
#include<vector>
#include<cassert>namespace bit {template<size_t N>class bitset {public://不用担心负数的问题，负数会转成size_t,还是可以做映射的。//bitset() {_bits.resize(N / 32 + 1, 0);}//把x映射的标记为1void set(size_t x){assert(x <= N);//因为没法开位数组，所以必须开int的话，要以32位为一组，分为存储。size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);//利用或，有1为1，让1左移j位，此时二进制位上，第j位是1，其他为0，然后让这个数跟_bits[i]或以下，这样就能让第i个整形，第j位修改为1//或许会疑惑，为什么不是32-j，因为左移是向高位移动，所以不管是小端机还是大端机，都一样。x%32，得到的是从低位到x的距离，整个内部存储，//映射不是线性的。}//把x映射的标记为0void reset(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;//跟上面类似，只是这里要让_bits[i]与上一个11111110111111111_bits[i] &= ~(1 << j);}//查找数是不是存在bool Test(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;//这里不修改，只探测，返回一个整型值，整型值转bool，非0真，0假。所以只要该二进制位为1，那最后返回就是真，为0就是假。return _bits[i] & (1 << j);}private:vector<int>_bits;};void test_bitset() {bitset<31>mp;mp.set(30);mp.set(20);mp.set(10);for (int i = 1; i <= 30; i++){if (mp.Test(i)){cout <<i<< "在" << endl;}else{cout <<i<< "不在" << endl;}}mp.reset(30);mp.set(29);for (int i = 1; i <= 30; i++){if (mp.Test(i)){cout << i << "在" << endl;}else{cout << i << "不在" << endl;}}}// 给定100亿个整数，设计算法找到只出现一次的整数？template<size_t N>class two_bitset {public:void set(size_t x){//00 0次，01 1次,10 2次及以上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);}}int test(size_t x){if (_bs1.Test(x) == false && _bs2.Test(x) == false)return 0;else if (_bs1.Test(x) == false && _bs2.Test(x) == true) {return 1;}else return 2;}private:bitset<N>_bs1;bitset<N>_bs2;};void test_two_bitset() {two_bitset<100>mp;int a[] = { 2,4,4,56,65,45,56,76,67,76 };for (auto e : a){mp.set(e);}for (auto e : a){cout << mp.test(e) << endl;}}
}

应用

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

依旧是利用位图，代码不写了，直接写思路。两个位图，两个文件分别存值，然后看是否两个位图里都存在这个数。存在就是交集，否则就不是交集一部分。

注意，不要被100亿数字吓到，整数，这里默认都是int范围的，也就是说位图肯定是可以存的，那这100亿有很多重复的数字，是不用管的，默认去重了。

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

是第一道题的变形，只是00 0次,01 1次, 10 2次 11 3次及以上

对于第一个问题，我们还可以限制内存大小，比如100亿，1G是够的，但是如果只让用512M呢？我们的思路是多批次读取，每次只统计一段范围的值。比如0-2^31-1是512M,2^31-2^32-1也是512M。这样每次读取都只用到512M。

4.布隆过滤器

主要是对位图的一个小修改，位图对于非整型数据，虽然也能存（通过转换成整型再映射的方式，但是冲突的概率很大），所以布隆的主要思想就是让单个数据映射多个位置，只要多个位置有一个位0，则一定不存在。多个位置全为1，只有很低的概率才是不存在，大概率是存在的。只要让映射的位置变多，冲突的概率就变小了。

模拟
#pragma once
#include<bitset>
#include<string>
struct HashFuncBKDF {//BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 131;}return hash;}
};
struct HashFuncAP {//APsize_t operator()(const string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++){//偶数位if ((i & 1) == 0){hash ^= ((hash << 7)) ^ (s[i]) ^ (hash >> 3);}//奇数位else{hash ^= (~(hash << 11)) ^ (s[i]) ^ (hash >> 5);}}return hash;}
};
struct HashFuncDJB {//DJBsize_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash = hash * 33 ^ ch;}return hash;}
};
template<size_t N, class K = string, class Hash1 =HashFuncBKDF, class Hash2= HashFuncAP, class Hash3 = HashFuncDJB>
class BloomFilter {
public:void Set(const K& key){size_t hash1 = Hash1()(key) % M;size_t hash2 = Hash2()(key) % M;size_t hash3 = Hash3()(key) % M;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool Test(const K& key){size_t hash1 = Hash1()(key) % M;if (_bs.test(hash1) == false)return false;size_t hash2 = Hash2()(key) % M;if (_bs.test(hash2) == false)return false;size_t hash3 = Hash3()(key) % M;if (_bs.test(hash3) == false)return false;//不存在是准确的return true;//存在是有可能误判的,因为可能这3个映射位置都跟别的冲突了//这也是为什么说映射位置增加在一定程度上是可以减少误判概率的}//为什么不实现reset？//因为删了某一个，会影响与他有冲突的元素，导致该元素被误判成不存在。
private://这里开多大，知乎上有一个大佬做了分析//https://zhuanlan.zhihu.com/p/43263751/static const size_t M = 8 * N;//为什么要用static？因为就算是常量，在这里也只是类里面的成员的声明，//在不实例化前是不占空间的，也就是说不会在常量区里面存放，这样编译器//就无法在常量区中找到他，无法找到，就说明这不是个常量，而bitset内部也是数组//存储，数组的大小必须是常量，所以只const，是会报错的//而static，是不属于单个对象，而是整个类的，就算没有实例化，他也是占据空间的。bitset<M> _bs;};void TestBloomFilter()
{string x[] = { "西瓜","苹果","梨子" };BloomFilter<10>bf;for (auto& s : x){bf.Set(s);}for (auto& s : x){cout << bf.Test(s) << endl;}for (auto& s : x){cout << bf.Test(s+" ") << endl;}
}
这里说个题外话，stl里的bitset，一千万级是可能栈溢出的，因为stl里是把数据放在栈上，用的是静态数组，而不是vector，可以实测，sizeof库里的bitset和我上面实现的bitset。

为什么可以测出是在栈上而不是堆上？我也不是很清楚，对这方面可以看下这篇文章

程序员应了解的那些事（9） STL vector：sizeof(vector)分析 + sizeof小结-CSDN博客

那实际使用的时候不想手撕怎么办，可以让布隆的成员bitset，以指针的形式存在，然后new一个就好，这样bitset就放在堆上了。

这里总结下布隆过滤器

优点：

1.增加和查询元素的时间复杂度O(K),K是哈希函数的个数，一般比较小。与数据量大小无关

2.哈希函数相互之间没有关系，方便硬件并行运算

3.布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

4.在能够承受一定的误判时，布隆过滤器比其他数据结构有很大的空间优势

5.数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

6.使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺陷：

1.有误判率，有个说法叫假阳性（False，Position），只能准确判断元素不在集合中，不能准确判断元素在集合中，（可以建立白名单，存储可能误判的数据）

2.不能获取元素本身

3.一般情况下不能从布隆过滤器中删除元素

4.如果采用计数方式删除，存在计数回绕问题。

应用

对于一些特殊场景，虽然不容忍误判，但是布隆过滤器还是可以做到减少数据库压力的作用。因为布隆过滤器判断不在，那一定是不在，可以直接返回结果，如果判断在，再去数据库进行查找，实现减少数据库压力的作用

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

近似算法，采用布隆过滤器，在，就是在，不在就是不在，因为有误判可能，所以只能是近似算法。

而精确算法：布隆做不到，而用哈希map或者红黑树等，也不现实，因为100亿个查询，就算一个查询只占50字节，那也是相当高的占用空间，所以还是采用哈希的思想，用哈希切分，将大文件差分成小文件，利用哈希函数，映射查询，将大文件拆分下来的文件进行编号，让哈希值做编号，对应查询放入对应的小文件中，因为哈希函数对同一个查询返回的哈希值一定是相同的，所以对于交集，只需要两个大文件A和B的每个Ai和Bi放入内存比较即可（这时候用红黑树、平衡树、哈希表等等，都可以）。具体操作，可以试着把100亿的文件，拆成1000份，也就是hash函数%的数是1000，之所以不拆500份，是因为查询的占据空间不是一样的，有些文件很大，有些文件很小，如果拆成500份，冲突多的话，两个文件会超过1g，就不能放入内存了，这样拆成1000份，就可以让冲突的可能性降低，如果冲突多，可以考虑%1000以上）

但是还是有极端情况，比如某些查询的值想当接近，导致某个文件过大，还是超过了1g，这时候如果对这个文件再次进行哈希切分，效果不大，因为在这个情况下，不管是什么哈希函数，最后还是可能会分到一个文件，还是超过了1g。这个问题其实不用管太多，因为如果是因为查询的值过于接近、冲突过多，导致的Ai文件过大，那直接读入bitset，或者set，map等，都是可以直接读的，因为这些容器基本都是去重的，虽然这个文件可能很大，但是去掉重复，也就那么点。

如果是大于1g，且重复内容不多的文件，那么才可以采取最开始说的，二次哈希切分，换个哈希函数。

总结下，对于冲突多的，采用二次哈希切分。对于重复多的，采用set、map、bitset等可以去重的容器读取文件即可。这也是哈希切分下来，某个文件过大的处理方案
2. 如何扩展BloomFilter使得它支持删除元素的操作

可以用引用计数的方式，这样就可以让布隆支持删除，但是这样空间消耗会大很多，一个标记要开8位。极端情况，消耗跟红黑树之类的差不多，这样就没有意义了

3.给一个超过100G大小的log文件，log中存着ip地址，设计算法找到出现次数最多的ip地址，并且如何找到top k的ip

这题跟上一次的思路是相似的。同样是哈希切分，让相同ip进入相同的文件，一个文件只会是相同的ip和有冲突的ip。这时候用map读文件，虽然没有限制内存，但是map的容量也是有限的，并且极端情况可能出现一个文件很大（因为冲突多而不是重复多，重复多放map里，只是让value++罢了），所以map有几率爆，这时候采取二次处理，即换个哈希函数，再次对该小文件进行哈希切分。而找到出现次数多的ip，只需要让每个文件挨个放进map计数即可，就可以知道答案了。而对于top k的ip，则只需要弄个优先队列的小堆，自己写个仿函数或比较函数即可。

结论：

海量数据问题特征：数据量大，单台机器内存存不下

1.先考虑是否有合适的数据结构可以解决，比如位图、堆、布隆过滤器等等

2.大事化小思路。哈希切分（不能平均切分，就算可以复杂度也很高，效率很慢，有些问题就算平均切分了，也无法解决)，切小之后，就能放内存中处理了