哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素
时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($lo{g}_{2}N$)，搜索的效率取决于搜索过程中元素的比较次数 。而我们知道数组即顺序表的随机访问是非常快的，如果我们存放的元素能和数组下标建立关系，那么查询效率可以达到理想极致的0(1).

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射的关系，那么在查找时通过该函数可以很快找到该元素

当向该结构中

• 插入元素

  ​ 根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

• 搜索元素

  ​ 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
  取元素比较，如果元素相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

例如：数据集合{1，7，6，4，5，9}；
哈希函数(hashFunc)设置为：hash(key) = key % sz; sz为开辟空间的大小.

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题 ？

会出现下标为4的位置已经有元素存储了，那么44该怎么存储呢?-----这种现象称为哈希冲突

哈希冲突

对于不同的关键子，通过同一个哈希函数，映射到同一位置的现象称为为哈希冲突/哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

哈希函数

1. 哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
2. 引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
   哈希函数设计原则：

1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
2. 哈希函数计算出来的地址能均匀分布在整个空间中
3. 哈希函数应该比较简单

除留余数法–(非常常用)

1. 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
   按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
2. 由于%的特性，除留余数法在哈希分割文件，布隆过滤器等都有使用

直接定址法–(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

平方取中法–(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

折叠法–(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

随机数法–(了解)

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法

数学分析法–(了解 ）

**设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。**例如：

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移
位、前两数与后两数叠加(如1234改成12+34=46)等方法。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

实际中更多的是使用开散列 解决哈希冲突。

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 ？

线性探测与二次探测

线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

插入
通过哈希函数获取待插入元素在哈希表中的位置.如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素 .

如插入44

删除：

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用状态法标记的伪删除法来删除一个元素。

enum   Status
{
EMPTY,
DELETE,	 
EXIT
};

二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位
置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法
为：$H_i$ = ($H_0$ + $i^2$ )% m, 或者：$H_i$ = ($H_0$ - $i^2$ )% m。其中：i =
1,2,3…， $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
对于2.1中如果要插入44，产生冲突，使用解决后的情况为：

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在
搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

闭散列代码

关键码函数

很明显当关键码是整形时，通过哈希映射非常简单，但是对于字符串类呢?

我们可以通过某个函数来获得字符串对应的整形，毕竟字符是一种asicc码。

template<class K>
struct DefaultHashFun
{size_t operator()(const K&k){return k;}
};
//特化
template<>
struct DefaultHashFun <string>
{size_t operator()(const string& str){size_t Hashi = 0;for (auto e : str){Hashi = Hashi * 131 + e;}return Hashi;}
};

扩容

当数组接近满时，闭散列的插入发生冲突的概率会逐渐变大，因此我们一把通过负载因子来控制数组的扩容。

负载因子=有效的元素个数/散列表的长度

if (_table.size()==0 || (double)_n / (double)_table.size() >0.7){//扩容int newsize = _table.size() == 0 ? 10 : 2 * _table.size();HashTable newHT;newHT._table.resize(newsize);for (auto & e : _table){if (e._status == EXIT){newHT.Insert(e._kv);}	}newHT._table.swap(_table);}

插入

bool Insert(const pair<K, V>& kv){if (_table.size()==0 || (double)_n / (double)_table.size() >0.7){//扩容int newsize = _table.size() == 0 ? 10 : 2 * _table.size();HashTable newHT;newHT._table.resize(newsize);for (auto & e : _table){if (e._status == EXIT){newHT.Insert(e._kv);}	}newHT._table.swap(_table);}int Hashi = DHF()(kv.first) % _table.size();int i = 1;while (_table[Hashi]._status == EXIT){Hashi = Hashi + i * i;//二次探测++i;Hashi%= _table.size();}_table[Hashi]._kv = kv;_table[Hashi]._status = EXIT;++_n;return true;}

删除

bool Erase(const K& k){auto ret = Find(k);if (ret){ret._status = DELETE;--_n;return true;}else{return false;}}

find

data* Find(const K&k){if (_table.size() == 0){return nullptr;}int Hashi = DHF()(k) % _table.size();int i = 1;//有负载因子存在，不会死循环while (_table[Hashi]._status!= EMPTY){if (_table[Hashi]._status != DELETE && _table[Hashi]._kv.first == k){return &_table[Hashi];}Hashi = Hashi + i*i;//二次探测++i;Hashi %= _table.size();}return nullptr;}

全部代码

enum   Status
{EMPTY,DELETE,EXIT
};
template<class K, class V>
struct  HashData
{pair<K,V> _kv= pair<K, V>();Status _status = EMPTY;
};
template<class K>
struct DefaultHashFun
{size_t operator()(const K&k){return k;}
};
//特化
template<>
struct DefaultHashFun <string>
{size_t operator()(const string& str){size_t Hashi = 0;for (auto e : str){Hashi = Hashi * 131 + e;}return Hashi;}
};template<class K,class V,class DefaultHashFun>
class HashTable
{public:typedef   HashData<K, V> data;typedef   DefaultHashFun DHF;bool Insert(const pair<K, V>& kv){if (_table.size()==0 || (double)_n / (double)_table.size() >0.7){//扩容int newsize = _table.size() == 0 ? 10 : 2 * _table.size();HashTable newHT;newHT._table.resize(newsize);for (auto & e : _table){if (e._status == EXIT){newHT.Insert(e._kv);}	}newHT._table.swap(_table);}int Hashi = DHF()(kv.first) % _table.size();int i = 1;while (_table[Hashi]._status == EXIT){Hashi = Hashi + i * i;//二次探测++i;Hashi%= _table.size();}_table[Hashi]._kv = kv;_table[Hashi]._status = EXIT;++_n;return true;}data* Find(const K&k){if (_table.size() == 0){return nullptr;}int Hashi = DHF()(k) % _table.size();int i = 1;//有负载因子存在，不会死循环while (_table[Hashi]._status!= EMPTY){if (_table[Hashi]._status != DELETE && _table[Hashi]._kv.first == k){return &_table[Hashi];}Hashi = Hashi + i*i;//二次探测++i;Hashi %= _table.size();}return nullptr;}bool Erase(const K& k){auto ret = Find(k);if (ret){ret._status = DELETE;--_n;return true;}else{return false;}}
private:vector<data> _table;size_t _n=0;//有效数据的个数
};

开散列

1.开散列是：指针数组加链表的结合，空间利用率非常高，而且很好控制

2. 开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
3. 开散列中每个桶中放的都是发生哈希冲突的元素

开散列中每个桶中放的都是发生哈希冲突的元素

代码

Insert

1.桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

2. 当扩容时，我们需要重新哈希，可以选择一个一个重新插入，也可以选择直接使用利用原始数组中的旧数据，重新哈希即可

pair <iterator ,bool>Insert(const T&data){//移动节点auto pos = Find(KFT()(data));if (pos!=end())return make_pair(pos, false);size_t sz = _table.size();if (_n ==sz){size_t newsize =sz == 0 ? 10 : 2 * sz;Self HT;HT._table.resize(newsize, 0);for (size_t i = 0; i < sz; ++i){Node* cur = _table[i];while (cur){int Hashi = HF()(KFT()(cur->_data)) % newsize;cur->_next = HT._table[Hashi];HT._table[Hashi] = cur;cur = cur->_next;}_table[i] = nullptr;//防止浅拷贝,局部变量释放时的的野指针问题}HT._table.swap(_table);}int Hashi = HF()(KFT()(data)) % _table.size();Node* newNode = new Node(data);newNode->_next = _table[Hashi];_table[Hashi] = newNode;++_n;return make_pair(iterator(newNode, this), true);}

Find

iterator Find(const K& key){if (_table.size() == 0){return iterator(nullptr, this);}int sz = _table.size();int Hashi = HF()(key) % sz;Node* cur = _table[Hashi];while (cur && KFT()(cur->_data) != key){cur = cur->_next;}return iterator(cur, this);}

Erase

bool Erase(const K& key){assert(_table.size());int Hashi = HF()(key) % _table.size();Node* pre = nullptr;Node* cur = _table[Hashi];while (cur){if (KFT()(cur->_data) == key){if (pre == nullptr){_table[Hashi] = cur->_next;}else{pre->_next = cur->_next;}delete cur;--_n;return true;}else{pre = cur;cur = cur->_next;}}return false;}

迭代器

当前桶访问完时，我们要计算下一个桶，而节点的地址我们知道了，可以直接确定当前桶的位置，为了确定下一个非空桶，我们需要一个指向哈希表的指针

同时为了访问方便，我们还需要将迭代器在哈希表中内置为友元类

template<class K, class Ref, class Ptr, class T, class KeyOfType, class HashFunc = DefaultHashFunc<K> >class  HT_Iterator{public:typedef HashNode<T>  Node;typedef KeyOfType KFT;typedef HashFunc HF;typedef my_hash::HT_Iterator<K, Ref, Ptr, T, KFT, HF> Self;typedef my_hash::HashTable<K, T, KFT, HF> HT;HT_Iterator() = default;HT_Iterator(Node* node = nullptr, const HT* ht = nullptr):_node(node), _ht(ht){;}HT_Iterator(const Self& self){_node = self._node;_ht = self._ht;}Self& operator++(){Node* pre = _node;_node = _node->_next;if (_node == nullptr){size_t Hashi = HF()(KFT()(pre->_data)) % _ht->_table.size();while (_node == nullptr && ++Hashi < _ht->_table.size()){_node = _ht->_table[Hashi];}if (Hashi == _ht->_table.size()){_node = nullptr;}}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator==(const Self& self){return _node == self._node;}bool operator!=(const Self& self){return _node != self._node;}Node* _node;const HT* _ht;};

全部代码

namespace my_hash
{template<class K>struct DefaultHashFunc{size_t operator()(const K& k){return k;}};//特化template<>struct DefaultHashFunc <string>{size_t operator()(const string& str){size_t Hashi = 0;for (auto e : str){Hashi = Hashi * 131 + e;}return Hashi;}};template<class T>struct HashNode{HashNode(const T& data = T()):_data(data){}T _data;HashNode* _next = nullptr;};template<class K, class T, class KeyOfType, class HashFunc = DefaultHashFunc<K>>class HashTable;//声明，方便迭代器中定义Hash表的指针template<class K, class Ref, class Ptr, class T, class KeyOfType, class HashFunc = DefaultHashFunc<K> >class  HT_Iterator{public:typedef HashNode<T>  Node;typedef KeyOfType KFT;typedef HashFunc HF;typedef my_hash::HT_Iterator<K, Ref, Ptr, T, KFT, HF> Self;typedef my_hash::HashTable<K, T, KFT, HF> HT;HT_Iterator() = default;HT_Iterator(Node* node = nullptr, const HT* ht = nullptr):_node(node), _ht(ht){;}HT_Iterator(const Self& self){_node = self._node;_ht = self._ht;}Self& operator++(){Node* pre = _node;_node = _node->_next;if (_node == nullptr){size_t Hashi = HF()(KFT()(pre->_data)) % _ht->_table.size();while (_node == nullptr && ++Hashi < _ht->_table.size()){_node = _ht->_table[Hashi];}if (Hashi == _ht->_table.size()){_node = nullptr;}}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator==(const Self& self){return _node == self._node;}bool operator!=(const Self& self){return _node != self._node;}Node* _node;const HT* _ht;};template<class K, class T, class KeyOfType, class HashFunc>class HashTable{typedef HashNode<T>  Node;typedef HashFunc HF;typedef KeyOfType KFT;typedef HashTable<K, T, KFT, HF> Self;template<class K, class Ref, class Ptr, class T, class KeyOfType, class HashFunc >friend class  HT_Iterator;public:typedef  my_hash::HT_Iterator<K, T&, T*, T, KFT, HF> iterator;typedef  my_hash::HT_Iterator<K, const T&, const T*, T, KFT, HF> const_iterator;iterator begin(){size_t i = 0;for (; i < _table.size(); ++i){if (_table[i])//第一个非空通{return iterator(_table[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}const_iterator  begin()const{size_t i = 0;for (; i < _table.size(); ++i){if (_table[i])//第一个非空通{return const_iterator(_table[i], this);}}return end();}const_iterator end()const{return const_iterator(nullptr, this);}public:HashTable() = default;HashTable(const Self& HT)//需要深拷贝{int sz = HT._table.size();for (int i = 0; i < sz; ++i){Node* cur = HT._table[i];while (cur){Insert(cur->_kv);cur = cur->_next;}}_n = HT._n;}Self& operator=(Self HT){HT._table.swap(_table);_n = HT._n;return *this;}~HashTable(){for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}//插入pair <iterator ,bool>Insert(const T&data){//移动节点auto pos = Find(KFT()(data));if (pos!=end())return make_pair(pos, false);size_t sz = _table.size();if (_n ==sz){size_t newsize =sz == 0 ? 10 : 2 * sz;Self HT;HT._table.resize(newsize, 0);for (size_t i = 0; i < sz; ++i){Node* cur = _table[i];while (cur){int Hashi = HF()(KFT()(cur->_data)) % newsize;cur->_next = HT._table[Hashi];HT._table[Hashi] = cur;cur = cur->_next;}_table[i] = nullptr;//防止浅拷贝,局部变量释放时的的野指针问题}HT._table.swap(_table);}int Hashi = HF()(KFT()(data)) % _table.size();Node* newNode = new Node(data);newNode->_next = _table[Hashi];_table[Hashi] = newNode;++_n;return make_pair(iterator(newNode, this), true);}iterator Find(const K& key){if (_table.size() == 0){return iterator(nullptr, this);}int sz = _table.size();int Hashi = HF()(key) % sz;Node* cur = _table[Hashi];while (cur && KFT()(cur->_data) != key){cur = cur->_next;}return iterator(cur, this);}bool Erase(const K& key){assert(_table.size());int Hashi = HF()(key) % _table.size();Node* pre = nullptr;Node* cur = _table[Hashi];while (cur){if (KFT()(cur->_data) == key){if (pre == nullptr){_table[Hashi] = cur->_next;}else{pre->_next = cur->_next;}delete cur;--_n;return true;}else{pre = cur;cur = cur->_next;}}return false;}private:vector<Node*> _table;size_t _n = 0;};
}

闭散列与开散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <=0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间 。

unordered_set的封装

namespace my_set
{template<class K>struct KeyOfType{const K& operator()(const K& key){return key;}};template<class K>class unorder_set{typedef  my_set::KeyOfType<K> KFT;typedef K T;typedef my_hash::DefaultHashFunc<K> HF;public:typedef typename my_hash::HashTable<K, T, KFT, HF>::const_iterator   iterator;typedef typename my_hash::HashTable<K, T, KFT, HF>::const_iterator   const_iterator;~unorder_set(){HT.~HashTable();}iterator begin()const{return HT.begin();}iterator end()const{return HT.end();}pair<iterator, bool>  Insert(const K& key){auto p = HT.Insert(key);// HT不可能实现一个const版的insert，因此要间接实现return 	make_pair(iterator(p.first._node, p.first._ht), p.second);}bool Erase(const K& key){return 	HT.Erase(key);}T* Find(const K& key){return HT.Find(key);}private:my_hash::HashTable<K, T, KFT, HF> HT;};void SetT(){unorder_set<int> set;set.Insert(2);set.Insert(3);set.Insert(4);set.Insert(5);set.Insert(6);set.Insert(7);set.Insert(8);set.Insert(9);set.Insert(12);set.Insert(13);set.Insert(14);unorder_set<int>::iterator it = set.begin();unorder_set<int>::iterator it2(it);while (it != set.end()){cout << *it << endl;++it;}}
}

unordered_map的封装

#pragma once
#include "Hash.h"namespace my_map
{template<class K, class V>struct KeyOfType{const K& operator()(const pair<const K, V>& kv){return kv.first;}};template<class K, class V>class unorder_map{typedef my_map::KeyOfType<K, V> KFT;typedef pair< K, V>  T;typedef my_hash::DefaultHashFunc<K> HF;public:typedef typename my_hash::HashTable<K, T, KFT, HF>::iterator iterator;typedef typename my_hash::HashTable<K, T, KFT, HF>::const_iterator const_iterator;iterator begin(){return HT.begin();}const_iterator begin()const{return HT.begin();}iterator end(){return HT.end();}const_iterator end()const{return HT.end();}~unorder_map(){HT.~HashTable();}pair<iterator, bool>  Insert(const T& data){return 	HT.Insert(data);}V& operator[](const K& key){return HT.Insert(make_pair(key, V())).first->second;}bool Erase(const K& key){return 	HT.Erase(key);}T* Find(const K& key){return HT.Find(key);}private:my_hash::HashTable<K, T, KFT, HF> HT;};/*void  MapT(){unorder_map<int, int> map;map[2] = 1;map[3] = 1;map[4] = 1;map[5] = 1;map[6] = 1;map[7] = 1;unorder_map<int, int>::iterator it = map.begin();while (it != map.end()){cout << it->first << " " << it->second << endl;++it;}}*/void MapT(){unorder_map<string, string> map;map["hello"] = "你好";map["word"] = "世界";map["helloword"] = "你好世界";unorder_map<string, string> ::iterator it = map.begin();while (it != map.end()){cout << it->first << " " << it->second << endl;++it;}}
}

哈希的应用！！！

位图

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

当我们在一个海量数据范围内判断某个数是否存在时，由于不能加载到内存，二分查找不能使用。文件外排序也不行，不支持随机访问。

那么我们该怎么处理呢？

我们知道一个bite位有2种转态0/1，而表示一个数据是否存在也是2种状态，因此我们可以通过某种映射，利用一个bite位1来表示该数存在，0表示不存在。 这样当有10亿个整型数据时，因为我们无法确定最大数据到底多少，因此直接开辟2^32-1个bite也就是 500M。这样同映射我们就可以在0（1）的时间内确定一个数据是否存在

位图代码

template<size_t N>//N代表最大的数据class bit_set{public:bit_set(){_bits.resize(N / 8 + 1, 0);}void set(size_t x)//添加x{if (text(x))return;size_t i = x / 8;//在哪个字节附近size_t j = x % 8;//相对i的距离_bits[i] |= (1 << j);//，因为0这个特殊的数字，所以直接位移就是x应该的位置，将对应位置变为1}void reset(size_t x)//删除x{if (!text(x))return;size_t i = x / 8;//在哪个字节附近size_t j = x % 8;//相对i的距离_bits[i] &= ~(1 << j);}bool text(size_t x){size_t i = x / 8;//在哪个字节附近size_t j = x % 8;//相对i的距离//&后为0说明不存在，&后大于0是说明存在return   _bits[i] & (1 << j);}private:std::vector<char> _bits;};

位图的应用

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

位图的局限性

位图对于海量的整形数据的处理很方便，但是对于字符串那个类型就很难处理了，因此为了处理字符串，在位图的基础通过加上哈希函数来即布隆过滤器来处理。

布隆过滤器

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

2. 布隆过滤器是一种近似算法，其对于不存在的数据的判断是准确的对于存在的数据可能存在“误判"，对于这种误判就要到相应的数据系统中查找了

3. 位图越长，哈希函数越多时，发生误判的可能性会越低，该如何选择呢?

如何选择哈希函数个数和布隆过滤器长度

详情请参考：https://zhuanlan.zhihu.com/p/43263751/

布隆过滤器的代码

布隆一般处理字符串，因此默认的数据类下是string，哈希函数的个数由使用者控制。M的值也由使用者控制。

namespace my_bloomfiter
{struct BKDRHash{size_t operator()(const string& s){// BKDRsize_t value = 0;for (auto ch : s){value *= 31;value += ch;}return value;}};struct APHash{size_t operator()(const string& s){size_t hash = 0;for (long 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 DJBHash{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}};//M=(k*N)/ln2template<size_t M, class K=string, class HashFunc1= BKDRHash, class HashFunc2=APHash, class HashFunc3= DJBHash>class BloomFilter{public:void Set(const K& key){//计算该值的映射位置size_t Hashi1 = HashFunc1()(key) % M;size_t Hashi2 = HashFunc2()(key) % M;size_t Hashi3 = HashFunc3()(key) % M;_bts.set(Hashi1);_bts.set(Hashi2);_bts.set(Hashi3);}bool Test(const K& key)//为真不一定就存在，但是为假就一定不存在	{//重新计算该值的映射位置size_t Hashi1 = HashFunc1()(key) % M;if (!_bts.test(Hashi1)){return false;}size_t Hashi2 = HashFunc2()(key) % M;if (!_bts.test(Hashi2)){return false;}size_t Hashi3 = HashFunc3()(key) % M;if (!_bts.test(Hashi3)){return false;}return true;//可能存在误判}private:bitset<M> _bts;};void TestBoolm(){//my_bloomfiter::BloomFilter < string, 44, my_bloomfiter::BKDRHash, my_bloomfiter::APHash, my_bloomfiter::DJBHash> blf;my_bloomfiter::BloomFilter<44> blf;string arr[] = { "苹果","苹果","香蕉","香蕉" ,"苹果","时间","eeeee","eeee","qqqqqq","111111"};for (auto e : arr){blf.Set(e);}for (auto e : arr){if (blf.Test(e)){cout << "存在" << e << endl;}else{cout << "不存在" << e << endl;}}if (blf.Test("芒果")){cout << "存在" << "芒果" << endl;}else{cout << "不存在" << "芒果" << endl;}if (blf.Test("西瓜")){cout << "存在" << "西瓜" << endl;}else{cout << "不存在" << "西瓜" << endl;}if (blf.Test("土豆")){cout << "存在" << "土豆" << endl;}else{cout << "不存在" << "土豆" << endl;}}
}

布隆过滤器的优点

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

布隆过滤器缺陷

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再
   建立一个白名单，存储可能会误判的数据)

2. 不能获取元素本身

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

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

布隆过滤器的删除

布隆过滤器的任务就是过滤掉不存在的数据，如果我们要删除数据，为了不影响其它数据，采用计数的方式进行删除

将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

海量数据面试题

面试题一：

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？与上题条件相同，如何找到top K的IP？

思路:

最多的iP地址：大文件就想到了分割为小文件，但因为存在重复数据的可能，单独分分割会出问题，因此我们可以通过哈希函数将重复的数据放到同一个文化或者桶中，

如果可以通过map第一个文件的去重后建个大堆就可以找出第一个文件的次数最大的ip，之后的文件的map依次于这个堆顶元素比较，大的话就更新这个次数最大的ip

如果建立map时出现内不够问题就再次分割这个小文件，换一个哈希函数，重新上述过程，如果还是不行就进行循环，直到确定最大次数的ip。

Topk

同问题一:只是在对第一个小文件要进行topk，之后将堆顶元素与剩下文件的每一个map的节点进行比较，大于top的就替换top

面试题二：

. 1. 给定100亿个整数，设计算法找到只出现一次的整数？

​ 用2个bite位可以表示4种状态，这里使用2个位图即可

template<size_t N>class bit_sets{bit_sets()=default;//调用自定义类型的构造函数即可void set(size_t x){int bt1 = bst1.test(x);int bt2 = bst2.test(x);if (bt1 == 0 && bt2 == 0)//出现0次{	//0bst2.set(x);//1}else if (bt1 == 0 && bt2 == 1)//出现1次{bst1.set(x);  //1bst2.reset(x);//0}else if (bt1 == 1 && bt2 == 0)//出现2次{//1bst2.set(x);//1}}void reset(size_t x){int bt1 = bst1.test(x);int bt2 = bst2.test(x);if (bt1 == 0 && bt2 == 0){;}else if (bt1 == 0 && bt2 == 1) //00{bst2.reset(x);}else if (bt1 == 1 && bt2 == 0)//01{bst1.reset(x);//0bst2.set(x);  //1}else if (bt1 == 1 && bt2 == 1)//10{		bst2.reset(x);//}}bool test(size_t x){return  bst1.text(x) || bst2.text(x);}private://利用同一位置有4种情况来解决一些问题bit_set<N> bst1;bit_set<N> bst2;};

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

   

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

   同1

面试题三

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

   近似算法：布隆过滤器

   

2. 如何扩展BloomFilter使得它支持删除元素的操作

​ 同上面布隆过滤器的删除