C++第四十弹---从零开始：模拟实现C++中的unordered_set与unordered_map

2024-08-23 13:20
文章标签 c++ unordered 第四十 set map 从零开始 模拟 实现

本文主要是介绍C++第四十弹---从零开始：模拟实现C++中的unordered_set与unordered_map，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 ✨个人主页： 熬夜学编程的小林

💗系列专栏： 【C语言详解】 【数据结构详解】【C++详解】

目录

1 哈希概念

2 哈希冲突

3 哈希函数

4 哈希冲突解决

4.1 闭散列

4.1.1. 线性探测

4.1.2. 二次探测

4.2 开散列

4.2.1. 开散列概念

4.2.2. 开散列实现

4.2.3. 开散列增容

4.2.4. 开散列的思考

4.2.5. 开散列与闭散列比较

5. 模拟实现

5.1 哈希表的改造

5.2 unordered_set

5.3 unordered_map

6 完整代码

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。


1 哈希概念


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


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

当向该结构中：

  • 插入元素

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

  • 搜索元素

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


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

例如：数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity;  capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。


问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

2 哈希冲突


对于两个数据元素的关键字k_i和 k_j(i != j)，有k_i != k_j，但有：Hash(k_i) ==Hash(k_j)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
 

发生哈希冲突该如何处理呢？


3 哈希函数


引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：

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

常见哈希函数
1. 直接定址法--(常用)

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


2. 除留余数法--(常用)

  • 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。


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


4. 折叠法--(了解)


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


5. 随机数法--(了解)


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


6. 数学分析法--(了解)


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

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


注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。


4 哈希冲突解决


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


4.1 闭散列


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


4.1.1. 线性探测


比如1(哈希概念)中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入

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

删除

  • 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};

线性探测的实现

template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state;
};template<class K, class V>
class HashTable
{
public:// 构造，默认开辟10个大小空间HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){// 检测哈希表底层空间是否充足// _CheckCapacity();size_t hashi = kv.first % _tables.size();// 线性探测while (_tables[hashi]._state == EXIST){++hashi;hashi %= _tables.size();}// 更新数据_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = key % _tables.size();// 线性探测，存在/删除状态均需查找while (_tables[hashi]._state != EMPTY){// 删除状态不能查找if (_tables[hashi]._state != DELETE &&_tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){// 查找是否有该key值，有则将状态修改为删除并--n，没有则返回falseHashData<K, V>* ret = Find(key);if (ret == nullptr)return false;else{ret->_state = DELETE;--_n;return true;}}
private:vector<HashData<K, V>> _tables;size_t _n = 0; // 有效数据个数
};

思考：哈希表什么情况下进行扩容？如何扩容？

void CheckCapacity()
{if (_n * 10 / _tables.size() >= 7){方式一：创建新的顺序表//size_t newsize = _tables.size() * 2;//vector<HashData<K, V>> newtables(newsize);旧表重新计算负载到新表//for (size_t i = 0; i < _tables.size(); i++)//{}// 方式二：创建新的哈希表，复用Insert函数HashTable<K, V, Hash> newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){// 当前位置值存在则插入if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}// 交换两个哈希表的地址_tables.swap(newHT._tables);}
}

线性探测优点：实现非常简单。
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？


4.1.2. 二次探测


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

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

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

4.2 开散列

4.2.1. 开散列概念


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

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

4.2.2. 开散列实现

// 哈希桶结点定义
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){}
};// 哈希表结构定义
template<class K,class V>
class HashTable
{typedef HashNode<K, V> Node;
public:// 构造函数，先开辟10个大小空间，并将有效数据个数初始化为0HashTable(){_tables.resize(10, nullptr);_n = 0;}bool Insert(const pair<K, V>& kv){// 不能重复插入if (Find(kv.first))return false;// 扩容...// _CheckCapacity();size_t hashi = kv.first % _tables.size();Node* newnode = new Node(kv);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}bool Erase(const K& key){// 找到在哪个桶size_t hashi = key % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){// 找到该值if (cur->_kv.first == key){// 删除的是第一个节点if (prev == nullptr){_tables[hashi] = 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){size_t hashi = key % _tables.size();// 找到桶的起始地址Node* cur = _tables[hashi];// 遍历桶while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;// 迭代往后走}return nullptr;}
private:vector<Node*> _tables;size_t _n = 0;
};

4.2.3. 开散列增容


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

void _CheckCapacity()
{// 扩容，负载因子为1if (_n == _tables.size()){// 将原节点链接到新表vector<Node*> newTables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 头插新表的位置size_t hashi = hs(kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables.swap(newTables);}}
}

4.2.4. 开散列的思考


1. 只能存储key为整形的元素，其他类型怎么解决？

哈希函数采用处理余数法，被模的key必须要为整形才可以处理，此处提供将key转化为整形的方法。

// 整形数据不需要转化
template<class K>
struct HashFunc
{size_t operator()(const K& key){return size_t(key);}
};// 特化，string类型
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};

4.2.5. 开散列与闭散列比较


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

5. 模拟实现


5.1 哈希表的改造


1. 模板参数列表的改造

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

2. 增加迭代器操作

为什么要获取哈希桶数据的指针？

因为当一个桶的中的数据遍历完之后，想要遍历下一个桶的数据，只有通过哈希桶这个表才能获取，因此我们需要一个哈希桶的指针。

// 前置声明，为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator
{typedef HashNode<T> Node;typedef __HTIterator<K, T, KeyOfT, Hash> Self;Node* _node;// 获取哈希桶数据的指针HashTable<K, T, KeyOfT, Hash>* _pht;__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){// 当前桶没走完，找当前桶的下一个结点if (_node->_next){_node = _node->_next;}else{Hash hs;KeyOfT kot;// 当前桶走完了，找下一个不为空的桶的第一个结点// 1、找当前结点在桶的哪个位置size_t i = hs(kot(_node->_data)) % _pht->_tables.size();++i;for (; i < _pht->_tables.size(); i++){if (_pht->_tables[i])break;}// 循环结束有两种情况，一种break结束，一种循环结束// 循环结束，该结点的下一个为nullptrif (i == _pht._tables.size()){_node = nullptr;}else{_node = _pht->_tables[i];}}}bool operator!=(const Self& s){return _node != s._node;}
};

3. 增加通过key获取value操作

template<class K,class T,class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;
public:typedef __HTIterator<T&,T*> iterator;typedef __HTIterator<const T&, const T*> const_iterator;const_iterator begin() const{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){// this -> const HashTable*return const_iterator(cur, this);}}return end();}const_iterator end() const{return const_iterator(nullptr, this);}iterator begin(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){// this -> HashTable*return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}HashTable(){_tables.resize(10, 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;// 不能重复插入//if (Find(kot(data)))//	return false;iterator it = Find(kot(data));if(it != end())return make_pair(it,false);Hash hs;// 扩容，负载因子为1if (_n == _tables.size()){// 将原节点链接到新表vector<Node*> newTables(_tables.size() * 2, 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;// 迭代往后走}// 没找到返回end()return end();}bool Erase(const K& key){KeyOfT kot;Hash hs;// 找到在哪个桶size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){// 找到该值if (kot(cur->_data) == key){// 删除的是第一个节点if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<Node*> _tables;size_t _n = 0;
};

5.2 unordered_set

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;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::const_iterator const_iterator;const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator,bool> insert(const K& key){return _ht.Insert(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;

5.3 unordered_map

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;typedef typename hash_bucket::HashTable<K, pair<const K,const V>, MapKeyOfT, Hash>::const_iterator const_iterator;const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}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;}
private:hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT, Hash> _ht;
};

6 完整代码

HashTable.h

#pragma once
#include<vector>template<class K>
struct HashFunc
{size_t operator()(const K& key){return size_t(key);}
};// 特化，string类型
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};namespace open_address
{enum State{EMPTY,EXIST,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state;};// 单独string版本仿函数struct StringHashFunc{// abcd// bcad// aadd// BKDRsize_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){// 有该则返回falseif (Find(kv.first))return false;// 扩容，载荷因子(有效数据个数/总的数据个数) >= 0.7则扩容// 整数相除还是整数，解决办法 : 1、*10 >= 7    2、*1.0成浮点数 if (_n * 10 / _tables.size() >= 7){方式一：创建新的顺序表//size_t newsize = _tables.size() * 2;//vector<HashData<K, V>> newtables(newsize);旧表重新计算负载到新表//for (size_t i = 0; i < _tables.size(); i++)//{}// 方式二：创建新的哈希表，复用Insert函数HashTable<K, V, Hash> newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){// 当前位置值存在则插入if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}// 交换两个哈希表的地址_tables.swap(newHT._tables);}// 计算放置数据的下标，key值可能不是整型，使用仿函数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;}HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();// 线性探测，存在/删除状态均需查找while (_tables[hashi]._state != EMPTY){// 删除状态不能查找if (_tables[hashi]._state != DELETE &&_tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){// 查找是否有该key值，有则将状态修改为删除并--n，没有则返回falseHashData<K, V>* ret = Find(key);if (ret == nullptr)return false;else{ret->_state = DELETE;--_n;return true;}}private:vector<HashData<K, V>> _tables;size_t _n = 0;// 有效数据个数};void TestHT1(){int a[] = { 10001,11,55,24,19,12,31 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}cout << ht.Find(55) << endl;cout << ht.Find(31) << endl;ht.Erase(55);cout << ht.Find(55) << endl;cout << ht.Find(31) << endl;}void TestHT2(){int a[] = { 10001,11,55,24,19,12,31 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(32, 32));ht.Insert(make_pair(32, 32));}// key不支持强转整形取模，那么就要自己提供转换成整形仿函数void TestHT3(){HashTable<string, int> ht;ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("left", 1));ht.Insert(make_pair("insert", 1));cout << StringHashFunc()("bacd") << endl;cout << StringHashFunc()("abcd") << endl;cout << StringHashFunc()("aadd") << endl;}void test_map1(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;}cout << countMap.load_factor() << endl;cout << countMap.max_load_factor() << endl;cout << countMap.size() << endl;cout << countMap.bucket_count() << endl;cout << countMap.max_bucket_count() << endl;for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}namespace hash_bucket
{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}};// 前置声明template<class K, class T, class KeyOfT, class Hash>class HashTable;//template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>//struct __HTIterator//{//	typedef HashNode<T> Node;//	typedef __HTIterator<K, T, KeyOfT, Hash> Self;//	//	Node* _node;//	// 获取哈希桶数据的指针//	HashTable<K, T, KeyOfT, Hash>* _pht;//	__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht)//		:_node(node)//		,_pht(pht)//	{}//	T& operator*()//	{//		return _node->_data;//	}//	Self& operator++()//	{//		// 当前桶没走完，找当前桶的下一个结点//		if (_node->_next)//		{//			_node = _node->_next;//		}//		else//		{//			Hash hs;//			KeyOfT kot;//			// 当前桶走完了，找下一个不为空的桶的第一个结点//			// 1、找当前结点在桶的哪个位置//			size_t i = hs(kot(_node->_data)) % _pht->_tables.size();//			++i;//			for (; i < _pht->_tables.size(); i++)//			{//				if (_pht->_tables[i])//					break;//			}//			// 循环结束有两种情况，一种break结束，一种循环结束//			// 循环结束，该结点的下一个为nullptr//			if (i == _pht._tables.size())//			{//				_node = nullptr;//			}//			else//			{//				_node = _pht->_tables[i];//			}//		}//	}//	bool operator!=(const Self& s)//	{//		return _node != s._node;//	}//};template<class K,class T,class KeyOfT,class Hash>class HashTable{typedef HashNode<T> Node;public:// 友元类 __HTIterator可以访问HashTable私有成员//template<class K, class T, class KeyOfT, class Hash>//friend struct __HTIterator;// 内部类template<class Ref,class Ptr>struct __HTIterator{typedef HashNode<T> Node;typedef __HTIterator Self;Node* _node;// 获取哈希桶数据的指针const HashTable* _pht;// 加const时const迭代器才能构造成功__HTIterator(Node* node, const HashTable* pht):_node(node), _pht(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){// 当前桶没走完，找当前桶的下一个结点if (_node->_next){_node = _node->_next;}else{Hash hs;KeyOfT kot;// 当前桶走完了，找下一个不为空的桶的第一个结点// 1、找当前结点在桶的哪个位置size_t i = hs(kot(_node->_data)) % _pht->_tables.size();++i;for (; i < _pht->_tables.size(); i++){if (_pht->_tables[i])break;}// 循环结束有两种情况，一种break结束，一种循环结束// 循环结束，该结点的下一个为nullptrif (i == _pht->_tables.size()){_node = nullptr;}else{_node = _pht->_tables[i];}}return *this;}bool operator!=(const Self& s){return _node != s._node;}};typedef __HTIterator<T&,T*> iterator;typedef __HTIterator<const T&, const T*> const_iterator;const_iterator begin() const{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){// this -> const HashTable*return const_iterator(cur, this);}}return end();}const_iterator end() const{return const_iterator(nullptr, this);}iterator begin(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){// this -> HashTable*return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}HashTable(){_tables.resize(10, 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;// 不能重复插入//if (Find(kot(data)))//	return false;iterator it = Find(kot(data));if(it != end())return make_pair(it,false);Hash hs;// 扩容，负载因子为1if (_n == _tables.size()){// 方式一：调用Insert函数，会对所有结点右一份拷贝，效率较低//HashTable<K, V> newHT;//newHT._tables.resize(_tables.size() * 2);//for (size_t i = 0; i < _tables.size(); i++)//{//	Node* cur = _tables[i];//	// 将每个桶中不为空的结点插入//	while (cur)//	{//		newHT.Insert(cur->_kv);//		cur = cur->_next;//	}//}交换两个哈希表的地址//_tables.swap(newHT._tables);// 方式二：将原节点链接到新表vector<Node*> newTables(_tables.size() * 2, 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;// 迭代往后走}// 没找到返回end()return end();}bool Erase(const K& key){KeyOfT kot;Hash hs;// 找到在哪个桶size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){// 找到该值if (kot(cur->_data) == key){// 删除的是第一个节点if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<Node*> _tables;size_t _n = 0;//vector<list<pair<K, V>>> _tables;};//void TestHT1()//{//	int a[] = { 10001,11,55,24,19,12,31,4,34,44};//	HashTable<int, int> ht;//	for (auto e : a)//	{//		ht.Insert(make_pair(e, e));//	}//	ht.Insert(make_pair(32, 32));//	ht.Insert(make_pair(32, 32));//	ht.Erase(31);//	ht.Erase(11);//}//void TestHT2()//{//	HashTable<string, int> ht;//	ht.Insert(make_pair("sort", 1));//	ht.Insert(make_pair("left", 1));//	ht.Insert(make_pair("insert", 1));//}
}

my_unordered_set.h

#pragma once
#include "HashTable.h"namespace lin
{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;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::const_iterator const_iterator;const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator,bool> insert(const K& key){return _ht.Insert(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};void Func(const unordered_set<int>& s){unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;}void test_unordered_set(){unordered_set<int> s;s.insert(31);s.insert(11);s.insert(5);s.insert(15);s.insert(25);unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;}
}

my_unordered_map.h

#pragma once
#include "HashTable.h"namespace lin
{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;typedef typename hash_bucket::HashTable<K, pair<const K,const V>, MapKeyOfT, Hash>::const_iterator const_iterator;const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}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;}private:hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT, Hash> _ht;};void test_unordered_map(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;}unordered_map<string, int>::iterator it = countMap.begin();while (it != countMap.end()){//it->first += 'x'; // key不能修改it->second += 1;  // value可以修改cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;#include "HashTable.h"
#include "my_unordered_set.h"
#include "my_unordered_map.h"
int main()
{//open_address::TestHT3();//open_address::test_map1();//hash_bucket::TestHT2();//lin::test_unordered_set();lin::test_unordered_map();return 0;
}

这篇关于C++第四十弹---从零开始：模拟实现C++中的unordered_set与unordered_map的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1099495。

相关文章

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2