做环境设计的网站,附近电脑培训班零基础,域名备案 填写网站信息吗,购物网站logo致前行路上的人#xff1a; 要努力#xff0c;但不要着急#xff0c;繁花锦簇#xff0c;硕果累累都需要过程#xff01; 目录 1. unordered系列关联式容器 1.1 unordered_map 1.1.1概念介绍#xff1a; 1.1.2 unordered_map的接口说明 1.2unordered_set 1.3常见面试题oj…致前行路上的人 要努力但不要着急繁花锦簇硕果累累都需要过程 目录 1. unordered系列关联式容器 1.1 unordered_map 1.1.1概念介绍 1.1.2 unordered_map的接口说明 1.2unordered_set 1.3常见面试题oj 2.底层结构 2.1 哈希概念 2.2 哈希冲突 2.3哈希函数 2.4哈希冲突解决 2.4.1闭散列 2.4.2开散列 3.模拟实现 3.1哈希表的改造 3.2unordered_map模拟实现 3.3unordered_set模拟实现 4.哈希的应用 4.1位图 4.1.1 位图概念 4.1.2 位图的实现 4.1.3 位图的应用 4.2哈希切割 4.3布隆过滤器 4.3.1布隆过滤器的提出 4.3.2布隆过滤的概念 4.3.3布隆过滤器的插入 4.2.4 布隆过滤器的查找 4.2.5 布隆过滤器删除 4.2.6如何选择哈希函数个数和布隆过滤器长度 4.2.6布隆过滤器优点 4.2.7 布隆过滤器缺陷 4.2.8布隆过滤器的应用场景 4.2.9布隆过滤器代码实现 4.2.10布隆过滤器的面试题 1. unordered系列关联式容器
在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到logN即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同本文中对unordered_map和unordered_set进行介绍unordered_multimap和unordered_multiset使用方式类型类似后面两个相较于前两个不同的是允许数据重复。
1.1 unordered_map
1.1.1概念介绍
1. unordered_map是存储key, value键值对的关联式容器其允许通过keys快速的索引到与其对应的value。 2. 在unordered_map中键值通常用于唯一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。 3. 在内部,unordered_map没有对kye, value按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。 4. unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。 5. unordered_map实现了直接访问操作符(operator[])它允许使用key作为参数直接访问value。 6. 它的迭代器至少是前向迭代器。
1.1.2 unordered_map的接口说明
1. unordered_map的构造
unordered_map 构造不同格式的unordered_map对象
2. unordered_map的容量
bool empty() const检测unordered_map是否为空size_t size() const 获取unordered_map的有效元素个数
3. unordered_map的迭代器
begin返回unordered_map第一个元素的迭代器end 返回unordered_map最后一个元素下一个位置的迭代器cbegin返回unordered_map第一个元素的const迭代器cend 返回unordered_map最后一个元素下一个位置的const迭代器
4. unordered_map的元素访问
operator[] 返回与key对应的value没有一个默认值
注意该函数中实际调用哈希桶的插入操作用参数key与V()构造一个默认值往底层哈希桶 中插入如果key不在哈希桶中插入成功返回V()插入失败说明key已经在哈希桶中 将key对应的value返回。
#include iostream
#include string
#include unordered_mapint main()
{std::unordered_mapstd::string, std::string mymap;mymap[Bakery] Barbara; // new element insertedmymap[Seafood] Lisa; // new element insertedmymap[Produce] John; // new element insertedstd::string name mymap[Bakery]; // existing element accessed (read)mymap[Seafood] name; // existing element accessed (written)mymap[Bakery] mymap[Produce]; // existing elements accessed (read/written)name mymap[Deli]; // non-existing element: new element Deli inserted!mymap[Produce] mymap[Gifts]; // new element Gifts inserted, Produce writtenfor (auto x : mymap) {std::cout x.first : x.second std::endl;}return 0;
}
运行结果 5. unordered_map的查询
iterator find(const K key)返回key在哈希桶中的位置size_t count(const K key)返回哈希桶中关键码为key的键值对的个数
6. unordered_map的修改操作
insert向容器中插入键值对erase删除容器中的键值对clear清空容器中有效元素个数void swap(unordered_map) 交换两个容器中的元素
7. unordered_map的桶操作
size_t bucket_count()const 返回哈希桶中桶的总个数size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数size_t bucket(const K key) 返回元素key所在的桶号
1.2unordered_set
unordered_set文档说明
1.3常见面试题oj
在长度 2N 的数组中找出重复 N 次的元素
class Solution {
public:int repeatedNTimes(vectorint nums) {size_t N nums.size() / 2;unordered_mapint,intm;//统计每个元素出现的次数for(auto e : nums){m[e];}//找到出现N次的元素for(auto e : m){if(e.second N)return e.first;}return -1;}
};
349. 两个数组的交集
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setints1(nums1.begin(),nums1.end());unordered_setints2(nums2.begin(),nums2.end());vectorint result;for(auto e : s1){if(s2.find(e) ! s2.end())result.push_back(e);}return result;}
}; 2.底层结构
unordered系列的关联式容器之所以效率比较高是因为其底层使用了哈希结构。
2.1 哈希概念
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素 时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即 O(log N)搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一 一映射的关系那么在查找时通过该函数可以很快找到该元素。 当向该结构中插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置 取元素比较若关键码相等则搜索成功 该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称 为哈希表(Hash Table)(或者称散列表
例如数据集合{176459}
哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小。 用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快 问题按照上述哈希方式向集合中插入元素44会出现什么问题
2.2 哈希冲突
不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
发生哈希冲突该如何处理呢
2.3哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。哈希函数设计原则 ~哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值 域必须在0到m-1之间 ~哈希函数计算出来的地址能均匀分布在整个空间中 ~哈希函数应该比较简单
常见哈希函数
1. 直接定址法--(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况2. 除留余数法--(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数 按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址、
2.4哈希冲突解决
解决哈希冲突的两种方法闭散列和开散列
2.4.1闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有 空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 呢
1. 线性探测
现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 插入 1.通过哈希函数获取待插入元素在哈希表中的位置 2.如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突 使用线性探测找到下一个空位置插入新元素 扩容 散列表中有一个载荷因子负载因子 散列表元素的个数 / 散列表的长度载荷因子越大产生冲突的可能性就越大载荷因子越小产生冲突的可能性就越小但是可能会造成空间浪费因此一般建议将载荷因子控制在0.7~0.8之间 删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素 会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影 响。因此线性探测采用标记的伪删除法来删除一个元素。
// 哈希表每个空间给个标记
// EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};
线性探测的实现
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};
template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash hash * 131 e;}return hash;}
};enum State
{EMPTY,EXIST,DELETE
};
templateclass K,class V
struct HashData
{pairK, V _kv;State _state EMPTY;
};
templateclass K, class V, class Hash HashFuncK
class HashTable
{typedef HashDataK, V data;
public:HashTable():_n(0){_tables.resize(10);}bool Insert(const pairK, V kv){if (Find(kv.first))return false;if (_n * 10 / _tables.size() 7){HashTableK, V,Hash newHT;newHT._tables.resize(_tables.size() * 2);for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash ha;size_t hashi ha(kv.first) % _tables.size();while (_tables[hashi]._state EXIST){//线性探测hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}data* Find(const K key){Hash ha;size_t hashi ha(key) % _tables.size();size_t starti hashi;while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();//极端场景下不是存在就是删除可能会造成死循环的问题if(hashi starti){break;}}return nullptr;}bool Erase(const K key){data* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}return false;}
private:vectordata _tables;size_t _n 0;
};线性探测优点实现非常简单 线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同 关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降 低。
2.4.2开散列
1. 开散列概念开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链 接起来各链表的头结点存储在哈希表中。 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。
2. 开散列实现
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};
template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash hash * 131 e;}return hash;}
};
templateclass K,class V
struct HashNode
{pairK, V _kv;HashNode* next;HashNode(const pairK,Vkv):_kv(kv),next(nullptr){}
};
templateclass K,class V,class HashHashFuncK
class HashTable
{typedef HashNodeK, V node;
public:HashTable():_n(0){_tables.resize(10);}~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;}}bool Insert(const pairK, V kv){//负载因子控制在1超过就扩容if (_n _tables.size()){/*HashTableK, V, Hash newHT;newHT._tables.resize(_tables.size() * 2);for (auto cur : _tables){while (cur){newHT.Insert(cur-_kv);cur cur-next;}}_tables.swap(newHT._tables);*/vectornode* newTable;newTable.resize(2 * _tables.size(), nullptr);for (size_t i 0; i _tables.size(); i){node* cur _tables[i];while (cur){node* next cur-next;size_t hashi Hash()(cur-_kv.first) % newTable.size();//头插到新表cur-next newTable[hashi];newTable[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTable);}size_t hashi Hash()(kv.first) % _tables.size();node* newNode new node(kv);newNode-next _tables[hashi];_tables[hashi] newNode;_n;return true;}node* Find(const K key){size_t hashi Hash()(key) % _tables.size();node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}else{cur cur-next;}}return nullptr;}bool Erase(const K key){size_t hashi Hash()(key) % _tables.size();node* prev nullptr;node* cur _tables[hashi];while (cur){if (cur-_kv.first key){if (cur _tables[hashi]){_tables[hashi] cur-next;delete cur;}else{prev-next cur-next;delete cur;}--_n;return true;}else{prev cur;cur cur-next;}}return false;}
private:vectornode* _tables;size_t _n 0;
};
3.模拟实现
3.1哈希表的改造
1. 模板参数列表的改造
K:关键码类型 T: 不同容器V的类型不同如果是unordered_mapT代表一个键值对如果是 unordered_set,T为 K KeyOfT: 因为V的类型不同通过value取key的方式就不同
Hash:哈希函数仿函数对象类型哈希函数使用除留余数法需要将Key转换为整形数字才能 取模
2.代码实现
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};
template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash hash * 131 e;}return hash;}
};
templateclass T
struct HashNode
{T _data;HashNodeT* next;HashNode(const T data):_data(data),next(nullptr){}
};
templateclass K,class T,class Hash,class KeyOfT
class HashTable;
templateclass K,class T,class Hash,class KeyOfT
struct __HTiterator
{typedef HashNodeT node;typedef __HTiteratorK, T, Hash, KeyOfT Self;typedef HashTableK, T, Hash, KeyOfT HT;node* _node;HT* ht;__HTiterator(node* node, HT* ht):_node(node), ht(ht) {}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator !(const Self s){return _node ! s._node;}Self operator(){if (_node-next){_node _node-next;}else{//当前桶走完了走桶的下一个KeyOfT kot;size_t hashi Hash()(kot(_node-_data)) % ht-_tables.size();hashi;while (hashi ht-_tables.size()){if (ht-_tables[hashi]){_node ht-_tables[hashi];break;}else{hashi;}}if (hashi ht-_tables.size())_node nullptr;}return *this;}
};
templateclass K,class T,class Hash,class KeyOfT
class HashTable
{typedef HashNodeT node;templateclass K, class T, class Hash, class KeyOfTfriend struct __HTiterator;
public:typedef __HTiteratorK, T, Hash, KeyOfT iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){if (_tables[i]){return iterator(_tables[i], this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}HashTable():_n(0){_tables.resize(10);}~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;}}pairiterator,bool Insert(const T data){KeyOfT kot;iterator it Find(kot(data));if (it ! end())return make_pair(it, false);//负载因子控制在1超过就扩容if (_n _tables.size()){/*HashTableK, V, Hash newHT;newHT._tables.resize(_tables.size() * 2);for (auto cur : _tables){while (cur){newHT.Insert(cur-_kv);cur cur-next;}}_tables.swap(newHT._tables);*/vectornode* newTable;newTable.resize(2 * _tables.size(), nullptr);for (size_t i 0; i _tables.size(); i){node* cur _tables[i];while (cur){node* next cur-next;size_t hashi Hash()(kot(cur-_data)) % newTable.size();//头插到新表cur-next newTable[hashi];newTable[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTable);}size_t hashi Hash()(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;size_t hashi Hash()(key) % _tables.size();node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur, this);}else{cur cur-next;}}return end();}bool Erase(const K key){KeyOfT kot;size_t hashi Hash()(key) % _tables.size();node* prev nullptr;node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){if (cur _tables[hashi]){_tables[hashi] cur-next;delete cur;}else{prev-next cur-next;delete cur;}--_n;return true;}else{prev cur;cur cur-next;}}return false;}
private:vectornode* _tables;size_t _n 0;
};
3.2unordered_map模拟实现
namespace ns
{templateclass K, class V,class Hash HashFuncKclass unordered_map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename HashTableK, pairconst K, V, Hash, MapKeyOfT::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator,bool Insert(const pairconst K, V kv){return _ht.Insert(kv);}V operator[](const K key){pairiterator, bool ret _ht.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:HashTableK, pairconst K,V, Hash, MapKeyOfT_ht;};
3.3unordered_set模拟实现
namespace ns
{templateclass K,class Hash HashFuncKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename HashTableK, K, Hash, SetKeyOfT::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator,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:HashTableK, K, Hash, SetKeyOfT_ht;};
4.哈希的应用
4.1位图
4.1.1 位图概念
关于位图的概念下面通过一道面试题来进行介绍
1. 面试题
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在 这40亿个数中。【腾讯】
这道题直观的思路是使用排序二分的方法或者是使用红黑树或者是使用哈希表但是这三种方法对于40亿个整数不合适因为40个整数大概占16GB的空间而普通计算机提供不了16GB的空间所以这三种方式都被否决了
下面介绍一种新的思路使用位图的方式进行判断。
数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一 个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0 代表不存在。比如 4.1.2 位图的实现
namespace ns
{templatesize_t Nclass bit_set{public:bit_set(){_bits.resize(N / 8 1, 0);}void set(size_t x){size_t i x / 8; //表示在第几个char上size_t j x % 8; //表示在几个char的bit位上_bits[i] | (1 j);}void reset(size_t x){size_t i x / 8;size_t j x % 8;_bits[i] (~(1 j));}bool test(size_t x){size_t i x / 8;size_t j x % 8;return _bits[i] (1 j);}private:vectorchar _bits;};void test_bit_set(){bit_set-1 bs1;bs1.set(10);bs1.set(30);bs1.set(40);bs1.set(20);bs1.set(1000);bs1.set(1090);bs1.set(4);cout bs1.test(10) endl;cout bs1.test(1) endl;cout bs1.test(40) endl;bs1.reset(40);cout bs1.test(40) endl;}
} 4.1.3 位图的应用
1. 给定100亿个整数设计算法找到只出现一次的整数
实现思路定义两个bit_set的对象00表示一次都没有出现01表示出现一次10表示出现一次以上
templatesize_t Nclass two_bit_set{public:void set(size_t x){if (!_bs1.test(x) !_bs2.test(x)) // 00{_bs2.set(x);}else if (!_bs1.test(x) _bs2.test(x)) //01{_bs1.set(x);_bs2.reset(x);}//10}void PrintOnce(){for (size_t i 0; i N; i){if (!_bs1.test(i) _bs2.test(i)){cout i ;}}cout endl;}private:bit_setN _bs1;bit_setN _bs2;};void test_two_bit_set(){two_bit_set100 tbs;int a[] { 3, 5, 6, 7, 8, 9, 33, 55, 67, 3, 3, 3, 5, 9, 33 };for (auto e : a){tbs.set(e);}tbs.PrintOnce();} 2. 给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集
实现思路定义两个bit_set的对象将100一个整数分别设置到两个对象中然后遍历找如果同时在两个对象中则说明就是交集
3. 位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整 数
实现思路定义两个bit_set的对象将100一个整数分别设置到两个对象中00表示一次都没有出现01表示出现一次10表示出现2次11表示出现3次及以上然后遍历查找出现次数不超过两次的所有整数
4.2哈希切割
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址
实现思路可以将100G大小的文件按照哈希切分的方式分别切到大小为1G的小文件然后通过map来一个一个统计次数统计完一个clear掉map再统计下一个当Ai小文件超过1个G的时候分两种情况第一种是这个小文件冲突的ip很多都是不同的ip,大多数都是不重复的map统计不下可以换一个字符串哈希函数递归再切分进行统计第二种情况是这个小文件冲突的ip很多大多数都是重复的map可以统计
如图所示 直接用map统计如果是第二种情况可以统计出来不会报错如果是第一种情况map insert插入失败相当于new结点失败可以捕获异常
4.3布隆过滤器
4.3.1布隆过滤器的提出
我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉 那些已经看过的内容。问题来了新闻客户端推荐系统如何实现推送去重的 用服务器记录了用 户看过的所有历史记录当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选过滤掉那 些已经存在的记录。 如何快速查找呢 1. 用哈希表存储用户记录缺点浪费空间 2. 用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理了。 3. 将哈希与位图结合即布隆过滤器
4.3.2布隆过滤的概念
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构的多个位置中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。 存在是不准确的因为可能不存在但是这个位置可能和别人冲突出现误判
不存在是准确的 4.3.3布隆过滤器的插入
布隆过滤器是一个bit数组如图所示 如果我们要映射一个值到布隆过滤器中我们需要使用多个不同的哈希函数生成多个哈希值并对每个生成的哈希值指向的 bit 位置 1例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7则上图转变为 Ok我们现在再存一个值 “tencent”如果哈希函数返回 3、4、8 的话图继续变为 值得注意的是4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在哈希函数返回了 1、5、8三个值结果我们发现 5 这个 bit 位上的值为 0说明没有任何一个值映射到这个 bit 位上因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话那么哈希函数必然会返回 1、4、7然后我们检查发现这三个 bit 位上的值均为 1那么我们可以说 “baidu” 存在了么答案是不可以只能是 “baidu” 这个值可能存在。
这是为什么呢答案跟简单因为随着增加的值越来越多被置为 1 的 bit 位也会越来越多这样某个值 “taobao” 即使没有被存储过但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 那么程序还是会判断 “taobao” 这个值存在。
4.2.4 布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特 位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为 零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可 能存在因为有些哈希函数存在一定的误判。 比如在布隆过滤器中查找alibaba时假设3个哈希函数计算的哈希值为1、3、7刚好和其 他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的。
4.2.5 布隆过滤器删除
布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。
比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也 被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。 一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计 数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储 空间的代价来增加删除操作。
注上面的方法也不能确保一定就能够删除因为要删除的元素无法确保是否真正存在在布隆过滤器中
4.2.6如何选择哈希函数个数和布隆过滤器长度
很显然过小的布隆过滤器很快所有的 bit 位均为 1那么查询任何值都会返回“可能存在”起不到过滤的目的了。布隆过滤器的长度会直接影响误报率布隆过滤器越长其误报率越小。
另外哈希函数的个数也需要权衡个数越多则布隆过滤器 bit 位置位 1 的速度越快且布隆过滤器的效率越低但是如果太少的话那我们的误报率会变高。 k 为哈希函数个数m 为布隆过滤器长度n 为插入的元素个数p 为误报率
如何选择适合业务的 k 和 m 值呢这里直接贴一个公式 4.2.6布隆过滤器优点
1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无 关 2. 哈希函数相互之间没有关系方便硬件并行运算 3. 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 4. 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势 5. 数据量很大时布隆过滤器可以表示全集其他数据结构不能 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
4.2.7 布隆过滤器缺陷
1. 有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再 建立一个白名单存储可能会误判的数据) 2. 不能获取元素本身 3. 一般情况下不能从布隆过滤器中删除元素 4. 如果采用计数方式删除可能会存在计数回绕问题
4.2.8布隆过滤器的应用场景
1.不需要一定准确的场景
2.可以在注册昵称的时候判重
如图所示 当客户端要查询某个id是否存在的时候首先在布隆过滤器中查找查找结果为不在就可以直接返回了如果查找的结果在就到数据库外设中查找这种方式就大大提高了查询效率
4.2.9布隆过滤器代码实现
#includeiostream
#includestring
#includevector
#includebitset
#includestdlib.h
using namespace std;
namespace ns
{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;}};//N是最多存储的元素个数X平均存储一个值开辟X个位templatesize_t N,size_t X,class K string,class HashFunc1 BKDRHash,class HashFunc2 APHash,class HashFunc3 DJBHashclass BloomFilter{public:void set(const K key){size_t hashi1 HashFunc1()(key) % (N * X);size_t hashi2 HashFunc2()(key) % (N * X);size_t hashi3 HashFunc3()(key) % (N * X);_bs.set(hashi1);_bs.set(hashi2);_bs.set(hashi3);}bool test(const K key){size_t hashi1 HashFunc1()(key) % (N * X);if (!_bs.test(hashi1))return false;size_t hashi2 HashFunc1()(key) % (N * X);if (!_bs.test(hashi2))return false;size_t hashi3 HashFunc1()(key) % (N * X);if (!_bs.test(hashi3))return false;//前面不存在判读都是准确的不存在误判return true; //可能会存在误判映射的几个位置冲突}private:bitsetN* X _bs;};void test_bloomfilter1(){string str[] { 猪八戒, 孙悟空, 沙悟净, 唐三藏, \白龙马1,1白龙马,白1龙马,白11龙马,1白龙马1 };BloomFilter10,5 bf;for (auto str : str){bf.set(str);}for (auto s : str){cout bf.test(s) endl;}cout endl;srand(time(0));for (const auto s : str){cout bf.test(s to_string(rand())) endl;}}void test_bloomfilter2(){srand(time(0));const size_t N 100000;BloomFilterN,6 bf;std::vectorstd::string v1;std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html;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::vectorstd::string v2;for (size_t i 0; i N; i){std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html;url std::to_string(999999 i);v2.push_back(url);}size_t n2 0;for (auto str : v2){if (bf.test(str)){n2;}}cout 相似字符串误判率: (double)n2 / (double)N endl;// 不相似字符串集std::vectorstd::string v3;for (size_t i 0; i N; i){string url zhihu.com;url std::to_string(i rand());v3.push_back(url);}size_t n3 0;for (auto str : v3){if (bf.test(str)){n3;}}cout 不相似字符串误判率: (double)n3 / (double)N endl;}
}
4.2.10布隆过滤器的面试题
1. 给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出 精确算法和近似算法
近似算法
可以使用布隆过滤器将一个文件的内容都set到布隆过滤器当中然后遍历另一个文件依次查找如果存在就说明是交集。
精确算法
将两个文件的内容分别通过哈希切分的方式切分成一个一个的小文件然后将小文件放到map中进行找交集。
切分的时候存在的两个问题
1.切分完之后的文件大小超过1G,大多数都是不重复的可以换一个哈希切分函数递归在切分
2.切分完之后的文件大小超过1G
