- - 🌈前言
🚁1、哈希表的改造
🚂2、模拟实现的完整代码
🚃3、哈希表的应用
- 🚄3.1、位图的概念
- 🚅3.2、位图的实现
- 🚆3.3、位图完整代码
- 🚉3.4、位图的应用
🚇4、位图的变形
🚈5、布隆过滤器
- 🚐5.1、布隆过滤器的提出
- 🚑5.2、布隆过滤器的概念
- 🚒5.3、布隆过滤器的插入
- 🚓5.4、布隆过滤器的查找
- 🚔5.5、布隆过滤器的删除
- 🚕5.6、布隆过滤器优缺点

🌈前言

本篇文章学习C++STL< unordered_map和unordered_set >的模拟实现！！！

🚁1、哈希表的改造

模板参数列表的改造

// 哈希桶节点
template <typename T>
struct HashNode
{
public:HashNode(const T& data): _data(data), _next(nullptr){}
public:T _data;HashNode<T>* _next;
};// Unordered_set -> HashTable<K, Key, KeyOfT, hashF>
// Unordered_map -> HashTable<K, pair<K, V>, KeyOfT, hashF>template <typename K, typename T, typename KeyOfT, typename hashF>
class HashTable
{};

模板参数解析：

K：关键码（Key）的类型
T：不同的容器，T的类型就不相同。如果是unordered_map，T代表一个键值对，如果是unordered_set，T代表一个关键码（Key）
KeyOfT：因为V的类型不同，通过value取key的方式就不同，详细见unordered_map/set的实现
hashF: 哈希仿函数，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模

增加迭代器操作

迭代器：

哈希桶的迭代器是单向的，因为它的底层是一个链表，只有指向下一个节点的指针
迭代器需要访问哈希桶中的私有成员，需要将迭代器设置成友元类
迭代器需要定义在哈希桶前面，但是迭代器需要访问哈希桶的私有成员，因为程序是从当前位置向上开始找哈希桶在不在，所有我们需要前置声明一下哈希桶类

namespace BUCKetHash
{// 前置声明，迭代器需要访问哈希桶类的私有成员template <typename K, typename T, typename KeyOfT, typename hashF>class HashTable;// 迭代器template <typename K, typename T, typename KeyOfT, typename hashF>class HTIterator{private:typedef HashNode<T> Node;					  // 哈希表节点typedef HashTable<K, T, KeyOfT, hashF> HT;	  // 哈希表typedef HTIterator<K, T, KeyOfT, hashF> Self; // 迭代器本身public:HTIterator(Node* _node, HT* _ht): node(_node), ht(_ht){}HTIterator(const HTIterator& hti): node(hti.node), ht(hti.ht){}Self& operator++(){// 如果传过来的节点指针不为空，则直接跳到下一个节点if (node->_next != nullptr){node = node->_next;}// 当前节点为空，找下一个桶else{KeyOfT kot;hashF hf;// 计算这个节点映射到桶的位置size_t hashi = hf(kot(node->_data));hashi %= ht->_tables.size();++hashi; // 当前桶已经遍历完，需要对hashi进行自增// 遍历判断其他哈希桶是否为空，不为空则返回这个桶的指针for (; hashi < ht->_tables.size(); ++hashi){if (ht->_tables[hashi] != nullptr){node = ht->_tables[hashi];break;}}// 映射位置等于有效数据时，说明已经越界（走到尾的情况）if (hashi == ht->_tables.size()){node = nullptr;}}return *this;}// 后置++，先使用后自增Self operator++(int){Self tmp(this);++(*this);return tmp;}T& operator*(){return node->_data;}T* operator->(){return &(node->_data);}bool operator!=(const HTIterator& hti) const{return node != hti.node;}bool operator==(const HTIterator& hti) const{return node == hti.node;}public:Node* node; // 哈希节点指针HT* ht;		// 哈希表指针（this）};
}

哈希桶迭代器自增图解：
在这里插入图片描述

增加通过key获取value操作

哈希桶节点的模板类型T是不确定的，是unordered_map的时候是键对值(pair<K, V>)，而unordered_set只是一个关键码(Key)
所以我们需要建立一个仿函数将它们进行区分（开头有讲到）

unordered_map：

namespace Myself
{template <typename K, typename V, typename hashF = BUCKetHash::HashDF<K>>class unordered_map{private:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}private:BUCKetHash::HashTable<K, pair<K, V>, MapKeyOfT, hashF> ht;}; 
}

unordered_set：

namespace Myself
{template <typename K, typename hashF = BUCKetHash::HashDF<K>>class unordered_set{private:struct SetKeyOfT{const K& operator()(const K& key){return key;}private:BUCKetHash::HashTable<K, K, SetKeyOfT, hashF> ht;};
}

增加通过哈希函数转换无符号整形操作

对关键码进行转换：

因为哈希桶需要对该关键码映射对应的位置，所有需要把该关键码统一修改

namespace BUCKetHash
{// 仿函数：处理特殊的Key值问题 -- 后面需要对数据进行无符号整形转换template <typename K>struct HashDF{size_t operator()(const K& key){return static_cast<size_t>(key);}};template <>struct HashDF<string>{size_t operator()(const string& str){size_t HDS = 0;for (auto& e : str){HDS = HDS * 131 + static_cast<size_t>(e);}return HDS;}};
}

🚂2、模拟实现的完整代码

HashTable.h

#pragma once#include <iostream>
#include <vector>
using namespace std;// 哈希桶（指针数组）：哈希表中存储指针，这个指针存储映射的值，映射相同位置时，创建新的节点直接链到这个指针中
namespace BUCKetHash
{// 仿函数：处理特殊的Key值问题 -- 后面需要对数据进行无符号整形转换template <typename K>struct HashDF{size_t operator()(const K& key){return static_cast<size_t>(key);}};template <>struct HashDF<string>{size_t operator()(const string& str){size_t HDS = 0;for (auto& e : str){HDS = HDS * 131 + static_cast<size_t>(e);}return HDS;}};// 哈希表节点template <typename T>struct HashNode{public:HashNode(const T& data): _data(data), _next(nullptr){}public:T _data;HashNode<T>* _next;};// 前置声明，迭代器需要访问哈希桶类的私有成员template <typename K, typename T, typename KeyOfT, typename hashF>class HashTable;// 迭代器template <typename K, typename T, typename KeyOfT, typename hashF>class HTIterator{private:typedef HashNode<T> Node;					  // 哈希表节点typedef HashTable<K, T, KeyOfT, hashF> HT;	  // 哈希表typedef HTIterator<K, T, KeyOfT, hashF> Self; // 迭代器本身public:HTIterator(Node* _node, HT* _ht): node(_node), ht(_ht){}HTIterator(const HTIterator& hti): node(hti.node), ht(hti.ht){}Self& operator++(){// 如果传过来的节点指针不为空，则直接跳到下一个节点if (node->_next != nullptr){node = node->_next;}// 当前节点为空，找下一个桶else{KeyOfT kot;hashF hf;// 计算这个节点映射到桶的位置size_t hashi = hf(kot(node->_data));hashi %= ht->_tables.size();++hashi; // 当前桶已经遍历完，需要对hashi进行自增for (; hashi < ht->_tables.size(); ++hashi){if (ht->_tables[hashi] != nullptr){node = ht->_tables[hashi];break;}}// 映射位置等于有效数据时，说明已经越界if (hashi == ht->_tables.size()){node = nullptr;}}return *this;}Self operator++(int){Self tmp(this);++(*this);return tmp;}T& operator*(){return node->_data;}T* operator->(){return &(node->_data);}bool operator!=(const HTIterator& hti) const{return node != hti.node;}bool operator==(const HTIterator& hti) const{return node == hti.node;}public:Node* node; // 哈希节点指针HT* ht;		// 哈希表指针（this）};// Unordered_set -> HashTable<K, Key, KeyOfT, hashF>// Unordered_map -> HashTable<K, pair<K, V>, KeyOfT, hashF>template <typename K, typename T, typename KeyOfT, typename hashF>class HashTable{template <typename K, typename T, typename KeyOfT, typename hashF>friend class HTIterator; // 迭代器内部需要访问哈希表的私有成员private:typedef HashNode<T> Node;public:typedef HTIterator<K, T, KeyOfT, hashF> iterator;typedef HTIterator<const K, const T, KeyOfT, hashF> const_iterator;public:iterator begin(){for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];if (cur != nullptr){return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}const_iterator cbegin() const{for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];if (cur != nullptr){return const_iterator(cur, this);}}return cend();}const_iterator cend() const{return const_iterator(nullptr, this);}public:HashTable() = default;HashTable(const HashTable& ht){_tables.resize(ht._tables.size(), nullptr);for (size_t i = 0; i < ht._tables.size(); ++i){Node* cur = ht._tables[i];while (cur != nullptr){this->Insert(kot(cur->_data));cur = cur->_next;}}}HashTable& operator=(const HashTable ht){HashTable tmp(ht);this->_n = tmp._n;tmp._tables.swap(_tables);return *this;}~HashTable(){for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur != nullptr){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}// 返回值为pair是为了支持unordered_map的[]重载pair<iterator, bool> Insert(const T& data){Node* IfExist = Find(kot(data));if (IfExist != nullptr)return make_pair(iterator(IfExist, this), false); // 插入识别，数据冗余if (_tables.size() == 0 || _tables.size() == _n){size_t NewSize = _tables.size() == 0 ? 10 : _tables.size() * 2;// 把旧哈希桶的节点重新映射到新开辟的哈希桶HashTable newHT;newHT._tables.resize(NewSize, nullptr);for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur != nullptr){// 将旧哈希桶的值挪到新哈希桶中 -- 头插Node* next = cur->_next; // 保存下一个节点，挪动后防止找不到size_t hashi = HashDF(kot(cur->_data)) % NewSize; // 需要重新映射新扩容后的哈希桶，模新长度的哈希桶cur->_next = newHT._tables[hashi];newHT._tables[hashi] = cur;cur = next;}_tables[i] = nullptr;}newHT._tables.swap(_tables);}// 跟闭散列的方法一样需要继续模表大小size_t hashi = HashDF(kot(data));hashi %= _tables.size();// 构造需要插入的键对值，然后插入到映射的位置 -- 画图Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;++_n;// 插入成功，返回指向新节点的迭代器return make_pair(iterator(newNode, this), true); }bool erase(const K& key){size_t hashi = HashDF(key);hashi %= _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur != nullptr){if (kot(cur->_data) == key){// 删除位置为"头"if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}Node* Find(const K& key){if (_tables.size() == 0)return nullptr;// 查找跟闭散列差不多size_t hashi = HashDF(key);hashi %= _tables.size();// 对映射的位置进行循环遍历查找Node* cur = _tables[hashi];while (cur != nullptr){if (kot(cur->_data) == key)return cur;cur = cur->_next;}return nullptr;}private:vector<Node*> _tables;size_t _n = 0;hashF HashDF;KeyOfT kot;};
}

Unordered_map.h

#pragma once
#include "HashTable.h"namespace Myself
{template <typename K, typename V, typename hashF = BUCKetHash::HashDF<K>>class unordered_map{private:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef BUCKetHash::HashNode<pair<K, V>> Node;public:// 迭代器和常量迭代器typedef typename BUCKetHash::HashTable<K, pair<K, V>, MapKeyOfT, hashF>::iterator iterator;typedef typename BUCKetHash::HashTable<K, pair<K, V>, MapKeyOfT, hashF>::const_iterator const_iterator;public:iterator begin(){return ht.begin();}iterator end(){return ht.end();}const_iterator cbegin() const{return ht.cbegin();}const_iterator cend() const{return ht.cend();}pair<iterator, bool> insert(const pair<K, V>& kv){return ht.Insert(kv);}bool erase(const K& key){return ht.erase(key);}Node* find(const K& key){return ht.Find(key);}V& operator[](const K& key){pair<iterator, bool> ret = ht.Insert(make_pair(key, V()));return ret.first->second;}private:BUCKetHash::HashTable<K, pair<K, V>, MapKeyOfT, hashF> ht;}; 
}

Unordered_set

#pragma once
#include "HashTable.h"
namespace Myself
{template <typename K, typename hashF = BUCKetHash::HashDF<K>>class unordered_set{private:struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef BUCKetHash::HashNode<K> Node;public:typedef typename BUCKetHash::HashTable<K, K, SetKeyOfT, hashF>::iterator iterator;typedef typename BUCKetHash::HashTable<K, K, SetKeyOfT, hashF>::const_iterator const_iterator;public:// 迭代器iterator begin(){return ht.begin();}iterator end(){return ht.end();}const_iterator cbegin() const{return ht.cbegin();}const_iterator cend() const{return ht.cend();}// 其他接口pair<iterator, bool> insert(const K& key){return ht.Insert(key);}bool erase(const K& key){return ht.erase(key);}Node* find(const K& key){return ht.Find(key);}private:BUCKetHash::HashTable<K, K, SetKeyOfT, hashF> ht;};
}

🚃3、哈希表的应用

🚄3.1、位图的概念

概念：

所谓位图，就是用每一位（比特位）来存放某种状态
适用海量数据，数据无重复的场景。通常用来判断某个数据是否存在

在这里插入图片描述

🚅3.2、位图的实现

🌈前言：位图常用的接口只有三个，插入、删除和查找

位图的结构：

位图的结构是一个vector，底层是char/int类型，char可以标记8个状态（1字节），而int可以标识32个状态（4字节），模板类型是一个无符号整形
位图的基本操作就是存储不重复数据，即可以使用0/1来标识存不存在

在这里插入图片描述

构造函数：

每个char类型可以标识8个状态，如果是80个数据的话，只需要开辟10个空间足以
如果是81 - 87的话，那么只需要多开辟一个char类型空间就足够了，也不会浪费很大内存

template <size_t N>
class bitset
{
public:bitset(){// N是数据个数，我们使用比特位来映射，char类型一个字节占八个比特位bit.resize((N / 8) + 1, 0);}
}

插入：

使用哈希表的直接定址法，用一个比特位标识映射的位置在不在
标识状态要注意大小端问题，否则会出错

namespace myself
{// 注意大小端问题template <size_t N>class bitset{public:void set(size_t x){// x映射的位置在第几个char中size_t i = x / 8;// x标识的状态在char中的第几个比特位size_t j = x % 8;// 将映射位置的值(bit[i]) "按位或" 上一个向左移动j位的值bit[i] |= (1 << j);}private:vector<char> bit;};
}

在这里插入图片描述

删除：

删除就是把这个数据映射在char中的位置的状态更改尾0即可

namespace myself
{template <size_t N>class bitset{public:void reset(size_t x){size_t i = x / 8;size_t j = x % 8;bit[i] &= ~(1 << j);}private:vector<char> bit;};
}

在这里插入图片描述

查找：

namespace myself
{template <size_t N>class bitset{public:bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return  bit[i] & (1 << j);}private:vector<char> bit;};
}

在这里插入图片描述

🚆3.3、位图完整代码

// 位图：哈希表的变式，用于处理海量数据
namespace myself
{// 注意大小端问题template <size_t N>class bitset{public:bitset(){// N是数据个数，我们使用比特位来映射，char类型一个字节占八个比特位bit.resize((N / 8) + 1, 0);}void set(size_t x){size_t i = x / 8;size_t j = x % 8;// 将映射位置的值(bit[i]) "按位或" 上一个向左移动j位的值bit[i] |= (1 << j);}void reset(size_t x){size_t i = x / 8;size_t j = x % 8;bit[i] &= ~(1 << j);}bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return  bit[i] & (1 << j);}private:vector<char> bit;};
}

🚉3.4、位图的应用

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

🚇4、位图的变形

首先抛出一个问题：给定100亿个整数，设计算法找出只出现一次和二次的整数！！！

首先，使用位图是解决不了这个问题的，因为位图只能标识两种状态（0/1）
这道题需要标识四种状态才能解决问题

思路：

在这里插入图片描述

完整代码：

namespace myself
{
template <size_t N>class two_bitset{public:void set(size_t x){bool in1 = bs1.test(x);bool in2 = bs2.test(x);// 如果二个位图中都不存在这个数据，则状态改为出现一次（01）if (in1 == 0 && in2 == 0){bs2.set(x);}// 如果这个数据已经存在，则状态改为出现二次（10）else if (in1 == 0 && in2 == 1){bs1.set(x);bs2.reset(x);}// 如果这个数据已经存在二次以上，则状态改为（11）else{bs1.set(x);}}// 只存在一次的数据bool is_once(size_t x){return bs1.test(x) == 0 && bs2.test(x) == 1;}private:bitset<N> bs1;bitset<N> bs2;};
}

🚈5、布隆过滤器

🚐5.1、布隆过滤器的提出

前言：我们使用哔哩哔哩时，下拉刷新会给我们不停的推荐新的内容，每次刷新都要对旧数据进行去重，那它是如何实现推送去重的呢？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新内容时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何快速查找呢？

解决方案：

用哈希表存储用户记录，缺点：浪费空间
用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了
将哈希与位图结合，即：布隆过滤器

🚑5.2、布隆过滤器的概念

概念：

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

在这里插入图片描述

🚒5.3、布隆过滤器的插入

向布隆过滤器插入"baidu"这一字符串：
在这里插入图片描述

随后再插入"tencent"这一字符串

在这里插入图片描述

注意：这里是假设，插入tencent时就发生了误判，但这不能代表什么，需要大量数据进行测试

namespace myself
{// 布隆过滤器 -- 映射多个无符号整形数据（消耗空间多），降低哈希冲突的概率，但是避免不了冲突// 假设现在设置三个哈希函数template <typename K, size_t M, typename HashFunc1, typename HashFunc2, typename HashFunc3>class BloomFilter{public:void Set(const K& key){size_t bf1 = HashFunc1()(key) % M;size_t bf2 = HashFunc2()(key) % M;size_t bf3 = HashFunc3()(key) % M;bs.set(bf1);bs.set(bf2);bs.set(bf3);}private:myself::bitset<M> bs;};
}

🚓5.4、布隆过滤器的查找

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

bool Test(const K& key)
{size_t bf1 = HashFunc1()(key) % M;if (bs.test(bf1) == false)return false;size_t bf2 = HashFunc2()(key) % M;if (bs.test(bf2) == false)return false;size_t bf3 = HashFunc3()(key) % M;if (bs.test(bf3) == false)return false;return true; // 可能三个位置都存在冲突...
}