C++ unordered_map unordered_set 模拟实现

1. 关于unordered_map 和 unordered_set

namespace open_hash
{template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:struct Node{std::pair<K, V> kv;Node* next;Node(const std::pair<K, V>& KV = std::pair<K, V>()) : kv(KV),next(nullptr){}};public:HashTable(): _load_factor(1.0),_n(0) {_hash.resize(10, nullptr);}~HashTable(){for (auto& node : _hash){while (node){Node* next = node->next;delete node;node = next;}}}size_t size() const{return _n;}Node* find(const K& key){size_t hash_index = _hash_func(key) % _hash.capacity();Node* node = _hash[hash_index];while (node){if (node->kv.first == key)return node;node = node->next;}return nullptr;}bool insert(std::pair<K, V> kv){if (find(kv.first))return false;if (1.0 * _n / _hash.capacity() >= _load_factor){size_t capacity = _hash.capacity() == 0 ? 10 : 2 * _hash.capacity();HashTable<K, V, Hash> new_hash;new_hash._hash.resize(capacity, nullptr);//将原来哈希桶中的节点转移到新的桶中for (auto& node : _hash){while (node){//从新计算映射关系size_t hash_index = _hash_func(node->kv.first) % new_hash._hash.capacity();Node* next = node->next;node->next = new_hash._hash[hash_index];new_hash._hash[hash_index] = node;node = next;}}_hash.swap(new_hash._hash);}Node* newnode = new Node(kv);size_t hash_index = _hash_func(kv.first) % _hash.capacity();//头插newnode->next = _hash[hash_index];_hash[hash_index] = newnode;++_n;return true;}bool erase(const K& key){size_t hash_index = _hash_func(key) % _hash.capacity();Node* node = _hash[hash_index];Node* prev = nullptr;while (node){if (node->kv.first == key){if (prev == nullptr)_hash[hash_index] = _hash[hash_index]->next;elseprev->next = node->next;delete node;--_n;return true;}prev = node;node = node->next;}return false;}private:std::vector<Node*> _hash;double _load_factor;Hash _hash_func;size_t _n;};
}

2. 模拟实现

2.1 修改哈希表的类模板参数

如果想要用同一份哈希表代码来模拟实现出unordered_map和unordered_set两份容器，就需要考虑一个问题：

• unordered_set是Key结构的；而unordered_map是Key_Value结构的

• 在上面的哈希表代码中，我们直接使用的就是KV模型，因此就需要想办法来屏蔽这种差异

可以通过这样的方式来解决：

将哈希表的模板参数改成这样：

template<class K, class T, class KeyOfT, class Hash>

K：Key值的类型

T：表示要存放什么类型的数据。

• 对于unordered_set，填写的就是K
• 对于unordered_set，填写的就是std::pair<K, V>
  

Hash：计算哈希值的哈希函数

KeyOfT：获得键值Key的函数

• 由于哈希表自己不知道存储的数据到底是Key模型的还是Key_Value模型的

• 因此需要通过一个函数KeyOfT来获得数据的键值

• 而这个KeyOfT由封装哈希表的unordered_map和unordered_set来提供

  类似这样：

  对于unordered_map，Key值是pair.first

  template <class K, class V, class Hash = HashFunc<const K>>
  class unordered_map
  {struct MapKeyOfT{const K operator()(const std::pair<const K, V>& p) const { return p.first;}};
  public:using HT = typename HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>;private:HT _ht;
  };
  

  对于unordered_set，Key值就是自己本身

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

2.2 哈希表的迭代器实现

注：STL中的unordered_map(set)​只支持正向迭代器，不支持反向迭代器

规定：哈希表迭代器的begin()，为第一个不为空的哈希桶中的第一个节点；哈希表迭代器的end()，为nullptr

对于哈希表的迭代器，我们只需要关注operator++()即可

对于开散列哈希桶的哈希表，当其迭代器向后移动一位之后，可能出现两种情况：

• 移动之后，不为空，说明这个哈希桶（单链表）还没有走完，那么直接返回这个节点即可

• 移动之后，为空，说明这个哈希桶（单链表）已经走完了

  • 那么就找下一个不为空的哈希桶，并返回这个哈希桶的第一个节点
  • 如果找不到下一个不为空的哈希桶了，就返回end()

通过上面的分析我们发现，对于哈希表的迭代器类，其需要两个成员来完成迭代工作：

• ​Node​​ ：用于迭代当前所在的哈希桶
• ​HashTable​​ ：用于迭代所有的哈希桶

根据上面的分析，我么可以实现出哈希表迭代器：

//非const迭代器
template<class K, class T, class KeyOfT, class Hash = HashFunc<const K>>
struct __HashIterator
{using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;using HT = typename HashTable<K, T, KeyOfT, Hash>;using Self = typename  __HashIterator< K, T, KeyOfT, Hash>;Node* node;HT* ht;__HashIterator(Node* n, HT* h) : node(n), ht(h) {}//前置++Self& operator++(){//如果已经是end()，直接返回if (nullptr == node)return *this;Node* next = node->next;if (next != nullptr)	//如果哈希桶还没走完，就迭代到哈希桶的下一个{node = next;return *this;}//否则，找到下一个非空哈希桶size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();while (++hash_index < ht->_hash.capacity()){//找到了，就迭代到这个非空哈希桶的第一个节点if (ht->_hash[hash_index]){node = ht->_hash[hash_index];return *this;}}//走到这里，说明已经把哈希数组走完了（不需要往回走）//也就是把所有的哈希桶走完了//即走到end() nullptrnode = nullptr;return *this;}//后置++Self operator++(int){Self temp = *this;this->operator++();return temp;}bool operator==(const Self& it) const{return node == it.node;}bool operator!=(const Self& it) const{return node != it.node;}T& operator*() const{return node->data;}T* operator->() const{return &node->data;}
};//const迭代器
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __HashConstIterator
{using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;using HT = typename HashTable<K, T, KeyOfT, Hash>;using Self = typename  __HashConstIterator< K, T, KeyOfT, Hash>;const Node* node;const HT* ht;__HashConstIterator(const Node* n, const HT* h) : node(n), ht(h) {}//前置++Self& operator++(){if (nullptr == node)return *this;Node* next = node->next;if (next != nullptr){node = next;return *this;}size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();while (++hash_index < ht->_hash.capacity()){if (ht->_hash[hash_index]){node = ht->_hash[hash_index];return *this;}}//走到这里，说明已经把哈希数组走完了（不需要往回走）//也就是把所有的哈希桶走完了//即走到尾 nullptrnode = nullptr;return *this;}//后置++Self operator++(int){Self temp = *this;this->operator++();return temp;}bool operator==(const Self& it) const{return node == it.node;}bool operator!=(const Self& it) const{return node != it.node;}const T& operator*() const{return node->data;}const T* operator->() const{return &node->data;}
};

2.3 修改哈希表部分函数的返回值

后续我们模拟实现unordered_set和unordered_map的接口都是直接调用其内部封装的哈希表的接口

因此，为了符合规范，我们需要对原先哈希表部分函数的返回值进行修改

find()

以unordered_map的成员函数find()为例：

iterator find ( const key_type& k );
const_iterator find ( const key_type& k ) const;

• 对于非const对象，返回非const迭代器
• 对于const对象，返回const迭代器

iterator find(const K& key)
{size_t hash_index = _hash_func(key) % _hash.capacity();Node* node = _hash[hash_index];while (node){if (_key_of_t(node->data) == key)return iterator(node, this);node = node->next;}return iterator(nullptr, this);
}const_iterator find(const K& key) const 
{size_t hash_index = _hash_func(key) % _hash.capacity();Node* node = _hash[hash_index];while (node){if (_key_of_t(node->data) == key)return const_iterator(node, this);node = node->next;}return const_iterator(nullptr, this);
}

insert()

以unordered_map的成员函数insert()为例：

pair<iterator,bool> insert ( const value_type& val );

可见，返回值是一个pair<iterator,bool>，其含义如下：

• 如果哈希表中已经有相同关键字的元素，那么就表示插入失败，并返回指向这个相同关键字元素的迭代器
• 如果哈希表中没有相同关键字的元素，那么就插入成功，并返回这个指向新插入的元素的迭代器

std::pair<iterator, bool> insert(const T& data)
{auto it = find(_key_of_t(data));if (it != end())return std::make_pair(it, false);if (1.0 * _n / _hash.capacity() >= _load_factor){size_t capacity = _hash.capacity() == 0 ? 10 : 2 * _hash.capacity();HashTable<K, T, KeyOfT, Hash> new_hash;new_hash._hash.resize(capacity, nullptr);//将原来哈希桶中的节点转移到新的桶中for (auto& node : _hash){while (node){//从新计算映射关系size_t hash_index = _hash_func(_key_of_t(node->data)) % new_hash._hash.capacity();Node* next = node->next;node->next = new_hash._hash[hash_index];new_hash._hash[hash_index] = node;node = next;}}_hash.swap(new_hash._hash);}Node* newnode = new Node(data);size_t hash_index = _hash_func(_key_of_t(data)) % _hash.capacity();//头插newnode->next = _hash[hash_index];_hash[hash_index] = newnode;++_n;return std::make_pair(iterator(newnode, this), true);
}

erase()

以unordered_map的成员函数erase()为例：

by position (1)	iterator erase ( const_iterator position );by key (2)	size_type erase ( const key_type& k );

1. 通过迭代器删除

   • 如果删除成功，就返回指向被删除元素的下一个元素的迭代器
   • 如果删除失败，就返回end()

2. 通过关键字Key删除

   • 如果删除成功，返回true
   • 如果删除失败，返回false

iterator erase(const_iterator pos)
{//不能删除end()if (pos == cend())return cend();size_t hash_index = _key_of_t(*pos) % _hash.capacity();Node* node = _hash[hash_index];Node* prev = nullptr;Node* next = nullptr;while (node){if (_key_of_t(node->data) == _key_of_t(*pos)){if (prev == nullptr)_hash[hash_index] = _hash[hash_index]->next;elseprev->next = node->next;delete node;--_n;//找到下一个节点next = (prev == nullptr) ? _hash[hash_index] : prev->next;if (next == nullptr){while (++hash_index < _hash.capacity()){if (_hash[hash_index]){next = _hash[hash_index];break;}}}return iterator(next, this);}prev = node;node = node->next;}return end();
}bool erase(const K& key)
{size_t hash_index = _hash_func(key) % _hash.capacity();Node* node = _hash[hash_index];Node* prev = nullptr;while (node){if (_key_of_t(node->data) == key){if (prev == nullptr)_hash[hash_index] = _hash[hash_index]->next;elseprev->next = node->next;delete node;--_n;return true;}prev = node;node = node->next;}return false;
}

开散列哈希表实现代码

namespace open_hash
{template<class K, class T, class KeyOfT, class Hash = HashFunc<const K>>class HashTable;template<class K, class T, class KeyOfT, class Hash = HashFunc<const K>>struct __HashIterator{using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;using HT = typename HashTable<K, T, KeyOfT, Hash>;using Self = typename  __HashIterator< K, T, KeyOfT, Hash>;Node* node;HT* ht;__HashIterator(Node* n, HT* h) : node(n), ht(h) {}//前置++Self& operator++(){if (nullptr == node)return *this;Node* next = node->next;if (next != nullptr){node = next;return *this;}size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();while (++hash_index < ht->_hash.capacity()){if (ht->_hash[hash_index]){node = ht->_hash[hash_index];return *this;}}//走到这里，说明已经把哈希数组走完了（不需要往回走）//也就是把所有的哈希桶走完了//即走到尾 nullptrnode = nullptr;return *this;}//后置++Self operator++(int){Self temp = *this;this->operator++();return temp;}bool operator==(const Self& it) const{return node == it.node;}bool operator!=(const Self& it) const{return node != it.node;}T& operator*() const{return node->data;}T* operator->() const{return &node->data;}};template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>struct __HashConstIterator{using Node = typename HashTable<K, T, KeyOfT, Hash>::Node;using HT = typename HashTable<K, T, KeyOfT, Hash>;using Self = typename  __HashConstIterator< K, T, KeyOfT, Hash>;const Node* node;const HT* ht;__HashConstIterator(const Node* n, const HT* h) : node(n), ht(h) {}//支持非const迭代器到const迭代器的类型转换__HashConstIterator(const __HashIterator<K, T, KeyOfT>& it) : node(it.node), ht(it.ht) {}//前置++Self& operator++(){if (nullptr == node)return *this;Node* next = node->next;if (next != nullptr){node = next;return *this;}size_t hash_index = Hash()(KeyOfT()(node->data)) % ht->_hash.capacity();while (++hash_index < ht->_hash.capacity()){if (ht->_hash[hash_index]){node = ht->_hash[hash_index];return *this;}}//走到这里，说明已经把哈希数组走完了（不需要往回走）//也就是把所有的哈希桶走完了//即走到尾 nullptrnode = nullptr;return *this;}//后置++Self operator++(int){Self temp = *this;this->operator++();return temp;}bool operator==(const Self& it) const{return node == it.node;}bool operator!=(const Self& it) const{return node != it.node;}const T& operator*() const{return node->data;}const T* operator->() const{return &node->data;}};template<class K, class T, class KeyOfT, class Hash>class HashTable{friend struct __HashIterator<K, T, KeyOfT, Hash>;;friend struct __HashConstIterator<K, T, KeyOfT, Hash>;public:struct Node{T data;Node* next;Node(const T& Data = T()) : data(Data),next(nullptr){}};public:using iterator = __HashIterator<K, T, KeyOfT, Hash>;using const_iterator = __HashConstIterator<K, T, KeyOfT, Hash>;using HT = HashTable<K, T, KeyOfT, Hash>;public:HashTable(): _load_factor(1.0),_n(0) {_hash.resize(10, nullptr);}//拷贝构造HashTable(const HT& ht):_load_factor(ht._load_factor),_n(ht._n),_hash_func(ht._hash_func),_key_of_t(ht._key_of_t){_hash.resize(ht._hash.capacity(), nullptr);for (auto& node : ht._hash){Node* cur = node;while (cur){size_t hash_index = _hash_func(_key_of_t(cur->data)) % _hash.capacity();Node* newnode = new Node(cur->data);newnode->next = _hash[hash_index];_hash[hash_index] = newnode;cur = cur->next;}}}//移动构造HashTable(HT&& ht){swap(ht);}HT& operator=(const HT& ht){HT temp(ht);swap(temp);return *this;}//移动赋值HT& operator=(HT&& ht){swap(ht);return *this;}~HashTable(){for (auto& node : _hash){while (node){Node* next = node->next;delete node;node = next;}}}void swap(HT& ht){std::swap(_hash, ht._hash);std::swap(_n, ht._n);std::swap(_hash_func, ht._hash_func);std::swap(_key_of_t, ht._key_of_t);std::swap(_load_factor, ht._load_factor);}iterator begin(){//找到第一个非空的哈希桶for (auto& node : _hash){if (node)return iterator(node, this);}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{//找到第一个非空的哈希桶for (auto& node : _hash){if (node)return const_iterator(node, this);}return const_iterator(nullptr, this);}const_iterator cbegin() const{//找到第一个非空的哈希桶for (auto& node : _hash){if (node)return const_iterator(node, this);}return const_iterator(nullptr, this);}const_iterator end() const{return const_iterator(nullptr, this);}const_iterator cend() const{return const_iterator(nullptr, this);}size_t size() const{return _n;}iterator find(const K& key){size_t hash_index = _hash_func(key) % _hash.capacity();Node* node = _hash[hash_index];while (node){if (_key_of_t(node->data) == key)return iterator(node, this);node = node->next;}return iterator(nullptr, this);}const_iterator find(const K& key) const {size_t hash_index = _hash_func(key) % _hash.capacity();Node* node = _hash[hash_index];while (node){if (_key_of_t(node->data) == key)return const_iterator(node, this);node = node->next;}return const_iterator(nullptr, this);}std::pair<iterator, bool> insert(const T& data){auto it = find(_key_of_t(data));if (it != end())return std::make_pair(it, false);if (1.0 * _n / _hash.capacity() >= _load_factor){size_t capacity = _hash.capacity() == 0 ? 10 : 2 * _hash.capacity();HashTable<K, T, KeyOfT, Hash> new_hash;new_hash._hash.resize(capacity, nullptr);//将原来哈希桶中的节点转移到新的桶中for (auto& node : _hash){while (node){//从新计算映射关系size_t hash_index = _hash_func(_key_of_t(node->data)) % new_hash._hash.capacity();Node* next = node->next;node->next = new_hash._hash[hash_index];new_hash._hash[hash_index] = node;node = next;}}_hash.swap(new_hash._hash);}Node* newnode = new Node(data);size_t hash_index = _hash_func(_key_of_t(data)) % _hash.capacity();//头插newnode->next = _hash[hash_index];_hash[hash_index] = newnode;++_n;return std::make_pair(iterator(newnode, this), true);}iterator erase(const_iterator pos){//不能删除end()if (pos == cend())return cend();size_t hash_index = _key_of_t(*pos) % _hash.capacity();Node* node = _hash[hash_index];Node* prev = nullptr;Node* next = nullptr;while (node){if (_key_of_t(node->data) == _key_of_t(*pos)){if (prev == nullptr)_hash[hash_index] = _hash[hash_index]->next;elseprev->next = node->next;delete node;--_n;//找到下一个节点next = (prev == nullptr) ? _hash[hash_index] : prev->next;if (next == nullptr){while (++hash_index < _hash.capacity()){if (_hash[hash_index]){next = _hash[hash_index];break;}}}return iterator(next, this);}prev = node;node = node->next;}return end();}bool erase(const K& key){size_t hash_index = _hash_func(key) % _hash.capacity();Node* node = _hash[hash_index];Node* prev = nullptr;while (node){if (_key_of_t(node->data) == key){if (prev == nullptr)_hash[hash_index] = _hash[hash_index]->next;elseprev->next = node->next;delete node;--_n;return true;}prev = node;node = node->next;}return false;}private:std::vector<Node*> _hash;double _load_factor;Hash _hash_func;KeyOfT _key_of_t;size_t _n;};
}

2.4 unordered_set 模拟实现

namespace lwj
{using namespace open_hash;template <class K, class Hash = HashFunc<const K>>class unordered_set{struct SetKeyOfT{const K operator()(const K& key) const{return key;}};public:using HT = typename HashTable<K, const K, SetKeyOfT, Hash>;using iterator = typename HT::iterator;using const_iterator = typename HT::const_iterator;using Self = typename unordered_set<K, Hash>;//支持默认构造unordered_set() = default;//拷贝构造unordered_set(const Self& set){_ht = set._ht;}//移动构造unordered_set(Self&& set){_ht.swap(set._ht);}//拷贝赋值Self& operator=(const Self& set){_ht = set._ht;return *this;}//移动复赋值Self& operator=(Self&& set){_ht.swap(set._ht);return *this;}bool count(const K& key) const{return find(key) != end();}iterator find(const K& key){return _ht.find(key);}const_iterator find(const K& key) const{return _ht.find(key);}std::pair<iterator, bool> insert(const K& val){return _ht.insert(val);}bool erase(const K& key){return _ht.erase(key);}iterator erase(const_iterator pos){return _ht.erase(pos);}iterator begin(){return _ht.begin();}const_iterator begin() const{return _ht.cbegin();}const_iterator cbegin() const{return _ht.cbegin();}iterator end(){return _ht.end();}const_iterator end() const{return _ht.cend();}const_iterator cend() const{return _ht.cend();}private:HT _ht;};
}

2.5 unordered_map 模拟实现

operator[] ()

mapped_type& operator[] ( const key_type& k );
mapped_type& operator[] ( key_type&& k );

V& operator[](const K& key)
{//无论inset成功插入与否，其都会返回一个指向key值的迭代器std::pair<iterator, bool> p = insert({ key, V() });return p.first->second;
}

整体实现

namespace lwj
{using namespace open_hash;template <class K, class V, class Hash = HashFunc<const K>>class unordered_map{struct MapKeyOfT{const K operator()(const std::pair<const K, V>& p) const { return p.first;}};public:using HT = typename HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>;using iterator = typename HT::iterator;using const_iterator = typename HT::const_iterator;using Self = typename unordered_map<K, V, Hash>;//支持默认构造unordered_map() = default;//拷贝构造unordered_map(const Self& map){_ht = map._ht;}//移动构造unordered_map(Self&& map){_ht.swap(map._ht);}//拷贝赋值Self& operator=(const Self& map){_ht = map._ht;return *this;}//移动赋值Self& operator=(Self&& map){_ht.swap(map._ht);return *this;}V& operator[](const K& key){std::pair<iterator, bool> p = insert({ key, V() });return p.first->second;}bool count(const K& key) const{return find(key) != end();}iterator find(const K& key){return _ht.find(key);}const_iterator find(const K& key) const{return _ht.find(key);}std::pair<iterator, bool> insert(const std::pair<const K, V>& val){return _ht.insert(val);}bool erase(const K& key){return _ht.erase(key);}iterator erase(const_iterator pos){return _ht.erase(pos);}iterator begin(){return _ht.begin();}const_iterator begin() const{return _ht.cbegin();}iterator end(){return _ht.end();}const_iterator end() const{return _ht.cend();}private:HT _ht;};
}