一、先实现哈希桶

1.1哈希桶的实现方法

1.2日常普遍的哈希桶存放的数据有两种：字符串和整形

为了减少字符串的误判（比如"abcd" 和 “acbd”）,我们每次加上一个字符串乘以一个数（这里我们可以查看字符串哈希算法）

这里我们每次就乘以31。

1.3哈希桶的实现代码+详解

1.3.1哈希桶的两种仿函数（int和string）

1.3.2哈希桶的节点（如果桶非常深，这里考虑挂红黑树）

1.3.3哈希表的构造函数、析构函数

1.3.4哈希表的查找和删除（和析构函数的原理类似）

这里有一点点的细节处理：需要判断该桶删除的位置到底是头，还是其他位置，分一下类

1.3.5哈希表的插入（这里插入需要判断总共桶的深度是否大于桶的长度，大于就扩容，桶太深不易于查找）

1.4哈希桶的测试

二、unordered_map、unordered_set的仿函数封装

2.1先封装仿函数

2.2加入迭代器（迭代器里面要存这张表，还有这个这个节点，然后还有对应的桶的序号）

2.3哈希桶改造（加入迭代器，为了使迭代器能够访问到表里面的私有成员，我们加了一个友元）

2.4unordered_map、unordered_set的内部封装

2.5const迭代器的改造

三、封装代码（比库里面的快一些，因为(在VS编辑器下)库里面的unordered_map、unordered_set里面需要多维护维护一个指针，这个指针是从插入第一个节点开始维护的）

unordered_map.h#pragma once
#include"HashTable.h"
namespace SF
{template<class K,class V,class Hash = HashFunc<K>>class unordered_map{struct KeyOfMap{const K& operator()(const pair<K, V>& kv){return kv.first;}};public://HashTable<K, pair<const K, V>, Hash, KeyOfMap>typedef typename hash_bucket::HashTable<K, pair<const K, V>, Hash, KeyOfMap>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}const V& operator[](const K& key) const{pair<iterator, bool> ret = _ht.Insert(make_pair(key,V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K,V>& data){return _ht.Insert(data);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, pair<const K,V>, Hash, KeyOfMap> _ht;};void test_map(){unordered_map<string, string> dict;dict.insert(make_pair("sort",""));dict.insert(make_pair("string","ַ"));dict.insert(make_pair("insert",""));auto iter = dict.begin();for (auto& kv : dict){//kv.first += 'x';kv.second += 'x';cout << kv.first << ":" << kv.second << endl;}cout << endl;string arr[] = { "苹果", "苹果","苹果", "苹果", "香蕉", "香蕉", "香蕉", "西瓜", "西瓜", "桂林米粉", "桂林米粉", "桂林米粉", "北京烤鸭" };unordered_map<string, int> count_map;for (auto& e : arr){count_map[e]++;}for (auto& kv : count_map){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}

unordered_set.h#pragma once
#include"HashTable.h"
namespace SF
{template<class K,class Hash = HashFunc<K>>class unordered_set{struct KeyOfSet{const K& operator()(const K& key){return key;}};public:typedef typename hash_bucket::HashTable<K,K, Hash, KeyOfSet>::iterator iterator;typedef typename hash_bucket::HashTable<K,K, Hash, KeyOfSet>::const_iterator const_iterator;iterator begin() {return iterator(_ht.begin());}iterator end() {return iterator(_ht.end());}const_iterator begin()const{return const_iterator(_ht.begin());}const_iterator end() const{return const_iterator(_ht.end());}pair<const_iterator, bool> insert(const K& key){auto ret = _ht.Insert(key);return pair<const_iterator, bool>(const_iterator(ret.first._pht,ret.first._node, ret.first._hashi),ret.second);}bool find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K,K, HashFunc<K>, KeyOfSet> _ht;};void test_set(){unordered_set<int> us;us.insert(5);us.insert(15);us.insert(52);us.insert(3);unordered_set<int>::iterator it = us.begin();while (it != us.end()){//*it += 5;cout << *it << " ";++it;}cout << endl;for (auto e : us){cout << e << " ";}cout << endl;}
}

HashTable.h#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;template<class K>
struct HashFunc
{size_t operator()(const K& key){return key;}
};template<>
struct HashFunc<string>//显示实例化
{size_t operator()(const string& kv){size_t hashi = 0;for (auto e : kv){hashi *= 31;hashi += e;}return hashi;}
};namespace hash_bucket
{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 Ptr,class Ref,class KeyOfT,class Hash>struct _HTIterator{typedef HashNode<T> Node;public://迭代器里面需要指向该位置的节点，然后还需要这张表，不然无法判断下一个位置，// 然后还需要该节点处于哪一个位置typedef _HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;typedef _HTIterator<K, T, T*, T&, KeyOfT, Hash> iterator;size_t _hashi;//该节点在哪一个桶Node* _node;const HashTable<K, T, Hash, KeyOfT>* _pht;_HTIterator(HashTable<K, T, Hash, KeyOfT>* pht,Node* node,size_t hashi):_pht(pht),_node(node),_hashi(hashi){}_HTIterator(const HashTable<K, T, Hash, KeyOfT>* pht, Node* node, size_t hashi):_pht(pht)//避免权限放大的影响, _node(node), _hashi(hashi){}_HTIterator(const iterator& iter) :_pht(iter._pht), _node(iter._node), _hashi(iter._hashi){}bool operator!=(const Self& s){return _node != s._node;}Ptr operator->(){return &_node->_data;}Ref operator*(){return _node->_data;}Self& operator++(){if (_node->_next){// 当前桶还有节点，走到下一个节点_node = _node->_next;}else{// 当前桶已经走完了，找下一个桶开始//KeyOfT kot;//Hash hf;//size_t hashi = hf(kot(_node->_data)) % _pht._tables.size();++_hashi;while (_hashi < _pht->_tables.size()){if (_pht->_tables[_hashi]){_node = _pht->_tables[_hashi];break;}++_hashi;}if (_hashi == _pht->_tables.size()){_node = nullptr;}}return *this;}};template<class K,class T,class Hash,class KeyOfT>class HashTable{public:typedef HashNode<T> Node;template<class K,class T,class Ptr,class Ref,class KeyOfT,class Hash>friend struct _HTIterator;typedef _HTIterator<K, T, T*, T&, KeyOfT, Hash> iterator;typedef _HTIterator<K, T,const T*, const T&, KeyOfT, Hash> const_iterator;public:iterator begin(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i])return iterator(this, _tables[i], i);}return end();}iterator end(){return iterator(this, nullptr, -1);}const_iterator begin() const{for (size_t i = 0; i < _tables.size(); i++){if (_tables[i])return const_iterator(this, _tables[i], i);}return end();}const_iterator end()const{return const_iterator(this, nullptr, -1);}HashTable(){_tables.resize(10, nullptr);}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}iterator Find(const K& key){Hash hf;KeyOfT kot;size_t hashi = hf(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(this, cur, hashi);}cur = cur->_next;}return end();}bool Erase(const K& key){Hash hf;KeyOfT kot;size_t hashi = hf(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}pair<iterator,bool> Insert(const T& data){Hash hf;KeyOfT kot;iterator it = Find(kot(data));if (it != end())return make_pair(it,false);if (_n == _tables.size()){HashTable<K, T, Hash,KeyOfT> newtable;newtable._tables.resize(2 * _tables.size(), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){size_t hashi = hf(kot(cur->_data)) % newtable._tables.size();newtable._tables[hashi] = cur;cur = cur->_next;}_tables[i] = nullptr;}_tables.swap(newtable._tables);//转移资源}_n++;size_t hashi = hf(kot(data)) % _tables.size();Node* newnode = new Node(data);//头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;return make_pair(iterator(this,newnode,hashi), true);}void Some(){size_t bucketSize = 0;size_t maxBucketLen = 0;size_t sum = 0;double averageBucketLen = 0;for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){++bucketSize;}size_t bucketLen = 0;while (cur){++bucketLen;cur = cur->_next;}sum += bucketLen;if (bucketLen > maxBucketLen){maxBucketLen = bucketLen;}}averageBucketLen = (double)sum / (double)bucketSize;printf("all bucketSize:%d\n", _tables.size());printf("bucketSize:%d\n", bucketSize);printf("maxBucketLen:%d\n", maxBucketLen);printf("averageBucketLen:%lf\n\n", averageBucketLen);}private:size_t _n = 0;vector<Node*> _tables;};
}

测试代码

#include"unorderset.h"
#include"unordermap.h"
int main()
{SF::test_map();SF::test_set();return 0;
}