• unordered_map，unordered_set模拟实现

    目录

    一 . 底层结构--哈希

    1.直接定址法

    2. 除留余数法 + 哈希桶

    3. 一些定义 

    二 . 模拟实现哈希表

    1.哈希表框架

    ​编辑

    2.插入

     3.查找 

    4 . 删除

    5.解决使用问题

    6.完整代码

    三 .实现unordered_map, unordered_set

    1. 初步实现unordered_map, unordered_set

    2.加上迭代器（自行理解）

     3.测试用例

    一 . 底层结构--哈希

    哈希思想：构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
    哈希方法构造出来的结构称为哈希表(Hash Table)(或者称散列表)

    1.直接定址法

    2. 除留余数法 + 哈希桶

    如果数据过多，并且数据很散，直接定址法不适合。

    3. 一些定义 

    不同关键字（4，14，24，84）通过相同的方法（% 10）计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

    解决哈希冲突两种常见的方法是：闭散列和开散列

    闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
    空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去

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

    二 . 模拟实现哈希表

    1.哈希表框架


     

    代码： 

    1. //节点
    2. template<class K, class V>
    3. struct HashNode
    4. {
    5. 	HashNode(const pair& kv)
    6. 		:_kv(kv)
    7. 		, _next(nullptr)
    8. 	{}
    9. 	pair _kv;
    10. 	HashNode* _next;
    11. };
    12.  
    13. template<class K, class V>
    14. {
    15.     typedef HashNode Node;
    16. public:
    17. 	HashTable()
    18. 	{
    19. 		_tables.resize(10, nullptr);
    20. 	}
    21.     ~HashTable()
    22. 	{
    23. 		for (size_t i = 0; i < _tables.size(); i++)
    24. 		{
    25. 			Node* cur = _tables[i];
    26. 			while (cur)
    27. 			{
    28. 				Node* next = cur->_next;
    29. 				delete cur;
    30. 				cur = next;
    31. 			}
    32. 		}
    33. 	}
    34.     //删除
    35.     //插入
    36.     //查找
    37.  
    38. private:
    39. 	vector _tables;
    40. 	size_t _n = 0; // 哈希表实际元素个数
    41. }

    _n存在的意义：判断_tables什么时候扩容。

    开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。
     

    2.插入

    1. bool Insert(const pair& kv)
    2. 	{
    3. 		if(Find(kv.first))
    4. 			return false;
    5. 	    //扩容
    6. 		if (_n / _tables.size() == 1)
    7. 		{
    8. 			size_t newSize = _tables.size() * 2;
    9. 			vector newTables;
    10. 			newTables.resize(newSize, nullptr);
    11. 			for (size_t i = 0; i < _tables.size(); i++)
    12. 			{
    13. 				Node* cur = _tables[i];
    14. 				while (cur)
    15. 				{
    16. 					size_t hashi = cur->_kv.first % newTables.size();
    17. 					cur->_next = newTables[hashi];
    18. 					newTables[hashi] = cur;
    19. 				}
    20. 				_tables[i] = nullptr;
    21. 			}
    22. 			_tables.swap(newTables);
    23. 		}
    24.  
    25. 		size_t hashi = kv.first % _tables.size();
    26. 		Node* newnode = new Node(kv);
    27. 		newnode->_next = _tables[hashi];
    28. 		_tables[hashi] = newnode;
    29. 		_n++;
    30.  
    31. 		return false;
    32. 	}

     3.查找 

    1. Node* Find(const K& key)
    2. 	{
    3. 		size_t hashi = key % _tables.size();//找到插入位置
    4. 		Node* cur = _tables[hashi];
    5. 		while (cur)
    6. 		{
    7. 			if (cur->_kv.first == key)
    8. 			{
    9. 				return cur;
    10. 			}
    11. 			cur = cur->_next;
    12. 		}
    13. 		return nullptr;
    14. 	}

    4 . 删除

     

    1. 	bool erase(const K& key)
    2. 	{
    3. 		size_t hashi = key % _tables.size();
    4. 		Node* cur = _tables[hashi];
    5. 		Node* prev = nullptr;
    6. 		if (cur->_kv.first == key)
    7. 		{
    8. 			_tables[hashi] = nullptr;
    9. 			return true;
    10. 		}
    11. 		while (cur)
    12. 		{
    13. 			if (cur->_kv.first == key)
    14. 			{
    15. 				prev->_next = cur->_next;
    16. 				delete cur;
    17. 				return true;
    18. 			}
    19. 			prev = cur;
    20. 			cur = cur->_next;
    21. 		}
    22. 		return false;
    23. 	}

    5.解决使用问题

    如果kv.first为string或者其他类型，就会出问题。

    解决：

    1. template<class K>
    2. struct HashFunc
    3. {
    4. 	size_t operator()(const K& key)
    5. 	{
    6. 		return (size_t)key;
    7. 	}
    8. };
    9. template<>
    10. struct HashFunc
    11. {
    12. 	size_t operator()(const string& key)
    13. 	{
    14. 		size_t sum = 0;
    15. 		for (auto& e : key)
    16. 		{
    17. 			sum *= 31;
    18. 			sum += e;
    19. 		}
    20. 		return sum;
    21. 	}
    22. };

    接着把所有用除留余数法的部分进行修改：

    6.完整代码

    1. #pragma once
    2.  
    3. template<class K, class V>
    4. struct HashNode
    5. {
    6. 	HashNode(const pair& kv)
    7. 		:_kv(kv)
    8. 		, _next(nullptr)
    9. 	{}
    10. 	pair _kv;
    11. 	HashNode* _next;
    12. };
    13.  
    14.  
    15. template<class K>
    16. struct HashFunc
    17. {
    18. 	size_t operator()(const K& key)
    19. 	{
    20. 		return (size_t)key;
    21. 	}
    22. };
    23. template<>
    24. struct HashFunc
    25. {
    26. 	size_t operator()(const string& key)
    27. 	{
    28. 		size_t sum = 0;
    29. 		for (auto& e : key)
    30. 		{
    31. 			sum *= 31;
    32. 			sum += e;
    33. 		}
    34. 		return sum;
    35. 	}
    36. };
    37.  
    38. //哈希桶
    39. template<class K, class V, class Hash = HashFunc>
    40. class HashTable
    41. {
    42. 	typedef HashNode Node;
    43. 	Hash hf;
    44. public:
    45. 	HashTable()
    46. 	{
    47. 		_tables.resize(10, nullptr);
    48. 	}
    49.  
    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. 	}
    63.  
    64. 	bool Insert(const pair& kv)
    65. 	{
    66. 		if(Find(kv.first))
    67. 			return false;
    68. 	    //扩容
    69. 		if (_n / _tables.size() == 1)
    70. 		{
    71. 			size_t newSize = _tables.size() * 2;
    72. 			vector newTables;
    73. 			newTables.resize(newSize, nullptr);
    74. 			for (size_t i = 0; i < _tables.size(); i++)
    75. 			{
    76. 				Node* cur = _tables[i];
    77. 				while (cur)
    78. 				{
    79. 					size_t hashi = hf(cur->_kv.first) % newTables.size();
    80. 					cur->_next = newTables[hashi];
    81. 					newTables[hashi] = cur;
    82. 				}
    83. 				_tables[i] = nullptr;
    84. 			}
    85. 			_tables.swap(newTables);
    86. 		}
    87.  
    88. 		size_t hashi = hf(kv.first) % _tables.size();
    89. 		Node* newnode = new Node(kv);
    90. 		newnode->_next = _tables[hashi];
    91. 		_tables[hashi] = newnode;
    92. 		_n++;
    93.  
    94. 		return false;
    95. 	}
    96.  
    97. 	Node* Find(const K& key)
    98. 	{
    99. 		size_t hashi = hf(key) % _tables.size();
    100. 		Node* cur = _tables[hashi];
    101. 		while (cur)
    102. 		{
    103. 			if (cur->_kv.first == key)
    104. 			{
    105. 				return cur;
    106. 			}
    107. 			cur = cur->_next;
    108. 		}
    109. 		return nullptr;
    110. 	}
    111.  
    112. 	bool erase(const K& key)
    113. 	{
    114. 		size_t hashi = hf(key) % _tables.size();
    115. 		Node* cur = _tables[hashi];
    116. 		Node* prev = nullptr;
    117. 		if (cur->_kv.first == key)
    118. 		{
    119. 			_tables[hashi] = nullptr;
    120. 			return true;
    121. 		}
    122. 		while (cur)
    123. 		{
    124. 			if (cur->_kv.first == key)
    125. 			{
    126. 				prev->_next = cur->_next;
    127. 				delete cur;
    128. 				return true;
    129. 			}
    130. 			prev = cur;
    131. 			cur = cur->_next;
    132. 		}
    133. 		return false;
    134. 	}
    135.  
    136. private:
    137. 	vector _tables;
    138. 	size_t _n = 0;
    139. };

    三 .实现unordered_map, unordered_set

    1. 初步实现unordered_map, unordered_set

    这部分内容类似红黑树封装map,set。

    unordered_set.h

    1. #pragma once
    2.  
    3. template<class K, class Hash = HashFunc>
    4. class unordered_set
    5. {
    6. 	struct KeyOfT
    7. 	{
    8. 		const K& operator()(const K& key)
    9. 		{
    10. 			return key;
    11. 		}
    12. 	};
    13.  
    14. public:
    15. 	bool insert(const K& key)
    16. 	{
    17. 		return _ht.Insert(key);
    18. 	}
    19.  
    20. 	bool erase(const K& key)
    21. 	{
    22. 		return _ht.Erase(key);
    23. 	}
    24.  
    25. 	HashNode* find(const K& key)
    26. 	{
    27. 		return _ht.Find(key);
    28. 	}
    29.  
    30.  
    31. private:
    32. 	HashTable _ht;
    33. };

    unordered_map.h

    1. #pragma once
    2.  
    3. template<class K, class V, class Hash = HashFunc>
    4. class unordered_map
    5. {
    6. 	struct KeyOfT
    7. 	{
    8. 		const K& operator()(const pair& kv)
    9. 		{
    10. 			return kv.first;
    11. 		}
    12. 	};
    13.  
    14. public:
    15. 	bool insert(const pair& key)
    16. 	{
    17. 		return _ht.Insert(key);
    18. 	}
    19.  
    20. 	bool erase(const K& key)
    21. 	{
    22. 		return _ht.Erase(key);
    23. 	}
    24.  
    25. 	HashNode>* find(const K& key)
    26. 	{
    27. 		return _ht.Find(key);
    28. 	}
    29.  
    30. private:
    31. 	HashTable, KeyOfT> _ht;
    32. };

    HashTable.h

    1. #pragma once
    2.  
    3.  
    4. template<class T>
    5. struct HashNode
    6. {
    7. 	HashNode(const T& data)
    8. 		:_data(data)
    9. 		, _next(nullptr)
    10. 	{}
    11. 	T _data;
    12. 	HashNode* _next;
    13. };
    14.  
    15.  
    16. template<class K>
    17. struct HashFunc
    18. {
    19. 	size_t operator()(const K& key)
    20. 	{
    21. 		return (size_t)key;
    22. 	}
    23. };
    24. template<>
    25. struct HashFunc
    26. {
    27. 	size_t operator()(const string& key)
    28. 	{
    29. 		size_t sum = 0;
    30. 		for (auto& e : key)
    31. 		{
    32. 			sum *= 31;
    33. 			sum += e;
    34. 		}
    35. 		return sum;
    36. 	}
    37. };
    38.  
    39. //哈希桶
    40. template<class K, class T, class KeyOfT>
    41. class HashTable
    42. {
    43. 	typedef HashNode Node;
    44. 	HashFunc hf;
    45. 	KeyOfT kot;
    46. public:
    47. 	HashTable()
    48. 	{
    49. 		_tables.resize(10, nullptr);
    50. 	}
    51.  
    52. 	~HashTable()
    53. 	{
    54. 		for (size_t i = 0; i < _tables.size(); i++)
    55. 		{
    56. 			Node* cur = _tables[i];
    57. 			while (cur)
    58. 			{
    59. 				Node* next = cur->_next;
    60. 				delete cur;
    61. 				cur = next;
    62. 			}
    63. 		}
    64. 	}
    65.  
    66. 	bool Insert(const T& data)
    67. 	{
    68. 		if(Find(kot(data)))
    69. 			return false;
    70. 	    //扩容
    71. 		if (_n / _tables.size() == 1)
    72. 		{
    73. 			size_t newSize = _tables.size() * 2;
    74. 			vector newTables;
    75. 			newTables.resize(newSize, nullptr);
    76. 			for (size_t i = 0; i < _tables.size(); i++)
    77. 			{
    78. 				Node* cur = _tables[i];
    79. 				while (cur)
    80. 				{
    81. 					size_t hashi = hf(kot(cur->_data)) % newTables.size();
    82. 					cur->_next = newTables[hashi];
    83. 					newTables[hashi] = cur;
    84. 				}
    85. 				_tables[i] = nullptr;
    86. 			}
    87. 			_tables.swap(newTables);
    88. 		}
    89.  
    90. 		size_t hashi = hf(kot(data)) % _tables.size();
    91. 		Node* newnode = new Node(data);
    92. 		newnode->_next = _tables[hashi];
    93. 		_tables[hashi] = newnode;
    94. 		_n++;
    95.  
    96. 		return false;
    97. 	}
    98.  
    99. 	Node* Find(const K& key)
    100. 	{
    101. 		size_t hashi = hf(key) % _tables.size();
    102. 		Node* cur = _tables[hashi];
    103. 		while (cur)
    104. 		{
    105. 			if (kot(cur->_data) == key)
    106. 			{
    107. 				return cur;
    108. 			}
    109. 			cur = cur->_next;
    110. 		}
    111. 		return nullptr;
    112. 	}
    113.  
    114. 	bool Erase(const K& key)
    115. 	{
    116. 		size_t hashi = hf(key) % _tables.size();
    117. 		Node* cur = _tables[hashi];
    118. 		Node* prev = nullptr;
    119. 		if (kot(cur->_data) == key)
    120. 		{
    121. 			_tables[hashi] = nullptr;
    122. 			return true;
    123. 		}
    124. 		while (cur)
    125. 		{
    126. 			if (kot(cur->_data) == key)
    127. 			{
    128. 				prev->_next = cur->_next;
    129. 				delete cur;
    130. 				return true;
    131. 			}
    132. 			prev = cur;
    133. 			cur = cur->_next;
    134. 		}
    135. 		return false;
    136. 	}
    137.  
    138. private:
    139. 	vector _tables;
    140. 	size_t _n = 0;
    141. };

    2.加上迭代器（自行理解）

    unordered_map.h

    1. #pragma once
    2.  
    3. template<class K, class V, class Hash = HashFunc>
    4. class unordered_map
    5. {
    6. 	struct KeyOfT
    7. 	{
    8. 		const K& operator()(const pair& kv)
    9. 		{
    10. 			return kv.first;
    11. 		}
    12. 	};
    13. public:
    14. 	typedef typename HashTableconst K, V>, KeyOfT, Hash>::iterator iterator;
    15.  
    16. 	iterator begin()
    17. 	{
    18. 		return _ht.begin();
    19. 	}
    20.  
    21. 	iterator end()
    22. 	{
    23. 		return _ht.end();
    24. 	}
    25.  
    26. 	pairbool> insert(const pair& kv)
    27. 	{
    28. 		return _ht.Insert(kv);
    29. 	}
    30.  
    31. 	V& operator[](const K& key)
    32. 	{
    33. 		pairbool> ret = _ht.Insert(make_pair(key, V()));
    34. 		return ret.first->second;
    35. 	}
    36.  
    37. 	const V& operator[](const K& key) const
    38. 	{
    39. 		pairbool> ret = _ht.Insert(make_pair(key, V()));
    40. 		return ret.first->second;
    41. 	}
    42.  
    43. 	iterator find(const K& key)
    44. 	{
    45. 		return _ht.Find(key);
    46. 	}
    47.  
    48. 	bool erase(const K& key)
    49. 	{
    50. 		return _ht.Erase(key);
    51. 	}
    52.  
    53. private:
    54. 	HashTableconst K, V>, KeyOfT, Hash> _ht;
    55. };

    unordered_set.h

    1. #pragma once
    2.  
    3.  
    4. template<class K, class Hash = HashFunc>
    5. class unordered_set
    6. {
    7. 	struct KeyOfT
    8. 	{
    9. 		const K& operator()(const K& key)
    10. 		{
    11. 			return key;
    12. 		}
    13. 	};
    14.  
    15. public:
    16. 	typedef typename HashTable::const_iterator iterator;
    17. 	typedef typename HashTable::const_iterator const_iterator;
    18.  
    19. 	const_iterator begin() const
    20. 	{
    21. 		return _ht.begin();
    22. 	}
    23.  
    24. 	const_iterator end() const
    25. 	{
    26. 		return _ht.end();
    27. 	}
    28.  
    29. 	pairbool> insert(const K& key)
    30. 	{
    31. 		auto ret = _ht.Insert(key);
    32. 		return pairbool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
    33. 	}
    34.  
    35. 	iterator find(const K& key)
    36. 	{
    37. 		return _ht.Find(key);
    38. 	}
    39.  
    40. private:
    41. 	HashTable _ht;
    42. };

    HashTable.h

    1. #pragma once
    2.  
    3.  
    4. template<class T>
    5. struct HashNode
    6. {
    7. 	HashNode(const T& data)
    8. 		:_data(data)
    9. 		, _next(nullptr)
    10. 	{}
    11. 	T _data;
    12. 	HashNode* _next;
    13. };
    14.  
    15.  
    16. template<class K>
    17. struct HashFunc
    18. {
    19. 	size_t operator()(const K& key)
    20. 	{
    21. 		return (size_t)key;
    22. 	}
    23. };
    24. template<>
    25. struct HashFunc
    26. {
    27. 	size_t operator()(const string& key)
    28. 	{
    29. 		size_t sum = 0;
    30. 		for (auto& e : key)
    31. 		{
    32. 			sum *= 31;
    33. 			sum += e;
    34. 		}
    35. 		return sum;
    36. 	}
    37. };
    38.  
    39. //前置声明
    40. template<class K, class T, class KeyOfT, class Hash>
    41. class HashTable;
    42.  
    43. //迭代器
    44. template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash = HashFunc>
    45. struct _HTIterator
    46. {
    47. 	typedef HashNode Node;
    48. 	typedef _HTIterator Self;
    49. 	Node* _node;
    50. 	size_t _hashi;
    51. 	const HashTable* _pht;
    52.  
    53. 	_HTIterator(Node* node, HashTable* pht, size_t hashi)
    54. 		:_node(node)
    55. 		, _hashi(hashi)
    56. 		, _pht(pht)
    57. 	{}
    58.  
    59. 	_HTIterator(Node* node, const HashTable* pht, size_t hashi)
    60. 		:_node(node)
    61. 		, _hashi(hashi)
    62. 		, _pht(pht)
    63. 	{}
    64.  
    65. 	Self& operator++()
    66. 	{
    67. 		if (_node->_next)
    68. 		{
    69. 			_node = _node->_next;
    70. 		}
    71. 		else//需要哈希表
    72. 		{
    73. 			++_hashi;
    74. 			while (_hashi < _pht->_tables.size())
    75. 			{
    76. 				if (_pht->_tables[_hashi])
    77. 				{
    78. 					_node = _pht->_tables[_hashi];
    79. 					break;
    80. 				}
    81. 				++_hashi;
    82. 			}
    83. 			if (_hashi == _pht->_tables.size())
    84. 			{
    85. 				_node = nullptr;
    86. 			}
    87. 		}
    88. 		return *this;
    89. 	}
    90.  
    91. 	bool operator!=(const Self& s)
    92. 	{
    93. 		return _node != s._node;
    94. 	}
    95.  
    96. 	Ref operator*()
    97. 	{
    98. 		return _node->_data;
    99. 	}
    100.  
    101. 	Ptr operator->()
    102. 	{
    103. 		return &(_node->_data);
    104. 	}
    105.  
    106. };
    107.  
    108.  
    109.  
    110.  
    111. //哈希桶
    112. template<class K, class T, class KeyOfT, class Hash = HashFunc>
    113. class HashTable
    114. {
    115. public:
    116. 	typedef HashNode Node;
    117.  
    118. 	//为了访问HashTable的私有成员
    119. 	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
    120. 	friend struct _HTIterator;
    121. 	typedef _HTIterator iterator;
    122. 	typedef _HTIteratorconst T&, const T*, KeyOfT, Hash> const_iterator;
    123.  
    124. 	Hash hf;
    125. 	KeyOfT kot;
    126. 	HashTable()
    127. 	{
    128. 		_tables.resize(10, nullptr);
    129. 	}
    130.  
    131. 	~HashTable()
    132. 	{
    133. 		for (size_t i = 0; i < _tables.size(); i++)
    134. 		{
    135. 			Node* cur = _tables[i];
    136. 			while (cur)
    137. 			{
    138. 				Node* next = cur->_next;
    139. 				delete cur;
    140. 				cur = next;
    141. 			}
    142. 		}
    143. 	}
    144.  
    145. 	iterator begin()
    146. 	{
    147. 		for (size_t i = 0; i < _tables.size(); i++)
    148. 		{
    149. 			if (_tables[i])
    150. 			{
    151. 				return iterator(_tables[i], this, i);
    152. 			}
    153. 		}
    154.  
    155. 		return end();
    156. 	}
    157.  
    158. 	iterator end()
    159. 	{
    160. 		return iterator(nullptr, this, -1);
    161. 	}
    162.  
    163. 	const_iterator begin() const
    164. 	{
    165. 		for (size_t i = 0; i < _tables.size(); i++)
    166. 		{
    167. 			if (_tables[i])
    168. 			{
    169. 				return const_iterator(_tables[i], this, i);
    170. 			}
    171. 		}
    172.  
    173. 		return end();
    174. 	}
    175.  
    176. 	const_iterator end() const
    177. 	{
    178. 		return const_iterator(nullptr, this, -1);
    179. 	}
    180.  
    181.     pairbool> Insert(const T& data)
    182. 	{
    183. 		iterator it = Find(kot(data));
    184. 		if (it != end())
    185. 			return make_pair(it, false);
    186. 	    //扩容
    187. 		if (_n / _tables.size() == 1)
    188. 		{
    189. 			size_t newSize = _tables.size() * 2;
    190. 			vector newTables;
    191. 			newTables.resize(newSize, nullptr);
    192. 			for (size_t i = 0; i < _tables.size(); i++)
    193. 			{
    194. 				Node* cur = _tables[i];
    195. 				while (cur)
    196. 				{
    197. 					size_t hashi = hf(kot(cur->_data)) % newTables.size();
    198. 					cur->_next = newTables[hashi];
    199. 					newTables[hashi] = cur;
    200. 				}
    201. 				_tables[i] = nullptr;
    202. 			}
    203. 			_tables.swap(newTables);
    204. 		}
    205.  
    206. 		size_t hashi = hf(kot(data)) % _tables.size();
    207. 		Node* newnode = new Node(data);
    208. 		newnode->_next = _tables[hashi];
    209. 		_tables[hashi] = newnode;
    210. 		_n++;
    211.  
    212. 		return make_pair(iterator(newnode, this, hashi), true);
    213. 	}
    214.  
    215. 	iterator Find(const K& key)
    216. 	{
    217. 		size_t hashi = hf(key) % _tables.size();
    218. 		Node* cur = _tables[hashi];
    219. 		while (cur)
    220. 		{
    221. 			if (kot(cur->_data) == key)
    222. 			{
    223. 				return iterator(cur, this, hashi);
    224. 			}
    225. 			cur = cur->_next;
    226. 		}
    227. 		return end();
    228. 	}
    229.  
    230. 	bool Erase(const K& key)
    231. 	{
    232. 		size_t hashi = hf(key) % _tables.size();
    233. 		Node* cur = _tables[hashi];
    234. 		Node* prev = nullptr;
    235. 		if (kot(cur->_data) == key)
    236. 		{
    237. 			_tables[hashi] = nullptr;
    238. 			return true;
    239. 		}
    240. 		while (cur)
    241. 		{
    242. 			if (kot(cur->_data) == key)
    243. 			{
    244. 				prev->_next = cur->_next;
    245. 				delete cur;
    246. 				return true;
    247. 			}
    248. 			prev = cur;
    249. 			cur = cur->_next;
    250. 		}
    251. 		return false;
    252. 	}
    253.  
    254. private:
    255. 	vector _tables;
    256. 	size_t _n = 0;
    257. };

     3.测试用例

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7. using namespace std;
    8. #include"HashTable.h"
    9. #include"myunordered_set.h"
    10. #include"myunordered_map.h"
    11.  
    12. void test()
    13. {
    14. 	//HashTable ht;
    15. 	//ht.Insert(make_pair("西瓜", 1));
    16. 	//HashNode* ret = ht.Find("西瓜");
    17. 	//ret->_kv.second++;
    18. 	//cout << ret->_kv.first << ":" << ret->_kv.second << endl;;
    19. 	//ht.Insert(make_pair("桃子", 1));
    20. 	//ht.Insert(make_pair("桃子", 2));
    21. 	//ht.Insert(make_pair("苹果", 1));
    22. }
    23.  
    24. //void testset()
    25. //{
    26. //	unordered_set us;
    27. //	us.insert("西瓜");
    28. //	us.insert("香蕉");
    29. //	us.insert("苹果");
    30. //	us.insert("西瓜");
    31. //
    32. //	us.erase("西瓜");
    33. //	HashNode* ret = us.find("香蕉");
    34. //	cout << ret->_data << endl;
    35. //}
    36.  
    37. //void testmap()
    38. //{
    39. //	string arr[] = { "西瓜", "香蕉", "西瓜", "苹果", "西瓜", "西瓜", "香蕉", "西瓜" };
    40. //	unordered_map up;
    41. //	for (auto e : arr)
    42. //	{
    43. //		HashNode>* ret = up.find(e);
    44. //		if (ret)
    45. //		{
    46. //			ret->_data.second++;
    47. //			cout << ret->_data.first << ":" << ret->_data.second << endl;
    48. //
    49. //		}
    50. //		else
    51. //		{
    52. //			up.insert(make_pair(e, 1));
    53. //		}
    54. //	}
    55. //	
    56. //}
    57.  
    58. void test_set()
    59. {
    60. 	// 17:05
    61. 	unordered_set<int> us;
    62. 	us.insert(5);
    63. 	us.insert(15);
    64. 	us.insert(52);
    65. 	us.insert(3);
    66.  
    67. 	unordered_set<int>::iterator it = us.begin();
    68. 	while (it != us.end())
    69. 	{
    70. 		cout << *it << " ";
    71. 		++it;
    72. 	}
    73. 	cout << endl;
    74.  
    75. 	for (auto e : us)
    76. 	{
    77. 		cout << e << " ";
    78. 	}
    79. 	cout << endl;
    80. }
    81.  
    82. void test_map()
    83. {
    84. 	//unordered_map dict;
    85. 	//dict.insert(make_pair("sort", ""));
    86. 	//dict.insert(make_pair("string", "ַ"));
    87. 	//dict.insert(make_pair("insert", ""));
    88.  
    89. 	//for (auto& kv : dict)
    90. 	//{
    91. 	//	//kv.first += 'x';
    92. 	//	kv.second += 'x';
    93.  
    94. 	//	cout << kv.first << ":" << kv.second << endl;
    95. 	//}
    96. 	//cout << endl;
    97.  
    98. 	string arr[] = { "西瓜", "苹果", "苹果", "胡萝卜", "梨子", "橘子", "哈密瓜", "桃子", "西瓜", "西瓜", "梨子" };
    99. 	unordered_mapint> count_map;
    100. 	for (auto& e : arr)
    101. 	{
    102. 		count_map[e]++;
    103. 	}
    104.  
    105. 	for (auto& kv : count_map)
    106. 	{
    107. 		cout << kv.first << ":" << kv.second << endl;
    108. 	}
    109. 	cout << endl;
    110. }
    111.  
    112. int main()
    113. {
    114. 	//test();
    115. 	//testset();
    116. 	//testmap();
    117. 	//test_set();
    118. 	test_map();
    119. 	return 0;
    120. }

  • 相关阅读:
    强化学习从基础到进阶-案例与实践[2]：马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代
    寻找更好的分类模型loss
    嵌入式学习-qt-Day4
    我们公司使用了6年的Spring Boot项目部署方案，打包 + 一键部署，稳的一批
    【斗破年番】蝎毕岩决战小医仙，魂殿铁护法出场，彩鳞再霸气护夫
    SSM框架--Spring配置文件
    敏捷.敏捷项目管理第二版.Jim Highsmith
    洛谷100题DAY6
    C/C++test——高效完成白盒测试
    React 重${}【ES6 引入了模板字符串解决这个问题】
  • 原文地址：https://blog.csdn.net/Pursue_Harmony/article/details/134485211