哈希表（模拟实现）

针对key是整型

闭散列 

enum State
{EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;//方便HashTable扩容的时候状态时EMPTY
};template<class K, class V>
class HashTable
{
public:bool Insert(const pair<K, V>& kv){if (Find(kv.first))//找到了有存在相同的key就不用插入了return false;// 负载因子超过0.7就扩容，载荷因子就是填入表中的元素的个数比上列表的长度。负载因子越大发生冲突的可能性就越大，而冲突会带来效率的下降。//if ((double)_n / (double)_tables.size() >= 0.7)//整型除以整形是不会得到小数的if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)//要考虑表为空也就是size为零的情况{//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;//首先要考虑表为空的情况，其次扩容扩的是size而不是capacity，如果扩capacity扩大的空间依旧无法访问，因为vector只能进行连续存储。最重要的是，之前的值存放的位置是按照%old_capacity存放的，而现在capacity变成了old_capacity的两倍，如果按照现在的capacity进行寻找的话，以前的值是找不到的。 //vector<HashData> newtables(newsize);遍历旧表，重新映射到新表//for (auto& data : _tables)//{//	if (data._state == EXIST)//	{//		// data存在就需要重新算在新表的位置//		size_t i = 1;//		size_t index = hashi;//		while (newtables[index]._state == EXIST)//		{//			index = hashi + i;//			index %= newtables.size();//			++i;//		}//		newtables[index]._kv = data._kv;//		newtables[index]._state = EXIST;//	}//}//_tables.swap(newtables);//底层也就是交换一下指针的顺序size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newht;newht._tables.resize(newsize);// 遍历旧表，重新映射到新表for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);//newht因为已经更新了size，所以负载因子一定不会超过，也就不会再扩容了，所以这里的insert只是重新复用一次线性探测的代码。}}_tables.swap(newht._tables);}size_t hashi = kv.first % _tables.size();//之所以不是%capacity的原因是因为vector只能连续存放// 线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state == EXIST)//遇到空或者删除才进行填充{index = hashi + i;index %= _tables.size();++i;}_tables[index]._kv = kv;_tables[index]._state = EXIST;_n++;return true;}HashData<K, V>* Find(const K& key){if (_tables.size() == 0)//要考虑表为空的情况，否则会发生下面的除0错误。{return nullptr;}size_t hashi = key % _tables.size();// 线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY)//只要状态不是空就继续找。但是可能存在一种情况，表里面除了存在就是删除，比如说插入数据后，再扩容前，再插入一部分数据，并且数据正好占据的是其它的非空位置，导致表里面除了存在就是删除，这时候就会陷入死循环。{if (_tables[index]._state == EXIST&& _tables[index]._kv.first == key)//表中的每个元素都是HashData类,其中由两个成员变量一个State、一个是pair，找的时候的前提是状态为EXIST，别的状态哪怕key值符合条件也不行。{return &_tables[index];}index = hashi + i;index %= _tables.size();++i;// 如果已经查找一圈，那么说明表里面只有存在和删除的状态if (index == hashi){break;}}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret)//找到了{ret->_state = DELETE;--_n;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n = 0; // 存储的数据个数//HashData* tables;//size_t _size;//size_t _capacity;
};void TestHashTable1()
{int a[] = { 3, 33, 2, 13, 5, 12, 1002 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(15, 15));if (ht.Find(13)){cout << "13在" << endl;}else{cout << "13不在" << endl;}ht.Erase(13);if (ht.Find(13)){cout << "13在" << endl;}else{cout << "13不在" << endl;}
}

开散列 

namespace HashBucket
{template<class K, class V>struct HashNode{HashNode<K, V>* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_next(nullptr), _kv(kv){}};template<class K, class V>class HashTable{typedef HashNode<K, V> Node;public:~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}Node* Find(const K& key){if (_tables.size() == 0)return nullptr;size_t hashi = key % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){size_t hashi = 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;return true;}else{prev = cur;cur = cur->_next;}}return false;}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}//负载因子越大，冲突概率越高，查找效率越低，空间利用率越高。// 负载因因子==1时扩容，此时table有的下标挂了数据,有的下标没有挂数据。if (_n == _tables.size()){/*size_t newsize = _tables.size() == 0 ? 10 : _tables.size()*2;HashTable<K, V> newht;newht.resize(newsize);for (auto cur : _tables){while (cur){newht.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newht._tables);*///下面方法的好处是相比上面不需要对旧值进行重新申请与释放。也就是原表的节点重新计算位置然后挪动到新表。size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = cur->_kv.first % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = kv.first % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 存储有效数据个数};void TestHashTable1(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(15, 15));ht.Insert(make_pair(25, 25));ht.Insert(make_pair(35, 35));ht.Insert(make_pair(45, 45));}void TestHashTable2(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Erase(12);ht.Erase(3);ht.Erase(33);}

 key可以是任意类型

namespace HashBucket
{template<class K, class V>struct HashNode{HashNode<K, V>* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_next(nullptr), _kv(kv){}};template<class K>struct HashFunc//仿函数，将key转换成为可以取模的整型值{size_t operator()(const K& key){return key;}};// 因为string经常被作为key，所以可以针对stirng做为key进行一个HashFunc特化template<>struct HashFunc<string>{// BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};template<class K, class V, class Hash = HashFunc<K>>//如果K是string类，HashFunc就会走上面的特化。class HashTable{typedef HashNode<K, V> Node;public:~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}Node* Find(const K& key){if (_tables.size() == 0)return nullptr;Hash hash;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 Erase(const K& key){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;return true;}else{prev = cur;cur = cur->_next;}}return false;}// size_t newsize = GetNextPrime(_tables.size());size_t GetNextPrime(size_t prime)//每次扩容的大小是一个素数值{// SGIstatic 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};size_t i = 0;for (; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){/*size_t newsize = _tables.size() == 0 ? 10 : _tables.size()*2;HashTable<K, V> newht;newht.resize(newsize);for (auto cur : _tables){while (cur){newht.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newht._tables);*///size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());//每次扩容的大小是一个素数值vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(cur->_kv.first) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kv.first) % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}size_t MaxBucketSize() //由于负载因子的控制，大多数的桶的长度都是0、1、2,不会太长。极端情况下如果某个桶的长度缺失很长，我们可以采用1、负载因子控制；2、单个桶超过一定长度，将这个桶改成红黑树。{size_t max = 0;for (size_t i = 0; i < _tables.size(); ++i){auto cur = _tables[i];size_t size = 0;while (cur){++size;cur = cur->_next;}//printf("[%d]->%d\n", i, size);if (size > max){max = size;}}return max;}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 存储有效数据个数};void TestHashTable1(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(15, 15));ht.Insert(make_pair(25, 25));ht.Insert(make_pair(35, 35));ht.Insert(make_pair(45, 45));}void TestHashTable2(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Erase(12);ht.Erase(3);ht.Erase(33);}struct HashStr//仿函数，将字符串转换成为整型{// BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;     hash *= 31;//防止字符串abc、acb、cba转整型的值相同}return hash;}};void TestHashTable3(){//HashTable<string, string, HashStr> ht;HashTable<string, string> ht;ht.Insert(make_pair("sort", "排序"));ht.Insert(make_pair("string", "字符串"));ht.Insert(make_pair("left", "左边"));ht.Insert(make_pair("right", "右边"));ht.Insert(make_pair("", "右边"));HashStr hashstr;cout << hashstr("abcd") << endl;cout << hashstr("bcda") << endl;cout << hashstr("aadd") << endl;cout << hashstr("eat") << endl;cout << hashstr("ate") << endl;}void TestHashTable4(){size_t N = 900000;HashTable<int, int> ht;srand(time(0));for (size_t i = 0; i < N; ++i){size_t x = rand()+i;ht.Insert(make_pair(x, x));}cout << ht.MaxBucketSize() << endl;}
}

unordered_map和unordered_set封装

HashTable

namespace HashBucket
{template<class T>struct HashNode{HashNode<T>* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}};// 前置声明template<class K, class T, class KeyOfT, class Hash>//KeyOfT就是取data里面的key，而Hash就是用来将key转换成为可以取模的整型class HashTable;//因为hash迭代器需要用到hash表，所以这里加上一个前置声明template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>struct __HashIterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;Node* _node;//迭代器封装了节点const HT* _ht;//迭代器还封装了哈希表__HashIterator(Node* node, const HT* ht):_node(node), _ht(ht){}__HashIterator(const Iterator& it):_node(it._node), _ht(it._ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){if (_node->_next != nullptr){_node = _node->_next;}else{// 找下一个不为空的桶KeyOfT kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();// 算出我当前的桶位置++hashi;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{++hashi;}}// 没有找到不为空的桶，返回end()if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};template<class K, class T, class KeyOfT, class Hash>class HashTable{template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct __HashIterator;//这样迭代器可以访问hash表中的_tables.size()，因为_tables是私有的。而且由于友元是模板的，所以还要加上模板参数，typedef HashNode<T> Node;public:typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> iterator;typedef __HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;iterator begin(){Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return iterator(cur, this);//迭代器除了传递指针还需要传一个hash表}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return const_iterator(cur, this);}const_iterator end() const{return const_iterator(nullptr, this);}~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}iterator Find(const K& key){if (_tables.size() == 0)return end();KeyOfT kot;Hash hash;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();}bool Erase(const K& key){Hash hash;KeyOfT kot;size_t hashi = hash(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;}else{prev = cur;cur = cur->_next;}}return false;}// size_t newsize = GetNextPrime(_tables.size());size_t GetNextPrime(size_t prime){// SGIstatic 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};size_t i = 0;for (; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];}pair<iterator, bool> Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it != end()){return make_pair(it, false);}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){/*size_t newsize = _tables.size() == 0 ? 10 : _tables.size()*2;HashTable<K, V> newht;newht.resize(newsize);for (auto cur : _tables){while (cur){newht.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newht._tables);*///size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){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.swap(newtables);}size_t hashi = hash(kot(data)) % _tables.size();// 头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), false);;}size_t MaxBucketSize(){size_t max = 0;for (size_t i = 0; i < _tables.size(); ++i){auto cur = _tables[i];size_t size = 0;while (cur){++size;cur = cur->_next;}//printf("[%d]->%d\n", i, size);if (size > max){max = size;}}return max;}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 存储有效数据个数};
}

set

namespace wjj
{template<class K, class Hash = HashFunc<K>>class unordered_set{public:struct SetKeyOfT//传的就是k{const K& operator()(const K& key){return key;}};public:typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;//取类模板里面的内嵌类型一定要加typename，否则无法分清楚是类里面的静态成员对象还是类型。typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::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();}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:HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht;};void print(const unordered_set<int>& s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;}void test_unordered_set1(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };unordered_set<int> s;for (auto e : a){s.insert(e);}s.insert(54);s.insert(107);unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;print(s);}
}

map

template<class K, class V, class Hash = HashFunc<K>>class unordered_map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::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();}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_unordered_map1(){unordered_map<int, int> m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));unordered_map<int, int>::iterator it = m.begin();while (it != m.end()){//it->first = 1;//it->second = 1;cout << it->first << ":" << it->second << endl;++it;}cout << endl;}void test_unordered_map2(){string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}class Date{friend struct HashDate;public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}bool operator==(const Date& d) const{return _year == d._year&& _month == d._month && _day == d._day;}friend ostream& operator<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}struct HashDate{size_t operator()(const Date& d){size_t hash = 0;hash += d._year;hash *= 31;hash += d._month;hash *= 31;hash += d._day;hash *= 31;return hash;}};// 一个类型要做unordered_map/unordered_set的key，要满足支持转换成取模的整形 和 ==比较// 一个类型要做map/set的key，要满足支持<比较/*if (cur->key < key){}else if (key < cur->key){}else{}*/void test_unordered_map4(){Date d1(2023, 3, 13);Date d2(2023, 3, 13);Date d3(2023, 3, 12);Date d4(2023, 3, 11);Date d5(2023, 3, 12);Date d6(2023, 3, 13);Date a[] = { d1, d2, d3, d4, d5, d6};unordered_map<Date, int, HashDate> countMap;for (auto e : a){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}