devbox
喵喵爱编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

unordered_map和unordered_set的模拟实现和封装

作者：喵喵爱编程 | 2024-08-05 15:56:32

赞

踩

unordered_map和unordered_set的模拟实现和封装

闭散列哈希表和开散列哈希桶数据结构

  1. enum State//状态
  2.     {
  3.         EMPTY,//空
  4.         EXIST,//存在
  5.         DELETE//删除
  6.     };
  7.  
  8. template<class K, class V>
  9. struct HashData//数据结构
  10.     {
  11.         pair<K, V> _kv;
  12.         State _state = EMPTY;
  13.     };
  14. 		template<class T>
  15. 		struct HashNode
  16.     {
  17.         HashNode<T>* _next;
  18.         T _data;
  19.  
  20.         HashNode(const T& data)
  21.                 :_next(nullptr)
  22.                 , _data(data)
  23.         {}
  24.     };

闭散列哈希表实际上就是一个vector数组，本质和顺序表一样，为了方便删除，我们直接给各个数据设置一个State值，当为EMPTY时则为空，能够插入值，当为EXIST时则为存在，不能插入值，当我们需要删除时，直接把状态值设置为DELETE，视为删除，插入值时只需要判断是否为EMPTY或DELETE即可。
开散列哈希桶则就是vector中存入指针，然后将key值链接起来。

哈希表HashTable

  1. 	class HashTable
  2.     {
  3.     public:
  4. 				bool Insert(const pair<K, V>& kv);
  5. 				HashData<K, V>* Find(const K& key);
  6. 				bool Erase(const K& key);
  7.     private:
  8.         vector<HashData<K, V>> _tables;
  9.         size_t _n = 0; // 存储的数据个数
  10.     };

Find()

  1. 		HashData<K, V>* Find(const K& key)
  2.         {
  3.             if (_tables.size() == 0)
  4.             {
  5.                 return nullptr;
  6.             }
  7.  
  8.             size_t hashi = key % _tables.size();
  9.  
  10.             // 线性探测
  11.             size_t i = 1;
  12.             size_t index = hashi;
  13.             while (_tables[index]._state != EMPTY)
  14.             {
  15.                 if (_tables[index]._state == EXIST
  16.                         && _tables[index]._kv.first == key)
  17.                 {
  18.                     return &_tables[index];
  19.                 }
  20.  
  21.                 index = hashi + i;//往后找
  22.                 index %= _tables.size();//找了一圈后 index==hashi
  23.                 ++i;
  24.                 //找完全部后没找到就退出循环
  25.                 if (index == hashi)
  26.                 {
  27.                     break;
  28.                 }
  29.             }
  30.  
  31.             return nullptr;
  32.         }

数据查找只需判断这个值是否存在，然后再一个一个往后找即可，用hashi定位key位置，如果哈希冲突，则该key闭散列了，要往后找，index加上i值一个一个往后找，当找完一圈后再模%，相等即找完。

Erase()

  1. 		bool Erase(const K& key)
  2.         {
  3.             HashData<K, V>* ret = Find(key);
  4.             if (ret)
  5.             {
  6.                 ret->_state = DELETE;//修改状态值即可“删除”
  7.                 --_n;
  8.                 return true;
  9.             }
  10.             else
  11.             {
  12.                 return false;
  13.             }
  14.         }

找到值后修改State状态为DELETE即可。

Insert()

首先判断是否需要扩容，如果负载因子>=7，则扩容

  1. 			//判断是否扩容
  2. 			//if ((double)_n / (double)_tables.size() >= 0.7)
  3. 		    if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
  4.             {
  5.                 size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
  6.                 HashTable<K, V> newht;
  7.                 newht._tables.resize(newsize);
  8.  
  9.                 // 遍历旧表，重新映射到新表
  10.                 for (auto& data : _tables)
  11.                 {
  12.                     if (data._state == EXIST)
  13.                     {
  14.                         newht.Insert(data._kv);
  15.                     }
  16.                 }
  17.  
  18.                 _tables.swap(newht._tables);
  19.             }
  20.  
  21.             size_t hashi = kv.first % _tables.size();

扩容的方法是把旧表遍历一边，重新插入到新表中，然后再交换两个表，更新映射关系hashi即可

  1. 		bool Insert(const pair<K, V>& kv)
  2.         {
  3.             if (Find(kv.first))//找到就不插入了
  4.                 return false;
  5.             // 判断扩容
  6. 						//
  7.             // 线性探测
  8.             size_t i = 1;
  9.             size_t index = hashi;
  10.             while (_tables[index]._state == EXIST)
  11.             {
  12.                 index = hashi + i;
  13.                 index %= _tables.size();
  14.                 ++i;
  15.             }
  16.  
  17.             _tables[index]._kv = kv;
  18.             _tables[index]._state = EXIST;
  19.             _n++;
  20.  
  21.             return true;
  22.         }

扩容完成后再继续线性探测，找到空位置插入。

迭代器

  1. 	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
  2.     struct __HashIterator
  3.     {
  4.         typedef HashNode<T> Node;
  5.         typedef HashTable<K, T, KeyOfT, Hash> HT;
  6.         typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
  7.  
  8.         typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
  9.  
  10.         Node* _node;
  11.         const HT* _ht;
  12.  
  13.         __HashIterator(Node* node, const HT* ht)
  14.                 :_node(node)
  15.                 , _ht(ht)
  16.         {}
  17.  
  18.         __HashIterator(const Iterator& it)
  19.                 :_node(it._node)
  20.                 , _ht(it._ht)
  21.         {}
  22. 				Ref operator*()
  23.         {
  24.             return _node->_data;
  25.         }
  26.  
  27.         Ptr operator->()
  28.         {
  29.             return &_node->_data;
  30.         }
  31.  
  32.         bool operator!=(const Self& s)
  33.         {
  34.             return _node != s._node;
  35.         }

迭代器的实现难点在于套模版，其他和红黑树的迭代器一样，也可以用非const构造const迭代器

opertor++()

  1. 				Self& operator++()
  2.         {
  3.             if (_node->_next != nullptr)
  4.             {
  5.                 _node = _node->_next;
  6.             }
  7.             else
  8.             {
  9.                 // 找下一个不为空的桶
  10.                 KeyOfT kot;
  11.                 Hash hash;
  12.                 // 算出我当前的桶位置
  13.                 size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
  14.                 ++hashi;
  15.                 while (hashi < _ht->_tables.size())
  16.                 {
  17.                     if (_ht->_tables[hashi])
  18.                     {
  19.                         _node = _ht->_tables[hashi];
  20.                         break;
  21.                     }
  22.                     else
  23.                     {
  24.                         ++hashi;
  25.                     }
  26.                 }
  27.  
  28.                 // 没有找到不为空的桶
  29.                 if (hashi == _ht->_tables.size())
  30.                 {
  31.                     _node = nullptr;
  32.                 }
  33.             }
  34.  
  35.             return *this;
  36.         }

一个桶的链表结束后，再找下一个不为空的桶。这里用了两个仿函数kot和hash，就是把_data中的key值传出来和size进行比较，后面封装unorderedmap和unorderedset会用到仿函数

  1. struct MapKeyOfT
  2.         {
  3.             const K& operator()(const pair<K, V>& kv)
  4.             {
  5.                 return kv.first;
  6.             }
  7.         };
  8. struct SetKeyOfT
  9.         {
  10.             const K& operator()(const K& key)
  11.             {
  12.                 return key;
  13.             }
  14.         };
  15.

Hash是将key值转化成[可以取模的整型]的仿函数

  1. template<class K>
  2. struct HashFunc
  3. {
  4.     size_t operator()(const K& key)
  5.     {
  6.         return key;
  7.     }
  8. };
  9.  
  10. // 特化
  11. template<>
  12. struct HashFunc<string>
  13. {
  14.     // BKDR
  15.     size_t operator()(const string& s)
  16.     {
  17.         size_t hash = 0;
  18.         for (auto ch : s)
  19.         {
  20.             hash += ch;
  21.             hash *= 31;
  22.         }
  23.  
  24.         return hash;
  25.     }
  26. };

由于string的特殊性，需要单独处理，这里用到了特化这个案例；乘以31是为了处理字符相同但是顺序不同的情况。

哈希桶

  1. template<class K, class T, class KeyOfT, class Hash>
  2. class HashTable
  3. {
  4.   template<class K1, class T1, class Ref, class Ptr, class KeyOfT1, class Hash1>
  5.   friend struct __HashIterator;
  6.  
  7.   typedef HashNode<T> Node;
  8. public:
  9.   typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
  10.   typedef __HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
  11. private:
  12.         vector<Node*> _tables; // 指针数组
  13.         size_t _n = 0; // 存储有效数据个数
  14.     };

要让迭代器可以访问私有成员，将它设置为友元函数，注意，模版的命名不能冲突。

  1. 		iterator begin()
  2.         {
  3.             Node* cur = nullptr;
  4.             for (size_t i = 0; i < _tables.size(); ++i)
  5.             {
  6.                 cur = _tables[i];
  7.                 if (cur)
  8.                 {
  9.                     break;
  10.                 }
  11.             }
  12.  
  13.             return iterator(cur, this);
  14.         }
  15.  
  16.         iterator end()
  17.         {
  18.             return iterator(nullptr, this);
  19.         }
  20.  
  21.         const_iterator begin() const
  22.         {
  23.             Node* cur = nullptr;
  24.             for (size_t i = 0; i < _tables.size(); ++i)
  25.             {
  26.                 cur = _tables[i];
  27.                 if (cur)
  28.                 {
  29.                     break;
  30.                 }
  31.             }
  32.  
  33.             return const_iterator(cur, this);
  34.         }
  35.  
  36.         const_iterator end() const
  37.         {
  38.             return const_iterator(nullptr, this);
  39.         }

begin只需要找到第一个不为空的桶中的第一个节点即可，end则为空。

Find()

  1. 		iterator Find(const K& key)
  2.         {
  3.             if (_tables.size() == 0)
  4.                 return end();
  5.  
  6.             KeyOfT kot;
  7.             Hash hash;
  8.             size_t hashi = hash(key) % _tables.size();
  9.             Node* cur = _tables[hashi];
  10.             while (cur)
  11.             {
  12.                 if (kot(cur->_data) == key)
  13.                 {
  14.                     return iterator(cur, this);
  15.                 }
  16.  
  17.                 cur = cur->_next;
  18.             }
  19.  
  20.             return end();
  21.         }

find没什么好说的，直接找到映射的桶，然后遍历链表即可

Erase()

  1. 		bool Erase(const K& key)
  2.         {
  3.             Hash hash;
  4.             KeyOfT kot;
  5.             size_t hashi = hash(key) % _tables.size();
  6.             Node* prev = nullptr;
  7.             Node* cur = _tables[hashi];
  8.             while (cur)
  9.             {
  10.                 if (kot(cur->_data) == key)
  11.                 {
  12.                     if (prev == nullptr)
  13.                     {
  14.                         _tables[hashi] = cur->_next;
  15.                     }
  16.                     else
  17.                     {
  18.                         prev->_next = cur->_next;
  19.                     }
  20.                     delete cur;
  21.  
  22.                     return true;
  23.                 }
  24.                 else
  25.                 {
  26.                     prev = cur;
  27.                     cur = cur->_next;
  28.                 }
  29.             }
  30.  
  31.             return false;
  32.         }

删除即是找到节点，然后再头删这个节点即可。

Insert()

  1. 		pair<iterator, bool> Insert(const T& data)
  2.         {
  3.             KeyOfT kot;
  4.             iterator it = Find(kot(data));
  5.             if (it != end())
  6.             {
  7.                 return make_pair(it, false);
  8.             }
  9.             Hash hash;
  10.             // 负载因因子==1时扩容
  11.             if (_n == _tables.size())
  12.                 size_t newsize = GetNextPrime(_tables.size());
  13.                 vector<Node*> newtables(newsize, nullptr);
  14.                 //for (Node*& cur : _tables)
  15.                 for (auto& cur : _tables)
  16.                 {
  17.                     while (cur)
  18.                     {
  19.                         Node* next = cur->_next;
  20.  
  21.                         size_t hashi = hash(kot(cur->_data)) % newtables.size();
  22.  
  23.                         // 头插到新表
  24.                         cur->_next = newtables[hashi];
  25.                         newtables[hashi] = cur;
  26.  
  27.                         cur = next;
  28.                     }
  29.                 }
  30.  
  31.                 _tables.swap(newtables);
  32.             }
  33.  
  34.             size_t hashi = hash(kot(data)) % _tables.size();
  35.             // 头插
  36.             Node* newnode = new Node(data);
  37.             newnode->_next = _tables[hashi];
  38.             _tables[hashi] = newnode;
  39.  
  40.             ++_n;
  41.             return make_pair(iterator(newnode, this), false);
  42.         }

插入主要还是扩容比较麻烦，这里用的是质数扩容，库里面用的就是这个：

  1. size_t GetNextPrime(size_t prime)
  2.         {
  3.             // SGI
  4.             static const int __stl_num_primes = 28;
  5.             static const unsigned long __stl_prime_list[__stl_num_primes] =
  6.                     {
  7.                             53, 97, 193, 389, 769,
  8.                             1543, 3079, 6151, 12289, 24593,
  9.                             49157, 98317, 196613, 393241, 786433,
  10.                             1572869, 3145739, 6291469, 12582917, 25165843,
  11.                             50331653, 100663319, 201326611, 402653189, 805306457,
  12.                             1610612741, 3221225473, 4294967291
  13.                     };
  14.  
  15.             size_t i = 0;
  16.             for (; i < __stl_num_primes; ++i)
  17.             {
  18.                 if (__stl_prime_list[i] > prime)
  19.                     return __stl_prime_list[i];
  20.             }
  21.  
  22.             return __stl_prime_list[i];
  23.         }

最大桶

  1. 		size_t MaxBucketSize()
  2.         {
  3.             size_t max = 0;
  4.             for (size_t i = 0; i < _tables.size(); ++i)
  5.             {
  6.                 auto cur = _tables[i];
  7.                 size_t size = 0;
  8.                 while (cur)
  9.                 {
  10.                     ++size;
  11.                     cur = cur->_next;
  12.                 }
  13.  
  14.                 //printf("[%d]->%d\\n", i, size);
  15.                 if (size > max)
  16.                 {
  17.                     max = size;
  18.                 }
  19.             }
  20.  
  21.             return max;
  22.         }

 哈希表实现完后，对于unordered_map/set只需要简单封装一下即可

  1. #include "HashTable.h"
  2.  
  3. namespace lty
  4. {
  5.     template<class K, class V, class Hash = HashFunc<K>>
  6.     class unordered_map
  7.     {
  8.     public:
  9.         struct MapKeyOfT
  10.         {
  11.             const K& operator()(const pair<K, V>& kv)
  12.             {
  13.                 return kv.first;
  14.             }
  15.         };
  16.     public:
  17.         typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
  18.         typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
  19.  
  20.         iterator begin()
  21.         {
  22.             return _ht.begin();
  23.         }
  24.  
  25.         iterator end()
  26.         {
  27.             return _ht.end();
  28.         }
  29.  
  30.         const_iterator begin() const
  31.         {
  32.             return _ht.begin();
  33.         }
  34.  
  35.         const_iterator end() const
  36.         {
  37.             return _ht.end();
  38.         }
  39.  
  40.         pair<iterator, bool> insert(const pair<K, V>& kv)
  41.         {
  42.             return _ht.Insert(kv);
  43.         }
  44.  
  45.         V& operator[](const K& key)
  46.         {
  47.             pair<iterator, bool> ret = insert(make_pair(key, V()));
  48.             return ret.first->second;
  49.             //first==iterator  first-> == _node->_data  
  50.               first->second==_node->_data->second,也就是V值
  51.         }
  52.  
  53.         iterator find(const K& key)
  54.         {
  55.             return _ht.Find(key);
  56.         }
  57.  
  58.         bool erase(const K& key)
  59.         {
  60.             return _ht.Erase(key);
  61.         }
  62.  
  63.     private:
  64.         HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
  65.     };

set和map除了K、V值的不一样，还有就是map重载了[]，和红黑树的[]一样，返回pari的second值

  1. #pragma once
  2. #include "HashTable.h"
  3.  
  4. namespace lty
  5. {
  6.     template<class K, class Hash = HashFunc<K>>
  7.     class unordered_set
  8.     {
  9.     public:
  10.         struct SetKeyOfT
  11.         {
  12.             const K& operator()(const K& key)
  13.             {
  14.                 return key;
  15.             }
  16.         };
  17.     public:
  18.         typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
  19.         typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
  20.  
  21.         iterator begin()
  22.         {
  23.             return _ht.begin();
  24.         }
  25.  
  26.         iterator end()
  27.         {
  28.             return _ht.end();
  29.         }
  30.  
  31.         const_iterator begin() const
  32.         {
  33.             return _ht.begin();
  34.         }
  35.  
  36.         const_iterator end() const
  37.         {
  38.             return _ht.end();
  39.         }
  40.  
  41.         pair<iterator, bool> insert(const K& key)
  42.         {
  43.             return _ht.Insert(key);
  44.         }
  45.  
  46.         iterator find(const K& key)
  47.         {
  48.             return _ht.Find(key);
  49.         }
  50.  
  51.         bool erase(const K& key)
  52.         {
  53.             return _ht.Erase(key);
  54.         }
  55.  
  56.     private:
  57.         HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
  58.     };

迭代器直接调用哈希中的即可。

哈希表的实现难点就在于模版的套用，很绕，只要搞懂了模版是怎么套用的，实现就会变得简单，只要知道哈希表原理即可。 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/933046
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号