一、前言
在C++11中，STL提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，但是效率却提高了。
unordered系列的关联式容器之所以效率比较高，是因为unordered系列的关联式容器的底层使用了我们前面所讲到的哈希结构。那么今天我们就来看看 unordered_set和unordered_map这两个容器的使用及其实现。
二、容器的使用
1、unordered_map
1、 unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2、 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3、 在内部unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4、 unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5、unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
int main() { unordered_map<string, int> countMap; string arr[] = { "苹果","香蕉","苹果","葡萄"，"西瓜" }; for (auto& e : arr) { auto it = countMap.find(e); /*if (it == countMap.end()) { countMap.insert(make_pair(e, 1)); } else { it->second++; }*/ countMap[e]++; } for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } return 0; }
从运行结果我们可以看出 unordered_map里面的数据是无序且数据是可以有重复的。
2、unordered_set
1、不再以键值对的形式存储数据，而是直接存储数据的值。
2、容器内部存储的各个元素的值都互不相等，且不能被修改。
3、不会对内部存储的数据进行排序。
int main() { unordered_set<int> us; us.insert(10); us.insert(1); us.insert(10); us.insert(3); us.insert(4); us.insert(4); auto it = us.begin(); while (it != us.end()) { cout << *it << " "; it++; } cout << endl; return 0; }
从运行结果我们可以看出 unordered_set里面的数据是无序且没有重复的。
三、哈希表的改造
从标准库中我们知道，unordered_set和unordered_map这两个容器的底层结构都是哈希表。但是两个容器所存储的数据类型不同，前者存储的是 key类型的数据，后者存储的是 key/value类型的数据。所以为了方便，我们需要像实现 map和set的底层红黑树那样，去实现一个通用的哈希表。所以我们需要对哈希表改造一下，来满足两个容器都可以使用。
1、结点
首先，我们需要对节点改造，使其能够满足两种存储方式。
template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) {} };
2、哈希表的迭代器
我们需要对哈希表指针和结点指针进行封装。
template<class K, class T, class Hash, class KeyOfT> class HashTable; template<class K, class T, class Hash, class KeyOfT> struct _HashIterator { typedef HashNode<T> Node; typedef HashTable<K, T, Hash, KeyOfT> HT; typedef _HashIterator<K, T, Hash, KeyOfT> Self; Node* _node; HT* _ht; };
* 构造函数
_HashIterator(Node* node, HT* ht) :_node(node) , _ht(ht) {}
* 重载 *
T& operator*() { return _node->_data; }
* 重载 ->
T* operator->() { return &_node->_data; }
* 重载 ++
思路：如果当前的哈希桶还有节点（即下一个结点不为空），那么++就是当前桶的当前节点的下一个节点，如果当前元素是所在桶的最后一个元素，那么++就是找下一个非空的哈希桶。
Self& operator++() { if (_node->_next) { //当前桶迭代 _node = _node->_next; } else { // 找下一个桶 Hash hash; KeyOfT kot; size_t i = hash(kot(_node->_data)) % _ht->_tables.size(); i++; for (; i < _ht->_tables.size(); i++) { if (_ht->_tables[i]) { _node = _ht->_tables[i]; break; } } //说明后面没有有数据的桶了 if (i == _ht->_tables.size()) { _node = nullptr; } } return *this; }
* 重载 != 和 ==
bool operator!=(const Self& s)const { return _node != s._node; } bool operator==(const Self& s)const { return _node == s._node; }
3、哈希表的析构
~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; } }
4、unordered_map的 [] 实现
我们知道，unordered_map的操作中可以通过[]来访问数据，并修改value值，那么这是怎么做到的呢？
其实要想实现[]，我们需要先把insert的返回值修改成pair<iterator,bool>，最后的返回值也要一起修改。如果有重复的元素就返回这个位置的迭代器，没有重复的就返回新节点newnode的迭代器。
pair<iterator, bool> insert(const T& data) { Hash hash; KeyOfT kot; //去重 iterator ret = Find(kot(data)); if (ret != end()) { return make_pair(ret, false); } //扩容 if (_size == _tables.size()) { size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 10; vector<Node*> newTables; newTables.resize(newsize, nullptr); //将旧表中结点移动映射到新表 for (size_t 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); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; _size++; return make_pair(iterator(newnode, this), true); }
有了上面的插入，我们就可以在unordered_map中实现[]的操作了。
5、修改后的哈希表
#pragma once #include<iostream> #include<string> #include<vector> using namespace std; template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) {} }; //前置声明 template<class K, class T, class Hash, class KeyOfT> class HashTable; template<class K, class T, class Hash, class KeyOfT> struct _HashIterator { typedef HashNode<T> Node; typedef HashTable<K, T, Hash, KeyOfT> HT; typedef _HashIterator<K, T, Hash, KeyOfT> Self; Node* _node; HT* _ht; _HashIterator(Node* node, HT* ht) :_node(node) , _ht(ht) {} T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } Self& operator++() { if (_node->_next) { //当前桶迭代 _node = _node->_next; } else { // 找下一个桶 Hash hash; KeyOfT kot; size_t i = hash(kot(_node->_data)) % _ht->_tables.size(); i++; for (; i < _ht->_tables.size(); i++) { if (_ht->_tables[i]) { _node = _ht->_tables[i]; break; } } //说明后面没有有数据的桶了 if (i == _ht->_tables.size()) { _node = nullptr; } } return *this; } bool operator!=(const Self& s)const { return _node != s._node; } bool operator==(const Self& s)const { return _node == s._node; } }; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; //特化 template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t val = 0; for (auto ch : key) { val *= 131; val += ch; } return val; } }; template<class K, class T, class Hash, class KeyOfT> class HashTable { typedef HashNode<T> Node; template<class K, class T, class Hash, class KeyOfT> friend struct _HashIterator; public: typedef _HashIterator<K, T, Hash, KeyOfT> 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); } ~HashTable() { for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; free(cur); cur = next; } _tables[i] = nullptr; } } pair<iterator, bool> insert(const T& data) { Hash hash; KeyOfT kot; //去重 iterator ret = Find(kot(data)); if (ret != end()) { return make_pair(ret, false); } //扩容 if (_size == _tables.size()) { size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 10; vector<Node*> newTables; newTables.resize(newsize, nullptr); //将旧表中结点移动映射到新表 for (size_t 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); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; _size++; return make_pair(iterator(newnode, this), true); } iterator Find(const K& key) { if (_tables.size() == 0) return end(); Hash hash; KeyOfT kot; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return iterator(cur, this); else cur = cur->_next; } return end(); } bool erase(const K& key) { if (_tables.size() == 0) { return false; } Hash hash; KeyOfT kot; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; while (cur) { if (kot(cur->_data) == key) { // 1、头删 // 2、中间删 if (prev == nullptr) { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; _size--; return true; } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _tables; size_t _size = 0; };
四、 unordered_set的实现
#pragma once #include"HashTable.h" namespace zdl { template<class K, class Hash = HashFunc<K>> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename HashTable<K, K, Hash, SetKeyOfT>::iterator iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } pair<iterator, bool> insert(const K& key) { return _ht.insert(key); } private: HashTable<K, K, Hash, SetKeyOfT> _ht; };
五、unordered_map的实现
#pragma once #include"HashTable.h" namespace zdl { 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 HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.insert(kv); } V& operator[](const K& key) { pair<iterator, bool> ret = _ht.insert(make_pair(key, V())); return ret.first->second; } private: HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht; }; }
