【C++进阶】哈希（万字详解）—— 运用篇(下） 快来打我* 2024-04-20 06:33 75阅读 0赞 > **?C++学习历程：入门** > > -------------------- > > * **博客主页：**[一起去看日落吗][Link 1] > * **持续分享博主的C++学习历程** > * **`博主的能力有限，出现错误希望大家不吝赐教`** > * **分享给大家一句我很喜欢的话：** 也许你现在做的事情，暂时看不到成果，但不要忘记，树?成长之前也要扎根，也要在漫长的时光?中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭?。 > > -------------------- > > ![在这里插入图片描述][eabca17da9704379a5f15832a495b4cc.jpeg_pic_center] ? ? ? ? -------------------- #### 目录 #### * ? 1. 模拟实现 * * ? 1.1 哈希表代码 * ? 1.2 哈希表的改造 * ? 1.3 哈希表的最终代码 * ? 1.4 unordered\_map 的模拟实现 * ? 2. 位图 * * ? 2.1 库中的位图 * ? 2.2 模拟实现位图 * ? 3. 布隆过滤器 * * ? 3.1 布隆过滤器提出 * ? 3.2 布隆过滤器概念 * ? 3.3 布隆过滤器优点 * ? 3.4 布隆过滤器缺陷 * ? 3.5 布隆过滤器模拟实现 * ? 4. 海量数据面试题 * * ? 4.1 位图应用 * ? 4.2 哈希切分+布隆过滤器应用 ## ? 1. 模拟实现 ## ### ? 1.1 哈希表代码 ### namespace Byih { template<class K, class V> struct HashNode { pair<K, V> _kv; HashNode<K, V>* _next; HashNode(const pair<K, V>& kv) :_kv(kv) , _next(nullptr) { } }; size_t GetNextPrime(size_t prime) { const int PRIMECOUNT = 28; static const size_t primeList[PRIMECOUNT] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; size_t i = 0; for (; i < PRIMECOUNT; ++i) { if (primeList[i] > prime) return primeList[i]; } return primeList[i]; } template<class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; public: // 拷贝 和 赋值 需要自己实现桶的拷贝 ~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; } _n = 0; } bool Erase(const K& key) { if (_tables.size() == 0) { return false; } Hash hf; // 素数 size_t index = hf(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[index]; while (cur) { if (cur->_kv.first == key) { // 1、cur是头结点 // 2、非头节点 if (prev == nullptr) { _tables[index] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } else { prev = cur; cur = cur->_next; } } return false; } Node* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } Hash hf; size_t index = hf(key) % _tables.size(); Node* cur = _tables[index]; while (cur) { if (cur->_kv.first == key) { return cur; } else { cur = cur->_next; } } return nullptr; } bool Insert(const pair<K, V>& kv) { Hash hf; //当负载因子到1时，进行扩容 if (_n == _tables.size()) { //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; size_t newSize = GetNextPrime(_tables.size()); //HashTable<K, V> newHT; vector<Node*> newtables; newtables.resize(newSize, nullptr); for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t index = hf(cur->_kv.first) % newSize; cur->_next = newtables[index]; newtables[index] = cur; cur = next; } _tables[i] = nullptr; } newtables.swap(_tables); } size_t index = hf(kv.first) % _tables.size(); Node* cur = _tables[index]; while (cur) { if (cur->_kv.first == kv.first) { return false; } else { cur = cur->_next; } } Node* newnode = new Node(kv); newnode->_next = _tables[index]; _tables[index] = newnode; ++_n; return true; } private: vector<Node*> _tables; size_t _n = 0; // 存储多少有效数据 }; } -------------------- ### ? 1.2 哈希表的改造 ### * 模板参数的改造 K:关键码类型 V: 不同容器V的类型不同，如果是unordered\_map，V代表一个键值对，如果是unordered\_set,V为 K KeyOfT: 在哈希表中需要取到value，因为V的类型不同，通过value取key的方式就不同，详细见unordered\_map/set的实现 Hash: 哈希函数仿函数对象类型，哈希函数使用除留余数法，如果是Key为string类型，需要将Key转换为整形数字才能取模 template<class K, class T, class KeyOfT, class Hash = HashFunc<T> > class HashBucket; -------------------- * 哈希表节点结构 template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) { } }; 如果是unordered\_map，v代表一个键值对，如果是unordered\_set,v为 K -------------------- * operator++模拟实现 当下一个节点不为空时，++后的节点就在当前桶，返回即可，当下一个节点为空时，我们需要找下一个桶，首先通过当前节点计算找到当前节点所在桶的位置index，计算出后，++index即找到了下一个桶，当下一个桶存在时，如果下一个桶里面有数据(即不为空)，则将第一个数据给当前节点，就实现了++，否则继续找下一个桶，当循环出来时，有可能是找到++后的节点了，也有可能说明走完了后面没有桶了，所以循环出来需要判断是不是没有桶了，没有桶则返回nullptr Self operator++() { if (_node->_next) // 在当前桶迭代 { _node = _node->_next; } else // 找下一个桶 { KeyOfT kot; const K& key = kot(_node->_data); Hash hf; size_t index = hf(key) % _ht->_tables.size(); ++index; _node = nullptr; while (index < _ht->_tables.size()) { if (_ht->_tables[index]) { _node = _ht->_tables[index]; break; } else { ++index; } } // 后面没有桶了 if (index == _ht->_tables.size()) { _node = nullptr; } } return *this; } -------------------- * operator\*的模拟实现 T& operator*() { return _node->_data; } -------------------- * operator->的模拟实现 T* operator->() { return &_node->_data; } -------------------- * operator==和operator!=的模拟实现 bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } -------------------- ### ? 1.3 哈希表的最终代码 ### namespace Byih { template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) { } }; size_t GetNextPrime(size_t prime) { const int PRIMECOUNT = 28; static const size_t primeList[PRIMECOUNT] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; size_t i = 0; for (; i < PRIMECOUNT; ++i) { if (primeList[i] > prime) return primeList[i]; } return primeList[i]; } // 前置声明 template<class K, class T, class Hash, class KeyOfT> class HashTable; template<class K, class T, class Hash, class KeyOfT> struct HTIterator { typedef HashNode<T> Node; typedef HashTable<K, T, Hash, KeyOfT> HT; typedef HTIterator<K, T, Hash, KeyOfT> Self; Node* _node; HT* _ht; HTIterator(Node* node, HT* ht) :_node(node) , _ht(ht) { } bool operator!=(const Self& s) const { return _node != s._node; } T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } Self operator++() { if (_node->_next) // 在当前桶迭代 { _node = _node->_next; } else // 找下一个桶 { KeyOfT kot; const K& key = kot(_node->_data); Hash hf; size_t index = hf(key) % _ht->_tables.size(); ++index; _node = nullptr; while (index < _ht->_tables.size()) { if (_ht->_tables[index]) { _node = _ht->_tables[index]; break; } else { ++index; } } // 后面没有桶了 if (index == _ht->_tables.size()) { _node = nullptr; } } return *this; } }; template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> class HashTable { typedef HashNode<T> Node; //template<class K, class T, class Hash, class KeyOfT> friend struct HTIterator<K, T, Hash, KeyOfT>; public: typedef HTIterator<K, T, Hash, KeyOfT> 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); } // 拷贝 和 赋值 需要自己实现桶的拷贝 ~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; } _n; } bool Erase(const K& key) { if (_tables.size() == 0) { return false; } Hash hf; KeyOfT kot; // 素数 size_t index = hf(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[index]; while (cur) { if (kot(cur->_data) == key) { // 1、cur是头结点 // 2、非头节点 if (prev == nullptr) { _tables[index] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } else { prev = cur; cur = cur->_next; } } return false; } Node* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } Hash hf; KeyOfT kot; size_t index = hf(key) % _tables.size(); Node* cur = _tables[index]; while (cur) { if (kot(cur->_data) == key) { return cur; } else { cur = cur->_next; } } return nullptr; } bool Insert(const T& data) { Hash hf; KeyOfT kot; //当负载因子到1时，进行扩容 if (_n == _tables.size()) { //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; size_t newSize = GetNextPrime(_tables.size()); //HashTable<K, V> newHT; vector<Node*> newtables; newtables.resize(newSize, nullptr); for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; const K& key = kot(cur->_data); size_t index = hf(key) % newSize; cur->_next = newtables[index]; newtables[index] = cur; cur = next; } _tables[i] = nullptr; } newtables.swap(_tables); } const K& key = kot(data); size_t index = hf(key) % _tables.size(); Node* cur = _tables[index]; while (cur) { if (kot(cur->_data) == kot(data)) { return false; } else { cur = cur->_next; } } Node* newnode = new Node(data); newnode->_next = _tables[index]; _tables[index] = newnode; ++_n; return true; } private: vector<Node*> _tables; size_t _n = 0; // 存储多少有效数据 }; } -------------------- ### ? 1.4 unordered\_map 的模拟实现 ### #pragma once #include "HashTable.h" namespace byh { template<class K, class V> class unordered_map { struct MapKeyOfT { const K& operator()(const pair<const K, V>& kv) const { return kv.first; } }; public: iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } //插入 pair<iterator,bool> insert(const pair<const K, V>& kv) { return _ht.Insert(kv); } //[]运算符重载 V& operator[](const K& key) { pair<iterator,bool> ret = insert(make_pair(key,V())); iterator it = ret.first; return it->second; } //删除 bool erase(const K& key) { return _ht.Erase(key); } //查找 iterator find(const K& key) { return _ht.Find(key); } private: Byih::HashTable<K, pair<const K, V>, MapKeyOfT> _ht; }; } 实现unordered\_map只需要调用底层哈希表对应的接口即可，实现unordered\_set不一样的是它不需要实现\[\]运算符重载 -------------------- ## ? 2. 位图 ## **所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的**。适用于海量数据的状态：比如：40亿数据，需要16G内存；若用位图存放这些数据在不在的状态，只需要16/32G，约500M。 数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如： ![在这里插入图片描述][c4d338a3871440d5a8b5abcb4798ed49.png] **主要应用：** 1. 快速查找某个数据是否在一个集合中 2. 排序 + 去重 3. 求两个集合的交集、并集等 4. 操作系统次磁盘中的标记等 * 优点：节省空间，速度快 * 缺点：只能处理整形数据 -------------------- ### ? 2.1 库中的位图 ### **主要接口：set（将某位设为1） reset（将某位设为0） test（判断某一位是否为1）** bitset<100> bs; //将某位设置为1 bs.set(11);bs.set(5);bs.set(78);bs.set(23);bs.set(12); //将某位设置为0 bs.reset(11); //判断某位是否为1 for (size_t i = 0; i < 100; i++) { //cout << i << ":" << bs.test(i) << " "; //if (i != 0 && i % 10 == 0) // cout << endl; if (bs.test(i) == 1) cout << i << " "; } cout << endl; -------------------- ### ? 2.2 模拟实现位图 ### template<size_t N> class byh { public: BitSet() { _bits.resize(N / 32 + 1, 0);//默认构造，会对位图进行初始化 } // 把x映射的位标记成1 void Set(size_t x) { assert(x < N); // 算出x映射的位在第i个整数 // 算出x映射的位在这个整数的第j个位 size_t i = x / 32; size_t j = x % 32; // _bits[i] 的第j位标记成1，并且不影响他的其他位 _bits[i] |= (1 << j); //或等于 //(1 << j) //00000001000000000 } void Reset(size_t x) { assert(x < N); size_t i = x / 32; size_t j = x % 32; // _bits[i] 的第j位标记成0，并且不影响他的其他位 _bits[i] &= (~(1 << j)); //与等于 //对 1 << j 取反就行 //~(1 << j) //1111111101111111111 } bool Test(size_t x) { assert(x < N); size_t i = x / 32; size_t j = x % 32; // 如果第j位是1，结果是非0，非0就是真 // 如果第j为是0，结果是0，0就是假 return _bits[i] & (1 << j);//直接把这一位取出来是1还是0 //return (_bits[i] >> j) & 1;//这样写也可以 } private: vector<int> _bits; }; -------------------- ## ? 3. 布隆过滤器 ## ### ? 3.1 布隆过滤器提出 ### 我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？ 1. 用哈希表存储用户记录，缺点：浪费空间 2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。 3. 将哈希与位图结合，即布隆过滤器 -------------------- ### ? 3.2 布隆过滤器概念 ### 布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 **一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中**。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。 ![在这里插入图片描述][b40d6a6807a64413a9225080c8910c3e.png] [原理讲解][Link 2] -------------------- ### ? 3.3 布隆过滤器优点 ### 1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关 2. 哈希函数相互之间没有关系，方便硬件并行运算 3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势 4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势 5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 -------------------- ### ? 3.4 布隆过滤器缺陷 ### 1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据) 2. 不能获取元素本身 3. 一般情况下不能从布隆过滤器中删除元素 4. 如果采用计数方式删除，可能会存在计数回绕问题 -------------------- ### ? 3.5 布隆过滤器模拟实现 ### //布隆过滤器实际上是对位图的改进，所以实现上也是对位图的封装，一般只提供set和test接口，不能实现reset（删除） template<size_t N, class K = std::string,class Hash1 = HashBKDR,class Hash2 = HashAP,class Hash3 = HashDJB> //后面几个是字符串哈希函数的仿函数 class BloomFilter { public: void Set(const K& key) { //Hash1 hf1; //size_t i1 = hf1(key);//以下写法也可以 size_t i1 = Hash1()(key) % N;//Hash1()是仿函数的匿名对象 size_t i2 = Hash2()(key) % N; size_t i3 = Hash3()(key) % N; cout << i1 << " " << i2 << " " << i3 << endl; _bitset.Set(i1); _bitset.Set(i2); _bitset.Set(i3); } bool Test(const K& key)//判断是否存在 { size_t i1 = Hash1()(key) % N; if (_bitset.Test(i1) == false) { return false; } size_t i2 = Hash2()(key) % N; if (_bitset.Test(i2) == false) { return false; } size_t i3 = Hash3()(key) % N; if (_bitset.Test(i3) == false) { return false; } // 这里3个位都在，有可能是其他key占了，在是不准确的，存在误判 // 不在是准确的 return true; } private: byh::BitSet<N> _bitset; // 对位图的封装 //byh::vector<char> _bitset; }; -------------------- ## ? 4. 海量数据面试题 ## ### ? 4.1 位图应用 ### * 题目一 **给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？** **思路**：100亿的整数范围还是42亿，因此用一个位图来存储只需要512M 将一个文件映射到位图中，再依次读取另一个文件的数据，看在不在位图中，在就是交集；或者构建两个位图，求他们的交集； * 题目二 **给定100亿个整数，设计算法找到只出现一次的整数？** **思路**：用位图的思想，一个bit位能表示两种状态，这里至少是3种状态，因此需要两个bit位00表示没出现；01表示只出现一次；10表示出现过2次及以上；将所有数插入位图中，然后遍历位图，找出标志位01的位即为所求 -------------------- ### ? 4.2 哈希切分+布隆过滤器应用 ### **哈希切分的原理**：就是将一个大文件，利用哈希的原理（i = Hash()(ip) % 100， i表示小文件的编号），将其分为若干个小文件。 **哈希切割的特点**：相同的ip一定进入了同一个小文件当中。 * 题目三 **给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法** 1. **近似算法**：利用布隆过滤器100亿个query（ip），可以看做string，假设为100G，那么两个文件一共是200G。将A文件依次映射到一个布隆过滤器中，再依次读取B文件中的数据，与布隆过滤器里的内容比较，在就是交集，但是会有一定的误判率。 2. **精确算法**：利用哈希切分 + 布隆过滤器 可以将AB文件都切割成200个小文件（哈希切分并不是均匀的，依次要保证小文件小于内存大小），按照同样的映射函数 i = Hash()(ip) % 200 这样AB中相同的ip，都进了各自对应的编号i的小文件，因此只需要依次比较Ai和Bi中的交集即可 ![在这里插入图片描述][575bdc5e2ed84ea8b848ad3d6ae419fc.png] * 题目四 **给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？** 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？ **思路**：哈希切分，切分成100个小文件（相同的ip一定进入了同一个小文件）然后只需统计各个小文件各个ip的频次（比如用一个map<string, int>统计），找出每个小文件频次最高的ip地址进行比较即可；要求 top K的ip，可以建一个K个元素小堆，后面的元素依次与堆顶元素比较，比它大就替换进堆，最终这个小堆就是top K ； ![在这里插入图片描述][0ef290c96c2041cba561d2a0f466735c.png] -------------------- [Link 1]: https://blog.csdn.net/m0_60338933?type=blog [eabca17da9704379a5f15832a495b4cc.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ae36f26ffa3b4478b894ceb82f58f08a.jpeg [c4d338a3871440d5a8b5abcb4798ed49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4fbb1998ea604c61987a91a1fd0fa406.png [b40d6a6807a64413a9225080c8910c3e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ab04efb838c24e238d35c557cee36ba1.png [Link 2]: https://zhuanlan.zhihu.com/p/43263751/ [575bdc5e2ed84ea8b848ad3d6ae419fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/493fdcc4a33747a3b238947c87f0dd55.png [0ef290c96c2041cba561d2a0f466735c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/e998499571074105bfa69895088fe3c0.png
相关 【C++进阶】map和set（ 万字详解）—— 上篇 C++map和set详解上篇，很快就会更新下篇，实现avl树红黑树和封装map和set 旧城等待，/ 2024年04月20日 06:24/ 0 赞/ 69 阅读
相关 【C++进阶】：哈希 哈希 一.unordered\_map 二.底层结构 1.哈希概念 2.解决哈希冲突 1.闭散列 ゞ 浴缸里的玫瑰/ 2024年03月03日 09:06/ 0 赞/ 102 阅读
相关 [C++] 哈希详解 目录 1. 哈希概念 2. 实现机制 2.1 插入时 2.2 查找时 2.3 缺陷 2.4 常见哈希函数 我就是我/ 2022年09月09日 02:19/ 0 赞/ 262 阅读
分手后的思念是犯贱
梦里梦外;
朱雀
傷城~
ゞ 浴缸里的玫瑰
我就是我
还没有评论，来说两句吧...