• C++：哈希，unordered_map和unordered_set

    目录

    一.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
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. using namespace std;
    8.  
    9. void test_set()
    10. {
    11. 	unordered_set<int> s;
    12. 	//set 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::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 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
    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 _kv;
    16. 	State _state;
    17. };
    18.  
    19. template<class K, class V>
    20. class HashTable
    21. {
    22. public:
    23. 	bool Insert(const pair& 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 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 _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
    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 a; 时不用传仿函数是因为template> 仿函数给了缺省参数，不传默认是基础的类struct DefaultHash，直接定义 unorodered_map b; 时也可以不用传仿函数是因为类模板特化，key是string就会使用特化版本的struct DefaultHash

    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
    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>
    28. 	class HashTable
    29. 	{
    30. 		typedef HashData Data;
    31. 	public:
    32.     ……

    3.开散列（哈希桶）

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

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

    1. #pragma once
    2. #include
    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 _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
    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>
    77. 	class HashTable
    78. 	{
    79. 		typedef HashData Data;
    80. 	public:
    81. 		bool Insert(const pair& 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 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 _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> 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 countHT;
    244. 		HashTableint> 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 countHT;
    261. 		//HashTable countHT;
    262.  
    263.  
    264. 		HashTableint> copy(countHT);
    265. 	}
    266. }
    267.  
    268. namespace Bucket
    269. {
    270. 	template<class K, class V>
    271. 	struct HashNode
    272. 	{
    273. 		pair _kv;
    274. 		HashNode* _next;
    275.  
    276. 		HashNode(const pair& kv)
    277. 			:_kv(kv)
    278. 			, _next(nullptr)
    279. 		{}
    280. 	};
    281.  
    282. 	template<class K, class V>
    283. 	class HashTable
    284. 	{
    285. 		typedef HashNode Node;
    286. 	public:
    287. 		bool Insert(const pair& 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 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 _tables;
    354. 		size_t _n = 0;
    355. 	};
    356.  
    357. 	void TestHT1()
    358. 	{
    359. 		int a[] = { 20, 5, 8, 99999, 10, 30, 50 };
    360. 		//HashTable> 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 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
    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
    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 _kv;
    37. 		HashNode* _next;
    38.  
    39. 		HashNode(const pair& kv)
    40. 			:_kv(kv)
    41. 			, _next(nullptr)
    42. 		{}
    43. 	};
    44.  
    45. 	template<class K, class V, class HashFunc = DefaultHash>
    46. 	class HashTable
    47. 	{
    48. 		typedef HashNode 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& 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 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 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 _tables;
    225. 		size_t _n = 0;
    226. 	};
    227.  
    228. 	void TestHT1()
    229. 	{
    230. 		int a[] = { 20, 5, 8, 99999, 10, 30, 50 };
    231. 		//HashTable> 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 copy(ht);
    270. 	}
    271.  
    272. 	void TestHT3()
    273. 	{
    274. 		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    275.  
    276. 		//HashTable countHT;
    277. 		HashTableint> 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 第二个模板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 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>
    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::iterator iterator;
    20.  
    21. 		iterator begin()
    22. 		{
    23. 			return _ht.begin();
    24. 		}
    25.  
    26. 		iterator end()
    27. 		{
    28. 			return _ht.end();
    29. 		}
    30.  
    31. 		pairbool> 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 _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 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::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 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>
    8. 	class unordered_map
    9. 	{
    10. 		struct MapKeyOfT
    11. 		{
    12. 			const K& operator()(const pair& kv)
    13. 			{
    14. 				return kv.first;
    15. 			}
    16. 		};
    17. 	public:
    18. 		typedef typename Bucket::HashTable, 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. 		pairbool> insert(const pair& 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. 			pairbool> ret = insert(make_pair(key, V()));
    48. 			return ret.first->second;
    49. 		}
    50.  
    51. 	private:
    52. 		Bucket::HashTable, MapKeyOfT, HashFunc> _ht;
    53. 	};
    54.  
    55. 	void test_map()
    56. 	{
    57. 		unordered_map 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::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
    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
    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* _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 Node;
    51. 		typedef __HTIterator Self;
    52. 	public:
    53. 		Node* _node;
    54. 		HashTable* _pht;
    55.  
    56. 		__HTIterator() {}    //默认构造函数和非默认构造函数重载
    57.  
    58. 		__HTIterator(Node* node, HashTable* 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, MapKeyOfT> _ht;
    117. 	// unordered_set ->HashTable _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 Node;
    125. 	public:
    126. 		typedef __HTIterator 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. 		pairbool> 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 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 _tables;
    309. 		size_t _n = 0;
    310. 	};
    311. }

    Test.cpp

    1. #include
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    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 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::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 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. }

  • 相关阅读:
    mdio bcm5482访问
    从入门开始手把手搭建千万级Java算法测试-计数排序与快速排序的比较(常规快排)比较
    visio导出SVG矢量图在wps中显示问题
    AMD有史以来最大的一笔交易，350亿美元收购赛灵思成功
    python高阶爬虫---视频类内容爬取（以BiliBili和城市影院为例说明）
    多语言的字符串处理记录
    SpringCloud Sleuth 分布式请求链路跟踪
    SQL二次注入详解
    create® 3入门教程-反应Reflexes
    索引数据结构选择
  • 原文地址：https://blog.csdn.net/zhang_si_hang/article/details/126739994