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

哈希表及unordered_map、unordered_set的模拟实现_哈希表使用方法unorderedmap

作者：我家小花儿 | 2024-08-13 06:40:28

赞

踩

哈希表使用方法unorderedmap

一、哈希表的概念

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

如果有一种数据结构，存储的数据与存储的位置呈映射关系，那么不需要进行比较直接通过对应的位置找到映射的数据。

其实这种数据结构就叫哈希表或者散列表，插入的数据通过哈希函数得到对应的位置，然后数据就插入在表中对应的位置上，

例如，我们在表中依次插入1、4、5、6、7、9，这里我们用的哈希函数是hash(key) = key % capacity，假设这个表的容量是10，并且插入的数据都小于容量，那么插入位置的下标和数据是相等的：

 那如果插入一个比容量大的数据呢？比如35呢？

35%10=5，可是下标为5的位置已经有数据了，那怎么办？

这个时候就会发生一个事情叫哈希冲突或哈希碰撞（即不同的数据通过相同的函数得到相同的地址）。

二、哈希函数

引起哈希冲突的其中一个原因可能是哈希函数设计的不够合理，我们先了解哈希函数的设计原则：

1、哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，其值域必须在0~(m-1)之间。

2、哈希函数计算出来的地址能均匀分布在整个空间中。

3、哈希函数应该比较简单。

常用的哈希函数：

1、直接定址法，哈希函数公式就是：hash(key) = A * key + B。

这个方法比较简单，但是它有局限性，它不能应用在海量数据中，太费空间了，适合用在数据比较小并且比较密集的情况。

2、除留余数法，设哈希表中允许的地址数为m，取一个接近或者等于m的质数p作除数，按照哈希函数hash(key) = key % p将关键码转换为哈希地址。

3、平方取中法，假设关键字为1234，它的平方就是1522756，取中间的三位数227作为哈希地址，平方取中法比较适合不知道关键字的分布，而位数又不是很大的情况。

还有一些其他的就不一一举例了...

三、解决哈希冲突

一、闭散列

当发生哈希冲突时，如果哈希表里还有空位置，那么就从映射的这个位置开始找下一个空位置，找到空位置就填上。

找下一个空位置的方法可以使用线性探测，拿上面那组数据为例，如果再次插入35，通过哈希函数得到哈希地址，为5，但是5这个位置已经有人了，那么就继续从5的位置后面继续走，直到找到空位置再填上，如果走到表的末尾还是没有空位置那就再从表头开始找（前提是确定有空位置），但是有一个情况要考虑，那就是删除的时候，首先我们先把35插入进去，经过线性探测最后是在哈希地址为8的位置停下并插入

之后我们再删除5，如果我们还想继续删除35，发现35通过哈希函数得到的哈希地址对应的位置没有数据，会误以为表中没有35。 

解决办法：把表中每个数据都加一个状态信息，分为三种状态，一个是默认的空状态（EMPTY），一个是存在状态（EXIST），一个为删除状态（DELETE）。如果我们删除数据的话只要把状态改为删除即可。

那要扩容的情况呢？

哈希表的载荷因子定义为 α = 填入表中的元素个数 / 哈希表长度，元素个数越多，载荷因子越大，发生哈希冲突的可能性也越大，反之越小，我们最好把荷载因子定义在0.7-0.8之间。

闭散列的实现：

  1. enum State { EMPTY, EXIST, DELETE };
  2.  
  3. 	/*template<class T>
  4. 	class HashFunction
  5. 	{
  6. 	public:
  7. 		size_t operator()(const T& val)
  8. 		{
  9. 			return val.first;
  10. 		}
  11. 	};*/
  12.  
  13. 	template<class K, class V>
  14. 	class HashTable
  15. 	{
  16. 		struct Elem
  17. 		{
  18. 			pair<K, V> _val;
  19. 			State _state;
  20. 		};
  21.  
  22. 	public:
  23. 		HashTable(size_t capacity = 3)
  24. 			: _ht(capacity), _size(0), _totalSize(0)
  25. 		{
  26. 			for (size_t i = 0; i < capacity; ++i)
  27. 				_ht[i]._state = EMPTY;
  28. 		}
  29.  
  30. 		// 插入
  31. 		bool Insert(const pair<K, V>& val)
  32. 		{
  33. 			if (Find(val.first) != -1)
  34. 				return false;
  35. 			CheckCapacity();
  36.  
  37. 			size_t hashi = HashFunc(val.first);
  38. 			size_t index = hashi;
  39. 			size_t i = 1;
  40. 			
  41. 			while (_ht[index]._state == EXIST)
  42. 			{
  43. 				index = hashi + i;
  44. 				index %= _ht.size();
  45. 				++i;
  46. 			}
  47.  
  48. 			_ht[index]._val = val;
  49. 			_ht[index]._state = EXIST;
  50. 			++_size;
  51. 			++_totalSize;
  52.  
  53. 			return true;
  54. 		}
  55.  
  56. 		// 查找
  57. 		size_t Find(const K& key)
  58. 		{
  59. 			size_t hashi = HashFunc(key);
  60. 			size_t i = 1;
  61. 			size_t index = hashi;
  62. 			while (_ht[index]._state != EMPTY)
  63. 			{
  64. 				if (_ht[index]._state == EXIST && _ht[index]._val == make_pair(key,key))
  65. 					return index;
  66.  
  67. 				index = hashi + i;
  68. 				index %= _ht.size();
  69. 				++i;
  70.  
  71. 				if (index == hashi)
  72. 					break;
  73. 			}
  74. 			return -1;
  75. 		}
  76.  
  77. 		// 删除
  78. 		bool Erase(const K& key)
  79. 		{
  80. 			//size_t hashi = HashFunc(key) % _ht.size();
  81. 			if (Find(key) != -1)
  82. 			{
  83. 				_ht[Find(key)]._state = DELETE;
  84. 				--_size;
  85.  
  86. 				return true;
  87. 			}
  88. 			return false;
  89. 		}
  90.  
  91. 		size_t Size()const
  92. 		{
  93. 			return _size;
  94. 		}
  95.  
  96. 		bool Empty() const
  97. 		{
  98. 			return _size == 0;
  99. 		}
  100.  
  101. 		void Swap(HashTable<K, V>& ht)
  102. 		{
  103. 			swap(_size, ht._size);
  104. 			swap(_totalSize, ht._totalSize);
  105. 			_ht.swap(ht._ht);
  106. 		}
  107.  
  108. 	private:
  109. 		size_t HashFunc(const K& key)
  110. 		{
  111. 			return key % _ht.capacity();
  112. 		}
  113.  
  114. 		void CheckCapacity()
  115. 		{
  116. 			if (_ht.size() == 0 || _size * 10 / _ht.size() >= 7)
  117. 			{
  118. 				size_t newsize = _ht.size() == 0 ? 10 : _ht.size() * 2;
  119. 				HashTable<K, V> newtable;
  120. 				newtable._ht.resize(newsize);
  121.  
  122. 				for(auto& e : _ht)
  123. 				{
  124. 					if (e._state == EXIST)
  125. 						newtable.Insert(e._val);
  126. 				}
  127. 				this->Swap(newtable);
  128. 			}
  129. 		}
  130. 	private:
  131. 		vector<Elem> _ht;
  132. 		size_t _size;
  133. 		size_t _totalSize;  // 哈希表中的所有元素：有效和已删除, 扩容时候要用到
  134. 	};

二、开散列

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

开散列的实现：

  1. template<class T>
  2. 	class HashFunc
  3. 	{
  4. 	public:
  5. 		size_t operator()(const T& val)
  6. 		{
  7. 			return val;
  8. 		}
  9. 	};
  10.  
  11. 	template<>
  12. 	class HashFunc<string>
  13. 	{
  14. 	public:
  15. 		size_t operator()(const string& s)
  16. 		{
  17. 			const char* str = s.c_str();
  18. 			unsigned int seed = 131; // 31 131 1313 13131 131313
  19. 			unsigned int hash = 0;
  20. 			while (*str)
  21. 			{
  22. 				hash = hash * seed + (*str++);
  23. 			}
  24.  
  25. 			return hash;
  26. 		}
  27. 	};
  28.  
  29. 	template<class V>
  30. 	struct HashBucketNode
  31. 	{
  32. 		HashBucketNode(const V& data)
  33. 			: _pNext(nullptr), _data(data)
  34. 		{}
  35. 		HashBucketNode<V>* _pNext;
  36. 		V _data;
  37. 	};
  38.  
  39. 	template<class V, class HF>
  40. 	class HashBucket;
  41.  
  42. 	template<class T,class Ref,class Ptr,class HF = HashFunc<T>>
  43. 	struct HashIterator
  44. 	{
  45. 		typedef HashBucketNode<T> Node;
  46. 		typedef HashBucket<T,HF> HT;
  47. 		typedef HashIterator<T,Ref,Ptr,HF> Self;
  48. 		typedef HashIterator<T,T&,T*> Iterator;
  49.  
  50. 		HashIterator(const Iterator& it)
  51. 			:_ht(it._ht)
  52. 			,_node(it._node)
  53. 		{}
  54.  
  55. 		HashIterator(Node* node,HT* ht)
  56. 			:_ht(ht)
  57. 			, _node(node)
  58. 		{}
  59.  
  60. 		Self& operator++()
  61. 		{
  62. 			if (_node->_pNext)
  63. 				_node = _node->_pNext;
  64. 			else
  65. 			{
  66. 				size_t hashi = HF()(_node->_data) % _ht->_table.size();
  67. 				++hashi;
  68. 				while (hashi < _ht->_table.size())
  69. 				{
  70. 					if (_ht->_table[hashi])
  71. 					{
  72. 						_node = _ht->_table[hashi];
  73. 						break;
  74. 					}
  75. 					++hashi;
  76. 				}
  77. 				if (hashi == _ht->_table.size())
  78. 					_node = nullptr;
  79. 			}
  80. 			return *this;
  81. 		}
  82.  
  83. 		Ref operator*()
  84. 		{
  85. 			return _node->_data;
  86. 		}
  87.  
  88. 		bool operator!=(const Self& it)
  89. 		{
  90. 			return this->_node != it._node;
  91. 		}
  92. 	private:
  93. 		Node* _node;
  94. 		const HT* _ht;
  95. 	};
  96.  
  97. 	// 本文所实现的哈希桶中key是唯一的
  98. 	template<class V, class HF = HashFunc<V>>
  99. 	class HashBucket
  100. 	{
  101. 		template<class T, class Ref, class Ptr, class HF>
  102. 		friend struct HashIterator;
  103. 	public:
  104. 		typedef HashBucketNode<V> Node;
  105. 		typedef Node* PNode;
  106. 		typedef HashBucket<V, HF> Self;
  107. 		typedef HashIterator<V, V&, V*, HF> iterator;
  108.  
  109. 	public:
  110. 		HashBucket(size_t capacity = 0)
  111. 			: _table(GetNextPrime(capacity))
  112. 			, _size(0)
  113. 		{}
  114.  
  115. 		~HashBucket()
  116. 		{
  117. 			Clear();
  118. 		}
  119.  
  120. 		iterator begin()
  121. 		{
  122. 			size_t hashi = 0;
  123. 			for (; hashi < _table.size(); ++hashi)
  124. 			{
  125. 				if (_table[hashi])
  126. 					return iterator(_table[hashi],this);
  127. 			}
  128. 			return iterator(_table[hashi],this);
  129. 		}
  130.  
  131. 		iterator end()
  132. 		{
  133. 			return iterator(nullptr,this);
  134. 		}
  135.  
  136. 		size_t GetNextPrime(size_t prime)
  137. 		{
  138. 			// SGI
  139. 			static const int __stl_num_primes = 28;
  140. 			static const unsigned long __stl_prime_list[__stl_num_primes] =
  141. 			{
  142. 				53, 97, 193, 389, 769,
  143. 				1543, 3079, 6151, 12289, 24593,
  144. 				49157, 98317, 196613, 393241, 786433,
  145. 				1572869, 3145739, 6291469, 12582917, 25165843,
  146. 				50331653, 100663319, 201326611, 402653189, 805306457,
  147. 				1610612741, 3221225473, 4294967291
  148. 			};
  149.  
  150. 			size_t i = 0;
  151. 			for (; i < __stl_num_primes; ++i)
  152. 			{
  153. 				if (__stl_prime_list[i] > prime)
  154. 					return __stl_prime_list[i];
  155. 			}
  156.  
  157. 			return __stl_prime_list[i];
  158. 		}
  159.  
  160. 		// 哈希桶中的元素不能重复
  161. 		Node* Insert(const V& data)
  162. 		{
  163. 			PNode node = Find(data);
  164. 			if (node)
  165. 				return node;
  166. 			else
  167. 			{
  168. 				//考虑扩容问题
  169. 				CheckCapacity();
  170. 				size_t hashi = HF()(data) % _table.size();
  171. 				Node* newnode = new Node(data);
  172. 				newnode->_pNext = _table[hashi];
  173. 				_table[hashi] = newnode;
  174. 				++_size;
  175.  
  176. 				return newnode;
  177. 			}
  178. 				
  179. 		}
  180.  
  181. 		// 删除哈希桶中为data的元素(data不会重复)
  182. 		bool Erase(const V& data)
  183. 		{
  184. 			size_t hashi = HF()(data) % _table.size();
  185. 			PNode node = _table[hashi];
  186. 			PNode prev = nullptr;
  187. 			while (node)
  188. 			{
  189. 				if (node->_data == data)
  190. 				{
  191. 					if (node == _table[hashi])
  192. 					{
  193. 						PNode next = node->_pNext;
  194. 						delete node;
  195. 						_table[hashi] = next;
  196. 						return true;
  197. 					}
  198. 					else
  199. 					{
  200. 						prev->_pNext = node->_pNext;
  201. 						delete node;
  202. 						return true;
  203. 					}
  204. 				}
  205. 				else
  206. 				{
  207. 					prev = node;
  208. 					node = node->_pNext;
  209. 				}
  210. 			}
  211. 			return false;
  212. 		}
  213.  
  214. 		Node* Find(const V& data)
  215. 		{
  216. 			if (_table.size() == 0)
  217. 				return nullptr;
  218. 			size_t hashi = HF()(data) % _table.size();
  219. 			PNode node = _table[hashi];
  220. 			while (node != nullptr && node->_data != data)
  221. 			{
  222. 				node = node->_pNext;
  223. 			}
  224. 			return node;
  225. 		}
  226.  
  227. 		size_t Size()const
  228. 		{
  229. 			return _size;
  230. 		}
  231.  
  232. 		bool Empty()const
  233. 		{
  234. 			return 0 == _size;
  235. 		}
  236.  
  237. 		void Clear()
  238. 		{
  239. 			for (auto& node : _table)
  240. 			{
  241. 				PNode cur = node;
  242. 				while (cur)
  243. 				{
  244. 					PNode next = cur->_pNext;
  245. 					delete cur;
  246. 					cur = next;
  247. 				}
  248. 			}
  249. 		}
  250.  
  251. 		size_t BucketCount()const
  252. 		{
  253. 			return _table.capacity();
  254. 		}
  255.  
  256. 		void Swap(Self& ht)
  257. 		{
  258. 			_table.swap(ht._table);
  259. 			swap(_size, ht._size);
  260. 		}
  261.  
  262. 	private:
  263. 		size_t HashFunc(const V& data)
  264. 		{
  265. 			return HF()(data) % _table.capacity();
  266. 		}
  267.  
  268. 		void CheckCapacity()
  269. 		{
  270. 			if (_size == _table.size())
  271. 			{
  272. 				/*vector<Node*> newtable = new vector<Node*>(_size);*/
  273. 				Self* newhashbucket = new Self(_size);
  274. 				for (auto& p : _table)
  275. 				{
  276. 					PNode cur = p;
  277. 					while (cur)
  278. 					{						
  279. 						PNode next = cur->_pNext;
  280.  
  281. 						size_t hashi = HF()(cur->_data) % newhashbucket->_table.size();
  282. 						cur->_pNext = newhashbucket->_table[hashi];
  283. 						newhashbucket->_table[hashi] = cur;
  284.  
  285. 						cur = next;
  286. 					}
  287. 				}
  288. 			}
  289. 		}
  290.  
  291. 	private:
  292. 		vector <Node*> _table;
  293. 		size_t _size;      // 哈希表中有效元素的个数
  294. 	};

在代码的最上方，我们定义了一个仿函数，其目的是存储数据的key不一定是整形，也可能是其他类型，就不方便转换成整型，所以可以通过仿函数转成整形。

四、unordered_set和unordered_map

其实它们的底层就是哈希表，所以模拟实现的话可以对哈希表进行封装就可以了。

一、unordered_set的模拟实现

  1. // 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
  2. 	template<class K, class V, class KeyOfValue, class HF>
  3. 	class HashBucket;
  4.  
  5. 	// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
  6. 	template <class K, class V,class Ref,class Ptr, class KeyOfValue, class HF>
  7. 	struct HBIterator
  8. 	{
  9. 		typedef HashBucket<K, V, KeyOfValue, HF> HashBucket;
  10. 		typedef HashBucketNode<V>* PNode;
  11. 		typedef HBIterator<K, V,Ref,Ptr, KeyOfValue, HF> Self;
  12.  
  13. 		HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr)
  14. 			:_pNode(pNode)
  15. 			,_pHt(pHt)
  16. 		{}
  17.  
  18. 		Self& operator++()
  19. 		{
  20. 			// 当前迭代器所指节点后还有节点时直接取其下一个节点
  21. 			if (_pNode->_pNext)
  22. 				_pNode = _pNode->_pNext;
  23. 			else
  24. 			{
  25. 				// 找下一个不空的桶，返回该桶中第一个节点
  26. 				size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data)) + 1;
  27. 				for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
  28. 				{
  29. 					if (_pNode = _pHt->_ht[bucketNo])
  30. 						break;
  31. 				}
  32. 				/*if (bucketNo == _pHt->BucketCount())
  33. 					_pNode = nullptr;*/
  34. 			}
  35.  
  36. 			return *this;
  37. 		}
  38. 		Self operator++(int)
  39. 		{
  40. 			Self tmp = *this;
  41. 			this->operator++();
  42. 			return tmp;
  43. 		}
  44.  
  45. 		V& operator*()
  46. 		{
  47. 			return this->_pNode->_data;
  48. 		}
  49.  
  50. 		V* operator->()
  51. 		{
  52. 			return &(this->_pNode->_data);
  53. 		}
  54.  
  55. 		bool operator==(const Self& it) const
  56. 		{
  57. 			return this->_pNode == it->_pNode;
  58. 		}
  59.  
  60. 		bool operator!=(const Self& it)const
  61. 		{
  62. 			return this->_pNode != it._pNode;
  63. 		}
  64.  
  65. 		PNode _pNode;             // 当前迭代器关联的节点
  66. 		HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
  67. 	};
  68.  
  69. 	// unordered_set中存储的是K类型，HF哈希函数类型
  70. 	// unordered_set在实现时，只需将hashbucket中的接口重新封装即可
  71. 	//template<class K, class HF = DefHashF<K>>
  72. 	template<class K, class HF = HashFunc<K>>
  73. 	class unordered_set
  74. 	{
  75. 		// 通过key获取value的操作
  76. 		struct KeyOfValue
  77. 		{
  78. 			const K& operator()(const K& data)
  79. 			{
  80. 				return data;
  81. 			}
  82. 		};
  83. 		typedef OpenHash::HashBucket<K, K, KeyOfValue, HF> HT;
  84. 	public:
  85. 		typedef typename HT::const_iterator iterator;
  86. 		typedef typename HT::const_iterator const_iterator;
  87. 		
  88. 	public:
  89. 		unordered_set() : _ht()
  90. 		{}
  91. 		
  92. 		iterator begin() { return _ht.begin(); }
  93. 		iterator end() { return _ht.end(); }
  94.  
  95. 		const_iterator begin()const { return _ht.begin(); }
  96. 		const_iterator end()const { return _ht.end(); }
  97. 		
  98. 		// capacity
  99. 		size_t size()const { return _ht.size(); }
  100. 		bool empty()const { return _ht.empty(); }
  101. 		///
  102. 		// lookup
  103. 		iterator find(const K& key) { return _ht.Find(key); }
  104. 		size_t count(const K& key) { return _ht.Count(key); }
  105. 		/
  106. 		// modify
  107. 		pair<iterator, bool> insert(const K& valye)
  108. 		{
  109. 			return _ht.Insert(valye);
  110. 		}
  111.  
  112. 		iterator erase(iterator position)
  113. 		{
  114. 			return _ht.Erase(position);
  115. 		}
  116. 		
  117. 		// bucket
  118. 		size_t bucket_count() { return _ht.BucketCount(); }
  119. 		size_t bucket_size(const K& key) { return _ht.Size(key); }
  120. 	private:
  121. 		HT _ht;
  122. 	};

二、unordered_map的模拟实现

  1. // 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
  2. 	template<class K, class V, class KeyOfValue, class HF>
  3. 	class HashBucket;
  4.  
  5. 	// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
  6. 	template <class K, class V, class KeyOfValue, class HF>
  7. 	struct HBIterator
  8. 	{
  9. 		typedef HashBucket<K, V, KeyOfValue, HF> HashBucket;
  10. 		typedef HashBucketNode<V>* PNode;
  11. 		typedef HBIterator<K, V, KeyOfValue, HF> Self;
  12.  
  13. 		HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr)
  14. 			:_pNode(pNode)
  15. 			,_pHt(pHt)
  16. 		{}
  17.  
  18. 		Self& operator++()
  19. 		{
  20. 			// 当前迭代器所指节点后还有节点时直接取其下一个节点
  21. 			if (_pNode->_pNext)
  22. 				_pNode = _pNode->_pNext;
  23. 			else
  24. 			{
  25. 				// 找下一个不空的桶，返回该桶中第一个节点
  26. 				size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data)) + 1;
  27. 				for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
  28. 				{
  29. 					if (_pNode = _pHt->_ht[bucketNo])
  30. 						break;
  31. 				}
  32. 			}
  33.  
  34. 			return *this;
  35. 		}
  36. 		Self operator++(int)
  37. 		{
  38. 			Self tmp = this;
  39. 			this->operator++();
  40. 			return tmp;
  41. 		}
  42.  
  43. 		V& operator*()
  44. 		{
  45. 			return _pNode->_data;
  46. 		}
  47.  
  48. 		V* operator->()
  49. 		{
  50. 			return &(_pNode->_data);
  51. 		}
  52.  
  53. 		bool operator==(const Self& it) const
  54. 		{
  55. 			return _pNode == it._pNode;
  56. 		}
  57.  
  58. 		bool operator!=(const Self& it) const
  59. 		{
  60. 			return _pNode != it._pNode;
  61. 		}
  62.  
  63. 		PNode _pNode;             // 当前迭代器关联的节点
  64. 		HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
  65. 	};
  66.  
  67. 	// unordered_map中存储的是pair<K, V>的键值对，K为key的类型，V为value的类型，HF哈希函数类型
  68. 	// unordered_map在实现时，只需将hashbucket中的接口重新封装即可
  69. 	template<class K, class V, class HF = HashFunc<K>>
  70. 	class unordered_map
  71. 	{
  72. 		// 通过key获取value的操作
  73. 		struct KeyOfValue
  74. 		{
  75. 			const K& operator()(const pair<K, V>& data)
  76. 			{
  77. 				return data.first;
  78. 			}
  79. 		};
  80. 		typedef OpenHash::HashBucket<K, pair<K, V>, KeyOfValue, HF> HT;
  81. 	public:
  82. 		typedef typename HT::iterator iterator;
  83. 	public:
  84. 		unordered_map() : _ht()
  85. 		{}
  86. 		
  87. 		iterator begin() { return _ht.begin(); }
  88. 		iterator end() { return _ht.end(); }
  89. 		
  90. 		// capacity
  91. 		size_t size()const { return _ht.size(); }
  92. 		bool empty()const { return _ht.empty(); }
  93. 		///
  94. 		// Acess
  95. 		V& operator[](const K& key)
  96. 		{
  97. 			pair<iterator, bool> ret = insert(make_pair(key, V()));
  98. 			return ret.first->second;
  99. 		}
  100. 		const V& operator[](const K& key)const
  101. 		{
  102. 			pair<iterator, bool> ret = insert(make_pair(key, V()));
  103. 			return ret.fisrt->second;
  104. 		}
  105. 		//
  106. 		// lookup
  107. 		iterator find(const K& key) { return _ht.Find(key); }
  108. 		size_t count(const K& key) { return _ht.Count(key); }
  109. 		/
  110. 		// modify
  111. 		pair<iterator, bool> insert(const pair<K, V>& valye)
  112. 		{
  113. 			return _ht.Insert(valye);
  114. 		}
  115.  
  116. 		iterator erase(iterator position)
  117. 		{
  118. 			return _ht.Erase(position);
  119. 		}
  120. 		
  121. 		// bucket
  122. 		size_t bucket_count() { return _ht.BucketCount(); }
  123. 		size_t bucket_size(const K& key) { return _ht.BucketSize(key); }
  124. 	private:
  125. 		HT _ht;
  126. 	};

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

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

  

闽ICP备14008679号