前言

 之前博主写过哈希表的原理的文章，今天我们就一起学习一下库里面的unordered_set与unordered_map,并利用之前的框架搭建出来一个简单的unordered_set与unordered_map。

一、基本框架

1.HashTable

	//KeyOfT实现类型的泛化，KeyOfF实现不同类型的映射函数的实现方式的泛化。template<class K, class T,class KeyOfT,class KeyOfF = KeyOff<K>>class HashTable{template<class K, class T, class Ref, class Ptr,class KeyOfT,class KeyOfF>friend struct HashIterator;//友元模板的迭代器的声明。typedef HashNode<T> Node;//结点的声明。public:typedef HashIterator<K, T,T&,T*, KeyOfT,KeyOfF> iterator;//普通迭代器typedef HashIterator<K, T,const T&, const T*, KeyOfT,KeyOfF> const_iterator;//const迭代器//迭代器iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;//构造函数HashTable(size_t n = 17);//析构函数~HashTable();//插入函数pair<iterator,bool> insert(const T& data);//删除函数bool erase(const K& key);private:vector<Node*> _table;size_t _n = 0;//有效结点的个数};
}

2.unordered_set

template<class K>class unordered_set{typedef K key_type;typedef K val_type;struct SetOfT{//取Set里面的key};typedef HashTable<K, K, SetOfT> hash_type;typedef typename hash_type::const_iterator iterator;typedef iterator const_iterator;public:const_iterator begin() const;const_iterator end() const;bool insert(const key_type& key);bool erase(const key_type& key);private:hash_type _hash;};

3.unordered_map

	template<class K,class V>class unordered_map{typedef K key_type;typedef pair<const K, V> val_type;typedef V map_type;struct MapOfT{key_type operator()(const val_type& x){return x.first;}};typedef HashTable<key_type, val_type, MapOfT> hash_type;typedef typename hash_type::iterator iterator;typedef typename hash_type::const_iterator const_iterator;public:iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;bool insert(const pair<K, V>& data);map_type& operator[](const key_type& key );bool erase(const K& key);private:hash_type _hash;};

二、基本实现

1.类型的泛化

由于unordered_map与unordered_set的底层用的都是哈希表，但是：

• unordered_set的val_type是key
• unordered_map的val_type是pair<key,value>

哈希表的val_type为pair<key,value>,因此需要对哈希表再泛化，将哈希表的val_type改为T，实现泛化，并且对Node结点的结构也要进行修改，将其变为：

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

插入接口也变为：

    bool insert(const T& data);//此处是返回值是未实现迭代器之前的接口函数。

如此，unordered_map与unordered_set 通过传参进行控制T的类型，进而实现泛化。

2.仿函数

 但是由于对哈希表来说我们需要取出key来进行哈希映射，由于：

• unordered_set传入的模板参数T就是key
• unordered_map传入的模板参数T是pair<key,value>

因此为了取出unordered_map的key，需要在unordered_map与unordered_set传参时实现一个能取出key的功能，也就是仿函数。

因此

• HashTable的模板参数：

								//取出T里面的keytemplate<class K, class T,class KeyOfT,class KeyOfF = KeyOff<K>>class HashTable;

• unordered_set的仿函数

	struct SetOfT{key_type operator()(const val_type& key){return key;}};

• unordered_map的仿函数

	struct MapOfT{key_type operator()(const val_type& x){return x.first;}};

3.迭代器

• 说明：迭代器为正向迭代器，库里面不存在反向迭代器，因为单链表不支持倒着走，并且没有意义。

3.1基本框架

    template<class K, class T, class KeyOfK,class KeyOfF>class HashTable;template<class K, class T,class Ref, class Ptr, class KeyOfT ,class KeyOfF>struct HashIterator{typedef HashNode<T> Node;typedef HashIterator<K, T,Ref,Ptr, KeyOfT,KeyOfF> self;typedef HashTable<K, T, KeyOfT, KeyOfF> Table;typedef HashIterator<K, T, T&, T*, KeyOfT,KeyOfF> iterator;HashIterator(Node* node,const Table* table):_node(node),_hash(table){}HashIterator(const iterator& it):_node(it._node),_hash(it._hash){}self operator ++();Ref operator*();Ptr operator->();bool operator != (const self& it);bool operator == (const self& it);private:Node* _node;const Table* _hash;//哈希表的指针};

 看到这样的结构，其实会感觉奇怪，因为里面竟然多了一个指针，深入思考不难理解，其实我们在遍历完一条链上的数据时，需要跳到下一条链上，这时该如何跳呢？是不是该用到哈希表？这里的指针就是哈希表，用来帮助我们寻找下一条链。

因此：这里的HashTable的前置声明，和在哈希表中出现的友元模板的声明就可以解释通了。

3.2 ++

• 核心逻辑：如果当前链，当前结点的下一个元素，不为空，跳到下一个结点，为空，则找到哈希表中不为空的下一条链的第一个结点。

 self operator ++(){Node* cur = _node;assert(cur);if (cur->_next){_node = cur->_next;return *this;}else{KeyOfF getkey;KeyOfT kot;K key = kot(cur->_data);int innode = getkey(key) % _hash->_table.size();++innode;while (innode < (int)_hash->_table.size()){if (_hash->_table[innode]){_node = _hash->_table[innode];return *this;}++innode;}//空。_node = nullptr;return *this;}}

3.3 构造函数

• 细节1

     HashIterator(Node* node,const Table* table):_node(node),_hash(table){}

• 这里的Table* 前面加的const修饰不是没有原因的，因为在哈希表中的const迭代器：

const_iterator end() const;

 这里的const是修饰的this指针，也就是 Table*, 但是由于是被const修饰表明其指向的内容不可以被修改，因此如果Table* 不加const，表明权限放大，会报错的，因此，这里为了实现const迭代器需要在Table* 前const。

• 细节2

	//哈希表的定义typedef HashIterator<K, T,T&,T*, KeyOfT,KeyOfF> iterator;typedef HashIterator<K, T,const T&, const T*, KeyOfT\,KeyOfF> const_iterator;//迭代器的定义typedef HashIterator<K, T, T&, T*, KeyOfT,KeyOfF> iterator;HashIterator(const iterator& it):_node(it._node),_hash(it._hash){}

• 迭代器的类是struct，默认成员公有可以突破类域进行访问。
• 当迭代器为const迭代器时，这里的iterator为const迭代器，可以实现不同类型之间进行转换的效果。
• 迭代器的参数多一个T，看似没有用，其实在这里定义iterater时有奇效。

3.3 完整代码

    template<class K, class T, class KeyOfK,class KeyOfF>class HashTable;template<class K, class T,class Ref, class Ptr, \class KeyOfT ,class KeyOfF>struct HashIterator{typedef HashNode<T> Node;typedef HashIterator<K, T,Ref,Ptr, KeyOfT,KeyOfF> self;typedef HashTable<K, T, KeyOfT, KeyOfF> Table;typedef HashIterator<K, T, T&, T*, KeyOfT,KeyOfF> iterator;HashIterator(Node* node,const Table* table):_node(node),_hash(table){}HashIterator(const iterator& it):_node(it._node),_hash(it._hash){}self operator ++(){Node* cur = _node;assert(cur);if (cur->_next){_node = cur->_next;return *this;}else{KeyOfF getkey;KeyOfT kot;K key = kot(cur->_data);int innode = getkey(key) % _hash->_table.size();++innode;while (innode < (int)_hash->_table.size()){if (_hash->_table[innode]){_node = _hash->_table[innode];return *this;}++innode;}//空。_node = nullptr;return *this;}}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator != (const self& it){return _node != it._node;}   bool operator == (const self& it){return _node == it._node;}private:Node* _node;const Table* _hash;};

4.insert

 在实现了之前的仿函数与迭代器我们的insert的最终版本即可出来了：

  pair<iterator,bool> insert(const T& data){KeyOfF getkey;KeyOfT kot;size_t loadfactor = _n * 10 / _table.size();if (loadfactor >= 10){//换新表size_t newsize = 2 * _table.size();HashTable<K, T,KeyOfT> new_table(newsize);//只能移数据for (int i = 0; i < (int)_table.size(); i++){Node* node = _table[i];int innode = i % newsize;while (node){node->_next = new_table._table[innode];new_table._table[innode] = node;node = node->_next;}}//交换数据swap(_table, new_table._table);}int innode = getkey(kot(data)) % _table.size();Node* head = _table[innode];while (head){if (head->_data == data)//排除重复数据{return make_pair(iterator(head,this),false);}head = head->_next;}Node* newnode = new(Node)(data);//指向头结点，更新头结点。newnode->_next = _table[innode];_table[innode] = newnode;_n++;return make_pair(iterator(newnode,this),true);}

• unordered_set的实现

	bool insert(const key_type& key){return _hash.insert(key).second;}//返回迭代器的版本const_iterator insert(const key_type& key){pair<typename hash_type::iterator, bool> x = \_hash.insert(key);//利用之前模板写的构造函数，进行不同类型之间的转化。pair<const_iterator, bool> data(x.first, x.second);return data.first;}

• unordered_map的实现

	bool insert(const pair<K, V>& data){return _hash.insert(data).second;}

5. []

• 只有map才能实现

	map_type& operator[](const key_type& key ){pair<iterator, bool> x = _hash.insert(make_pair(key,\map_type()));return x.first->second;}

总结

 有之前的封装map与set的经验，想必这里按部就班一步一步进行实现，一步一步进行纠错是不难实现的，最后如果觉得文章有所帮助的话，不妨点个赞鼓励一下吧！