目录
一.unordered_set和unordered_set
二.哈希表的改造
三.整体代码
1.MyUnorderedMap.h
2.MyUnorderedSet.h
3.HashTable.h
4.Hash.cpp
一.unordered_set和unordered_set
unordered_set和unordered_map的实现通过调用哈希表即可
#pragma once#include"HashTable.h"using namespace open_hash;namespace wzyl{template<class K,class V,class Hash=open_hash::_Hash<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>, MapKeyOfT, Hash>::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>, MapKeyOfT, Hash> _ht;};void test_unordered_map(){unordered_map<string,string> m;m.insert(make_pair("string", "字符串"));m.insert(make_pair("vector", "数组"));m.insert(make_pair("left", "左边"));m.insert(make_pair("right", "右边"));m["end"] = "尾";m["left"] = "left";unordered_map<string,string>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;}}#pragma once#include"HashTable.h"using namespace open_hash;namespace wzyl{template<class K,class Hash=open_hash::_Hash<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename HashTable<K, K, SetKeyOfT, Hash>::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, SetKeyOfT,Hash> _ht;};void test_unordered_set(){unordered_set<int> s;s.insert(1);s.insert(5);s.insert(4);s.insert(3);unordered_set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}}二.哈希表的改造
因为unordered_set和unordered_map要支持迭代器遍历,所以为哈希表中添加迭代器
template<class K,class T,class KeyOfT,class Hash>struct __HashTableIterator{typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;Node* _node;HT* _pht;__HashTableIterator(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{KeyOfT koft;size_t i = _pht->HashFunc(koft(_node->_data)) % _pht->_tables.size();++i;for (; i < _pht->_tables.size(); i++){Node* cur = _pht->_tables[i];if (cur){_node = cur;return *this;}}_node = nullptr;}return *this;}bool operator!=(const Self& s){return _node != s._node;}};三.整体代码
1.MyUnorderedMap.h
#pragma once#include"HashTable.h"using namespace open_hash;namespace wzyl{template<class K,class V,class Hash=open_hash::_Hash<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>, MapKeyOfT, Hash>::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>, MapKeyOfT, Hash> _ht;};void test_unordered_map(){unordered_map<string,string> m;m.insert(make_pair("string", "字符串"));m.insert(make_pair("vector", "数组"));m.insert(make_pair("left", "左边"));m.insert(make_pair("right", "右边"));m["end"] = "尾";m["left"] = "left";unordered_map<string,string>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;}}2.MyUnorderedSet.h
#pragma once#include"HashTable.h"using namespace open_hash;namespace wzyl{template<class K,class Hash=open_hash::_Hash<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename HashTable<K, K, SetKeyOfT, Hash>::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, SetKeyOfT,Hash> _ht;};void test_unordered_set(){unordered_set<int> s;s.insert(1);s.insert(5);s.insert(4);s.insert(3);unordered_set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}}3.HashTable.h
#pragma once#include<vector>#include<string>template<class K>struct SetKeyOfT{const K& operator()(const K& key){return key;}};template<class K, class V>struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};namespace close_hash{enum State{EMPTY,EXITS,DELETE,};template<class T>struct HashData{T _data;State _state;};//unordered_set --> HashTable<K, K>//unordered_map --> HashTable<K, pair<K, V>>template<class K, class T, class KeyOfT>class HashTable{typedef HashData<T> HashData;public:bool Insert(const T& d){//负载因子 = 表中数据/表的大小 -->衡量哈希表满的程度//表越接近满,插入数据越容易冲突,冲突越多,效率越低//哈希表并不是满了增容,在开放定址法中,一般负载因子到0.7左右就开始增容//负载因子越小,冲突概率越低,整体效率越高,但是浪费空间越大//所以负载因子一般取一个折中值KeyOfT koft;if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7){//开2倍的新表//遍历旧表的数据,将旧表的数据在新表中重新映射//释放旧表/*vector<HashData> newtables;size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;newtables.resize(newsize);for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXITS){size_t index = koft(_tables[i]._data) % newtables.size();while (newtables[index]._state == EXITS){++index;if (index == _tables.size()){index = 0;}}newtables[index] = _tables[i];}}_tables.swap(newtables);*/HashTable<K, T, KeyOfT> newht;size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;newht._tables.resize(newsize);for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXITS){newht.Insert(_tables[i]._data);}}_tables.swap(newht._tables);}//线性探测//计算d中的key在表中映射的位置/*size_t index = koft(d) % _tables.size();while (_tables[index]._state == EXITS){if (koft(_tables[index]._data) == koft(d)){return false;}++index;if (index == _tables.size()){index = 0;}}_tables[index]._data = d;_tables[index]._state = EXITS;_num++;*///二次探测size_t start = koft(d) % _tables.size();size_t index = start;int i = 1;while (_tables[index]._state == EXITS){if (koft(_tables[index]._data) == koft(d)){return false;}index = start + i * i;++i;index %= _tables.size();}_tables[index]._data = d;_tables[index]._state = EXITS;_num++;return true;}HashData* Find(const K& key){KeyOfT koft;//计算key在表中映射的位置size_t index = koft(key) % _tables.size();while (_tables[index]._state != EMPTY){if (koft(_tables[index]._data) == key){if (_tables[index]._state == EXITS){return &_tables[index];}else if (_tables[index]._state == DELETE){return nullptr;}}++index;if (index == _tables.size()){index = 0;}return nullptr;}}bool Erase(const K& key){HashData* ret = Find(key);if (ret){ret->_state = DELETE;--_num;return true;}else{return false;}}private:vector<HashData> _tables;size_t _num = 0;//存了几个有效数据};}namespace open_hash{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data) :_data(data), _next(nullptr) { }};template<class K, class T, class KeyOfT, class Hash>class HashTable;template<class K,class T,class KeyOfT,class Hash>struct __HashTableIterator{typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;Node* _node;HT* _pht;__HashTableIterator(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{KeyOfT koft;size_t i = _pht->HashFunc(koft(_node->_data)) % _pht->_tables.size();++i;for (; i < _pht->_tables.size(); i++){Node* cur = _pht->_tables[i];if (cur){_node = cur;return *this;}}_node = nullptr;}return *this;}bool operator!=(const Self& s){return _node != s._node;}};template<class K>struct _Hash{const K& operator()(const K& key){return key;}};template<>struct _Hash<std::string>{size_t operator()(const std::string& key){//BKDR Hashsize_t hash = 0;for (size_t i = 0; i < key.size(); ++i){hash *= 131;hash += key[i];}return hash;}};template<class K, class T, class KeyOfT, class Hash=_Hash<K>>class HashTable{typedef HashNode<T> Node;public:friend struct __HashTableIterator<K, T, KeyOfT, Hash>;typedef __HashTableIterator<K, T, KeyOfT, Hash> 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(){Clear();}void Clear(){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 HashFunc(const K& key){Hash hash;return hash(key);}pair<iterator, bool> Insert(const T& data){KeyOfT koft;//如果负载因子等于1就增容,避免大量的哈希冲突if (_tables.size() == _num){vector<Node*> newtables;size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;newtables.resize(newsize);for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t index = HashFunc(koft(cur->_data)) % newtables.size();cur->_next = newtables[index];newtables[index] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}size_t index = HashFunc(koft(data)) % _tables.size();//查找值在不在表中Node* cur = _tables[index];while (cur){if (koft(cur->_data) == koft(data)){return make_pair(iterator(cur, this), false);}else{cur = cur->_next;}}//头插(尾插也可以)Node* newnode = new Node(data);newnode->_next = _tables[index];_tables[index] = newnode;++_num;return make_pair(iterator(newnode, this), true);}Node* Find(const K& key){KeyOfT koft;size_t index = HashFunc(key) % _tables.size();Node* cur = _tables[index];while (cur){if (koft(cur->_data) == key){return cur;}else{cur = cur->_next;}}return nullptr;}bool Erase(const K& key){KeyOfT koft;size_t index = HashFunc(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[index];while (cur){if (koft(cur->_data) == key){if (prev == nullptr){_tables[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<Node*> _tables;size_t _num = 0;};}4.Hash.cpp
#include<iostream>using namespace std;#include"HashTable.h"#include"MyUnorderedMap.h"#include"MyUnorderedSet.h"int main(){wzyl::test_unordered_set();wzyl::test_unordered_map();return 0;}