1.哈希桶

hash.h

#pragma once
#include<iostream>
#include<vector>
using namespace std;template<class T>
struct HashNode
{HashNode(const T& data):_data(data),_next(nullptr){}T _data;HashNode<T>* _next;
};
template<class K>
struct HashFunc
{const K& operator()(const K& key){return key;}
};
template<>
struct HashFunc<string>
{size_t operator()(const string& skey){size_t ret = 0;for (size_t i = 0; i < skey.size(); i++){ret *= 131;ret += skey[i];}return ret;}
};
template<class K, class T, class KOFT, class Hash>
class HashTable;
template<class K, class T, class KOFT, class Hash>
struct __iterator
{KOFT koft;Hash hash;typedef HashNode<T> HashNode;typedef __iterator<K, T, KOFT, Hash> Self;typedef HashTable<K, T, KOFT, Hash> HT;HashNode* _node;HT* _Ht;__iterator(HashNode* h ,HT* pht):_node(h),_Ht(pht){}T& operator*(){return _node->_data;}T* operator->(){return &(_node->_data);}Self operator++(){if (_node->_next)//如果_node的后面不为空{_node = _node->_next;return *this;}else //如果node的后面为空{//向通过data中的key算出映射的位置;int index = hash(koft(_node->_data)) % (_Ht->_ht.capacity());index++;for (; index < (_Ht->_ht.size()); ++index){if (_Ht->_ht[index]){_node = _Ht->_ht[index];return *this;}}_node = nullptr;return *this;}}bool operator!=(const Self& it){return (_node != it._node);}
};template<class K,class T,class KOFT,class Hash>
class HashTable
{
public:friend struct __iterator<K, T, KOFT, Hash>;typedef __iterator<K, T, KOFT, Hash> iterator;KOFT koft;Hash hash;typedef HashNode<T> HashNode;HashTable(size_t initcapacity = 10):_size(0), _ht(initcapacity){}~HashTable(){clear();}iterator begin(){for (size_t i = 0; i < _ht.size(); ++i){if (_ht[i]){return iterator(_ht[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}void clear() //delete掉hash桶中所有new的节点{for (size_t i = 0; i < _ht.capacity(); i++){HashNode* cur = _ht[i];while (cur){HashNode* next = cur->_next;delete cur;cur = next;}_ht[i] = nullptr;}}void Checkcapacity(){//当平衡因子=1时扩容;if (_size == _ht.capacity()){HashTable<K, T, KOFT,Hash> newHash(2 * _ht.capacity());for (size_t i = 0; i < _ht.capacity(); i++){HashNode* cur = _ht[i];while (cur){newHash.insert(cur->_data);cur = cur->_next;}}_ht.swap(newHash._ht);}}pair<iterator,bool> insert(const T& data){//1.Check容量控制平衡因子Checkcapacity();//2.获取indexint index = hash(koft(data)) % _ht.capacity();//3.检查index位置处是否有相同的元素HashNode* cur = _ht[index];while (cur){if (koft(data) == koft(cur->_data)){return make_pair(iterator(cur,this),false);}cur = cur->_next;}//4.头插节点HashNode* newnode = new HashNode(data);newnode->_next = _ht[index];_ht[index] = newnode;++_size;return make_pair(iterator(newnode,this),true);}iterator find(const K& key){int index = hash(key) % _ht.capacity();HashNode* cur = _ht[index];while (cur){if (key == koft(cur->_data)){return iterator(cur,this);}cur = cur->_next;}return iterator(nullptr);}bool erase(const K& key){int index =hash(key) % _ht.capacity();HashNode* cur = _ht[index];HashNode* prev = nullptr;while (cur){if (key == koft(cur->_data)){if (prev == nullptr) //cur就是头结点{_ht[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_size;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<HashNode*> _ht;size_t _size;
};

2.unordered_map.h

#pragma once
#include"hash.h"namespace klaus
{template<class K,class V, class Hash = HashFunc<K>> //将hash接口开放，用户可自定义处理非string和int的映射方式class map{public:struct KOFT{const K& operator()(const pair<K,V>& data){return data.first;}};typedef HashTable<K, pair<K, V>, KOFT,Hash> HashTable;struct HashNode;typedef typename HashTable::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);}iterator find(const K& key){return ht.find(key);}bool erase(const K& key){return ht.erase(key);}V& operator[](const K& key){pair<iterator, bool> ret = ht.insert(make_pair(key, V()));return ret.first->second;}private:HashTable ht;};
}

3.unordered_set.h

#pragma once
#include"hash.h"
namespace klaus
{template<class K, class Hash = HashFunc<K>> //将hash接口开放，可以用户自己单独处理非string和int的映射class set{public:struct KOFT{const K& operator()(const K& key){return key;}};typedef typename HashTable<K,K,KOFT,Hash>::iterator iterator;iterator begin(){return ht.begin();}iterator end(){return ht.end();}pair<iterator, bool> insert(const K& key){return ht.insert(key);}iterator find(const K& key){return ht.find(key);}bool erase(const K& key){return ht.erase(key);}private:HashTable<K, K, KOFT, Hash> ht;};
}