现在代码已经写得差不多了，那如果我们想用上面的代码统计出现次数可以吗？很明显不可以，因为字符串不能够取模。那么我们可以给HashTable增加一个仿函数Hash，其可以将不能取模的类型转成可以取模的类型。
template <class K> struct HashFunc { size_t operator()(const K& key) { return key; } }; // 特化 template <> struct HashFunc<string> { size_t operator()(const string& key) { size_t val = 0; for (auto ch : key) { val += ch; } return val; } };
注：要求 hashi 的地方都需要用仿函数Hash来求，也就是哈希函数。
上面写的仿函数HashFunc<string>写得并不是很好，因为其面对一些不相同的字符串，求出来的哈希值却是相同的，这样哈希冲突的概率就会上升了。
那我们参考该博客：字符串哈希算法改进一下。
// BKDRHash template <> struct HashFunc<string> { size_t operator()(const string& key) { size_t val = 0; for (auto ch : key) { val += 131 * val + ch; } return val; } };
以上就是闭散列的线性探测的内容，那我们来总结一下线性探测的优缺点。
线性探测优点：实现非常简单。
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据堆积，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。
为了缓解这个问题，二次探测就登场了。（注：它也无法完全解决哈希冲突的问题）
二次探测
bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; // 负载因子到了就要扩容 if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) { size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; HashTable<K, V, HashFunc<K>> newHT; newHT._tables.resize(newSize); // 旧表的数据映射到新表 for (auto& e : _tables) { if (e._state == EXIST) { newHT.Insert(e._kv); } } _tables.swap(newHT._tables); } // 二次探测 Hash hash; size_t i = 0; size_t start = hash(kv.first) % _tables.size(); size_t hashi = start; while (_tables[hashi]._state == EXIST) { ++i; hashi = start + i * i; hashi %= _tables.size(); } // 找到空位置就插入元素 _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_size; return true; }
闭散列的完整代码
namespace CloseHash { // 标识状态 enum State { EMPTY, EXIST, DELETE }; template <class K, class V> struct HashData { pair<K, V> _kv; State _state = EMPTY; }; template <class K> struct HashFunc { size_t operator()(const K& key) { return 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 V, class Hash = HashFunc<K>> class HashTable { public: HashData<K, V>* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } Hash hash; size_t hashi = hash(key) % _tables.size(); size_t start = hashi; while (_tables[hashi]._state != EMPTY) { // 状态不是删除才能找到,否则会有BUG if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } ++hashi; hashi %= _tables.size(); // 找了一圈都没找到 if (hashi == start) // 防止插入又删除的场景 break; } return nullptr; } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; // 负载因子到了就要扩容 if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) { size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; HashTable<K, V, HashFunc<K>> newHT; newHT._tables.resize(newSize); // 旧表的数据映射到新表 for (auto& e : _tables) { if (e._state == EXIST) { newHT.Insert(e._kv); } } _tables.swap(newHT._tables); } //Hash hash; //size_t hashi = hash(kv.first) % _tables.size(); // 注意模除的是_table.size() 线性探测 //while (_tables[hashi]._state == EXIST) //{ // ++hashi; // hashi %= _tables.size(); //} 找到空位置就插入元素 //_tables[hashi]._kv = kv; //_tables[hashi]._state = EXIST; //++_size; // 二次探测 Hash hash; size_t i = 0; size_t start = hash(kv.first) % _tables.size(); size_t hashi = start; while (_tables[hashi]._state == EXIST) { ++i; hashi = start + i * i; hashi %= _tables.size(); } // 找到空位置就插入元素 _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_size; return true; } bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) // 元素存在 { ret->_state = DELETE; --_size; return true; } else return false; } void Print() { for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]._state == EXIST) { printf("[%d:%d] ", i, _tables[i]._kv.first); } else { printf("[%d:*] ", i); } } cout << endl; } private: vector<HashData<K, V>> _tables; size_t _size = 0; // 有效数据的个数 }; }
线性探测和二次探测都没有从本质上解决哈希冲突占用位置的问题，这时候就需要开散列的拉链法（哈希桶）
2. 开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合。每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
注：拉链法并不会出现所有元素都在同一个同中的情况，因为有负载因子的存在，也就不会出现
O(N)的查找效率问题。如果还想进一步提高效率，桶中也可以挂红黑树。但是本人模拟实现的哈希桶是挂单向链表的，因为单向链表也够用了，相比双向链表更节省空间。
开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能。因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。由于素数作为哈希表的长度可以产生最分散的余数，从而尽可能减小哈希冲突。所以，我们可以提前生成一个素数表就能知道下一次扩容的大小了。
namespace HashBucket { // 哈希函数 template <class K> struct HashFunc { size_t operator()(const K& key) { return 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 V> struct HashNode { pair<K, V> _kv; HashNode<K, V>* _next; HashNode(const pair<K, V>& kv) : _kv(kv) , _next(nullptr) {} }; template <class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; private: 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; } public: Node* Find(const K& key) { if (_tables.size() == 0) return nullptr; // 在对应的桶查找 Hash hash; //size_t hashi = Hash()(key) % _tables.size(); size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) return cur; cur = cur->_next; } return nullptr; } bool Insert(const pair<K, V>& kv) { // 去重 if (Find(kv.first)) return false; // 负载因子到1扩容 if (_size == _tables.size()) { //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newTables(__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; Hash hash; size_t hashi = hash(cur->_kv.first) % newTables.size(); cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } // 头插 Hash hash; size_t hashi = hash(kv.first) % _tables.size(); Node* newnode = new Node(kv); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_size; return true; } bool Erase(const K& key) { if (_tables.size() == 0) return false; Hash hash; size_t hashi = hash(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { // 头删 if (prev == nullptr) _tables[hashi] = cur->_next; else // 中间删 prev->_next = cur->_next; delete cur; --_size; return true; } prev = cur; cur = cur->_next; } return false; // 表中没有key } HashTable() = default; // 强制生成默认构造函数 // 拷贝构造采用的是尾插 HashTable(const HashTable& ht) { _tables.resize(ht._tables.size(), nullptr); _size = ht._size; // 深拷贝 for (size_t i = 0; i < ht._tables.size(); ++i) { Node* tail = nullptr; Node* cur = ht._tables[i]; Node* next = nullptr; while (cur) { next = cur->_next; Node* newnode = new Node(cur->_kv); if (tail == nullptr) _tables[i] = newnode; else tail->_next = newnode; tail = newnode; cur = next; } } } // 析构函数 ~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; } } // 元素的个数 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 > 0) // printf("[%d]号桶长度:%d\n", i, len); if (len > maxLen) { maxLen = len; } } return maxLen; } private: vector<Node*> _tables; size_t _size = 0; // 有效数据的个数 }; void TestHT1() { int n = 1000000; vector<int> v; v.reserve(n); srand(time(0)); for (int i = 0; i < n; ++i) { //v.push_back(i); v.push_back(rand() + i); // 重复少 //v.push_back(rand()); // 重复多 } size_t begin1 = clock(); HashTable<int, int> ht; for (auto e : v) { ht.Insert(make_pair(e, e)); } size_t end1 = clock(); cout << "数据个数:" << ht.Size() << endl; cout << "表的长度:" << ht.TablesSize() << endl; cout << "桶的个数:" << ht.BucketNum() << endl; cout << "平均每个桶的长度:" << (double)ht.Size() / (double)ht.BucketNum() << endl; cout << "最长的桶的长度:" << ht.MaxBucketLenth() << endl; cout << "负载因子:" << (double)ht.Size() / (double)ht.TablesSize() << endl; } }
3. 开散列与闭散列比较
应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子 a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。
哈希表的插入只要是扩容和重新映射位置带来的消耗，而 set 是红黑树中节点的变色和旋转。如果提前知道哈希表的长度，我们可以通过 resize 或者 reserve 接口提前开好空间，减小扩容带来的消耗。
👉开散列实现 unordered_map 和 unordered_set👈
想要开散列实现 unordered_map 和 unordered_set，需要改造开散列Find和Insert函数，再加上一个迭代器和取得类型的仿函数。
#pragma once namespace Joy { // 哈希函数 template <class K> struct HashFunc { size_t operator()(const K& key) { return 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 T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) : _data(data) , _next(nullptr) {} }; // 前置声明:因为__HashIterator需要使用HashTable* template <class K, class T, class Hash, class KeyOfT> class HashTable; // K是关键字key的的类型,T是节点数据的类型,Hash是哈希函数,KeyOfT是取出key值大小的仿函数 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* _pht; // 指向哈希表的指针 __HashIterator(Node* node, HT* pht) : _node(node) , _pht(pht) {} 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)) % _pht->_tables.size(); ++i; for (; i < _pht->_tables.size(); ++i) { // 找到第一个不为空的桶就break if (_pht->_tables[i]) { _node = _pht->_tables[i]; break; } } // 说明后面没有有数据的桶了 if (i == _pht->_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, class T, class Hash, class KeyOfT> class HashTable { typedef HashNode<T> Node; friend struct __HashIterator<K, T, Hash, KeyOfT>; private: 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; } public: typedef __HashIterator<K, T, Hash, KeyOfT> iterator; iterator begin() { for (size_t i = 0; i < _tables.size(); ++i) { // 第一个不为空的桶就是begin() if (_tables[i]) return iterator(_tables[i], this); } return end(); } iterator end() { return iterator(nullptr, this); } iterator Find(const K& key) { if (_tables.size() == 0) return end(); // 在对应的桶查找 Hash hash; KeyOfT kot; //size_t hashi = Hash()(key) % _tables.size(); size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return iterator(cur, this); cur = cur->_next; } return end(); // key不在哈希表中 } pair<iterator, bool> Insert(const T& data) { Hash hash; KeyOfT kot; // 去重 iterator ret = Find(kot(data)); if (ret != end()) return make_pair(ret, false); // 负载因子到1扩容 if (_size == _tables.size()) { //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newTables(__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 = 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); } bool Erase(const K& key) { if (_tables.size() == 0) return false; Hash hash; size_t hashi = hash(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { // 头删 if (prev == nullptr) _tables[hashi] = cur->_next; else // 中间删 prev->_next = cur->_next; delete cur; --_size; return true; } prev = cur; cur = cur->_next; } return false; // 表中没有key } HashTable() = default; // 强制生成默认构造函数 // 拷贝构造采用的是尾插 HashTable(const HashTable& ht) { _tables.resize(ht._tables.size(), nullptr); _size = ht._size; // 深拷贝 for (size_t i = 0; i < ht._tables.size(); ++i) { Node* tail = nullptr; Node* cur = ht._tables[i]; Node* next = nullptr; while (cur) { next = cur->_next; Node* newnode = new Node(cur->_data); if (tail == nullptr) _tables[i] = newnode; else tail->_next = newnode; tail = newnode; cur = next; } } } // 析构函数 ~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; } } 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 > 0) // printf("[%d]号桶长度:%d\n", i, len); if (len > maxLen) { maxLen = len; } } return maxLen; } private: vector<Node*> _tables; size_t _size = 0; // 有效数据的个数 }; }
哈希表的迭代器中有节点的指针和指向哈希表的指针，因为迭代器是用来遍历的，所以需要哈希表才能找到下一个节点的指针。因为哈希表是在迭代器后面实现的，所以要在前面加一个哈希表的前置声明。注意：因为哈希表是私有的，所以可以将迭代器弄成哈希表的友元类，友元声明时也需要将模板参数带上。还需要注意的是，哈希表的 const 迭代器不能复用普通迭代器的代码。
实现 unordered_map 和 unordered_set
#pragma once #include "HashTable.h" namespace Joy { 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: // 加上typename告诉编译器这是类型声明 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; } unordered_map() = default; // 拷贝构造 unordered_map(const unordered_map& m) : _ht(m._ht) {} private: HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht; }; void MapTest() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; unordered_map<string, int> countMap; for (auto& str : arr) { ++countMap[str]; } for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl; } }
#pragma once #include "HashTable.h" namespace Joy { 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); } unordered_set() = default; // 拷贝构造 unordered_set(const unordered_set& s) : _ht(s._ht) {} private: HashTable<K, K, Hash, SetKeyOfT> _ht; }; void SetTest() { unordered_set<int> s; s.insert(2); s.insert(1); s.insert(3); s.insert(5); s.insert(4); for (auto e : s) { cout << e << " "; } cout << endl; } }
unordered_map 和 unordered_set 的接口并没有全部实现，主要是理解它们实现的原理。
一道小小的面试题：一个类型K去做set和 unordered_set 的模板参数要什么要求？set 要求该类型能够支持小于比较或者显示提供比较的仿函数，unordered_set 要求该类型对象能够转换成整型或者提供转换成整型的仿函数，还要求该类型对象可以支持等于比较或者提供等于比较的仿函数（判断哈希表中是否已经存在该对象）。
👉总结👈
本篇博客主要介绍什么是哈希表、哈希表的使用、哈希冲突、闭散列和开散列的实现以及 unordered_map 和 unordered_set 的模拟实现等等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
