devbox
码创造者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++：哈希，unordered_map和unordered_set_unordered map时间复杂度

作者：码创造者 | 2024-08-23 02:38:04

赞

踩

unordered map时间复杂度

目录

一.unordered_map和unordered_set

1.时间复杂度：它们查找的时间复杂度平均都是O(1)

2.它们的底层结构相同，都使用哈希桶

简单的使用代码：

二.哈希

1. 直接定址法--(数分布集中 常用)

2. 除留余数法--(数分布不集中,均匀 常用)

3.哈希冲突

（2）闭散列

线性探测：

添加状态

二次探测

4.负载因子

5.哈希冲突的处理方法和哈希函数 区分

阶段一：只有插入的哈希

阶段二：完善哈希表，雏形哈希桶

1.当key是string或其他类型，如何映射？

2.仿函数中的特化

3.开散列（哈希桶）

阶段三：完善哈希桶

析构函数

优化insert

总代码：

阶段四：模拟实现unorderedmap/set

（1）template 第二个模板T

（2）class KeyOfT模板参数：

（3）HashFunc模板 要放到 UnorderedSet.h / UnorderedMap.h 中

UnorderedSet.h

UnorderedMap.h

HashTable.h

Test.cpp

一.unordered_map和unordered_set

unordered_map和unordered_set和map/set用法一样，不同就是unordered_map和unordered_set不排序，map/set自动排序

1.时间复杂度：它们查找的时间复杂度平均都是O(1)

哈希是通过哈希函数来计算元素的存储位置的，找的时候同样通过哈希函数找元素位 置，不需要循环遍历因此时间复杂度为O(1)

2.它们的底层结构相同，都使用哈希桶

3.它们在进行元素插入时，不需要比较key找待插入元素的位置，只需要通过哈希函数，就可以确认元素需要存储的位置。

简单的使用代码：

  1. #include<iostream>
  2. #include <set>
  3. #include <map>
  4. #include <unordered_set>
  5. #include <unordered_map>
  6. #include <time.h>
  7. using namespace std;
  8.  
  9. void test_set()
  10. {
  11. 	unordered_set<int> s;
  12. 	//set<int> s;
  13. 	s.insert(2);
  14. 	s.insert(3);
  15. 	s.insert(1);
  16. 	s.insert(2);
  17. 	s.insert(5);
  18.  
  19. 	//unordered_set<int>::iterator it = s.begin();
  20. 	auto it = s.begin();
  21. 	while (it != s.end())
  22. 	{
  23. 		cout << *it << " ";
  24. 		++it;
  25. 	}
  26. 	cout << endl;
  27.  
  28. 	for (auto e : s)
  29. 	{
  30. 		cout << e << " ";
  31. 	}
  32. 	cout << endl;
  33. }
  34.  
  35. void test_op()    //用于记录插入1000w个数两个容器花费时间的函数
  36. {
  37. 	int n = 10000000;
  38. 	vector<int> v;
  39. 	v.reserve(n);
  40. 	srand(time(0));
  41. 	for (int i = 0; i < n; ++i)
  42. 	{
  43. 		//v.push_back(i);
  44. 		//v.push_back(rand()+i);  // 重复少
  45. 		v.push_back(rand());  // 重复多
  46. 	}
  47.  
  48. 	size_t begin1 = clock();
  49. 	set<int> s;
  50. 	for (auto e : v)
  51. 	{
  52. 		s.insert(e);
  53. 	}
  54. 	size_t end1 = clock();
  55.  
  56. 	size_t begin2 = clock();
  57. 	unordered_set<int> us;
  58. 	for (auto e : v)
  59. 	{
  60. 		us.insert(e);
  61. 	}
  62. 	size_t end2 = clock();
  63.  
  64. 	cout << s.size() << endl;
  65.  
  66. 	cout << "set insert:" << end1 - begin1 << endl;
  67. 	cout << "unordered_set insert:" << end2 - begin2 << endl;
  68.  
  69.  
  70. 	size_t begin3 = clock();
  71. 	for (auto e : v)
  72. 	{
  73. 		s.find(e);
  74. 	}
  75. 	size_t end3 = clock();
  76.  
  77. 	size_t begin4 = clock();
  78. 	for (auto e : v)
  79. 	{
  80. 		us.find(e);
  81. 	}
  82. 	size_t end4 = clock();
  83. 	cout << "set find:" << end3 - begin3 << endl;
  84. 	cout << "unordered_set find:" << end4 - begin4 << endl;
  85.  
  86. 	
  87. 	size_t begin5 = clock();
  88. 	for (auto e : v)
  89. 	{
  90. 		s.erase(e);
  91. 	}
  92. 	size_t end5 = clock();
  93.  
  94. 	size_t begin6 = clock();
  95. 	for (auto e : v)
  96. 	{
  97. 		us.erase(e);
  98. 	}
  99. 	size_t end6 = clock();
  100. 	cout << "set erase:" << end5 - begin5 << endl;
  101. 	cout << "unordered_set erase:" << end6 - begin6 << endl;
  102. }
  103.  
  104. void test_map()
  105. {
  106. 	unordered_map<string, string> dict;
  107. 	dict.insert(make_pair("sort", "排序"));
  108. 	dict.insert(make_pair("left", "左边"));
  109. 	dict.insert(make_pair("left", "剩余"));
  110. 	dict["string"];
  111. 	dict["left"] = "剩余";
  112. 	dict["string"] = "字符串";
  113. }
  114.  
  115. int main()
  116. {
  117. 	//test_set();
  118. 	//test_op();
  119. 	test_map();
  120.  
  121. 	return 0;
  122. }

二.哈希

哈希（散列）-映射：存储关键字跟存储位置建立关联关系

值和存储位置——> 映射关系 ——> 查找按映射关系去找

哈希是一种用来进行高效查找的数据结构，查找的时间复杂度平均为O(1)

采用哈希方式解决问题时，必须使用哈希函数

哈希查找的时间复杂度不一定是O(1)（因为存在哈希冲突，一般基本都是O(1)）

哈希是以牺牲空间为代价，提高查询的效率（采用哈希处理时，一般所需空间都会比元素个数多，否则产生冲突的概率就比较大，影 响哈希的性能）

直接建立映射关系问题:
1、数据范围分布很广、不集中（除留余数法解决）
2、key的数据不是整数,是字符串怎么办?是自定义类型对象怎么办?

1. 直接定址法--(数分布集中 常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且集中连续的情况

2. 除留余数法--(数分布不集中,均匀 常用)

key %表大小——>映射的位置
                         下面都假设这个表大小是10

 除留余数法会有个问题，就是哈希冲突

3.哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突 或哈希碰撞。

例如：除留余数法中，20%表大小10=0，把20放在下标0处，如果有30,50呢，30,50%10也得放在下标0处，所以要解决哈希冲突，解决哈希冲突两种常见的方法是：闭散列和开散列。

（2）闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置
呢？闭散列分为线性探测和二次探测

线性探测：

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

hash(key)%N + i（i= 0,1,2,3...）：比如10%N(N是表大小10)=0，因为下标0已经放了20，则再加i=1，10%10+1=1，就把10放到了下标是1的地方。30：放30就是30%10+2=2，把30放到了下标是2的地方
 

 缺点:我占你的，你占他的，拥堵

添加状态

比如查找50时，一直找到空就停止，但是如果在50之前有删除的数据，就会在删除数据的位置停下，这样就找不到50了，所以添加个状态用于区分空和删除的位置。遇到空EMPTY就停，遇到删除DELETE和存在 EXITS就不停 

  1. enum State   
  2. {
  3. 	EMPTY,
  4. 	EXITS,
  5. 	DELETE
  6. };

二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位
置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，改成每次跳 i² 个

hash(key)%N + i² （i= 0,1,2,3...）

比如10%N(N是表大小10)=0，因为下标0已经放了20，则再加 i² =1，10%10+1=1，就把10放到了下标是1的地方。30：放30就是30%10+2²=4，把30放到了下标是4的地方

对上面方法的优化:不那么拥堵

starti %= _tables.size();还是.capacity() ？

_tables.size()是能存数据的位置个数，_tables.capacity()是总容量大小（包括没有初始化的空间）类似resize和reserve的区别，starti %= _tables.size(); 插入数据只能插在能插入的位置，因为_tables[hashi] 的operator[] 会自动检查这个位置是否有值还是没有值的随机数，有值就可以插入。

4.负载因子

负载因子（散列表的载荷因子α） = 填入表中的元素个数 / 哈希表的长度

由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，表明填入表中的元素越多，产生冲突的可能性就越大:反之，α越小，标明填入表中的元素越少，产生冲突的可能性就越小。

哈希表什么情况下进行扩容？如何扩容？
负载因子大于0.7就扩容。

5.哈希冲突的处理方法和哈希函数 区分

 哈希函数作用是：建立元素与其存储位置之前的对应关系的，在存储元素时，先通过哈希函数计算元素在哈希表格中的存储位置，然后存储元素。好的哈希函数可以减少冲突的概率，但是不能绝对避免哈希函数，万一发生哈希冲突，得需要借助哈希冲突处理方法来 解决。

   常见的哈希函数有：直接定址法、除留余数法、平方取中法、随机数法、数字分析法、叠加法等

   常见哈希冲突处理：闭散列（线性探测、二次探测）、开散列(链地址法)、多次散列

常见哈希函数 ：
1. 直接定址法--(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
2. 除留余数法--(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3. 平方取中法--(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
4. 折叠法--(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这
几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5. 随机数法--(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中
random为随机数函数。
通常应用于关键字长度不等时采用此法
6. 数学分析法--(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定
相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只
有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散
列地址。

阶段一：只有插入的哈希

  1. #pragma once
  2. #include<vector>
  3.  
  4. enum State    
  5. {
  6. 	EMPTY,
  7. 	EXITS,
  8. 	DELETE
  9. };
  10.  
  11. // 休息21:16继续
  12. template<class K, class V>
  13. struct HashData
  14. {
  15. 	pair<K, V> _kv;
  16. 	State _state;
  17. };
  18.  
  19. template<class K, class V>
  20. class HashTable
  21. {
  22. public:
  23. 	bool Insert(const pair<K, V>& kv)
  24. 	{
  25. // 负载因子到0.7及以上，就扩容。这里算 负载因子>0.7,因为是小数，前面可能需要类型转换，否则除出来是0，我们不如把 负载因子*10>7
  26. 		if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
  27. 		{    
  28. 			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
  29. 			// 扩容以后，需要重新映射
  30. 			HashTable<K, V> newHT;
  31. 			newHT._tables.resize(newSize);
  32. 			// 遍历旧表，插入newHT
  33. 			for (auto& e : _tables)
  34. 			{
  35. 				if (e._state == EXITS)
  36. 				{
  37. 					newHT.Insert(e._kv);
  38. 				}
  39. 			}
  40. 			newHT._tables.swap(_tables);
  41. 		}
  42.  
  43. 		size_t starti = kv.first;
  44. 		starti %= _tables.size();
  45.  
  46. 		size_t hashi = starti;
  47. 		size_t i = 1;
  48. 		// 线性探测/二次探测
  49. 		while (_tables[hashi]._state == EXITS)
  50. 		{
  51. 			hashi = starti + i;
  52. 			++i;
  53. 			hashi %= _tables.size();
  54. 		}
  55.  
  56. 		_tables[hashi]._kv = kv;
  57. 		_tables[hashi]._state = EXITS;
  58. 		_n++;
  59. 	}
  60. 	
  61. 	HashData* Find(const K& key);
  62. 	bool Erase(const K& key);
  63.  
  64. private:
  65. 	vector<HashData> _tables;
  66. 	size_t _n = 0; // 存储关键字个数
  67. };

阶段二：完善哈希表，雏形哈希桶

1.当key是string或其他类型，如何映射？

key是string或者自定义类型时，需要转成整数再映射进哈希表，这个转成整数的方法有多样，比如：string类型转成整数方法是BKDR法，hash乘一个值131再加字符串的ASCII值，这样能减少冲突。如果仅仅是通过整个字符串的ASCII值来来映射，比如"abc"和"bac"就一样，一样就是哈希冲突，哈希冲突也没关系，我们有处理哈希冲突的机制：把映射到同一位置的值像下一个位置放（线性探测）。类似于先放20后再放10，映射在大小是10的哈希表中，都放在0处，哈希冲突了，就可以把10放在20后面的空位置上。

  1.     template<>
  2. 	struct DefaultHash<string>
  3. 	{
  4. 		size_t operator()(const string& key)
  5. 		{             //key是string类型用仿函数DefaultHash转成整数
  6. 			//转换方法：BKDR ，数学研究出来的
  7. 			size_t hash = 0;
  8. 			for (auto ch : key) 
  9. 			{    
  10. 				hash = hash * 131 + ch;    //hash乘一个值131再加字符串的ASCII
  11. 			}
  12.  
  13. 			return hash;
  14. 		}
  15. 	};

2.仿函数中的特化

这样模拟实现unorodered_map时，直接定义 unorodered_map<int,int> a; 时不用传仿函数是因为template<class K, class V, class HashFunc = DefaultHash<K>> 仿函数给了缺省参数，不传默认是基础的类struct DefaultHash，直接定义 unorodered_map<string,string> b; 时也可以不用传仿函数是因为类模板特化，key是string就会使用特化版本的struct DefaultHash<string>

  1.     template<class K>
  2. 	struct DefaultHash
  3. 	{
  4. 		size_t operator()(const K& key)
  5. 		{
  6. 			return (size_t)key;
  7. 		}
  8. 	};
  9.  
  10.  
  11. 	template<>
  12. 	struct DefaultHash<string>
  13. 	{
  14. 		size_t operator()(const string& key)
  15. 		{             //key是string类型用仿函数DefaultHash转成整数
  16. 			//转换方法：BKDR ，数学研究出来的
  17. 			size_t hash = 0;
  18. 			for (auto ch : key) 
  19. 			{    
  20. 				hash = hash * 131 + ch;    //hash乘一个值131再加字符串的ASCII
  21. 			}
  22.  
  23. 			return hash;
  24. 		}
  25. 	};
  26.  
  27. template<class K, class V, class HashFunc = DefaultHash<K>>
  28. 	class HashTable
  29. 	{
  30. 		typedef HashData<K, V> Data;
  31. 	public:
  32.     ……

3.开散列（哈希桶）

（1） 哈希桶/开散列/链地址法/开链法 概念
开散列法又叫 哈希桶/链地址法/开链法，数据不存在表中，表里面存储一个链表指针，冲突的数据链表形式挂起来。 哈希桶用 单链表，不进行插入删除操作就不用双向链表，仅头插就可以，而且单链表比双向链表少存一个指针，能省则省。

vector<Node*> 数组每个位置存的是链表第一个值的指针

  1. #pragma once
  2. #include<vector>
  3.  
  4. namespace CloseHash
  5. {
  6.  
  7. 	enum State
  8. 	{
  9. 		EMPTY,
  10. 		EXITS,
  11. 		DELETE
  12. 	};
  13.  
  14.  
  15. 	template<class K, class V>
  16. 	struct HashData
  17. 	{
  18. 		pair<K, V> _kv;
  19. 		State _state = EMPTY;
  20. 	};
  21.  
  22. 	template<class K>
  23. 	struct DefaultHash
  24. 	{
  25. 		size_t operator()(const K& key)
  26. 		{
  27. 			return (size_t)key;
  28. 		}
  29. 	};
  30.  
  31.  
  32. 	template<>
  33. 	struct DefaultHash<string>
  34. 	{
  35. 		size_t operator()(const string& key)
  36. 		{             //key是string类型用仿函数DefaultHash转成整数
  37. 			//转换方法：BKDR ，数学研究出来的
  38. 			size_t hash = 0;
  39. 			for (auto ch : key) 
  40. 			{    
  41. 				hash = hash * 131 + ch;    //hash乘一个值131再加字符串的ASCII
  42. 			}
  43.  
  44. 			return hash;
  45. 		}
  46. 	};
  47.  
  48. 	//struct StringHash
  49. 	//{
  50. 	//	// "abcd"
  51. 	//	// "aa"
  52. 	//	size_t operator()(const string& key)
  53. 	//	{
  54. 	//		//return key[0];     可以
  55. 	//		//return (size_t)&key; 不行
  56. 	//
  57. 	//		/*size_t hash = 0;
  58. 	//		for (auto ch : key)
  59. 	//		{
  60. 	//			hash += ch;
  61. 	//		}
  62. 	//
  63. 	//		return hash;*/
  64. 	//
  65. 	//		// BKDR
  66. 	//		size_t hash = 0;
  67. 	//		for (auto ch : key)
  68. 	//		{
  69. 	//			hash = hash* 131 + ch;
  70. 	//		}
  71. 	//
  72. 	//		return hash;
  73. 	//	}
  74. 	//};
  75.  
  76. 	template<class K, class V, class HashFunc = DefaultHash<K>>
  77. 	class HashTable
  78. 	{
  79. 		typedef HashData<K, V> Data;
  80. 	public:
  81. 		bool Insert(const pair<K, V>& kv)
  82. 		{
  83. 			if (Find(kv.first))    //去冗余 易错点1，容易忘写
  84. 			{
  85. 				return false;
  86. 			}
  87.  
  88. 			// 负载因子到0.7及以上，就扩容
  89. 			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
  90. 			{
  91. 				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
  92. 				// 扩容以后，需要重新映射
  93. 				HashTable<K, V, HashFunc> newHT;
  94. 				newHT._tables.resize(newSize);
  95. 				// 遍历旧表，插入newHT
  96. 				for (auto& e : _tables)
  97. 				{
  98. 					if (e._state == EXITS)    //易错点2，容易忘写
  99. 					{
  100. 						newHT.Insert(e._kv);
  101. 					}
  102. 				}
  103. 				newHT._tables.swap(_tables);
  104. 			}
  105.  
  106. 			HashFunc hf;
  107. 			size_t starti = hf(kv.first);
  108. 			starti %= _tables.size();
  109.  
  110. 			size_t hashi = starti;
  111. 			size_t i = 1;
  112. 			// 线性探测/二次探测
  113. 			while (_tables[hashi]._state == EXITS)
  114. 			{
  115. 				hashi = starti + i;
  116. 				++i;
  117. 				hashi %= _tables.size();
  118. 			}
  119.  
  120. 			_tables[hashi]._kv = kv;
  121. 			_tables[hashi]._state = EXITS;
  122. 			_n++;
  123.  
  124. 			return true;
  125. 		}
  126.  
  127. 		Data* Find(const K& key)
  128. 		{
  129. 			if (_tables.size() == 0)  //哈希表还没数据时不能查找
  130. 			{
  131. 				return nullptr;
  132. 			}
  133.  
  134. 			HashFunc hf;
  135. 			size_t starti = hf(key);  //不同类型的key通过对应的仿函数转成整数-
  136. 			starti %= _tables.size();//-比如key是string类型，就-        
  137. 			size_t hashi = starti;           //-用仿函数DefaultHash转成整形
  138. 			size_t i = 1;
  139. 			while (_tables[hashi]._state != EMPTY)
  140. 			{    //下面如果状态是DELETE就无法被查找到
  141. 				if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
  142. 				{
  143. 					return &_tables[hashi];
  144. 				}
  145.  
  146. 				hashi = starti + i;
  147. 				++i;
  148. 				hashi %= _tables.size();
  149. 			}
  150.  
  151. 			return nullptr;
  152. 		}
  153.  
  154. 		bool Erase(const K& key)
  155. 		{
  156. 			Data* ret = Find(key);
  157. 			if (ret)
  158. 			{
  159. 				ret->_state = DELETE;
  160. 				--_n;
  161. 				return true;
  162. 			}
  163. 			else
  164. 			{
  165. 				return false;
  166. 			}
  167. 		}
  168.  
  169. 	private:
  170. 		vector<Data> _tables;
  171. 		size_t _n = 0; // 存储关键字个数
  172. 	};
  173.  
  174.  
  175. 	void TestHT1()
  176. 	{
  177. 		int a[] = { 20, 5, 8, 99999, 10, 30, 50 };
  178. 		//HashTable<int, int, DefaultHash<int>> ht;
  179. 		HashTable<int, int> ht;
  180.  
  181. 		if (ht.Find(10))
  182. 		{
  183. 			cout << "找到了10" << endl;
  184. 		}
  185.  
  186. 		for (auto e : a)
  187. 		{
  188. 			ht.Insert(make_pair(e, e));
  189. 		}
  190.  
  191. 		// 测试扩容
  192. 		ht.Insert(make_pair(15, 15));
  193. 		ht.Insert(make_pair(5, 5));
  194. 		ht.Insert(make_pair(15, 15));
  195.  
  196. 		if (ht.Find(50))
  197. 		{
  198. 			cout << "找到了50" << endl;
  199. 		}
  200.  
  201. 		if (ht.Find(10))
  202. 		{
  203. 			cout << "找到了10" << endl;
  204. 		}
  205.  
  206. 		ht.Erase(10);
  207. 		ht.Erase(10);
  208.  
  209. 		if (ht.Find(50))
  210. 		{
  211. 			cout << "找到了50" << endl;
  212. 		}
  213.  
  214. 		if (ht.Find(10))
  215. 		{
  216. 			cout << "找到了10" << endl;
  217. 		}
  218. 	}
  219.  
  220. 	void TestHT2()
  221. 	{
  222. 		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
  223.  
  224. 		/*string s1("苹果");
  225. 		string s2("果苹");
  226. 		string s3("果果");
  227. 		string s4("萍果");
  229. 		string s5("abcd");
  230. 		string s6("bcad");
  231. 		string s7("aadd");
  233. 		StringHash hf;
  234. 		cout << hf(s1) << endl;
  235. 		cout << hf(s2) << endl;
  236. 		cout << hf(s3) << endl;
  237. 		cout << hf(s4) << endl << endl;
  238. 		cout << hf(s5) << endl;
  239. 		cout << hf(s6) << endl;
  240. 		cout << hf(s7) << endl;*/
  241.  
  242.  
  243. 		//HashTable<string, int, StringHash> countHT;
  244. 		HashTable<string, int> countHT;
  245.  
  246. 		for (auto& str : arr)
  247. 		{
  248. 			auto ret = countHT.Find(str);
  249. 			if (ret)
  250. 			{
  251. 				ret->_kv.second++;
  252. 			}
  253. 			else
  254. 			{
  255. 				countHT.Insert(make_pair(str, 1));
  256. 			}
  257. 		}
  258.  
  259. 		// 对应类型配一个仿函数，仿函数对象实现把key对象转换成映射的整数
  260. 		//HashTable<Date, int, DateHash> countHT;
  261. 		//HashTable<Student, int, StudentHash> countHT;
  262.  
  263.  
  264. 		HashTable<string, int> copy(countHT);
  265. 	}
  266. }
  267.  
  268. namespace Bucket
  269. {
  270. 	template<class K, class V>
  271. 	struct HashNode
  272. 	{
  273. 		pair<K, V> _kv;
  274. 		HashNode<K, V>* _next;
  275.  
  276. 		HashNode(const pair<K, V>& kv)
  277. 			:_kv(kv)
  278. 			, _next(nullptr)
  279. 		{}
  280. 	};
  281.  
  282. 	template<class K, class V>
  283. 	class HashTable
  284. 	{
  285. 		typedef HashNode<K, V> Node;
  286. 	public:
  287. 		bool Insert(const pair<K, V>& kv)
  288. 		{
  289. 			if (Find(kv.first))
  290. 			{
  291. 				return false;
  292. 			}
  293.  
  294. 			// 负载因子 == 1 扩容
  295. 			if (_tables.size() == _n)
  296. 			{
  297. 				// 扩容，有缺陷，可以再优化，大家下去可以思考一下
  298. 				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
  299. 				HashTable<K, V> newHT;
  300. 				newHT._tables.resize(newSize, nullptr);
  301.  
  302. 				for (size_t i = 0; i < _tables.size(); ++i)
  303. 				{
  304. 					Node* cur = _tables[i];
  305. 					while (cur)
  306. 					{
  307. 						newHT.Insert(cur->_kv);
  308. 						cur = cur->_next;
  309. 					}
  310. 				}
  311.  
  312. 				newHT._tables.swap(_tables);
  313. 			}
  314.  
  315. 			size_t hashi = kv.first;
  316. 			hashi %= _tables.size();
  317.  
  318. 			// 头插到对应的桶即可
  319. 			Node* newnode = new Node(kv);
  320. 			newnode->_next = _tables[hashi];
  321. 			_tables[hashi] = newnode;
  322.  
  323. 			++_n;
  324.  
  325. 			return true;
  326. 		}
  327.  
  328. 		Node* Find(const K& key)
  329. 		{
  330. 			if (_tables.size() == 0)
  331. 			{
  332. 				return nullptr;
  333. 			}
  334.  
  335. 			size_t hashi = key;
  336. 			hashi %= _tables.size();
  337. 			Node* cur = _tables[hashi];
  338. 			while (cur)
  339. 			{
  340. 				if (cur->_kv.first == key)
  341. 				{
  342. 					return cur;
  343. 				}
  344.  
  345. 				cur = cur->_next;
  346. 			}
  347.  
  348. 			return nullptr;
  349. 		}
  350.  
  351. 	private:
  352. 		// 指针数组
  353. 		vector<Node*> _tables;
  354. 		size_t _n = 0;
  355. 	};
  356.  
  357. 	void TestHT1()
  358. 	{
  359. 		int a[] = { 20, 5, 8, 99999, 10, 30, 50 };
  360. 		//HashTable<int, int, DefaultHash<int>> ht;
  361. 		HashTable<int, int> ht;
  362.  
  363. 		if (ht.Find(10))
  364. 		{
  365. 			cout << "找到了10" << endl;
  366. 		}
  367.  
  368. 		for (auto e : a)
  369. 		{
  370. 			ht.Insert(make_pair(e, e));
  371. 		}
  372.  
  373. 		// 测试扩容
  374. 		ht.Insert(make_pair(15, 15));
  375. 		ht.Insert(make_pair(5, 5));
  376. 		ht.Insert(make_pair(15, 15));
  377. 		ht.Insert(make_pair(25, 15));
  378. 		ht.Insert(make_pair(35, 15));
  379. 		ht.Insert(make_pair(45, 15));
  380. 	}
  381. }

阶段三：完善哈希桶

新增析构函数，优化版insert，删除Erase，拷贝构造,赋值(自己写)，Hashfunc(string也可以%)

析构函数

vector是自定义类型会去调用自己的析构函数析构数组，但不会释放每个位置上的链表的节点，我们要一个一个释放每个链表的每个节点

  1. 	    ~HashTable()
  2. 		{
  3. 			for (size_t i = 0; i < _tables.size(); ++i)
  4. 			{
  5. 				Node* cur = _tables[i];
  6. 				while (cur)
  7. 				{
  8. 					Node* next = cur->_next;
  9. 					delete cur;
  10. 					cur = next;
  11. 				}
  12.  
  13. 				_tables[i] = nullptr;
  14. 			}
  15. 		}

优化insert

开一个新的扩容后大小的数组newTable，把原数组_table的节点一个一个头插到新数组中，这样就避免原方法中的双重消耗：新开节点(插入数组)，释放旧数组节点

  1. bool Insert(const T& data)
  2. 		{
  3. 			HashFunc hf;
  4. 			KeyOfT kot;
  5.  
  6. 			if (Find(kot(data)))
  7. 			{
  8. 				return false;
  9. 			}
  10.  
  11. 			// 负载因子 == 1 扩容
  12. 			if (_tables.size() == _n)
  13. 			{
  14. 				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
  15. 				vector<Node*> newTable;    //开一个新的扩容后大小的数组
  16. 				newTable.resize(newSize, nullptr); //开一个新的扩容后大小的数组
  17. 				for (size_t i = 0; i < _tables.size(); ++i)
  18. 				{
  19. 					Node* cur = _tables[i];
  20. 					while (cur)
  21. 					{
  22. 						Node* next = cur->_next;
  23.  
  24. 						size_t hashi = hf(kot(cur->_data)) % newSize;
  25. 						cur->_next = newTable[hashi];
  26. 						newTable[hashi] = cur;
  27.  
  28. 						cur = next;
  29. 					}
  30.  
  31. 					_tables[i] = nullptr;
  32. 				}
  33.  
  34. 				newTable.swap(_tables);
  35. 			}
  36.  
  37. 			size_t hashi = hf(kot(data));
  38. 			hashi %= _tables.size();
  39.  
  40. 			// 头插到对应的桶即可
  41. 			Node* newnode = new Node(data);
  42. 			newnode->_next = _tables[hashi];
  43. 			_tables[hashi] = newnode;
  44.  
  45. 			++_n;
  46.  
  47. 			return true;
  48. 		}

总代码：

  1. #pragma once
  2. #include<vector>
  3.  
  4. template<class K>
  5. struct DefaultHash
  6. {
  7. 	size_t operator()(const K& key)
  8. 	{
  9. 		return (size_t)key;
  10. 	}
  11. };
  12.  
  13.  
  14. template<>
  15. struct DefaultHash<string>
  16. {
  17. 	size_t operator()(const string& key)
  18. 	{
  19. 		// BKDR
  20. 		size_t hash = 0;
  21. 		for (auto ch : key)
  22. 		{
  23. 			hash = hash * 131 + ch;
  24. 		}
  25.  
  26. 		return hash;
  27. 	}
  28. };
  29.  
  30.  
  31. namespace Bucket
  32. {
  33. 	template<class K, class V>
  34. 	struct HashNode
  35. 	{
  36. 		pair<K, V> _kv;
  37. 		HashNode<K, V>* _next;
  38.  
  39. 		HashNode(const pair<K, V>& kv)
  40. 			:_kv(kv)
  41. 			, _next(nullptr)
  42. 		{}
  43. 	};
  44.  
  45. 	template<class K, class V, class HashFunc = DefaultHash<K>>
  46. 	class HashTable
  47. 	{
  48. 		typedef HashNode<K, V> Node;
  49. 	public:
  50. 		~HashTable()
  51. 		{
  52. 			for (size_t i = 0; i < _tables.size(); ++i)
  53. 			{
  54. 				Node* cur = _tables[i];
  55. 				while (cur)
  56. 				{
  57. 					Node* next = cur->_next;
  58. 					delete cur;
  59. 					cur = next;
  60. 				}
  61.  
  62. 				_tables[i] = nullptr;
  63. 			}
  64. 		}
  65.  
  66. 		bool Insert(const pair<K, V>& kv)
  67. 		{
  68. 			if (Find(kv.first))
  69. 			{
  70. 				return false;
  71. 			}
  72.  
  73. 			HashFunc hf;
  74.  
  75. 			// 负载因子 == 1 扩容
  76. 			if (_tables.size() == _n)
  77. 			{
  78. 				// 扩容，有缺陷，可以再优化，大家下去可以思考一下
  79. 				/*size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
  80. 				HashTable<K, V> newHT;
  81. 				newHT._tables.resize(newSize, nullptr);
  83. 				for (size_t i = 0; i < _tables.size(); ++i)
  84. 				{
  85. 					Node* cur = _tables[i];
  86. 					while (cur)
  87. 					{
  88. 						newHT.Insert(cur->_kv);
  89. 						cur = cur->_next;
  90. 					}
  91. 				}
  93. 				newHT._tables.swap(_tables);*/
  94.  
  95. 				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
  96. 				vector<Node*> newTable;
  97. 				newTable.resize(newSize, nullptr);
  98. 				for (size_t i = 0; i < _tables.size(); ++i)
  99. 				{
  100. 					Node* cur = _tables[i];
  101. 					while (cur)
  102. 					{
  103. 						Node* next = cur->_next;
  104.  
  105. 						size_t hashi = hf(cur->_kv.first) % newSize;
  106. 						cur->_next = newTable[hashi];
  107. 						newTable[hashi] = cur;
  108.  
  109. 						cur = next;
  110. 					}
  111.  
  112. 					_tables[i] = nullptr;
  113. 				}
  114.  
  115. 				newTable.swap(_tables);
  116. 			}
  117.  
  118. 			size_t hashi = hf(kv.first);
  119. 			hashi %= _tables.size();
  120.  
  121. 			// 头插到对应的桶即可
  122. 			Node* newnode = new Node(kv);
  123. 			newnode->_next = _tables[hashi];
  124. 			_tables[hashi] = newnode;
  125.  
  126. 			++_n;
  127.  
  128. 			return true;
  129. 		}
  130.  
  131. 		Node* Find(const K& key)
  132. 		{
  133. 			if (_tables.size() == 0)
  134. 			{
  135. 				return nullptr;
  136. 			}
  137.  
  138. 			HashFunc hf;
  139. 			size_t hashi = hf(key);
  140. 			//size_t hashi = HashFunc()(key);
  141.  
  142. 			hashi %= _tables.size();
  143. 			Node* cur = _tables[hashi];
  144. 			while (cur)
  145. 			{
  146. 				if (cur->_kv.first == key)
  147. 				{
  148. 					return cur;
  149. 				}
  150.  
  151. 				cur = cur->_next;
  152. 			}
  153.  
  154. 			return nullptr;
  155. 		}
  156.  
  157. 		bool Erase(const K& key)
  158. 		{
  159. 			if (_tables.size() == 0)
  160. 			{
  161. 				return false;
  162. 			}
  163.  
  164. 			HashFunc hf;
  165. 			size_t hashi = hf(key);
  166. 			hashi %= _tables.size();
  167. 			Node* prev = nullptr;
  168. 			Node* cur = _tables[hashi];
  169. 			while (cur)
  170. 			{
  171. 				if (cur->_kv.first == key)
  172. 				{
  173. 					if (prev == nullptr)
  174. 					{
  175. 						_tables[hashi] = cur->_next;
  176. 					}
  177. 					else
  178. 					{
  179. 						prev->_next = cur->_next;
  180. 					}
  181.  
  182. 					delete cur;
  183. 					
  184. 					return true;
  185. 				}
  186.  
  187. 				prev = cur;
  188. 				cur = cur->_next;
  189. 			}
  190.  
  191. 			return false;
  192.  
  193. 			//size_t hashi = key;
  194. 			//hashi %= _tables.size();
  195. 			//Node* cur = _tables[hashi];
  196. 			//while (cur)
  197. 			//{
  198. 			//	if (cur->_kv.first == key)
  199. 			//	{
  200. 			//		if (cur->_next == nullptr)
  201. 			//		{
  202. 			//			cur->_kv = _tables[hashi]->_kv;
  203. 			//			Node* first = _tables[hashi];
  204. 			//			_tables[hashi] = first->_next;
  205. 			//			delete first;
  206. 			//		}
  207. 			//		else
  208. 			//		{
  209. 			//			//....
  210. 			//		}
  211.  
  212. 			//		return true;
  213. 			//	}
  214.  
  215. 			//	prev = cur;
  216. 			//	cur = cur->_next;
  217. 			//}
  218.  
  219. 			//return false;
  220. 		}
  221.  
  222. 	private:
  223. 		// 指针数组
  224. 		vector<Node*> _tables;
  225. 		size_t _n = 0;
  226. 	};
  227.  
  228. 	void TestHT1()
  229. 	{
  230. 		int a[] = { 20, 5, 8, 99999, 10, 30, 50 };
  231. 		//HashTable<int, int, DefaultHash<int>> ht;
  232. 		HashTable<int, int> ht;
  233.  
  234. 		if (ht.Find(10))
  235. 		{
  236. 			cout << "找到了10" << endl;
  237. 		}
  238.  
  239. 		for (auto e : a)
  240. 		{
  241. 			ht.Insert(make_pair(e, e));
  242. 		}
  243.  
  244. 		ht.Erase(20);
  245. 		ht.Erase(10);
  246. 		ht.Erase(30);
  247. 		ht.Erase(50);
  248.  
  249.  
  250. 		// 测试扩容
  251. 		ht.Insert(make_pair(15, 15));
  252. 		ht.Insert(make_pair(5, 5));
  253. 		ht.Insert(make_pair(15, 15));
  254. 		ht.Insert(make_pair(25, 15));
  255. 		ht.Insert(make_pair(35, 15));
  256. 		ht.Insert(make_pair(45, 15));
  257. 	}
  258.  
  259. 	void TestHT2()
  260. 	{
  261. 		int a[] = { 20, 5, 8, 99999, 10, 30, 50 };
  262. 		HashTable<int, int> ht;
  263. 		for (auto e : a)
  264. 		{
  265. 			ht.Insert(make_pair(e, e));
  266. 		}
  267.  
  268. 		// 需要自己实现拷贝构造，完成链表桶深拷贝
  269. 		//HashTable<int, int> copy(ht);
  270. 	}
  271.  
  272. 	void TestHT3()
  273. 	{
  274. 		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
  275.  
  276. 		//HashTable<string, int, StringHash> countHT;
  277. 		HashTable<string, int> countHT;
  278.  
  279. 		for (auto& str : arr)
  280. 		{
  281. 			auto ret = countHT.Find(str);
  282. 			if (ret)
  283. 			{
  284. 				ret->_kv.second++;
  285. 			}
  286. 			else
  287. 			{
  288. 				countHT.Insert(make_pair(str, 1));
  289. 			}
  290. 		}
  291. 	}
  292. }

阶段四：模拟实现unorderedmap/set

（1）template<class K, class T, class KeyOfT, class HashFunc> 第二个模板T

作用是让同一份哈希桶的代码能区分unordered_set和unordered_map，如果是unordered_set模板T就传入K，unordered_map模板T就传入pair

（2）class KeyOfT模板参数：

用于取出map中的pair中的K，取set中的key

  1.         KeyOfT kot;
  2.  
  3. 			if (Find(kot(data)))
  4. 			{
  5. 				return false;
  6. 			}

（3）HashFunc模板 要放到 UnorderedSet.h / UnorderedMap.h 中

因为K可能是 Date 这些自定义类型，无法直接比较，要写个仿函数DateHash，test_set() 中定义对象时就传这个仿函数unordered_set<Date, DateHash> sd;

UnorderedSet.h

  1. pragma once
  2.  
  3. #include "HashTable.h"
  4.  
  5. namespace bit
  6. {
  7. 	// 21:06
  8. 	template<class K, class HashFunc = DefaultHash<K>>
  9. 	class unordered_set
  10. 	{
  11. 		struct SetKeyOfT
  12. 		{
  13. 			const K& operator()(const K& key)
  14. 			{
  15. 				return key;
  16. 			}
  17. 		};
  18. 	public:
  19. 		typedef typename Bucket::HashTable<K, K, SetKeyOfT, HashFunc>::iterator iterator;
  20.  
  21. 		iterator begin()
  22. 		{
  23. 			return _ht.begin();
  24. 		}
  25.  
  26. 		iterator end()
  27. 		{
  28. 			return _ht.end();
  29. 		}
  30.  
  31. 		pair<iterator, bool> insert(const K& key)
  32. 		{
  33. 			return _ht.Insert(key);
  34. 		}
  35.  
  36. 		iterator find(const K& key)
  37. 		{
  38. 			return _ht.Find(key);
  39. 		}
  40.  
  41. 		bool erase(const K& key)
  42. 		{
  43. 			return _ht.Erase(key);
  44. 		}
  45. 	private:
  46. 		Bucket::HashTable<K, K, SetKeyOfT, HashFunc> _ht;
  47. 	};
  48.  
  49. 	struct Date
  50. 	{
  51. 		Date(int year = 1, int month = 1, int day = 1)
  52. 		:_year(year)
  53. 		, _month(month)
  54. 		, _day(day)
  55. 		{}
  56.  
  57. 		bool operator==(const Date& d) const
  58. 		{
  59. 			return _year == d._year
  60. 				&& _month == d._month
  61. 				&& _day == d._day;
  62. 		}
  63.  
  64. 		int _year;
  65. 		int _month;
  66. 		int _day;
  67. 	};
  68.  
  69. 	struct DateHash
  70. 	{
  71. 		size_t operator()(const Date& d)
  72. 		{
  73. 			//return d._year + d._month + d._day;
  74. 			size_t hash = 0;
  75. 			hash += d._year;
  76. 			hash *= 131;
  77. 			hash += d._month;
  78. 			hash *= 1313;
  79. 			hash += d._day;
  80.  
  81. 			//cout << hash << endl;
  82.  
  83. 			return hash;
  84. 		}
  85. 	};
  86.  
  87. 	void test_set()
  88. 	{
  89. 		unordered_set<int> s;
  90. 		//set<int> s;
  91. 		s.insert(2);
  92. 		s.insert(3);
  93. 		s.insert(1);
  94. 		s.insert(2);
  95. 		s.insert(5);
  96. 		s.insert(12);
  97.  
  98. 		//unordered_set<int>::iterator it = s.begin();
  99. 		unordered_set<int>::iterator it;
  100. 		it = s.begin();
  101.  
  102. 		//auto it = s.begin();
  103. 		while (it != s.end())
  104. 		{
  105. 			cout << *it << " ";
  106. 			++it;
  107. 		}
  108. 		cout << endl;
  109.  
  110. 		
  111. 		for (auto e : s)
  112. 		{
  113. 			cout << e << " ";
  114. 		}
  115. 		cout << endl;
  116.  
  117. 		unordered_set<Date, DateHash> sd;
  118. 		sd.insert(Date(2022, 3, 4));
  119. 		sd.insert(Date(2022, 4, 3));
  120. 	}
  121. }

UnorderedMap.h

  1. #pragma once
  2.  
  3. #include "HashTable.h"
  4.  
  5. namespace bit
  6. {
  7. 	template<class K, class V, class HashFunc = DefaultHash<K>>
  8. 	class unordered_map
  9. 	{
  10. 		struct MapKeyOfT
  11. 		{
  12. 			const K& operator()(const pair<K, V>& kv)
  13. 			{
  14. 				return kv.first;
  15. 			}
  16. 		};
  17. 	public:
  18. 		typedef typename Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc>::iterator iterator;
  19.  
  20. 		iterator begin()
  21. 		{
  22. 			return _ht.begin();
  23. 		}
  24.  
  25. 		iterator end()
  26. 		{
  27. 			return _ht.end();
  28. 		}
  29.  
  30. 		pair<iterator, bool> insert(const pair<K, V>& kv)
  31. 		{
  32. 			return _ht.Insert(kv);	
  33. 		}
  34.  
  35. 		iterator find(const K& key)
  36. 		{
  37. 			return _ht.Find(key);
  38. 		}
  39.  
  40. 		bool erase(const K& key)
  41. 		{
  42. 			return _ht.Erase(key);
  43. 		}
  44.  
  45. 		V& operator[](const K& key)
  46. 		{
  47. 			pair<iterator, bool> ret = insert(make_pair(key, V()));
  48. 			return ret.first->second;
  49. 		}
  50.  
  51. 	private:
  52. 		Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc> _ht;
  53. 	};
  54.  
  55. 	void test_map()
  56. 	{
  57. 		unordered_map<string, string> dict;
  58. 		dict.insert(make_pair("sort", ""));
  59. 		dict.insert(make_pair("left", ""));
  60. 		dict.insert(make_pair("left", "ʣ"));
  61. 		dict["string"];
  62. 		dict["left"] = "ʣ";
  63. 		dict["string"] = "ַ";
  64.  
  65. 		unordered_map<string, string>::iterator it = dict.begin();
  66. 		while (it != dict.end())
  67. 		{
  68. 			cout << it->first << " " << it->second << endl;
  69. 			++it;
  70. 		}
  71.  
  72. 		cout << endl;
  73.  
  74. 		for (auto& kv : dict)
  75. 		{
  76. 			cout << kv.first << " " << kv.second << endl;
  77. 		}
  78. 	}
  79. }

HashTable.h

  1. #pragma once
  2. #include<vector>
  3.  
  4. template<class K>
  5. struct DefaultHash
  6. {
  7. 	size_t operator()(const K& key)
  8. 	{
  9. 		return (size_t)key;
  10. 	}
  11. };
  12.  
  13.  
  14. template<>
  15. struct DefaultHash<string>
  16. {
  17. 	size_t operator()(const string& key)
  18. 	{
  19. 		// BKDR
  20. 		size_t hash = 0;
  21. 		for (auto ch : key)
  22. 		{
  23. 			hash = hash * 131 + ch;
  24. 		}
  25.  
  26. 		return hash;
  27. 	}
  28. };
  29.  
  30. namespace Bucket
  31. {
  32. 	template<class T>
  33. 	struct HashNode
  34. 	{
  35. 		T _data;
  36. 		HashNode<T>* _next;
  37.  
  38. 		HashNode(const T& data)
  39. 			:_data(data)
  40. 			, _next(nullptr)
  41. 		{}
  42. 	};
  43.  
  44. 	template<class K, class T, class KeyOfT, class HashFunc>
  45. 	class HashTable;
  46.  
  47. 	template<class K, class T, class KeyOfT, class HashFunc>
  48. 	class __HTIterator
  49. 	{
  50. 		typedef HashNode<T> Node;
  51. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;
  52. 	public:
  53. 		Node* _node;
  54. 		HashTable<K, T, KeyOfT, HashFunc>* _pht;
  55.  
  56. 		__HTIterator() {}    //默认构造函数和非默认构造函数重载
  57.  
  58. 		__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
  59. 			:_node(node)
  60. 			, _pht(pht)
  61. 		{}
  62.  
  63. 		Self& operator++()
  64. 		{
  65. 			if (_node->_next)
  66. 			{
  67. 				_node = _node->_next;
  68. 			}
  69. 			else
  70. 			{
  71. 				KeyOfT kot;
  72. 				HashFunc hf;
  73. 				size_t hashi = hf(kot(_node->_data)) % _pht->_tables.size();
  74. 				++hashi;
  75. 				//找下一个不为空的桶
  76. 				for (; hashi < _pht->_tables.size(); ++hashi)
  77. 				{
  78. 					if (_pht->_tables[hashi])
  79. 					{
  80. 						_node = _pht->_tables[hashi];
  81. 						break;
  82. 					}
  83. 				}
  84.  
  85. 				// 没有找到不为空的桶，用nullptr去做end标识
  86. 				if (hashi == _pht->_tables.size())
  87. 				{
  88. 					_node = nullptr;
  89. 				}
  90. 			}
  91.  
  92. 			return *this;
  93. 		}
  94.  
  95. 		T& operator*()
  96. 		{
  97. 			return _node->_data;
  98. 		}
  99.  
  100. 		T* operator->()
  101. 		{
  102. 			return &_node->_data;
  103. 		}
  104.  
  105. 		bool operator!=(const Self& s) const
  106. 		{
  107. 			return _node != s._node;
  108. 		}
  109.  
  110. 		bool operator==(const Self& s) const
  111. 		{
  112. 			return _node == s._node;
  113. 		}
  114. 	};
  115.  
  116. 	// unordered_map ->HashTable<K, pair<K, V>, MapKeyOfT> _ht;
  117. 	// unordered_set ->HashTable<K, K, SetKeyOfT> _ht;
  118. 	template<class K, class T, class KeyOfT, class HashFunc>
  119. 	class HashTable
  120. 	{
  121. 		template<class K, class T, class KeyOfT, class HashFunc>
  122. 		friend class __HTIterator;
  123.  
  124. 		typedef HashNode<T> Node;
  125. 	public:
  126. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;
  127.  
  128. 		iterator begin()
  129. 		{
  130. 			for (size_t i = 0; i < _tables.size(); ++i)
  131. 			{
  132. 				Node* cur = _tables[i];
  133. 				if (cur)
  134. 				{
  135. 					return iterator(cur, this);
  136. 				}
  137. 			}
  138.  
  139. 			return end();
  140. 		}
  141.  
  142. 		iterator end()
  143. 		{
  144. 			return iterator(nullptr, this);
  145. 		}
  146.  
  147. 		~HashTable()
  148. 		{
  149. 			for (size_t i = 0; i < _tables.size(); ++i)
  150. 			{
  151. 				Node* cur = _tables[i];
  152. 				while (cur)
  153. 				{
  154. 					Node* next = cur->_next;
  155. 					delete cur;
  156. 					cur = next;
  157. 				}
  158.  
  159. 				_tables[i] = nullptr;
  160. 			}
  161. 		}
  162.  
  163. 		size_t GetNextPrime(size_t prime)
  164. 		{
  165. 			const int PRIMECOUNT = 28;
  166. 			static const size_t primeList[PRIMECOUNT] =
  167. 			{
  168. 				53ul, 97ul, 193ul, 389ul, 769ul,
  169. 				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
  170. 				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
  171. 				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
  172. 				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
  173. 				1610612741ul, 3221225473ul, 4294967291ul
  174. 			};
  175.  
  176. 			// 获取比prime大那一个素数
  177. 			size_t i = 0;
  178. 			for (; i < PRIMECOUNT; ++i)
  179. 			{
  180. 				if (primeList[i] > prime)
  181. 					return primeList[i];
  182. 			}
  183.  
  184. 			return primeList[i];
  185. 		}
  186.  
  187. 		pair<iterator, bool> Insert(const T& data)
  188. 		{
  189. 			HashFunc hf;
  190. 			KeyOfT kot;
  191.  
  192. 			iterator pos = Find(kot(data));
  193. 			if (pos != end())
  194. 			{
  195. 				return make_pair(pos, false);
  196. 			}
  197.  
  198. 			// 负载因子 == 1 扩容
  199. 			if (_tables.size() == _n)
  200. 			{
  201. 				//size_t newSize = _tables.size() == 0 ? 11 : _tables.size() * 2;
  202. 				size_t newSize = GetNextPrime(_tables.size());
  203. 				if (newSize != _tables.size())
  204. 				{
  205. 					vector<Node*> newTable;
  206. 					newTable.resize(newSize, nullptr);
  207. 					for (size_t i = 0; i < _tables.size(); ++i)
  208. 					{
  209. 						Node* cur = _tables[i];
  210. 						while (cur)
  211. 						{
  212. 							Node* next = cur->_next;
  213.  
  214. 							size_t hashi = hf(kot(cur->_data)) % newSize;
  215. 							cur->_next = newTable[hashi];
  216. 							newTable[hashi] = cur;
  217.  
  218. 							cur = next;
  219. 						}
  220.  
  221. 						_tables[i] = nullptr;
  222. 					}
  223.  
  224. 					newTable.swap(_tables);
  225. 				}
  226. 			}
  227.  
  228. 			size_t hashi = hf(kot(data));
  229. 			hashi %= _tables.size();
  230.  
  231. 			// 头插到对应的桶即可
  232. 			Node* newnode = new Node(data);
  233. 			newnode->_next = _tables[hashi];
  234. 			_tables[hashi] = newnode;
  235.  
  236. 			++_n;
  237.  
  238. 			return make_pair(iterator(newnode, this), false);;
  239. 		}
  240.  
  241. 		iterator Find(const K& key)
  242. 		{
  243. 			if (_tables.size() == 0)
  244. 			{
  245. 				return iterator(nullptr, this);
  246. 			}
  247.  
  248. 			KeyOfT kot;
  249. 			HashFunc hf;
  250. 			size_t hashi = hf(key);
  251. 			//size_t hashi = HashFunc()(key);
  252.  
  253. 			hashi %= _tables.size();
  254. 			Node* cur = _tables[hashi];
  255. 			while (cur)
  256. 			{
  257. 				if (kot(cur->_data) == key)
  258. 				{
  259. 					return iterator(cur, this);
  260. 				}
  261.  
  262. 				cur = cur->_next;
  263. 			}
  264.  
  265. 			return iterator(nullptr, this);
  266. 		}
  267.  
  268. 		bool Erase(const K& key)
  269. 		{
  270. 			if (_tables.size() == 0)
  271. 			{
  272. 				return false;
  273. 			}
  274.  
  275. 			HashFunc hf;
  276. 			KeyOfT kot;
  277. 			size_t hashi = hf(key);
  278. 			hashi %= _tables.size();
  279. 			Node* prev = nullptr;
  280. 			Node* cur = _tables[hashi];
  281. 			while (cur)
  282. 			{
  283. 				if (kot(cur->_data) == key)
  284. 				{
  285. 					if (prev == nullptr)
  286. 					{
  287. 						_tables[hashi] = cur->_next;
  288. 					}
  289. 					else
  290. 					{
  291. 						prev->_next = cur->_next;
  292. 					}
  293.  
  294. 					delete cur;
  295. 					
  296. 					return true;
  297. 				}
  298.  
  299. 				prev = cur;
  300. 				cur = cur->_next;
  301. 			}
  302.  
  303. 			return false;
  304. 		}
  305.  
  306. 	private:
  307. 		// 指针数组
  308. 		vector<Node*> _tables;
  309. 		size_t _n = 0;
  310. 	};
  311. }

Test.cpp

  1. #include<iostream>
  2. #include <set>
  3. #include <map>
  4. #include <unordered_set>
  5. #include <unordered_map>
  6. #include <time.h>
  7. using namespace std;
  8.  
  9. #include "HashTable.h"
  10. #include "UnorderedMap.h"
  11. #include "UnorderedSet.h"
  12.  
  13. void test_set()
  14. {
  15. 	unordered_set<int> s;
  16. 	//set<int> s;
  17. 	s.insert(2);
  18. 	s.insert(3);
  19. 	s.insert(1);
  20. 	s.insert(2);
  21. 	s.insert(5);
  22.  
  23. 	//unordered_set<int>::iterator it = s.begin();
  24. 	auto it = s.begin();
  25. 	while (it != s.end())
  26. 	{
  27. 		cout << *it << " ";
  28. 		++it;
  29. 	}
  30. 	cout << endl;
  31.  
  32. 	for (auto e : s)
  33. 	{
  34. 		cout << e << " ";
  35. 	}
  36. 	cout << endl;
  37. }
  38.  
  39. void test_op()
  40. {
  41. 	int n = 10000000;
  42. 	vector<int> v;
  43. 	v.reserve(n);
  44. 	srand(time(0));
  45. 	for (int i = 0; i < n; ++i)
  46. 	{
  47. 		//v.push_back(i);
  48. 		//v.push_back(rand()+i);  // 重复少
  49. 		v.push_back(rand());  // 重复多
  50. 	}
  51.  
  52. 	size_t begin1 = clock();
  53. 	set<int> s;
  54. 	for (auto e : v)
  55. 	{
  56. 		s.insert(e);
  57. 	}
  58. 	size_t end1 = clock();
  59.  
  60. 	size_t begin2 = clock();
  61. 	unordered_set<int> us;
  62. 	for (auto e : v)
  63. 	{
  64. 		us.insert(e);
  65. 	}
  66. 	size_t end2 = clock();
  67.  
  68. 	cout << s.size() << endl;
  69.  
  70. 	cout << "set insert:" << end1 - begin1 << endl;
  71. 	cout << "unordered_set insert:" << end2 - begin2 << endl;
  72.  
  73.  
  74. 	size_t begin3 = clock();
  75. 	for (auto e : v)
  76. 	{
  77. 		s.find(e);
  78. 	}
  79. 	size_t end3 = clock();
  80.  
  81. 	size_t begin4 = clock();
  82. 	for (auto e : v)
  83. 	{
  84. 		us.find(e);
  85. 	}
  86. 	size_t end4 = clock();
  87. 	cout << "set find:" << end3 - begin3 << endl;
  88. 	cout << "unordered_set find:" << end4 - begin4 << endl;
  89.  
  90. 	
  91. 	size_t begin5 = clock();
  92. 	for (auto e : v)
  93. 	{
  94. 		s.erase(e);
  95. 	}
  96. 	size_t end5 = clock();
  97.  
  98. 	size_t begin6 = clock();
  99. 	for (auto e : v)
  100. 	{
  101. 		us.erase(e);
  102. 	}
  103. 	size_t end6 = clock();
  104. 	cout << "set erase:" << end5 - begin5 << endl;
  105. 	cout << "unordered_set erase:" << end6 - begin6 << endl;
  106. }
  107.  
  108. void test_map()
  109. {
  110. 	unordered_map<string, string> dict;
  111. 	dict.insert(make_pair("sort", "排序"));
  112. 	dict.insert(make_pair("left", "左边"));
  113. 	dict.insert(make_pair("left", "剩余"));
  114. 	dict["string"];
  115. 	dict["left"] = "剩余";
  116. 	dict["string"] = "字符串";
  117. }
  118.  
  119. int main()
  120. {
  121. 	bit::test_set();
  122. 	//test_op();
  123. 	bit::test_map();
  124. 	//Bucket::TestHT3();
  125. 	//TestHT2();
  126.  
  127. 	return 0;
  128. }

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号