模拟实现STL中的unordered_map和unordered_set

目录

1.unordered_map和unordered_set简介

2.unordered_map和unordered_set设计图

3.迭代器的设计

4.哈希表的设计

5.my_unordered_map和my_unordered_set代码

1.unordered_map和unordered_set简介

unordered_map和unordered_set的使用非常类似于map和set，两者之间的差异在于底层的数据结构不同，unordered_map和unordered_set的底层使用的数据结构是哈希表，map和set底层使用的数据结构是红黑树。哈希表和红黑树都是查找效率非常高的数据结构，红黑树的查找效率是O(logN)，哈希表的查找效率是O(1)，总体来说哈希表的查找效率略胜一筹，但是红黑树是接近平衡的二叉搜索树，具有隐藏技能 —— 中序遍历，数据有序(升序)，map和set的遍历采用的就是中序遍历；也就是说，遍历map和set得到的数据是有序的，而哈希表的遍历是无序的，所以，为了区分功能相同而底层数据结构的不同的关联式容器，以哈希表为底层数据结构的map和set前加上unordered，unordered其实就是无序的意思。

2.unordered_map和unordered_set设计图

unordered_map和unordered_set底层是开散列方式实现的哈希表，要想实现unordered_map和unordered_set，需要在内部封装哈希表；但是，STL中的容器都提供统一的访问方式 —— 迭代器，所以我们还需要实现unordered_map和unordered_set的迭代器。说白了，unordered_map和unordered_set就是通过组合 哈希表 和 迭代器 来实现的。而unordered_map和unordered_set实现上的区别就是内部存储的数据不同(一个存储键值对，一个存储元素本身)，但是整体的设计框架是相同的。

unordered_map和unordered_set的设计图如下：

一个问题：unordered_map中存储的是键值对，unordered_set中存储的是一个个的元素，而二者的底层使用的数据结构都是 开散列实现的哈希表，那我们需要将哈希表实现两份吗？这个问题和map和set中数据存储的问题相同，如果实现两份的话，就会造成代码重复和冗余；解决方案也是和map、set中解决该问题的方式相同。请看下图：

可以看出，在使用上，unordered_set传递一个模板参数，unordered_map传递两个模板参数，但是在unordered_map和unordered_set中封装的哈希表都需要传递两个参数；所以unordered_map中将K类型传给底层哈希表的第一个参数，用 K 和 V封装出pair<K,V>类型传给 底层哈希表的第二个参数；unordered_set中传递给底层哈希表的第一个和第二个参数的类型都是K。这样，哈希表中第二个模板参数T就是哈希表中实际存储的数据类型。于是，就实现了复用同一个 哈希表的类模板。

那第一个模板参数是不是没用呢？并不是，因为，unordered_map和unordered_set的使用上是以Key值  (K类型的数据) 为主的，并且有些操作也是根据Key值来进行的，比如：查找操作。所以我们也是需要单独的K类型的数据的。

获取数据中的Key值问题

由于同一个类模板的哈希表中经常涉及数据的比较，unordered_set中数据的比较是按照Key值来比较的，unordered_map中数据的比较也是按照Key值来比较的。但是在同一个类模板的哈希表中不能使用同样的方式获取Key值，所示实现一个获取Key值的仿函数，该仿函数作为参数传递给哈希表。

实现代码如下：

// unordered_map中获取Key值的仿函数
struct MapKeyOfT
{const K& operator()(const pair<K, V>& kv){return kv.first;}
};// unordered_set中获取Key值的仿函数
struct SetKeyOfT
{const K& operator()(const K& key){return key;}
};

3.迭代器的设计

unordered_map和unordered_set迭代器的设计不同于map和set，map和set的迭代器的操作主要是是在一棵二叉搜索树上进行，所以封装结点的指针即可；但是unordered_map和unordered_set的迭代器的操作是在哈希表上进行的，而哈希表是由 _table 和 _table下挂的一个个的结点组成的，所以 unordered_map 和 unordered_set 的迭代器需要封装 哈希表 和 结点的指针 (对于哈希表的封装，也采用指针的形式) 。

迭代器总体设计图如下：

迭代器的那些操作

operator* 和 operator->操作：迭代器模仿的是指针的操作，指针常用的操作就是 解引用 * 和 箭头访问操作符 ->；operator* 用于取出结点中的数据，operator->用于返回节点中数据的地址。代码如下：

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

迭代器的++操作：迭代器的++操作用于实现 用迭代器遍历哈希表中的数据，所以我们需要依次遍历桶，如果桶不为空，就遍历桶中的数据，遍历完当前桶中的数据之后，再遍历下一个桶中的数据；如果桶为空，直接遍历下一个桶；迭代器++操作代码如下：

		Self& operator++(){if (_node->_next){// 当前桶还是节点_node = _node->_next;}else{// 当前桶走完了，找下一个桶KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();// 找下一个桶hashi++;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}hashi++;}// 后面没有桶了if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}

判断相等和不相等操作：迭代器判断相等和不相等，只需要判断迭代器中 结点的指针是否相等。代码如下所示：

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

4.哈希表的设计

哈希表的实现有闭散列和开散列两种方式，我们采用开散列的方式实现，哈希表的设计图如下所示：

哈希函数

哈希表主要通过哈希函数来计算出 存储的数据 和 数据存储的位置 之间的映射关系。在该设计中，我们采用 除留余数法 来计算 存储元素 和 存储位置 之间的映射关系；但是，该方法只适用于整形的数据，因为并不是所有类型的数据都能进行取余运算，所以，对于一些不能取余的类型的数据，我们需要提供一个仿函数来计算出其哈希值，方便其进行取余运算，从而计算出数据的存储位置。

哈希函数示例代码如下：

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
// 特化
template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}
};

哈希表中的操作

begin()和end()操作：begin()用于返回哈希表中第一个结点的迭代器，end()用于返回最后一个结点的下一个位置的迭代器，其实就是空。

代码实现如下：

    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);}

数据的插入：哈希表中插入数据是哈希表的精髓，因为数据的插入位置和数据之间通过哈希函数建立一 一映射的关系，通过数据的值，就可以很快的判断出数据存储的位置；并且通过限制负载因子来防止桶中的数据过多，从而为飞速的查找效率打下基础。

开散列的哈希表中的数据的插入采用头插的方式，代码实现如下：

bool Insert(const T& data)
{KeyOfT kot;if (Find(kot(data)))return false;Hash hs;// 负载因子到1就扩容if (_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 true;
}

数据的查找：在哈希表中查找一个值，首先通过哈希函数计算出该元素在哈希表中的第几个桶，然后遍历该桶下的数据，找到了就返回该结点的地址，没找到就返回空。

代码如下：

Node* 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 cur;}cur = cur->_next;}return nullptr;
}

数据的删除：删除一个数据的时候，首先要找到该数据所在的结点，找到该结点之后，删除即可。如果不存在该数据，则返回false。

删除代码如下：

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){prev->_next = cur->_next;}else{_tables[hashi] = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;
}

5.my_unordered_map和my_unordered_set代码

my_unordered_map代码如下：

#include "Open_HashTable.h"namespace wall
{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;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const pair<K, V>& kv){return _ht.Insert(kv);}bool erase(const K& key){_ht.Erase(key);}iterator find(const K& key){Node* ret = Find(key);return iterator(ret);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};
}

my_unordered_set代码如下：

#include "Open_HashTable.h"namespace wall
{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;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const K& key){return _ht.Insert(key);}bool erase(const K& key){_ht.Erase(key);}iterator find(const K& key){Node* ret = Find(key);return iterator(ret);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};
}

总结：可以看出，模拟实现的unordered_map和unordered_set主要是对 哈希表 和 迭代器进行了组合和封装，通过添加一些操作来更加方便的使用底层的数据结构。