从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)（中）：https://developer.aliyun.com/article/1522331
2.2 封装unordered_set和unordered_map
有了前面的经验（map的方括号重载要改insert的返回值），这里先把完整的unordered_set.h和unordered_map.h写出来，看看需要怎么改。封装就是套一层，还是很容易的：
完整unordered_map.h
#pragma once #include "HashTable.h" namespace rtx { 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); // 先看下面，所以insert要返回插入后的键值对 } bool find(const K& key) { return _ht.Find(key); } bool erase(const K& key) { return _ht.Erase(key); } V& operator[](const K& key) // 根据原功能，返回的是键值对中key对应的value的引用。 { // 当key不存在时，operator[]用默认value与key构造键值对然后插入 pair<iterator, bool> ret = _ht.Insert(make_pair(key, V())); return ret.first->second; } protected: HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht; }; }
完整unordered_set.h
#pragma once #include "HashTable.h" namespace rtx { 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) //和unordered_map保持一致 { return _ht.Insert(key); } bool find(const K& key) { return _ht.Find(key); } bool erase(const K& key) { return _ht.Erase(key); } protected: HashTable<K, K, Hash, SetKeyOfT> _ht; }; }
2.3 修改哈希桶
先给哈希桶的模板参数增加两个仿函数，用typedef封装迭代器，并给迭代器传对应的模板参数。还需要在哈希表中增加获取迭代器起始位置和结束位置的接口：
- 在获取其实位置时，需要从头开始遍历哈希表项，寻找到第一个桶的头节点作为起始位置。
- 使用空指针代替迭代器的结束位置。
- 在构造迭代器时，直接传this指针去定义迭代器中的哈希表指针。
在插入中，凡是使用到key值以及用key取模的地方，都要用仿函数取获得。包括删除和删除中也是，插入之前要查找下，先把查找改了：让其返回迭代器，如果存在，返回key所在位置的迭代器，如果不存在，返回末尾的迭代器。
iterator Find(const K& key) { if (_tables.size() == 0) { return end(); } Hash hs; KeyOfT kot; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { return iterator(cur,this); } cur = cur->_next; } return end(); }
然后修改哈希表的Inerst，返回由迭代器和布尔值组成的键值对。
- 先进行查找，如果存在，则返回key所在位置的迭代器和false组成的键值对。
- 查找结构不存在，则返回插入新节点后key所在位置的迭代器和true组成的键值对。
pair<iterator, bool> Insert(const T& data) { KeyOfT kot; iterator ret = Find(kot(data)); if (ret != end()) { return make_pair(ret, false); } Hash hs; if (_size == _tables.size()) // 负载因子到1就扩容 { //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newTables; //newTables.resize(newSize, nullptr); newTables.resize(__stl_next_prime(_tables.size()), 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; ++_size; return make_pair(iterator(newnode, this), true); }
删除只需在移除用上KeyOfT仿函数，然后就改完了，程序就能跑起来了：
完整HashTable.h：
#pragma once #include <iostream> #include <vector> using namespace std; template<class T> struct HashNode { T _data; HashNode* _next; // 不用存状态栏了，存下一个结点指针 HashNode(const T& data) :_data(data) , _next(nullptr) {} }; template<class K> struct HashFunc // 可以把闭散列的HashFunc放在外面直接用，但是这就不放了 { size_t operator()(const K& key) { return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行 } }; template<> struct HashFunc<string> // 上面的特化 { size_t operator()(const string& key) { size_t val = 0; for (const auto& ch : key) { val *= 131; val += ch; } return val; } }; template<class K, class T, class Hash, class KeyOfT> class HashTable; // 前置声明 template<class K, class T, class Hash, class KeyOfT> class __HashIterator { public: typedef HashNode<T> Node; typedef HashTable<K, T, Hash, KeyOfT> HT; typedef __HashIterator<K, T, Hash, KeyOfT> Self; Node* _node; // 数据结点 HT* _pht; // 哈希表指针 __HashIterator(Node* node, HT* pht) :_node(node) , _pht(pht) {} Self& operator++() { if (_node->_next) // 不是桶中的最后一个数据 { _node = _node->_next; } else // 是桶中的最后一个数据，找下一个桶 { Hash hs; KeyOfT kot; size_t i = hs(kot(_node->_data)) % _pht->_tables.size() + 1;//没+1是当前桶位置 for (; i < _pht->_tables.size(); ++i) { if (_pht->_tables[i]) // 向后迭代找到了有桶的位置 { _node = _pht->_tables[i]; // 把这个位置给_node break; } } if (i == _pht->_tables.size()) // 后面都没桶了 { _node = nullptr; } } return *this; // this调用该函数的对象（迭代器），指向下一个后解引用返回 } T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } bool operator!=(const Self& s) const { return s._node != _node; } bool operator==(const Self& s) const { return s._node == _node; } }; template<class K, class T, class Hash, class KeyOfT> class HashTable { public: template<class K, class T, class Hash, class KeyOfT> friend class __HashIterator; typedef HashNode<T> Node; 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); // 构造：(Node * node, HT * pht) } } 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; delete cur; cur = next; } _tables[i] = nullptr; } } iterator Find(const K& key) { if (_tables.size() == 0) { return end(); } Hash hs; KeyOfT kot; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { return iterator(cur,this); } cur = cur->_next; } return end(); } inline size_t __stl_next_prime(size_t n) { static const size_t __stl_num_primes = 28; static const size_t __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 }; for (size_t i = 0; i < __stl_num_primes; ++i) { if (__stl_prime_list[i] > n) { return __stl_prime_list[i]; } } return -1; // 不会走到这，随便返回一个值 } pair<iterator, bool> Insert(const T& data) { KeyOfT kot; iterator ret = Find(kot(data)); if (ret != end()) { return make_pair(ret, false); } Hash hs; if (_size == _tables.size()) // 负载因子到1就扩容 { //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newTables; //newTables.resize(newSize, nullptr); newTables.resize(__stl_next_prime(_tables.size()), 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; ++_size; return make_pair(iterator(newnode, this), true); } bool Erase(const K& key) { if (_tables.size() == 0) // 防止除零错误 { return false; } Hash hs; KeyOfT kot; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; while (cur) { if (kot(cur->_data) == key) { if (prev == nullptr) // 头插，先把指针数组存的指针指向cur的下一个 { _tables[hashi] = cur->_next; } else // 中间删 { prev->_next = cur->_next; } delete cur; // 统一在这delete return true; } prev = cur; // 往后走 cur = cur->_next; } return false; // 没找到 } size_t Size() // 存的数据个数 { return _size; } size_t TablesSize() // 表的长度 { return _tables.size(); } size_t BucketNum() // 桶的个数 { size_t num = 0; for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) // 如果不是空就有桶 { ++num; } } return num; } size_t MaxBucketLenth() // 最长桶的长度 { size_t maxLen = 0; for (size_t i = 0; i < _tables.size(); ++i) { size_t len = 0; Node* cur = _tables[i]; while (cur) { ++len; cur = cur->_next; } if (len > maxLen) { maxLen = len; } } return maxLen; } protected: vector<Node*> _tables; // 指针数组 size_t _size; };
Test.cpp:
#include "UnorderedSet.h" #include "UnorderedMap.h" namespace rtx { void test_unordered_set() { unordered_set<int> s; s.insert(2); s.insert(3); s.insert(1); s.insert(2); s.insert(5); unordered_set<int>::iterator it = s.begin(); //auto it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl << endl;; } void test_unordered_map() { unordered_map<string, string> dict; dict.insert(make_pair("sort", "排序")); dict.insert(make_pair("string", "字符串")); dict.insert(make_pair("left", "左边")); unordered_map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { cout << it->first << ":" << it->second << endl; ++it; } cout << endl; unordered_map<string, int> countMap; string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; for (const auto& e : arr) { countMap[e]++; } for (const auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } } } int main() { rtx::test_unordered_set(); rtx::test_unordered_map(); return 0; }
3. 题外话+笔试选择题
还有一些接口函数和仿函数参数这里并没有实现，正如以前说的，模拟实现不是为了造一个更好的轮子，而是理解它的底层实现。还有就是库里面unordered系列都提供了比较key相不相等的仿函数：
本篇模拟实现的是直接调用的等于，这样就写死了，比如key是日期类的指针比较就是比较指针的地址了，但是我们想要比较的是指针指向的内容。所以应该是要加上这个仿函数的，我们以前写过类似的这里就不加上去了。
所以就会有下面的面试题：
笔试选择题1：关于unordered_map和unordered_set说法错误的是（）
A.它们中存储元素的类型不同，unordered_map存储键值对，而unordered_set中只存储key
B.它们的底层结构相同，都使用哈希桶
C.它们查找的时间复杂度平均都是O(1)
D.它们在进行元素插入时，都得要通过key的比较去找待插入元素的位置
笔试选择题2：关于unordered_map和unordered_set说法错误的是（）
A.它们中都存储的键值对
B.map适合key有序的场景，unordered_map没有有序的要求
C.它们中元素查找的方式相同
D.map的底层结构是红黑树，unordered_map的底层结构是哈希桶
答案及解析：
笔试选择题1：
A：正确，参考unordered_map和unordered_set的文档说明
B：正确，都采用的是哈希桶来实现的
C：正确，哈希是通过哈希函数来计算元素的存储位置的，找的时候同样通过哈希函数找元素位 置，不需要循环遍历因此时间复杂度为O(1)
D：错误，不需要比较，只需要通过哈希函数，就可以确认元素需要存储的位置
选D
笔试选择题2：
A：正确，结合文档说明
B：正确，因为map的底层是红黑树，红黑树中序遍历可以得到关于key有序的序列，而unordered _map底层是哈希 桶，哈希对于其存储的元素是否有序，并不关心
C：错误，map按照二叉搜索树的规则查找，unordered_map按照哈希方式进行查找
D：正确
选C
本篇完。
下一篇也是高阶数据结构的内容：从C语言到C++_32（哈希的应用）位图bitset+布隆过滤器+哈希切割。
