C++--哈希封装my_unordered_set和my_unordered_map

目录

一，引言

二，基本结构

三，hash迭代器

四，HashTable的基本结构

一，引言

在实现哈希表之后，在unordered_set和unordered_map的学习中。了解到这两者的数据结构底层是由哈希表实现的，为此在实现哈希表的基础上对哈希表进行封装。

二，基本结构

首先要需要对Node节点进行修改。此过程和红黑树的封装类似。由上层结构决定是set还是map：
参考代码如下：

template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) {} };

T的具体类型由上层传入进行决定。

KeyOFT仿函数以及hash仿函数

在上述节点的基本类型中为T类型，因此并不直到上层究竟是map还是set。为此第一个仿函数的作用是返回这两者的key值。

hash仿函数和哈希表的实现中作用一致，这里就不详细讲解。

三，hash迭代器

哈希表表支持的迭代器是单向迭代器，红黑树所支持的是双向迭代器。但是基础机构基本上相似，参考代码如下：

template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash> struct HTIterator { typedef HashNode<T> Node; typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self; Node* _node; const HashTable<K, T, KeyOfT, Hash>* _pht; HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht) :_node(node) , _pht(pht) {} };

由于迭代器要实现++操作。哈希表内部是链式结构，在迭代器++的过程中，当该节点所链接的节点结束，则需要寻找下一个数组的节点。为此不仅需要node指针指向节点，还需要哈希表指针指向该哈希表。

在该迭代器的模板的第二，三，四个参数分别代表这数据（数据类型）（数据指针类型）（数据引用类型）。方便后续区分const迭代器。在迭代器内部封装的结构和红黑树相似。

operator*

Ref operator*() { return _node->_data; }

operator->

Ptr operator->() { return &_node->_data; }

operator!=

bool operator!=(const Self& s) { return _node != s._node; }

operator++

Self& operator++() { if (_node->_next) { _node = _node->_next; } else { KeyOfT kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _pht > _tables.size(); ++hashi; while (hashi < _pht->_tables.size()) { if (_pht->_tables[hashi]) { break; } ++hashi; } if (hashi == _pht->_tables.size()) { _node = nullptr; // end() } else { _node = _pht->_tables[hashi]; } } return *this; }

若该节点的下一个位置还有节点，则直接node++。若已经到这条链的最后一个节点。则重新确定这个节点的位置。找到下一个非空节点。返回这个位置的迭代器。

四，HashTable的基本结构

template<class K, class T, class KeyOfT, class Hash> class HashTable { // 友元声明 template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash> friend struct HTIterator; typedef HashNode<T> Node; public: typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> private: vector<Node*> _tables; // size_t _n = 0; // };

这里需要注意类模板的友元声明。使得上文HTIterator能够访问HashTable的私有成员。

下面就是迭代器封装

Iterator Begin() { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) { return Iterator(cur, this); } } return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin() const { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) { return ConstIterator(cur, this); } } return End(); } ConstIterator End() const { return ConstIterator(nullptr, this); }

Insert的修改

Insert修改和这个基本上都类似。

五，my_unordered_set封装

基本结构和红黑树相似，与红黑树不同的是这里需要提供上文中所将到的KeyOFT，来返回key的值，参考代码如下：

struct SetKeyOfT { const K& operator()(const K& key) { return key; } };

基本结构如下：

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>::ConstIterator const_iterator; private: hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht; };

这里需要注意不能单单用typedef，而是要使用typedef typename来强调后者修饰的是类型，而不是变量。map和set基本上一致。