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

开散列法实现哈希桶_哈希散列值桶数

作者：正经夜光杯 | 2024-08-10 19:06:46

赞

踩

哈希散列值桶数

上节我们介绍了闭散列法实现哈希表的操作，今天我们来看开散列法实现哈希桶的操作。

开散列法（链地址法(开链法)）

      开散列法首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点组成 一个向量，因此，向量的元素个数与可能的桶数一致。

设元素的关键码为37,25,14,36,49,68,57,11,散列表为HT[12]，表的大小为12，散列函数为Hash(x) = x % 11   Hash(37)=4          Hash(25)=3      Hash(14)=3      Hash(36)=3

   Hash(49)=5      Hash(68)=2      Hash(57)=2      Hash(11)=0

 

通常，每个桶中的同义词子表都很短，设有n个关键码通过某一个散列函数，存放到散列表中的m个桶 中，那么每一个桶中的同义词子表的平均长度为n/m。这样以搜索平均长度为n/m的同义词子表代替了 搜索长度为n的顺序表，搜索效率快的多。

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上，由于开地址法必须保持 大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7 而表项所占空间又比指针大 的多，所以使用链地址法反而比开地址法节省存储空间。

在此次操作中，我们对关键元素key 和 下标value 值用键值对（pair<K,V>）进行封装，并对程序加入了迭代器，增加了难度。

但是原理不变。

（1）仿函数

  1. class KeyToIntDef
  2. {
  3. public:
  4. 	size_t operator()(const size_t& key)
  5. 	{
  6. 		return key;
  7. 	}
  8. };
  9. class stringToInt
  10. {
  11. public:
  12. 	size_t operator()(const string& key)
  13. 	{
  14. 		return BKDRHash(key.c_str());
  15. 	}
  16. private:
  17. 	static size_t BKDRHash(const char* str)
  18. 	{
  19. 		unsigned int seed = 131;
  20. 		unsigned int hash = 0;
  21. 		while (*str)
  22. 		{
  23. 			hash = hash*seed + (*str++);
  24.  
  25. 		}
  26. 		return (hash & 0x7FFFFFFF);
  27. 	}
  28. };

（2）素数表增容

  1. const int _PriSize = 28;
  2. static size_t GetNextPrime(const size_t& value)
  3. {
  4. 	
  5. 		static const unsigned long _PrimeList[_PriSize] =
  6. 		{
  7.  
  8. 			53ul, 97ul, 193ul, 389ul, 769ul,
  9.  
  10. 			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
  11.  
  12. 			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
  13.  
  14. 			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
  15.  
  16. 			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
  17.  
  18. 			1610612741ul, 3221225473ul, 4294967291ul
  19. 		};
  20. 		for (int i = 0; i < _PriSize; i++)
  21. 		{
  22. 			if (_PrimeList[i]>value)
  23. 				return _PrimeList[i];
  24. 		}
  25. 		return _PrimeList[_PriSize - 1];
  26. }
  27.

（3）哈希桶的结点元素

  1. template<class K, class V>
  2. struct HashBucketNode
  3. {
  4. 	HashBucketNode(const pair<K, V>& key)
  5. 	:_key(key)
  6. 	, _PNext(NULL)
  7. 	{}
  8.  
  9. 	pair<K, V> _key;
  10. 	HashBucketNode<K, V>* _PNext;
  11. };

（4）迭代器对指针的封装

包括构造函数，拷贝构造函数，前置++，后置++，->的重载，*的重载，判断是否相等或不相等等操作；

  1. //迭代器
  2. template<class K,class V,class KToInt>
  3. class HashBucketIterator
  4. {
  5. 	typedef HashBucketNode<K, V> Node;
  6. 	typedef Node* PNode;
  7. 	typedef HashBucketIterator<K, V, KToInt> IteratorSelf;
  8. public:
  9. 	PNode _Pcur; //迭代器成员变量
  10. 	HashBucket<K, V, KToInt>* _hb; //指向哈希表的指针
  11. public: 
  12.  
  13. 	HashBucketIterator()
  14. 		:_Pcur(NULL)
  15. 		,_hb(NULL)
  16. 	{}
  17. 	HashBucketIterator(const PNode pcur, HashBucket<K, V, KToInt>*hb)
  18. 		:_Pcur(pcur)
  19. 		, _hb(hb)
  20. 	{}
  21. 	HashBucketIterator(const IteratorSelf& s)
  22. 		:_Pcur(s._Pcur)
  23. 		, _hb(s._hb)
  24. 	{}
  25.  
  26. 	IteratorSelf& operator++()
  27. 	{
  28. 		Next();
  29. 		return *this;
  30. 	}
  31. 	IteratorSelf operator++(int)
  32. 	{
  33. 		IteratorSelf temp(*this);
  34. 		Next();
  35. 		return temp;
  36. 	}
  37. 	pair<K, V>& operator*()
  38. 	{
  39. 		return _Pcur->_key;
  40. 	}
  41. 	pair<K, V>* operator->()
  42. 	{
  43. 		return &(operator*());
  44. 	}
  45. 	bool operator==(const IteratorSelf& s)
  46. 	{
  47. 		return _Pcur == s._Pcur;
  48. 	}
  49. 	bool operator != (const IteratorSelf& s)
  50. 	{
  51. 		return !(operator==(s));
  52. 	}
  53.  
  54. private:
  55. 	void Next()
  56. 	{
  57. 		if (_Pcur->_PNext)
  58. 			_Pcur = _Pcur->_PNext;
  59. 		else
  60. 		{
  61. 			//找下一个哈希桶
  62. 			size_t bucketNo = _hb->HashFunc(_Pcur->_key.first) + 1;
  63. 			for (; bucketNo < _hb->BucketCount(); bucketNo++)
  64. 			{
  65. 				if (_hb->_table[bucketNo])
  66. 				{
  67. 					_Pcur = _hb->_table[bucketNo];
  68. 					return;
  69. 				}
  70. 					
  71.             }
  72. 			_Pcur = NULL;
  73. 		}
  74. 		return;
  75. 	}
  76.  
  77.  
  78. };

（5）哈希桶的实现

  1. template<class K,class V,class KToInt>
  2. class HashBucket
  3. {
  4. 	typedef HashBucketNode<K, V> Node;
  5. 	typedef Node* PNode;
  6. 	friend HashBucketIterator<K, V, KToInt>;
  7. public:
  8.  typedef HashBucketIterator<K, V, KToInt> Iterator;
  9. public:
  10. 	HashBucket( size_t capacity=10)
  11. 		:_size(0)
  12. 	{
  13.      	capacity = GetNextPrime(capacity);
  14. 		_table.resize(capacity);
  15. 	}
  16. 	Iterator Begin()
  17. 	{
  18. 		for (size_t bucketNo = 0; bucketNo < _table.capacity(); ++bucketNo)
  19. 		{
  20. 			if (_table[bucketNo])
  21. 				return Iterator(_table[bucketNo], this);
  22. 		}
  23. 		return Iterator(NULL, this);
  24. 	}
  25. 	Iterator End()
  26. 	{
  27. 		return Iterator(NULL, this);
  28. 	}
  29. 	//插入重复元素
  30. 	pair<Iterator, bool> InsertEqual(const pair<K, V>& key)
  31. 	{
  32. 		CheckCapacity();
  33. 		size_t addre = HashFunc(key.first);
  34. 		PNode pcur = _table[addre];
  35. 		PNode newNode = new Node(key);
  36. 		//头插
  37. 		newNode->_PNext = pcur;
  38. 		_table[addre] = newNode;
  39.  
  40. 		_size++;
  41. 		return make_pair(Iterator(newNode, this), true);
  42.  
  43. 	}
  44. 	//插入唯一元素
  45. 	pair<Iterator, bool> InsertUnique(const pair<K, V>& key)
  46. 	{
  47. 		CheckCapacity();
  48. 		size_t addre = HashFunc(key.first);
  49. 		PNode pcur = _table[addre];
  50. 		//查找是否有相同元素
  51. 		while (pcur)
  52. 		{
  53. 			if (pcur->_key.first == key.first)
  54. 				return make_pair(Iterator(NULL,this), false);
  55. 			pcur = pcur->_PNext;
  56. 		}
  57.  
  58. 		//插入结点
  59. 		PNode newNode = new Node(key);
  60. 		newNode->_PNext = _table[addre];
  61. 		_table[addre] = newNode;
  62. 		_size++;
  63. 		return make_pair(Iterator(newNode, this), true);
  64. 	}
  65.  
  66. 	//查找元素
  67. 	Iterator Find(const pair<K,V>& key)
  68. 	{
  69. 		size_t addre = HashFunc(key.first);
  70. 		PNode pcur = _table[addre];
  71. 		while (pcur)
  72. 		{
  73. 			if (pcur->_key.first == key.first)
  74. 				return Iterator(pcur, this);
  75. 			pcur = pcur->_PNext;
  76. 		}
  77. 		return Iterator(NULL, this);
  78. 	}
  79.  
  80. 	//删除唯一元素
  81. 	pair<Iterator, bool> EraseUnique(const pair<K, V>& key)
  82. 	{
  83. 		size_t addre = HashFunc(key.first);
  84. 		PNode pcur = _table[addre];
  85. 		PNode pre = NULL;
  86. 		if (_table[addre] == NULL)
  87. 			return make_pair(Iterator(NULL, this), false);
  88. 		while (pcur)
  89. 		{
  90. 			if (pcur->_PNext->_key.first == key.first)
  91. 			{
  92. 				if (pcur == _table[addre])
  93. 				{
  94. 					_table[addre] = NULL;
  95. 				}
  96. 				else
  97. 				{
  98. 					pre->_PNext = pcur->_PNext;
  99. 				}
  100. 				delete pcur;
  101. 				pcur = NULL;
  102. 				--size;
  103. 				return make_pair(Iterator(pre, this), true);
  104. 			}
  105. 			pre = pcur;
  106. 			pcur = pcur->_PNext;
  107. 		}
  108. 		return make_pair(Iterator(NULL, this), false);
  109. 	}
  110.  
  111. 	//删除值不唯一
  112. 	pair<Iterator, bool> EraseEqual(const pair<K, V>& key)
  113. 	{
  114. 		size_t addre = HashFunc(key.first);
  115. 		PNode pcur = _table[addre];
  116. 		PNode pre = NULL;
  117. 		if (_table[addre] == NULL)
  118. 			return make_pair(Iterator(NULL, this), false);
  119. 		while (pcur)
  120. 		{
  121. 			if (pcur->_key.first == key.first)
  122. 			{
  123. 				 if (pcur == _table[addre])
  124. 				{
  125. 					 _table[addre] = pcur->_PNext;
  126. 					 delete pcur;
  127. 					 pcur = NULL;
  128. 				}
  129. 				 else
  130. 				 {
  131. 					 pre->_PNext = pcur->_PNext;
  132. 					 delete pcur;
  133. 					 pcur = pcur->_PNext;
  134. 				 }
  135. 				 _size--;
  136. 				
  137. 			}
  138. 			else
  139. 			{
  140. 				pre = pcur;
  141. 				pcur = pre->_PNext;
  142. 			}
  143. 		}
  144. 		return make_pair(Iterator(NULL, this), false);
  145.  
  146. 	}
  147. 	//值为key 的元素个数
  148. 	size_t Count(const pair<K, V>& key)
  149. 	{
  150. 		size_t addre = HashFunc(key.first);
  151. 		size_t count = 0;
  152. 		PNode pcur = _table[addre];
  153. 		while (pcur)
  154. 		{
  155. 			if (pcur->_key.first == key.first)
  156. 				count++;
  157. 			pcur = pcur->_PNext;
  158. 		}
  159. 		return count;
  160. 	}
  161. 	//桶的个数
  162. 	size_t BucketCount()const 
  163. 	{
  164. 		return _table.capacity();
  165. 	}
  166. 	//桶内元素的个数
  167. 	size_t BucketElemSize(size_t bucketNo)const
  168. 	{
  169. 		size_t count = 0;
  170. 		PNode pcur = _table[bucketNo];
  171. 		while (pcur)
  172. 		{
  173. 			count++;
  174. 			pcur = pcur->_PNext;
  175. 		}
  176. 		return count;
  177.  
  178. 	}
  179. 	//查找值为key,如果找到了，返回对应的value；如果没有找到，则插入该节点，返回缺省的value。
  180. 	V& FindOrInsert(const pair<K,V>& key)
  181. 	{
  182. 		size_t addre = HashFunc(key.first);
  183. 		PNode pcur = _table[addre];
  184. 		while (pcur)
  185. 		{
  186. 			if (pcur->_key.first == key.first)
  187. 				return pcur->_key.second;
  188. 			pcur = pcur->_PNext;
  189. 		}
  190. 		pair<Iterator, bool> ret = InsertUnique(make_pair(key.first, V()));
  191. 		return (*(ret.first)).second;
  192. 			
  193. 	}
  194. 	//判断是否为空
  195. 	bool Empty()const 
  196. 	{
  197. 		return _size == 0;
  198. 	}
  199. 	//插入的总数
  200. 	size_t numsize()const
  201. 	{
  202. 		return _size;
  203. 	}
  204. 	//清空
  205. 	void clear()
  206. 	{
  207. 		for (size_t bucketNo = 0; bucketNo < _table.capacity(); ++bucketNo)
  208. 		{
  209. 			PNode pcur = _table[bucketNo];
  210. 			while (pcur)
  211. 			{
  212. 				PNode pDel = pcur->_PNext;
  213. 				delete pcur;
  214. 				pcur = pDel;
  215. 				_size--;
  216. 			}
  217. 		}
  218. 	}
  219. 	~HashBucket()
  220. 	{
  221. 		clear();
  222. 	}
  223. private:
  224. 	void CheckCapacity()
  225. 	{
  226. 		size_t capacity = _table.capacity();
  227. 		if (_size==capacity)
  228. 		{
  229. 			size_t newcapacity = GetNextPrime(capacity);
  230. 			HashBucket<K, V, KToInt> hb(newcapacity);
  231. 			for (size_t bucketNo = 0; bucketNo < capacity; bucketNo++)
  232. 			{
  233. 				PNode pcur = _table[bucketNo];
  234. 				while (pcur)
  235. 				{
  236. 					hb.InsertEqual(pcur->_key);
  237. 					pcur = pcur->_PNext;
  238. 				}
  239. 			}
  240. 			swap(hb._table, _table);
  241. 			_size = hb._size;
  242. 		}
  243.  
  244. 	}
  245. 	size_t HashFunc(const K& key)
  246. 	{
  247. 		return KToInt()(key) % _table.capacity();
  248. 	}
  249. private:
  250. 	vector<PNode> _table;
  251. 	size_t _size;
  252. };

（6）测试函数

  1. void test()
  2. {
  3. 	HashBucket<int, int, KeyToIntDef> hb(20);
  4. 	hb.InsertUnique(make_pair(2,2));
  5. 	hb.InsertUnique(make_pair(3, 3));
  6. 	hb.InsertUnique(make_pair(4, 4));
  7. 	hb.InsertUnique(make_pair(2, 5));
  8.  
  9. 	/*hb.InsertEqual(make_pair(3, 3));
  10. 	hb.InsertEqual(make_pair(3, 4));
  12. 	hb.EraseEqual(make_pair(3, 3));*/
  13. 	
  14. 	/*cout<<hb.FindOrInsert(make_pair(2, 2));
  15. 	cout << hb.FindOrInsert(make_pair(9, 2));*/
  16. 	HashBucket<int, int, KeyToIntDef>::Iterator it = hb.Begin();
  17. 	if (!hb.Empty())
  18. 	{
  19. 		while (it != hb.End())
  20. 		{
  21. 			cout << it->first << " ";
  22. 			cout << (*it).second << endl;
  23. 			it++;
  24. 		}
  25. 		cout << hb.BucketCount();
  26. 		cout << hb.numsize();
  27. 	}
  28.  
  29. 	//HashBucket<string, string, stringToInt>hb2(20);
  30. 	//hb2.InsertUnique(make_pair("1111", "1111"));
  31. 	//hb2.InsertUnique(make_pair("2222", "2222"));
  32. 	//hb2.InsertUnique(make_pair("3333", "3333"));
  33. 	//hb2.InsertUnique(make_pair("2222", "1111"));
  34.  
  35. 	//cout << hb2.BucketCount();
  36. 	//cout << hb2.numsize();
  37.  
  38. 	cout << hb2.FindOrInsert(make_pair("2222", "2222"));
  39. 	cout << hb2.FindOrInsert(make_pair("4444", "4444"));
  40. }

大家可以自己利用哈希桶封装unordered_map啊！

 

 

 

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

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

  

闽ICP备14008679号