【unordered_map和unordered_set的封装】

简介: 【unordered_map和unordered_set的封装】

1 哈希表的基本改造

这里的思路与前面讲解map/set的封装思路一致,STL不喜欢直接实例化出两份几乎相同的代码,所以用了模板参数来处理,还是老规矩:set中传入的是<K,K>,map中传入的是<K,Pair<K,V>>.这样我们在哈希桶的结构中只需要用一个T类型的模板参数接受上层传入的参数即可。

基本框架的改造:

namespace BucketHash
{
  template<class T>
  struct BucketHashNode
  {
    BucketHashNode* _next;
    T _data;
    BucketHashNode(const T& data)
      :_next(nullptr)
      ,_data(data)
    {}
  };
  template<class K>
  struct HashTranfor
  {
    size_t operator()(const K& k)
    {
      return (size_t)k;
    }
  };
  //特化一个版本出来
  template<>
  struct HashTranfor<string>
  {
    // BKDR
    size_t operator()(const string& key)
    {
      size_t val = 0;
      for (auto ch : key)
      {
        val *= 131;
        val += ch;
      }
      return val;
    }
  };
  static const int __stl_num_primes = 28;
  static const unsigned long __stl_prime_list[__stl_num_primes] =
  {
    53,         97,         193,       389,       769,
    1543,       3079,       6151,      12289,     24593,
    49157,      98317,      196613,    393241,    786433,
    1572869,    3145739,    6291469,   12582917,  25165843,
    50331653,   100663319,  201326611, 402653189, 805306457,
    1610612741, 3221225473, 4294967291
  };
  template<class K, class T,class Hash,class KeyOfT>//给出第一个模板参数的目的是为了Insert
                          //时能够正确将K插入
  class HashTable
  {
  private:
    typedef BucketHashNode<T> Node;
    vector<Node*> _tables;
    size_t _size = 0;
  public:
    size_t GetCapacity(size_t sz)
    {
      int i = 0;
      for (; i < __stl_num_primes; ++i)
      {
        if (sz < __stl_prime_list[i]) break;
      }
      return __stl_prime_list[i];
    }
    ~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;
      }
    }
    size_t Size()const
    {
      return _tables.size();
    }
    size_t BucketSize()const
    {
      int cnt = 0;
      for (int i = 0; i < Size(); ++i)
      {
        if (_tables[i])
          ++cnt;
      }
      return cnt;
    }
    size_t MaxBucketSize()const
    {
      int maxLen = 0;
      for (int i = 0; i < Size(); ++i)
      {
        Node* cur = _tables[i];
        int len = 0;
        while (cur)
        {
          ++len;
          cur = cur->_next;
        }
        maxLen = max(maxLen, len);
      }
      return maxLen;
    }
  };

注意:

  • 为了得到set和map比较的参数所以我们设置一个模板参数KeyOfT来获取set/map比较大小的数据。

2 迭代器

封装中最重要的一环就是迭代器了,那么究竟该如何设计迭代器呢?

2.1 迭代器的大致框架

首先我们来想想:迭代器究竟该有哪些成员?

由于迭代器要支持++操作(这里的迭代器不支持- -操作,因为是单向迭代器(底层用的是单链表)),所以我们得拿到整张表来方便我们遍历,我们还需要结点指针来帮助我们取数据。

所以我们就能够搭建出迭代器的大致框架了:

  //前置声明
  template<class K, class T, class Hash, class KeyOfT>
  class HashTable;
  //迭代器
  template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
  struct __TableIterator
  {
    typedef BucketHashNode<T> Node;
    typedef HashTable<K, T, Hash, KeyOfT> HTable;
    typedef __TableIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
    typedef __TableIterator<K, T, T&, T*, Hash, KeyOfT> Iterator;
    Node* _node;//结点指针,方便取数据
    HTable* _ht;//找到哈希表
    __TableIterator(Node* node,HTable* ht)
      :_node(node)
      ,_ht(ht)
    {}
    __TableIterator(const Iterator& it)
      :_node(it._node)
      ,_ht(it._ht)
    {}
    Ref operator*()
    {
      return _node->_data;
    }
    Ptr operator->()
    {
      return &_node->_data;
    }
    bool operator==(const Self& self)const
    {
      return self._node == _node;
    }
    bool operator!=(const Self& self)const
    {
      return self._node != _node;
    }
  };

注意:迭代器的成员变量由于用到了哈希桶结构,而哈希桶的实现在迭代器的下面,所以我们要在迭代器前面加上一个前置声明

现在的关键是如何实现出++运算符的重载。

2.2 ++运算符重载的实现

其实这个的实现也不难,我们已经拿到了哈希表,所以只需要从当前位置找到表中下一个位置即可:

    Self& operator++()
    {
      if (_node->_next)
        _node = _node->_next;
      else
      {
        Hash hash;
        KeyOfT kot;
        size_t hashi = hash(kot(_node->_data)) % _ht->Size();
        ++hashi;
        for (; hashi < _ht->Size(); ++hashi)
        {
          if (_ht->_tables[hashi])
          {
            _node = _ht->_tables[hashi];
            break;
          }
        }
        if (hashi == _ht->Size())
          _node = nullptr;
      }
      return *this;
    }

但是还有一个问题:我们哈希表的实现中成员变量是私有的,所以迭代器是不能够访问的,为了方便我们可以在哈希表结构中加上友元声明,当然大家自己也可以实现get接口取数据,方法有很多,大家可以自行选择。

class HashTable
  {
  private:
    template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
    friend struct __TableIterator;
    typedef BucketHashNode<T> Node
  };

2.3 哈希表的完善

  template<class K, class T,class Hash,class KeyOfT>//给出第一个模板参数的目的是为了Insert
                          //时能够正确将K插入
  class HashTable
  {
  private:
    template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
    friend struct __TableIterator;
    typedef BucketHashNode<T> Node;
    vector<Node*> _tables;
    size_t _size = 0;
  public:
    typedef __TableIterator<K, T, T&, T*, Hash, KeyOfT> iterator;
    typedef __TableIterator<K, T, const T&, const T*, Hash, KeyOfT> const_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);
    }
    const_iterator begin()const
    {
      for (size_t i = 0; i < _tables.size(); ++i)
      {
        if (_tables[i])
          return const_iterator(_tables[i], this);
      }
      return end();
    }
    const_iterator end()const
    {
      return const_iterator(nullptr, this);
    }
    size_t GetCapacity(size_t sz)
    {
      int i = 0;
      for (; i < __stl_num_primes; ++i)
      {
        if (sz < __stl_prime_list[i]) break;
      }
      return __stl_prime_list[i];
    }
    ~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;
      Hash hash;
      auto ret = Find(kot(data));
      if (ret != end())
        return make_pair(ret, false);
      //扩容,负载因子为1
      if (_size == _tables.size())
      {
        //int newcapacity = _tables.size() == 0 ? 10 : _tables.size() * 2;
        int newcapacity =GetCapacity(_tables.size());
        vector<Node*> newTables;//这里直接用vector的目的是可以直接用原表的结点直接链接即可
                    //不必多拷贝结点
        newTables.resize(newcapacity);
        for (int i = 0; i < _tables.size(); ++i)
        {
          Node* cur = _tables[i];
          //头插
          while (cur)
          {
            Node* next = cur->_next;
            size_t hashi = hash(kot(cur->_data)) % newTables.size();
            cur->_next = newTables[hashi];
            newTables[hashi] = cur;
            cur=next;
          }
          _tables[i] = nullptr;
        }
        _tables.swap(newTables);
      }
      size_t hashi = hash(kot(data)) % _tables.size();
      Node* newNode = new Node(data);//这里不要加kot
      newNode->_next = _tables[hashi];
      _tables[hashi] = newNode;
      ++_size;
      return make_pair(iterator(newNode,this), true);
    }
    iterator Find(const K& k)
    {
      if (_tables.size()==0)
        return end();
      KeyOfT kot;
      Hash hash;
      size_t hashi = hash(k) % _tables.size();
      Node* cur = _tables[hashi];
      while (cur)
      {
        if (kot(cur->_data) == k)
          return iterator(cur,this);
        cur = cur->_next;
      }
      return end();
    }
    bool Erase(const K& k)
    {
      if (Find(k) == nullptr)
        return false;
      KeyOfT kot;
      Hash hash;
      size_t hashi = hash(k) % _tables.size();
      if (kot(_tables[hashi]->_data) == k)
      {
        Node* del = _tables[hashi];
        _tables[hashi] = del->_next;
        delete del;
        --_size;
        return true;
      }
      Node* cur = _tables[hashi];
      while (cur->_next && kot(cur->_next->_data) != k)
      {
        cur = cur->_next;
      }
      Node* del = cur->_next;
      cur->_next = del->_next;
      delete del;
      --_size;
      return true;
    }
    size_t Size()const
    {
      return _tables.size();
    }
    size_t BucketSize()const
    {
      int cnt = 0;
      for (int i = 0; i < Size(); ++i)
      {
        if (_tables[i])
          ++cnt;
      }
      return cnt;
    }
    size_t MaxBucketSize()const
    {
      int maxLen = 0;
      for (int i = 0; i < Size(); ++i)
      {
        Node* cur = _tables[i];
        int len = 0;
        while (cur)
        {
          ++len;
          cur = cur->_next;
        }
        maxLen = max(maxLen, len);
      }
      return maxLen;
    }
  };

注意:由于迭代器的构造中我们需要哈希表的指针,而恰好this就是哈希表指针,所以我们传入this即可。另外find和inset时为了与STL保持一致,我们将返回值分别修改为iterator和pair<terator,bool>。

3 unordered_map和unordered_set的封装

这个思路与红黑树种map/set的封装思路一致,如何实现unordered_map支持修改val,不支持修改key;而unordered_set不支持修改key也是一致的:unordered_map的pair中的参数给<const K,V>,而unordered_set的普通迭代器是用const迭代器实现的,const迭代器也是用const迭代器实现的。

但是unordered_set中这样实现就会有一些问题:我们用了普通迭代器构造了const迭代器,这样肯定是会编译报错的,所以在迭代器的中我们还得增加一个构造:

    typedef __TableIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
    typedef __TableIterator<K, T, T&, T*, Hash, KeyOfT> Iterator;
    Node* _node;//结点指针
    HTable* _ht;//找到哈希表
    __TableIterator(const Iterator& it)
      :_node(it._node)
      ,_ht(it._ht)
    {}

这样如果上层传入的是普通迭代器那么就是一个拷贝构造,传入的是const迭代器的话就是用了普通迭代器构造const迭代器。这点大家一定要注意。

3.1 unordered_map

  template<class K, class V, class Hash = BucketHash::HashTranfor<K>>
  class unordered_map
  {
    struct MapKeyOfT
    {
      const K& operator()(const pair<K,V>& kv)
      {
        return kv.first;
      }
    };
  private:
    BucketHash::HashTable<K, pair<const K,V>, Hash, MapKeyOfT> _tab;
  public:
    typedef typename BucketHash::HashTable<K, pair<const K,V>, Hash, MapKeyOfT>::iterator iterator;
    //这里要加上typename 的原因是告诉编译器这里是模板的声明而不是静态成员的声明
    iterator begin()
    {
      return _tab.begin();
    }
    iterator end()
    {
      return _tab.end();
    }
    pair<iterator, bool> insert(const pair<K,V>& kv)
    {
      return _tab.Insert(kv);
    }
    V& operator[](const K& k)
    {
      auto ret = _tab.Insert(make_pair(k, V()));
      return ret.first->second;
    }
  };

3.2 unordered_set

  template<class K, class Hash = BucketHash::HashTranfor<K>>
  class unordered_set
  {
    struct SetKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  private:
    BucketHash::HashTable<K, K, Hash, SetKeyOfT> _tab;
  public:
    typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator;
    //这里要加上typename 的原因是告诉编译器这里是模板的声明而不是静态成员的声明
    typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator;
    iterator begin()
    {
      return _tab.begin();
    }
    iterator end()
    {
      return _tab.end();
    }
    const_iterator begin()const
    {
      return _tab.begin();
    }
    const_iterator end()const
    {
      return _tab.end();
    }
    pair<iterator, bool> insert(const K& k)
    {
      return _tab.Insert(k);
    }
  };

好了,这样封装基本上大致框架也就完成了。

如果该文对你有帮助的话能不能一键三连支持博主呢?💘💘💘


Fox!
+关注
目录
打赏
0
0
0
0
2
分享
相关文章
哈希表模拟封装unordered_map和unordered_set
哈希表模拟封装unordered_map和unordered_set
只会“有序无序”?面试官嫌弃的List、Set、Map回答!
小米,一位热衷于技术分享的程序员,通过与朋友小林的对话,详细解析了Java面试中常见的List、Set、Map三者之间的区别,不仅涵盖了它们的基本特性,还深入探讨了各自的实现原理及应用场景,帮助面试者更好地准备相关问题。
73 20
|
2月前
|
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
79 18
你对Collection中Set、List、Map理解?
【C++】unordered_map(set)
C++中的`unordered`容器(如`std::unordered_set`、`std::unordered_map`)基于哈希表实现,提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中,每个桶可存储一个或多个元素,以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列,以及迭代器。哈希函数用于计算元素的哈希值,冲突通过开链法解决,负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1),但在冲突较多时可能退化为O(n)。
37 5
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法,并探讨了它们在前端开发中的具体应用,包括如何利用这些数据结构来解决常见的编程问题。
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
【Java集合类面试二十二】、Map和Set有什么区别?
该CSDN博客文章讨论了Map和Set的区别,但提供的内容摘要并未直接解释这两种集合类型的差异。通常,Map是一种键值对集合,提供通过键快速检索值的能力,而Set是一个不允许重复元素的集合。
【Java集合类面试五】、 如何得到一个线程安全的Map?
如何得到一个线程安全的Map的方法包括:使用Collections工具类将Map包装为线程安全,使用java.util.concurrent包下的ConcurrentHashMap,以及不推荐使用性能较差的Hashtable。
【Java集合类面试四】、 描述一下Map put的过程
这篇文章详细描述了HashMap中put操作的过程,包括首次扩容、计算索引、插入数据以及链表转红黑树和可能的再次扩容。
【Java集合类面试四】、 描述一下Map put的过程
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等