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

哈希表及其实现

作者：神奇cpp | 2024-08-10 19:00:19

赞

踩

哈希表及其实现

哈希概念

        顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(log2N)，搜索的效率取决于搜索过程中元素的比较次数。

        哈希方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

        构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

        例如：数据集合{1，7，6，4，5，9}

        哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

        用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度非常快。

哈希冲突

对于两个数据元素的关键字key1和 key2，有key1！=key2，但有：Hash(key1) == Hash(key2)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突。

常见的哈希函数

1.直接定值法

        取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

        优点：不会发生Hash冲突，简单。

        缺点：可能会分布不均匀，使Hash表的一部分未被利用，导致浪费空间。

        例如：key={1,2,4,6,10000}，哈希函数为Hash（key）= key。

        这样需要开一个大小为10000的数组但是仅仅存储这几个值，中间部分造成了极大的浪费。

2.除留余数法

        设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数， 按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。

        优点：可以自行规定表的大小，使插入数据可以均匀占据空间。

         缺点：造成哈希冲突。例如：15,22mod7都等于1，都占据1的位置。
        
        本文的Hash表模拟实现选用的Hash函数是 除留余数法。

如何解决Hash冲突？

闭散列的开放定值法

本质上是当前位置冲突，后面找一个合适的位置继续储存。

线性探测法

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

例子：{1,4,24,34,7,44,17}（注意顺序！）

需要枚举类型表示一个位置的状态

  1. enum State
  2. {
  3.    
  4. 	EMPTY,//空值，一开始一张表里都是空值
  5. 	EXIST,//有值，插入值时相应的位置变成有值
  6.  
  7. 	DELETE//删除，在删除后，防止再次查找时，走到该位置停止
  8. };

注意：本质上需要有值和无值即可，但是这里有一个DELETE，它是在查找时起作用

哈希表结构

代码如下： 

  1. enum State
  2. {
  3. 	EMPTY,
  4. 	EXIST,
  5. 	DELETE
  6. };
  7. template<class K,class V>
  8. struct HashData
  9. {
  10. 	par<K, V> _data;
  11. 	State _state = EMPTY;//开始都标记为空
  12. };
  13. template<class K,class V>
  14. class HashTable
  15. {
  16. public:
  17. 	//插入
  18.     ……
  19. 	//删除
  20.     ……
  21. 	//寻找
  22. private:
  23. 	vector<HashData<K, V>> _table;
  24. 	size_t _n = 0;实际插入数据的个数
  25. };
 构造函数
  1. 		HashTable(size_t size = 10)//默认开10个类型的大小
  2. 		{
  3. 			_table.resize(size);
  4. 		}
插入函数

功能：给定一个值，通过哈希函数找到一个适合这个值位置的地址，插入。

        这种插入方法世间复杂度是O（1）。

        i=key%表的大小，如果i位置已经有值了，就线性往后找到空位置，放进去。

  1. 	//插入
  2. 	bool Insert(const pair<K，V>& kv)
  3. 	{
  4. 		size_t hashi = kv.first % _table.size();//根据值找位置
  5.  
  6. 		while (_table[hashi]._state != EMPTY)//找到位置后判断是否发生哈希冲突
  7. 		{
  8. 			hashi++;//该位置有值（发生哈希冲突），向后移动。
  9. 			hashi %= _table.size();//防止越界（线性探测规则）
  10. 		}
  11.  
  12.         //解决哈希冲突后，在该位置插入值
  13. 		_table[hashi]._data = kv;
  14. 		_table[hashi]._state = EXIST;
  15. 		++_n;
  16.  
  17. 		return true;
  18. 	}
扩容问题

        空间是有限的，一直插入，总会有空间不够的情况。

负载因子------衡量哈希表的拥挤程度，空间的剩余情况

        负载因子越大，哈希表越拥挤，空间剩余越少，可能造成的哈希冲突越多，效率越低。

计算公式：负载因子=已有数据/表的大小

        一般控制在0.7左右，当负载因子大于等于0.7时扩容。

方法：再建一个两倍大小的哈希表，将原来哈希表的数据重新插入到这个新的哈希表，最后交换一下哈希表的地址。

  1. //扩容问题
  2. //当负载因子到达0.7时，此时扩容
  3. if (10 * _n / _table.size() >= 7)//此处同时乘以10，防止小数进行比较
  4. {
  5. 	HashTable<K, V> newHT(2 * _table());//新开一个空间是两倍的哈希表
  6. 	for (auto& e : _table)
  7. 	{
  8. 		if (e._state == EXIST)
  9. 		{
  10. 			newHT.Insert(e._data);//不会出现无穷递归，因为插入的新表里时负载因子小，不会走扩容,直接走线性探测插入
  11. 		}
  12. 	}
  13. 	_table.swap(newHT._table);//使用的是vector容器的swap
  14. }

完整的插入代码：

  1. 		bool Insert(const pair<K,V>& kv)
  2. 		{
  3. 			//扩容问题
  4. 			//当负载因子到达0.7时，此时扩容
  5. 			if (10 * _n / _table.size() >= 7)//此处同时乘以10，防止小数进行比较
  6. 			{
  7. 				HashTable<K, V> newHT(2 * _table());//新开一个空间是两倍的哈希表
  8. 				for (auto& e : _table)
  9. 				{
  10. 					if (e._state == EXIST)
  11. 					{
  12. 						newHT.Insert(e._data);//不会出现无穷递归，因为插入的新表里时负载因子小，不会走扩容,直接走线性探测插入
  13. 					}
  14. 				}
  15. 				_table.swap(newHT._table);//使用的是vector容器的swap
  16. 			}
  17.  
  18. 			//线性探测
  19. 			size_t hashi = kv.first % _table.size();
  20. 			while (_table[hashi]._state != EMPTY)
  21. 			{
  22. 				hashi++;
  23. 				hashi %= _table.size();
  24. 			}
  25. 			_table[hashi]._data = kv;
  26. 			_table[hashi]._state = EXIST;
  27. 			++_n;
  28. 			return true;
  29. 		}
查找函数

功能：给定key值查找该节点的地址。

        查找的时间复杂度是O（1），因为直接根据哈希函数定位到地址，如果有哈希冲突，进行常阶的移位比较。（几乎不需要比较！）

        i=key%表的大小，如果i不是要查找的key就线性往后查找，直到找到或者遇到空（如果是DELETE，还要继续往后查找）。

        如果找到了表的结尾，就要回到头查找。

  1. 	HashData<K, V>* Find(const K& key)
  2. 		{
  3. 			size_t hashi = key % _table.size();
  4.  
  5.             //开始寻找
  6. 			while (_table.[hashi]._state != EMPTY)
  7. 			{
  8. 				if (_table.[hashi]._state == EXIST
  9. 					&& key == _table[hashi]._data.first)
  10. 				{
  11. 					return &_table[hashi];
  12. 				}
  13.  
  14.  
  15. 				//探测规则（这里是线性探测）
  16. 				hashi++;//如果没找到，说明冲突了，向后线性探测。
  17. 				hashi %= _tables.size();//hashi向后++时，可能会越界，应该按照取余的方式控制在这个数组长度的范围内
  18. 			}
  19. 			return nullptr;
  20. 		}
删除函数

功能：给定key值，根据key值找到某节点，删除该节点

        很简单，只要用Find找到要删除的即可。

  1. 		//删除
  2. 		bool Erase(const K& key)
  3. 		{
  4. 			HashData<K, V>* ret = Find(key);//通过key找到节点的位置
  5.  
  6. 			if (ret)//若节点存在
  7. 			{
  8. 				--_n;
  9. 				ret->_state = DELETE;//删除
  10. 				return true;
  11. 			}
  12. 			else
  13. 			{
  14. 				return false;
  15. 			}
  16. 		}
总代码
  1.  
  2. 	enum State
  3. 	{
  4. 		EMPTY,
  5. 		EXIST,
  6. 		DELETE
  7. 	};
  8. 	template<class K, class V>
  9. 	struct HashData
  10. 	{
  11. 		pair<K, V> _data;
  12. 		State _state = EMPTY;//开始都标记为空
  13. 	};
  14.  
  15. 	template<class K, class V>
  16. 	class HashTable
  17. 	{
  18. 	public:
  19. 		HashTable(size_t size = 10)
  20. 		{
  21. 			_table.resize(size);
  22. 		}
  23. 		//插入
  24. 		bool Insert(const pair<K,V>& kv)
  25. 		{
  26. 			//扩容问题
  27. 			//当负载因子到达0.7时，此时扩容
  28. 			if (10 * _n / _table.size() >= 7)//此处同时乘以10，防止小数进行比较
  29. 			{
  30. 				HashTable<K, V> newHT(2 * _table.size());//新开一个空间是两倍的哈希表
  31. 				for (auto& e : _table)
  32. 				{
  33. 					if (e._state == EXIST)
  34. 					{
  35. 						newHT.Insert(e._data);//不会出现无穷递归，因为插入的新表里时负载因子小，不会走扩容
  36. 					}
  37. 				}
  38. 				_table.swap(newHT._table);
  39. 			}
  40.  
  41. 			//线性探测
  42. 			size_t hashi = kv.first % _table.size();
  43. 			while (_table[hashi]._state != EMPTY)
  44. 			{
  45. 				hashi++;
  46. 				hashi %= _table.size();
  47. 			}
  48. 			_table[hashi]._data = kv;
  49. 			_table[hashi]._state = EXIST;
  50. 			++_n;
  51. 			return true;
  52. 		}
  53. 		//寻找
  54. 		HashData<K, V>* Find(const K& key)
  55. 		{
  56. 			size_t hashi = key % _table.size();
  57. 			while (_table[hashi]._state != EMPTY)
  58. 			{
  59. 				if (_table[hashi]._state == EXIST
  60. 					&& key == _table[hashi]._data.first)
  61. 				{
  62. 					return &_table[hashi];
  63. 				}
  64.  
  65. 				//探测规则（这里是线性探测）
  66. 				hashi++;//如果没找到，说明冲突了，向后线性探测。
  67. 				hashi %= _table.size();//hashi向后++时，可能会越界，应该按照取余的方式控制在这个数组长度的范围内
  68. 			}
  69. 			return nullptr;
  70. 		}
  71. 		//删除
  72. 		bool Erase(const K& key)
  73. 		{
  74. 			HashData<K, V>* ret = Find(key);
  75. 			if (ret->_state == EXIST)
  76. 			{
  77. 				--_n;
  78. 				ret->_state = DELETE;
  79. 				return true;
  80. 			}
  81. 			else
  82. 			{
  83. 				return false;
  84. 			}
  85. 		}
  86. 	private:
  87. 		vector<HashData<K, V>> _table;
  88. 		size_t _n = 0;
  89. 	};

开散列法

        开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

        本质：当使用除留余数法在同一个位置存储多个值时（发生哈希冲突），则在同一个位置以链表的形式储存多个值。 

例子：{1,4,24,34,7,44,17}（不是很注重顺序）

哈希表结构 

代码如下： 

  1. template<class K,class V>
  2. struct HashNode
  3. {
  4. 	HashNode<K, V>* next;
  5. 	pair<K, V> _kv;
  6. };
  7.  
  8. template<class K,class V>
  9. class HashTable
  10. {
  11. 	typedef HashNode<K,V> Node;
  12. public:
  13. 	//插入
  14.  
  15. 	//寻找
  16.  
  17. 	//删除
  18. private:
  19. 	vector<Node*> _table;
  20. 	size_t _n = 0;
  21. };

构造函数

  1. 		HashTable(size_t size = 10)
  2. 		{
  3. 			_table.resize(size);
  4. 		}

析构函数

        为什么需要写析构函数？对于vector有它自己的析构函数，而我们对每个vector储存的指针指向链表没有析构，会导致内存泄漏。

        下面是对HashNode的节点组成的链表进行析构。

  1. 		~HashTable()
  2. 		{
  3. 			for (size_t i = 0; i < _table.size(); i++)
  4. 			{
  5. 				Node* cur = _table[i];
  6.  
  7. 				while (cur)//将该节点的链表全部删除
  8. 				{
  9. 					Node* next = cur->_next;
  10. 					delete cur;
  11. 					cur = next;
  12. 				}
  13. 				_table[i] = nullptr;
  14. 			}
  15. 		}

插入

功能：给定节点的key值，插入哈希表

原理：先根据key值计算出要插入节点的位置，再头插入链表。

  1. 		//插入
  2. 		bool Insert(const pair<K, V>& kv)
  3. 		{
  4. 			size_t hashi = kv.first % _table.size();//计算位置
  5. 			Node* newnode = new Node(kv);
  6.  
  7. 			//头插
  8. 			newnode->_next = _table[hashi];//将新节点的_next指向最开始的节点，而vector保存的就是开始节点的指针
  9. 			_table[hashi] = newnode;//vector存储的指针换成刚插入的节点
  10. 			++_n;
  11.  
  12. 			return true;
  13. 		}
扩容问题

当实际节点数等于表的大小时，扩容。

原理：开个两倍的新表，将原来节点重新定址后插入新表中，交换两个表。

注：不要重新开节点，直接将老表的节点重新定值插入新表中，防止创建新节点造成过多的开销。

  1. 		//插入
  2. 		bool Insert(const pair<K, V>& kv)
  3. 		{
  4. //--------------------------------------------------------------------------------------
  5. 			//扩容
  6. 			if (_n == _table.size())//当实际位置的节点个数等于表的大小时进行扩容
  7. 			{
  8.                 //1.开一个大小为旧表两倍的新表
  9. 				vector<Node*> newTable(_table.size() * 2, nullptr);
  10.                 //2.遍历旧表每一个vector的每一个链表，将每个节点插入到新表
  11. 				for (size_t i = 0; i < _table.size(); i++)//遍历每一个表中vector单元
  12. 				{
  13. 					//取出旧表中的节点，重新定址后挂到新表桶中
  14. 					Node* cur = _table[i];
  15. 					while (cur)
  16. 					{
  17. 						Node* next = cur->_next;//保存第一个节点的下一个节点
  18.  
  19. 						//头插到新表
  20. 						size_t hashi = cur->_kv.first % newTable.size();//重新定址
  21. 						cur->_next = newTable[hashi];//这个vector单元保存的是第一个节点的指针
  22. 						newTable[hashi] = cur;//将vector保存的节点替换成新头插的节点
  23.  
  24. 						cur = next;//再去刚才没有移动的下一个节点
  25. 					}
  26. 					_table[i] = nullptr;//原表vector处置空
  27. 				}
  28.                 //3.交换两表
  29. 				_table.swap(newTable);
  30. 			}
  31. //--------------------------------------------------------------------------------------
  32. 			size_t hashi = kv.first % _table.size();//计算位置
  33. 			Node* newnode = new Node(kv);
  34.  
  35. 			//头插
  36. 			newnode->_next = _table[hashi];//将新节点的_next指向最开始的节点，而vector保存的就是开始节点的指针
  37. 			_table[hashi] = newnode;//vector存储的指针换成刚插入的节点
  38. 			++_n;
  39.  
  40. 			return true;
  41. 		}

查找

功能：给定一个（key）值，找到这个储存这个值的地址。

原理：根据key值计算索引位置，去该索引位置处遍历所挂的链表，直到找到key值所在的节点

  1. 		//寻找
  2. 		Node* Find(const K& key)
  3. 		{
  4. 			size_t hashi = key % _table.size();//计算这个值的位置
  5. 			Node* cur = _table[hashi];//找到这个位置
  6.  
  7. 			//遍历这个位置挂的节点
  8. 			while (cur)
  9. 			{
  10. 				if (cur->_kv.first == key)
  11. 				{
  12. 					return cur;
  13. 				}
  14. 				cur = cur->_next;
  15. 			}
  16.  
  17. 			return nullptr;
  18. 		}

删除

功能：给定一个（key）值，删除储存该值的节点

原理：根据key值计算出对应vector的位置，然后遍历比较vector下挂的链表，并删除节点

  1. 		//删除
  2. 		bool Erase(const K& key)
  3. 		{
  4. 			size_t hashi = key % _table.szie();//计算要删节点的位置
  5. 			Node* prev = nullptr;
  6. 			Node* cur = _table[hashi];
  7. 			while (cur)
  8. 			{
  9. 				if (cur->_kv.first == key)//找到了该值所对应的节点
  10. 				{
  11. 					if (prev)//删除中间节点
  12. 					{
  13. 						prev->_next = cur->_next;//跳过cur节点，将prev节点与cur的下一个节点连接
  14. 					}
  15. 					else//删除第一个节点
  16. 					{
  17. 						_table[hashi] = cur->_next;//将vector中储存第二个节点
  18. 					}
  19.  
  20. 					delete cur;
  21. 					--_n;
  22. 					return true;
  23. 				}
  24. 				//向下搜索
  25. 				prev = cur;
  26. 				cur = cur->_next;
  27. 			}
  28.  
  29. 			return false;
  30. 		}

总代码

  1. namespace syb1
  2. {
  3.  
  4. 	template<class K,class V>
  5. 	struct HashNode
  6. 	{
  7. 		HashNode<K, V>* _next;
  8. 		pair<K, V> _kv;
  9.  
  10. 		HashNode(const pair<K,V>& kv)
  11. 			:_next(nullptr)
  12. 			,_kv(kv)
  13. 		{}
  14. 	};
  15. 	template<class K,class V>
  16. 	class HashTable
  17. 	{
  18. 		typedef HashNode<K,V> Node;
  19. 	public:
  20. 		HashTable(size_t size = 10)
  21. 		{
  22. 			_table.resize(size);
  23. 		}
  24. 		~HashTable()
  25. 		{
  26. 			for (size_t i = 0; i < _table.size(); i++)
  27. 			{
  28. 				Node* cur = _table[i];
  29.  
  30. 				while (cur)//将该节点的链表全部删除
  31. 				{
  32. 					Node* next = cur->_next;
  33. 					delete cur;
  34. 					cur = next;
  35. 				}
  36. 				_table[i] = nullptr;
  37. 			}
  38. 		}
  39. 		//插入
  40. 		bool Insert(const pair<K, V>& kv)
  41. 		{
  42. 			//扩容
  43. 			if (_n == _table.size())//当实际位置的节点个数等于表的大小时进行扩容
  44. 			{
  45. 				vector<Node*> newTable(_table.size() * 2, nullptr);
  46. 				for (size_t i = 0; i < _table.size(); i++)//遍历每一个表中vector单元
  47. 				{
  48. 					//取出旧表中的节点，重新定址后挂到新表桶中
  49. 					Node* cur = _table[i];
  50. 					while (cur)
  51. 					{
  52. 						Node* next = cur->_next;//保存第一个节点的下一个节点
  53.  
  54. 						//头插到新表
  55. 						size_t hashi = cur->_kv.first % newTable.size();//重新定址
  56. 						cur->_next = newTable[hashi];//这个vector单元保存的是第一个节点的指针
  57. 						newTable[hashi] = cur;//将vector保存的节点替换成新头插的节点
  58.  
  59. 						cur = next;//再去刚才没有移动的下一个节点
  60. 					}
  61. 					_table[i] = nullptr;//原表vector处置空
  62. 				}
  63.  
  64. 				_table.swap(newTable);
  65. 			}
  66.  
  67. 			size_t hashi = kv.first % _table.size();//计算位置
  68. 			Node* newnode = new Node(kv);
  69.  
  70. 			//头插
  71. 			newnode->_next = _table[hashi];//将新节点的_next指向最开始的节点，而vector保存的就是开始节点的指针
  72. 			_table[hashi] = newnode;//vector存储的指针换成刚插入的节点
  73. 			++_n;
  74.  
  75. 			return true;
  76. 		}
  77. 		//寻找
  78. 		Node* Find(const K& key)
  79. 		{
  80. 			size_t hashi = key % _table.size();//计算这个值的位置
  81. 			Node* cur = _table[hashi];//找到这个位置
  82.  
  83. 			//遍历这个位置挂的节点
  84. 			while (cur)
  85. 			{
  86. 				if (cur->_kv.first == key)
  87. 				{
  88. 					return cur;
  89. 				}
  90. 				cur = cur->_next;
  91. 			}
  92.  
  93. 			return nullptr;
  94. 		}
  95. 		//删除
  96. 		bool Erase(const K& key)
  97. 		{
  98. 			size_t hashi = key % _table.szie();//计算要删节点的位置
  99. 			Node* prev = nullptr;
  100. 			Node* cur = _table[hashi];
  101. 			while (cur)
  102. 			{
  103. 				if (cur->_kv.first == key)
  104. 				{
  105. 					if (prev)//删除中间节点
  106. 					{
  107. 						prev->_next = cur->_next;//跳过cur节点，将prev节点与cur的下一个节点连接
  108. 					}
  109. 					else//删除第一个节点
  110. 					{
  111. 						_table[hashi] = cur->_next;//将vector中储存第二个节点
  112. 					}
  113.  
  114. 					delete cur;
  115. 					--_n;
  116. 					return true;
  117. 				}
  118. 				//向下搜索
  119. 				prev = cur;
  120. 				cur = cur->_next;
  121. 			}
  122.  
  123. 			return false;
  124. 		}
  125. 	private:
  126. 		vector<Node*> _table;
  127. 		size_t _n = 0;
  128. 	};
  129. }

 

关于不同类型的key值

        对于key值是int型参数时，直接进行取模运算，即可得到映射的位置。但是对于字符串类型（string）的key值,或者是结构体类型的key值，如何确定其映射的位置呢？我们可以利用仿函数将其他类型的key值转化。

插入浮点类型的值

原理：非常简单，直接强转

  1. template<class K>
  2. struct HashFunc
  3. {
  4. 	size_t operator()(const K& key)
  5. 	{
  6. 		return (size_t)key;
  7. 	}
  8. };

插入字符串类型的值

原理：读取string每一个字符，将其的ASCII值每次乘一个值后加到Hash变量中，最后返回这个值Hash，这样就对每一个不同字符串都得到一个不同的key值。

关于溢出问题：如果字符串太长，通过这样方式转换成整形后溢出怎么办？不用管，自动截断，得到一个key值。

关于每次乘的值：选31 131 1313 13131 131313这些值都可以

  1. struct HashFuncString
  2. {
  3. 	size_t operator()(const string& s)
  4. 	{
  5. 		size_t hash = 0;
  6. 		for (auto e : s)
  7. 		{
  8. 			hash += e;
  9. 			hash *= 131;//可以防止顺序不同造成的位置相同
  10. 		}
  11.  
  12. 		return hash;
  13. 	}
  14. };

插入结构体类型的值

 原理：同上，将每个元素转换成整形后乘上131加在一起。

  1. struct HashFuncDate
  2. {
  3. 	size_t operator()(const Date& d)
  4. 	{
  5. 		size_t hash = 0;
  6. 		hash += d._year;
  7. 		hash *= 131;
  8. 		
  9. 		hash += d._month;
  10. 		hash *= 131;
  11.  
  12. 		hash += d._day;
  13. 		hash *= 131;
  14. 	}
  15. };

总结：以后对于各种各样的key值，我们可以把每个元素划分出来（结构体类型的将每个元素划分出来，string类型的划分成一个个char型）乘上一个特定的数加在一起，从而得到一个int型的key值。

使用：当key值为不同的类型时，使用仿函数作用在key值上，使key值变成int型数据。

以查找函数为例：

  1. 		HashData<K, V>* Find(const K& key)//<------传string类型数据
  2. 		{
  3. //-----------------------------------------------------------------------------------------
  4. 			HashFuncString hs;//类构造一个对象
  5. 			size_t hashi = hs(key) % _table.size();用仿函数将key转换成int类型的数据
  6. //-----------------------------------------------------------------------------------------
  7. 			while (_table[hashi]._state != EMPTY)
  8. 			{
  9. 				if (_table[hashi]._state == EXIST
  10. 					&& key == _table[hashi]._data.first)
  11. 				{
  12. 					return &_table[hashi];
  13. 				}
  14. 				hashi++;
  15. 				hashi %= _table.size();
  16. 			}
  17. 			return nullptr;
  18. 		}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/959953
推荐阅读
相关标签

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

  

闽ICP备14008679号