快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

STL库中，set类和map类都是红黑树作为底层实现的，与之类似，unordered系列的unordered_set类和unordered_map类，都是通过哈希表作为底层来实现的。

一、哈希表（改造版）

1.1 结点

template<class T>
struct HashNode
{HashNode<T>* _next;T _data;HashNode(const T& data): _next(nullptr), _data(data){}
};

细节：

• 将数据类型改为T，因为要同时适用unordered_set（存储键值）和unordered_map（存储键值对）

1.2 迭代器

改造后的哈希表，最重要的功能之一就是支持单向迭代器

template<class K, class T, class KeyOfT, class Hash>
class HashTable;//前置声明template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HashIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> Ht;typedef HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;typedef HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;Node* _node;const Ht* _ht;HashIterator(Node* node, const Ht* ht): _node(node), _ht(ht){}HashIterator(const Iterator& it): _node(it._node), _ht(it._ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(operator*());}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

细节：

1. 一些基本的迭代器范式操作已经给出，重点的++操作后面详细实现
2. 增加_ht成员变量，原因：当一条单链表走到空，则需要走到下一个哈希桶的位置，需要哈希表的地址
3. 这里存在相互引用的问题，所以前置声明哈希表
4. const修饰_ht，使const迭代器能够被构造
5. 迭代器的拷贝构造函数有两个用途：
   • 以普通迭代器拷贝出普通迭代器（普通迭代器调用时）
   • 以普通迭代器拷贝出const迭代器（const迭代器调用时）

1.2.1 operator++

Self& operator++()
{if (_node->_next){_node = _node->_next;}else{int flag = 0;size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();for (size_t i = hashi + 1; i < _ht->_tables.size(); ++i){if (_ht->_tables[i]){_node = _ht->_tables[i];flag = 1;break;}}if (!flag){_node = nullptr;}}return *this;
}Self operator++(int)
{Self tmp = *this;++*this;return tmp;
}

细节：

1. 前置++的思路：
   • 下一个结点不为空，则跳到下一位
   • 下一个结点为空，则先取模算出哈希地址，再往后探测不为空的哈希桶
2. 后置++：复用前置++，返回临时对象

1.3 本体

1.3.1 成员变量和默认成员函数

template<class K, class T, class KeyOfT, class Hash>
class HashTable
{template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct HashIterator;
protected:typedef HashNode<T> Node;
public:HashTable(){_tables.resize(10);}~HashTable(){for (auto& cur : _tables){while (cur){Node* del = cur;cur = cur->_next;delete del;}}}
protected:vector<Node*> _tables;size_t _n = 0;//有效数据个数
};

细节：

1. 将迭代器声明为友元，使迭代器内部可操作_tables
2. 第三个模板参数为KeyOfT（仿函数类型），用于获取不同数据T的键值key来进行比较
3. 第四个模板参数为Hash（仿函数类型），用于将不同类型key转换为整型来进行取模

1.3.2 begin和end

typedef HashIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
typedef HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;iterator begin()
{for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){return iterator(_tables[i], this);}}return iterator(nullptr, this);
}const_iterator begin() const
{for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){return const_iterator(_tables[i], this);}}return const_iterator(nullptr, this);
}iterator end()
{return iterator(nullptr, this);
}const_iterator end() const
{return const_iterator(nullptr, this);
}

细节：

1. begin返回最开始不为空的哈希桶的迭代器，end返回空迭代器
2. 构造迭代器需要传入哈希表本身的地址，这里直接传this指针即可

1.3.3 Find

iterator Find(const K& key)
{size_t hashi = Hash()(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (KeyOfT()(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return iterator(nullptr, this);
}

细节：

1. 返回迭代器
2. 运用两个仿函数，Hash转整型，KeyOfT获取键值

1.3.4 Insert

pair<iterator, bool> Insert(const T& data)
{KeyOfT kot;iterator it = Find(kot(data));if (it._node)//保持key唯一{return make_pair(it, false);}Hash hash;if (_n == _tables.size())//负载因子为1时，扩容{size_t newsize = _tables.size() * 2;vector<Node*> newtables(newsize);for (auto& cur : _tables){while (cur){Node* next = cur->_next;//将旧表结点重新映射到新表上size_t hashi = hash(kot(cur->_data)) % newsize;cur->_next = newtables[hashi];newtables[hashi] = cur;//跳回旧表的下一结点cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kot(data)) % _tables.size();Node* newnode = new Node(data);//头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), true);
}

细节：

1. 返回pair，第一个参数为迭代器，第二个参数为布尔值（记录是否插入成功）
2. 运用两个仿函数，Hash转整型，KeyOfT获取键值

1.3.5 Erase

bool Erase(const K& key)
{size_t hashi = Hash()(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (KeyOfT()(cur->_data) == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;
}

细节：运用两个仿函数，Hash转整型，KeyOfT获取键值

二、unordered_set

2.1 成员变量与仿函数

template<class K, class Hash = HashFunc<K>>
class unordered_set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public:
protected:HashTable<K, K, SetKeyOfT, Hash> _ht;
};

细节：

1. unordered_set类仿函数，直接返回参数key
2. 成员变量的第二个模板参数为K，第三个模板参数为SetKeyOfT
3. 模板Hash可以根据特定需要而传手动实现的哈希化函数

2.2 begin和end

typedef typename HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;iterator begin()
{return _ht.begin();
}const_iterator begin() const
{return _ht.begin();
}iterator end()
{return _ht.end();
}const_iterator end() const
{return _ht.end();
}

细节：

1. 加上typename关键字，编译器才能识别类型
2. unordered_set中存储的键值key均不允许修改，所以其普通迭代器和const迭代器均为哈希表的const迭代器
3. 由于unordered_set的普通迭代器也是哈希表的const迭代器，调用普通begin()时，便有从普通迭代器到const迭代器的转换，此时之前写的拷贝构造（以普通迭代器拷贝构造const迭代器）便派上用场了。

2.3 find

iterator find(const K& key)
{return _ht.Find(key);
}

2.4 insert

pair<iterator, bool> insert(const K& key)
{return _ht.Insert(key);
}

细节：

1. 插入参数类型为K（键值）
2. 此时也有从普通迭代器到const迭代器的转换

2.5 erase

bool erase(const K& key)
{return _ht.Erase(key);
}

三、unordered_map

3.1 成员变量与仿函数

template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};
public:
protected:HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};

细节：

1. unordered_map类仿函数，返回参数pair的first
2. 成员变量的第二个模板参数为pair，第三个模板参数为MapKeyOfT
3. 模板Hash可以根据特定需要而传手动实现的哈希化函数

3.2 begin和end

typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;iterator begin()
{return _ht.begin();
}const_iterator begin() const
{return _ht.begin();
}iterator end()
{return _ht.end();
}const_iterator end() const
{return _ht.end();
}

细节：

1. 加上typename关键字，编译器才能识别类型
2. unordered_map同样不允许修改key，故加上const修饰，但是允许修改存储的value，所以普通和const迭代器一一对应

3.3 find

iterator find(const K& key)
{return _ht.Find(key);
}

3.4 insert

pair<iterator, bool> insert(const pair<const K, V>& kv)
{return _ht.Insert(kv);
}

细节：插入参数类型为pair（键值对）

3.5 operator[ ]

unordered_map最好用的重载运算符[ ]，我们肯定也要实现，平常插入和修改使用[ ]更加方便。

V& operator[](const K& key)
{pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;
}

细节：

1. 插入成功便是插入，插入失败便是查找+修改
2. 返回value的引用，可以直接插入或修改

3.6 erase

bool erase(const K& key)
{return _ht.Erase(key);
}

真诚点赞，手有余香