unordered —— 无序的，从表面上来看，与 map 和 set 不同之处就在于，unordered_map 和 unordered_set 无法保证插入数据是有序的；
尽管如此，由于这两种容器内部封装了“哈希桶”，可以实现快速查找数据 —— 这一优点与 map 和 set 相同。
其实，除了内部结构的不同外，其余与 map 和 set 没什么不同，一样的 insert、find、erase … … 在我们模拟过 map set 的基础上，再学习封装 无序map 和 无序set 实在简单。
因此，本文的重点在于迭代器的运行逻辑 —— operator++() ，和理解模板、仿函数等。
最后，补充一个概念：
哈希是一种思想，将传入的数据映射成一个或多个整型；哈希表 / 哈希桶则是一种实现哈希思想的结构。
一、改造哈希桶
1.1 初步搭建 HashTable
// 改造 HashNode
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_next(nullptr)
,_data(data)
{}
};
// 改造 HashTable
// 此处 HashFunc 与《开散列哈希桶》中提供的无异
// KeyOfT 与 map set 中的无异，都是用于从 T 中取到键值
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
public:
typedef HashNode<T> Node;
private:
vector<Node*> _tables;
size_t _n = 0;
};
1.2 数据插入 数据查找
- 数据插入 —— Insert()
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
iterator ret = Find(kot(data)); // 未实现的 Find，返回值为 iterator
if (ret != end())// 找到了
{
return make_pair(ret, false);
}
// 扩容
// ...
// 插入
Hash hs;
size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
_n++;
return make_pair(new_iterator, true); // 此处为伪代码！
}
与普通哈希桶不同的地方在于此： size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值 ，多套了一层仿函数。
PS：
-
扩容逻辑与哈希桶完全一致。
-
return make_pair(new_iterator, true);为伪代码，用new_iterator代表插入节点的迭代器 —— 后面介绍迭代器时，会将这里的坑填上！
- 数据查找 —— Find()
很多新手不理解为什么在封装 map set 要这样构造 —— 好像传入了两个 Key ：
map: RBTree<K, pair<const K, V>, ... > _t;
set: RBTree<K, const K, ...> _t;
我们通常是 t.find(key1); t,erase(key2); 这种方式使用 find() 和 erase() ，无论 t 是 map 还是 set。
意思就是，第一个模板参数 K 是为了解决 map 的查找和删除等的问题。
iterator Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator_cur; // 这里同样是伪代码！
}
cur = cur->_next;
}
return iterator_nullptr;// 伪代码
}
iterator_cur 代表 cur 位置的迭代器； iterator_nullptr 代表 空迭代器，这两个迭代器的空白会在后面填补。
二、迭代器封装 __Hash_Iterator
__Hash_Iterator 内部应该传入什么呢？节点的指针吗？哈希桶的指针吗？
我们希望可以通过迭代器遍历整个哈希桶，同时要能取到当前迭代器所在节点的数据，因此，迭代器内部应有节点的指针和哈希桶的指针。
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __Hash_Iterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HashTable;
typedef __Hash_Iterator<K, T, KeyOfT, Hash> Self;
Node* _node;
HashTable* _ht;
__Hash_Iterator(Node* node, HashTable* ht)
:_node(node)
,_ht(ht)
{}
};
2.1 operator++()
operator++() 需要考虑两种情形：
- _node->_next 不为空，++ 后，_node = _node->_next
- _node->_next 为空，则往后遍历 HashTable，直到找到下一个不为空的位置，或者遍历完整个 HashTable 。
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
hashi++; // 从当前位置的后一个位置开始查找
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
// 找到下一个位置，跳出循环
_node = _ht->_tables[hashi];
break;
}
++hashi;
}
if (hashi == _ht->_tables.size()) // 遍历结束，没有下一个节点
{
_node = nullptr;
}
}
return *this;
}
2.2 operator!=() operator*() operator->()
bool operator!=(const Self& s)
{
return _node != s._node;
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
2.3 完善 HashTable
针对第一部分中迭代器遗留问题，在这里将其完善。
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
public:
typedef HashNode<T> Node;
typedef __Hash_Iterator<K, T, KeyOfT, Hash> iterator;
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
Hash hs;
iterator ret = Find(kot(data)); // 未实现的 Find，返回值为 iterator
if (ret != end())// 找到了
{
return make_pair(ret, false);
}
// 扩容
if (_n == _tables.size())
{
vector<Node*> newTables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hs(kot(cur->_data)) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
// 插入
size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
_n++;
return make_pair(iterator(newNode, this), true); //
}
iterator Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return iterator(nullptr, this);
}
bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr) // cur == _tables[hashi]
{
_tables[hashi]->_next = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
2.4 begin() end()
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
三、unordered_map unordered_set 封装
unordered_map
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
public:
struct MapKeyOfT
{
K operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
unordered_set
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
public:
struct SetKeyOfT
{
K operator()(const K& key)
{
return key;
}
};
typedef typename HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
private:
HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
注意：
如果直接将以上代码在 VS 中运行，会出现以下几个错误：
该问题的原因是，在 __Hash_Iterator 之前并未声明 HashTable 。
template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值
class HashTable; // 声明
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __Hash_Iterator
{
// ...
};
该问题在于，__Hash_Iterator 无法访问 HashTable 的 private 成员变量，解决办法是将 __Hash_Iterator 写成 HashTable 的友元类。
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
public:
template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值
friend struct __Hash_Iterator; // 友元
// ...
};
四、完整代码
My_Unordered_Map.h
#include "HashTable.h"
namespace MY_Test
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
public:
struct MapKeyOfT
{
K operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
void test_map1()
{
unordered_map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
for (auto& kv : dict)
{
//kv.first += 'x';
kv.second += 'y';
cout << kv.first << ":" << kv.second << endl;
}
}
void test_map2()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };
unordered_map<string, int> countMap;
for (auto& e : arr)
{
/*if (e == "ݮ")
{
int i = 0;
}*/
countMap[e]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
}
My_Unordered_Set.h
#include "HashTable.h"
namespace MY_Test
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
public:
struct SetKeyOfT
{
K operator()(const K& key)
{
return key;
}
};
typedef typename HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
private:
HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
void test_set1()
{
unordered_set<int> us;
us.insert(3);
us.insert(1);
us.insert(5);
us.insert(15);
us.insert(45);
us.insert(7);
unordered_set<int>::iterator it = us.begin();
while (it != us.end())
{
//*it += 100;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : us)
{
cout << e << " ";
}
cout << endl;
}
}
HashTable.h
#include <vector>
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
size_t hash = key;
return hash;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash = hash * 131 + e;
}
return hash;
}
};
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_next(nullptr)
, _data(data)
{}
};
template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值
class HashTable; // 声明
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __Hash_Iterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HashTable;
typedef __Hash_Iterator<K, T, KeyOfT, Hash> Self;
Node* _node;
HashTable* _ht;
__Hash_Iterator(Node* node, HashTable* ht)
:_node(node)
, _ht(ht)
{}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
hashi++; // 从当前位置的后一个位置开始查找
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
// 找到下一个位置，跳出循环
_node = _ht->_tables[hashi];
break;
}
++hashi;
}
if (hashi == _ht->_tables.size()) // 遍历结束，没有下一个节点
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
};
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
public:
typedef HashNode<T> Node;
typedef __Hash_Iterator<K, T, KeyOfT, Hash> iterator;
template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值
friend struct __Hash_Iterator; // 友元
HashTable()
{
_tables.resize(10);
}
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
Hash hs;
iterator ret = Find(kot(data)); // 未实现的 Find，返回值为 iterator
if (ret != end())// 找到了
{
return make_pair(ret, false);
}
// 扩容
if (_n == _tables.size())
{
vector<Node*> newTables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hs(kot(cur->_data)) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
// 插入
size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
_n++;
return make_pair(iterator(newNode, this), true); //
}
iterator Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return iterator(nullptr, this);
}
bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr) // cur == _tables[hashi]
{
_tables[hashi]->_next = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
![[图解]实现领域驱动设计译文暴露的问题04](https://img-blog.csdnimg.cn/direct/5b1a9564908f4267a25284033e14cd68.png)
