在源码中，这两个STL容器都是共用一个框架的所以，我们就用一个框架实现两个
容器，代码细节都在注释上
HashTable.h
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <vector> #include <string> #include <utility> #include <algorithm> #include <utility> //namespace txh //{ // enum state // { // EMPTY,//空 // EXITS,//存在 // DELETE,//被删除 // }; // template<class K,class V>//元素类 // class HashData//先画一个存放数据的蓝图，声明和定义 // { // public: // std::pair<K,V> _kv;//哈希表，我们要根据key(也是模板的K)值去模一个值，得到哈希值存到哈希表的位置 // //V是数据类型 // // //我们在查找的时候不知道用什么表示为空，没有一个合适的数，0吗，-1，不对，因为这些都有可能是某个数0，-1 // //所以不能用，我们用另一种方法，那就是在每个数据上存一个标志代表是否为空 // // //前面定义了enum类型，类名是state， // state _state = EMPTY;//默认都是空 // }; // // // // //线性探测法 // template<class K,class V,class keyConv> // class HashTable // { // public: // typedef HashData<K, V> data; // keyConv kc; // HashTable() // :_n(0) // { // _table.resize(11); // } // // //那如果key值不是int而是string 类型呢,我们不可能去特意在模板里判断一个数是否是string类型 // //那么我们可以传一个模板,因为我们hash主要的是要把key值转换成hash值 // //我们用一个模板类去封装转换成hash值的方式 // bool insert(const std::pair<K,V>& kv)//插入元素,我们用pair类接受 // { // //如果表内有相同的值的话，就不插入了 // if (find(kv.first)) // { // return false; // } // // if (_n * 10 / _table.size() > 7)//负载因子大于0.7我们的冲突就会变大，导致效率下降 // //在线性探测中，所以我们就需要扩容，扩多少倍呢，扩质数倍其实是很好的，java中只是扩2倍，没有按质数扩 // //按质数扩会降低哈希冲突率 // { // HashTable<K, V,keyConv> newtable; // newtable._table.resize(2 * _table.size()); // // for (auto& e:_table)//为什么要重新插入，是因为我们扩容之后，下标映射变了，所以要重新插入 // { // if(e._state == EXITS) // { // /* int hashi = e._kv.first % newtable._table.size(); // newtable._table[hashi]._kv = e._kv; // newtable._table[hashi]._state = e._state;*/ // newtable.insert(e._kv);//复用写法 // } // } // _table.swap(newtable._table);//2023年的现代写法,新表代替了旧表 // } // // // //线性探测 // size_t hashi = kc(kv.first) % _table.size(); //成员里不用capacity的原因是我们的vector的下标引用只能引用size内的值，capacity // //肯定大于等于size,所以肯定不能去模除capacity // size_t i = 0; // while (_table[hashi]._state != EMPTY)//查看当前表的每个元素类是否有空,没空一直继续 // { // //如果当前的hashi被占了，直接去下一个厕所看(就是相邻的下一个)，所以有了i // //i控制每一轮要看的厕所不是上一次看过的，所以i++ // ++hashi; // hashi %= _table.size();//防止越界 // } // _table[hashi]._kv = kv; // _table[hashi]._state = EXITS; // ++_n; // return true; // } // // data* find(const K& key) // { // size_t hashi = kc(key) % _table.size(); // size_t i = 0; // while (_table[hashi]._state != EMPTY)//这是线性探测 // { // if (_table[hashi]._kv.first == key // && _table[hashi]._state == EXITS) // { // return &_table[hashi]; // } // hashi++; // hashi %= _table.size();//防止越界 // } // // return nullptr; // } // // bool erase(const K& key) // { // data* ret = find(key); // if (!ret) // { // return false; // } // else // { // ret->_state = DELETE; // _n--; // return true; // } // } // private: // std::vector<data> _table;//当前存放元素的表, // size_t _n;//代表当前表内有多少个元素 // //负载因子是什么呢，就是总共插入的元素 除以 总元素 就是负载因子 // }; //} // template <typename T> struct HashFunc { size_t operator()(const T& key)//键值接受 { size_t hashi = key; return hashi; } };//声明键值转换函数是模板类,因为模板类只是个图纸 template <>//特化之前一定要有一个基础类 struct HashFunc<std::string> { size_t operator()(const std::string& key) { size_t hashi = 0; for (auto e : key)//关键值转hash { hashi *= 131; hashi += e; } return hashi; } }; namespace HashBucket { //开散列，拉链法 template<class T>//改造后只有一个参数，我们自动去识别是一个参数还是两个参数 struct HashNode { HashNode(const T& data) :_data(data), next(nullptr) {} T _data; HashNode* next; }; template<class K, class T, class keyCon, class KeyofT> class HashTable;//在hashIterator类前面声明,编译器就会跟着这个声明去找到相应的模板 //容器都有迭代器,所以我们要封装一个迭代器，因为我们的迭代器会有重载*，->这种，所以我们直接传ptr这种吧 template<class K,class T,class Ref,class Ptr,class keyCon,class KeyofT> class _HashIterator { public: typedef HashNode<T> node; typedef _HashIterator<K, T, T&, T*, keyCon, KeyofT> iterator; typedef HashTable<K, T, keyCon, KeyofT> HT; _HashIterator(node* node1,HT* ht) :_node(node1),_ht(ht){} _HashIterator(const iterator& it):_node(it._node),_ht(it._ht){} typedef _HashIterator<K,T,Ref,Ptr,keyCon,KeyofT> self; self& operator++() { //先看当前桶里是否有元素，如果后续有元素，那就在桶里++，如果桶里没有，那么就去其他桶 //里找 node* cur = _node->next; if (cur) { _node = _node->next; //返回迭代器本身 } else { //去遍历这个桶，找到后续第一个有元素的桶 keyCon kc; //找到当前迭代器里的节点的桶的位置 size_t hashi = kc(_node->_data) % _ht->_table.size(); //遍历这个桶 ++hashi; while (hashi < _ht->_table.size()) { if (_ht->_table[hashi]) { _node = _ht->_table[hashi]; break; } hashi++; } if (hashi == _ht->_table.size()) { _node = nullptr; } } return *this; } self operator++(int) { //后置++ self ret = self(_node,_ht); node* cur = _node; if (cur) { _node = _node->next; //返回迭代器本身 } else { //去遍历这个桶，找到后续第一个有元素的桶 keyCon kc; //找到当前迭代器里的节点的桶的位置 size_t hashi = kc(_node->_data) % _ht->_table.size(); //遍历这个桶 ++hashi; while (hashi < _ht->_table.size()) { if (_ht->_table[hashi]) { _node = _ht->_table[hashi]; break; } hashi++; } if (hashi == _ht->_table.size()) { _node = nullptr; } } return ret;//返回迭代器对象的时候，会进行拷贝构造，所以不用担心生命周期 } bool operator!=(const self& s) { return s._node != _node; } Ref operator*() { return _node->_data; } Ptr& operator->() { return &_node->_data; } public: node* _node;//有了迭代器，我们就可以直接用迭代器,迭代器++，就是这里的_node = _node->next等 //我们的++，--操作还会设计到遍历桶，我们的遍历桶只在HashTable里面设计了,所以我们需要有一个 //可以操作HashTable的动作，因为都是算类，我们可以设计一个指针进行操作,我们用友元 HT* _ht; }; //第二个才是数，第一个只是我们的键值 template<class K, class T, class keyCon,class KeyofT> class HashTable { public: //友元声明 template<class K,class T,class Ref,class Ptr,class KeyCon, class KeyofT>//声明这个_hashIterator是个模板类，告诉编译器我要这个_HashIterator模板类 //是HashTable类的友元 friend class _HashIterator; typedef _HashIterator<K,T,T&,T*,keyCon,KeyofT> iterator; typedef _HashIterator<K, T,const T&,const T*,keyCon,KeyofT> const_iterator; //我们通过传的模板参数来控制我们的迭代器是否是const迭代器 typedef HashNode<T> node; keyCon hash; KeyofT koft; size_t _stl_next_prime(size_t size) { static const int __stl_num_primes = 28; static const unsigned long __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 (int i = 0;i < __stl_num_primes;i++) { if (__stl_prime_list[i] > size) { return __stl_prime_list[i]; } } } HashTable() :_n(0) { _table.resize(_stl_next_prime(_table.size())); } ~HashTable() { for (auto e : _table) { node* cur = e; while (cur)//把在桶里的元素删除 { node* next = cur->next; delete cur; cur = next; } e = nullptr; } } iterator begin() { node* cur = nullptr; //找到第一个有元素的桶 for (size_t hashi = 0;hashi < _table.size();hashi++) { cur = _table[hashi]; if (cur) { break; } } return iterator(cur,this);//传值返回,生命周期就不用管，他会执行一次拷贝构造 //匿名构造函数 } iterator end() { return iterator(nullptr, this);//传值返回,生命周期就不用管，他会执行一次拷贝构造 } const_iterator begin() const { node* cur = nullptr; for (size_t i = 0; i < _table.size(); ++i) { cur = _table[i]; if (cur) { break; } } return const_iterator(cur, this); } const_iterator end() const{return const_iterator(nullptr, this);} std::pair<iterator,bool> insert(const T& data) { iterator ret = find(koft(data)); if (ret != end())//有该点的话 { return std::make_pair(ret, true); } //拉链法中，当负载因子等于1的时候，哈希的冲突就会变大，桶里的元素可能最多，所以负载因子为1就扩容最好 if (_n == _table.size())//负载因子等于1 { /*HashTable<K, V, keyCon> newHash;*/ /*newHash._table.resize(_table.size() * 2);*/ //这种做法很费效率，因为每次插入要重新new一个节点，并释放，所以同样映射的节点就不需要重新new了 std::vector<node*> newtable; /*newtable.resize(_table.size() * 2,nullptr);*/ //扩容 newtable.resize(_stl_next_prime(_table.size())); //重新映射 for (auto& e : _table) { node* cur = e; //头插 while (cur) { node* next = cur->next; //哈希重新映射 size_t hashi = hash(koft(cur->_data)) % newtable.size(); cur->next = newtable[hashi];//将未插入之前的头插到cur的next newtable[hashi] = cur; cur = next; } e = nullptr; } //现代写法 _table.swap(newtable);//旧表换新表,只是表新表的内容搬到旧表中 //新表不用手动释放,生命周期只在当前作用域中，如果出了作用域会自动销毁(调用析构函数) } //这里的kc是实例化后的对象，所以可以kc(kv.first)，但是不能用hash(kv.first)，因为hash不是一个实例化的对象，需要把他实例化 //之后才能调用 size_t hashi = hash(koft(data)) % _table.size(); //头插 node* newnode = new node(data); newnode->next = _table[hashi]; _table[hashi] = newnode; ++_n; return std::make_pair(iterator(newnode,this),true); } iterator find(const K& key) { size_t hashi = hash(key) % _table.size();//根据关键值算出哈希值 node* cur = _table[hashi]; //在桶里寻找 while (cur) { if (koft(cur->_data) == key) { return iterator(cur,this); } cur = cur->next; } return iterator(nullptr,this); } bool erase(const K& key) { size_t hashi = hash(key) % _table.size(); node* cur = _table[hashi];//找到了桶 node* prev = nullptr; while (cur) { if (cur->_kv.first == key) { //如果是头节点的话 if (cur->_kv == _table[hashi]) { _table[hashi] = cur->next; } else//找到的这个key值不是头结点的话 { prev->next = cur->next; } delete cur; --_n; return true; } else//继续找 { prev = cur; cur = cur->next; } } return false; } private: std::vector<node*> _table;//每个位置存放hashnode类，里面有指针,存放的是头结点 size_t _n; }; } //先改造哈希表 //int main() //{ // // /*txh::HashTable<int,int,> h1;*/ // // //h1.insert(std::make_pair(4,1)); // //h1.insert(std::make_pair(4,1)); // //h1.insert(std::make_pair(4,1)); // //h1.insert(std::make_pair(3,1)); // // //h1.insert(std::make_pair(7,1)); // // /*txh::HashTable<std::string, int,HashFunc<std::string>> h1; // h1.insert(std::make_pair("苹果", 1)); // h1.insert(std::make_pair("香蕉", 1)); // h1.insert(std::make_pair("梨", 1)); // h1.insert(std::make_pair("苹果", 1)); // txh::HashData<std::string, int>* ret = h1.find("苹果"); // ret->_kv.second++; // h1.erase("苹果");*/ // // HashBucket::HashTable<int, int, HashFunc<int>> h1; // // h1.insert(std::make_pair(3, 1)); // h1.insert(std::make_pair(4, 1)); // h1.insert(std::make_pair(3, 1)); // h1.insert(std::make_pair(3, 1)); // h1.insert(std::make_pair(12, 1)); // h1.insert(std::make_pair(12, 1)); // return 0; //} template<class T> struct compare { bool operator()(const T& t1,const T& t2) { return t1 > t2; } };
unordered_map.h
#pragma once #include "HashTable.h" #include "unordered_map.h" #include "unordered_set.h" #include <iostream> namespace txh { template<class K,class T,class keyCon = HashFunc<K>> class unordered_map { public: struct mapkeyoft { const K& operator()(const std::pair<K,T>& kv) { return kv.first; } }; typedef typename HashBucket::HashTable<K, std::pair<K, T>, keyCon, mapkeyoft>::iterator iterator; typedef typename HashBucket::HashTable<K, std::pair<K, T>, keyCon, mapkeyoft>::const_iterator const_iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } const_iterator begin()const { return _ht.begin(); } const_iterator end()const { return _ht.end(); } std::pair<iterator, bool> insert(const std::pair<K, T>& data) { return _ht.insert(data); } T& operator[](const K& key) { std::pair<iterator, bool> ret = insert(std::make_pair(key , T)); return ret.first->second; //加->就是得到了data,然后second } iterator find(const K& key) { return _ht.find(key); } bool erase(const K& key) { _ht.erase(key); } private: HashBucket::HashTable<K, std::pair<K, T>, keyCon, mapkeyoft> _ht; }; }
unordered_set.h
#pragma once #include "HashTable.h" #include <iostream> #include <utility> namespace txh { template<class K,class keyCon = HashFunc<K>> class unordered_set { struct keyofset { const K& operator()(const K& data) { return data; } }; public: typedef typename HashBucket::HashTable<K, K, keyCon, keyofset>::const_iterator iterator; typedef typename HashBucket::HashTable<K, K, keyCon, keyofset>::const_iterator const_iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } const_iterator begin()const { return _ht.begin(); } const_iterator end()const { return _ht.end(); } std::pair<iterator, bool> insert(const K& data) { return _ht.insert(data); } iterator find(const K& data) { return _ht.find(data); } bool erase(const K& data) { return _ht.erase(data); } private: HashBucket::HashTable<K, K, keyCon, keyofset> _ht; }; }
test.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include "unordered_map.h" #include "unordered_set.h" #include "HashTable.h" #include <iostream> #include <algorithm> #include <utility> int main() { txh::unordered_set<int, HashFunc<int>> s1; s1.insert(1); return 0; }
