C++学习：哈希表unordered_set/unordered_map的封装
·
前面我们已经学习过哈希表的底层结构，本期就让我们结合STL源码的内容和以往实现的哈希表对unordered_map和unordered_set进行封装
相关内容作者的个人gitee：楼田莉子/CPP代码学习喜欢请点个赞谢谢
目录
源码及框架分析
SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表，只容器的名字是hash_map和hash_set，他是作为⾮标准的容器出现的，⾮标准是指⾮C++标准规定必须实现的，源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中
hash_map和hash_set的实现结构框架核⼼部分截取出来如下：
//为了可读性作者稍稍改了一下格式
// stl_hash_set
template <class Value, class HashFcn = hash<Value>,class EqualKey = equal_to<Value>,
class Alloc = alloc>
class hash_set
{
private:
typedef hashtable<Value, Value, HashFcn, identity<Value>,EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::const_iterator iterator;
typedef typename ht::const_iterator const_iterator;
hasher hash_funct() const { return rep.hash_funct(); }
key_equal key_eq() const { return rep.key_eq(); }
}
// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>,
class EqualKey = equal_to<Key>,class Alloc = alloc>
class hash_map
{
private:
typedef hashtable<pair<const Key, T>, Key, HashFcn,
select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef T data_type;
typedef T mapped_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::iterator iterator;
typedef typename ht::const_iterator const_iterator;
};
// stl_hashtable.h
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,class Alloc>
class hashtable
{
public:
typedef Key key_type;
typedef Value value_type;
typedef HashFcn hasher;
typedef EqualKey key_equal;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node<Value> node;
vector<node*,Alloc> buckets;
size_type num_elements;
public:
typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
Alloc> iterator;
pair<iterator, bool> insert_unique(const value_type& obj);
};
template <class Value>
struct __hashtable_node
{
__hashtable_node* next;
Value val;
}通过源码可以看到，结构上hash_map和hash_set跟map和set的完全类似，复⽤同⼀个hashtable实现key和key/value结构，hash_set传给hash_table的是两个key，hash_map传给hash_table的是pair<const key, value>
接下来我们就来对unordered_set/unordered_map进行模拟实现
实现出复用哈希表的框架，并支持insert
key参数就⽤K，value参数就⽤V，哈希表中的数据类型，我们使⽤T。
map和set相⽐⽽⾔unordered_map和unordered_set的模拟实现类结构更复杂⼀点，但是
⼤框架和思路是完全类似的。
因为HashTable实现了泛型不知道T参数导致是K，还是pair<K, V>，那么insert内部进⾏插⼊时要⽤K对象转换成整形取模和K⽐较相等，因为pair的value不参与计算取模，且默认⽀持的是key和value⼀起⽐较相等，我们需要时的任何时候只需要⽐较K对象，所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K⽐较相等
//unordered_set.h
#pragma once
#include"HashTable2.h"
namespace The_Song_of_the_end_of_the_world
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
pair<iterator, bool> insert(const K& k)
{
return _t.Insert(k);
}
private:
HashTable<K, const K, SetKeyOfT, Hash> _t;
};
}
//unordered_map.h
#pragma once
#include"HashTable2.h"
namespace The_Song_of_the_end_of_the_world
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _t;
};
}
//HashTable2.h
#pragma once
#include<vector>
#include<utility>
#include<string>
using namespace std;
namespace The_Song_of_the_end_of_the_world
{
//STL源码：https://github.com/microsoft/STL/blob/master/stl/inc/hash_table.h
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
typedef HashNode<T> Node;
public:
HashTable()
:_tables(__stl_next_prime(1), nullptr)
, _n(0)
{
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 当前桶的节点重新映射挂到新表
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
auto it = Find(kot(data));
if (it != End())
return { it, false };
Hash hs;
// 负载因子==1扩容
if (_n == _tables.size())
{
//HashTable<K, V> newHT;
//newHT._tables.resize(_tables.size()*2);
//// 遍历旧表将所有值映射到新表
//for (auto cur : _tables)
//{
// while (cur)
// {
// newHT.Insert(cur->_kv);
// cur = cur->_next;
// }
//}
//_tables.swap(newHT._tables);
vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
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();
// 头插
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return { Iterator(newNode, this), true };
}
Iterator Find(const K& key)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
return { cur, this };
cur = cur->_next;
}
return End();
}
private:
//vector<list<pair<K, V>>> _tables;
vector<Node*> _tables;
size_t _n = 0; // 实际存储的数据个数
};
}
迭代器的实现
思路：
iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算符实现，迭代器像指针⼀样访问的⾏为，要注意的是哈希表的迭代器是单向迭代器。
这⾥的难点是operator++的实现。iterator中有⼀个指向结点的指针，如果当前桶下⾯还有结点，则结点的指针指向下⼀个结点即可。如果当前桶⾛完了，则需要想办法计算找到下⼀个桶。这⾥的难点是反⽽是结构设计的问题，参考上⾯的源码，我们可以看到iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶⾛完了，要计算下⼀个桶就相对容易多了，⽤key值计算出当前桶位置，依次往后找下⼀个不为空的桶即可。
begin()返回第⼀个桶中第⼀个节点指针构造的迭代器，这⾥end()返回迭代器可以⽤空表⽰。
unordered_set的iterator也不⽀持修改，我们把unordered_set的第⼆个模板参数改成const K即可，
HashTable<K, const K, SetKeyOfT, Hash> _ht;unordered_map的iterator不⽀持修改key但是可以修改value，我们把unordered_map的第⼆个模板参数pair的第⼀个参数改成const K即可
HashTable<K, pair<const K, V>,MapKeyOfT, Hash> _ht;模拟实现
//unordered_set.h
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin() const
{
return _t.Begin();
}
const_iterator end() const
{
return _t.End();
}
private:
HashTable<K, const K, SetKeyOfT, Hash> _t;
};
//unordered_map.h
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin() const
{
return _t.Begin();
}
const_iterator end() const
{
return _t.End();
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _t;
};
}
//HashTable2.h
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
// 前置声明
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 HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const HT* _ht;
HTIterator(Node* node, const HT* ht)
:_node(node)
, _ht(ht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next) // 当前还有节点
{
_node = _node->_next;
}
else // 当前桶为空，找下一个不为空的桶的第一个
{
size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi != _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
hashi++;
}
// 最后一个桶的最后一个节点已经遍历结束，走到end()去，nullptr充当end()
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
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 HTIterator;
typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
Iterator Begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return Iterator(_tables[i], this);
}
}
return End();
}
Iterator End()
{
return Iterator(nullptr, this);
}
ConstIterator Begin() const
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return ConstIterator(_tables[i], this);
}
}
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
};map实现[]
unordered_map要⽀持[]主要需要修改insert返回值⽀持，修改HashTable中的insert返回值为
pair<Iterator, bool> Insert(const T& data)通过insert实现[]插入
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}源码
unordered_set.h
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin() const
{
return _t.Begin();
}
const_iterator end() const
{
return _t.End();
}
pair<iterator, bool> insert(const K& k)
{
return _t.Insert(k);
}
bool erase(const K& key)
{
return _t.Erase(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
HashTable<K, const K, SetKeyOfT, Hash> _t;
};unordered_map.h
#pragma once
#include"HashTable2.h"
namespace The_Song_of_the_end_of_the_world
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin() const
{
return _t.Begin();
}
const_iterator end() const
{
return _t.End();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
bool erase(const K& key)
{
return _t.Erase(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _t;
};
}HashTable2.h
#pragma once
#include<vector>
#include<utility>
#include<string>
using namespace std;
namespace The_Song_of_the_end_of_the_world
{
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
// BKDR
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto ch : str)
{
hash += ch;
hash *= 131;
}
return hash;
}
};
inline unsigned long __stl_next_prime(unsigned long n)
{
//STL源码：https://github.com/microsoft/STL/blob/master/stl/inc/hash_table.h
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{
}
};
// 前置声明
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 HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const HT* _ht;
HTIterator(Node* node, const HT* ht)
:_node(node)
, _ht(ht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next) // 当前还有节点
{
_node = _node->_next;
}
else // 当前桶为空，找下一个不为空的桶的第一个
{
size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi != _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
hashi++;
}
// 最后一个桶的最后一个节点已经遍历结束，走到end()去，nullptr充当end()
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
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 HTIterator;
typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
Iterator Begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return Iterator(_tables[i], this);
}
}
return End();
}
Iterator End()
{
return Iterator(nullptr, this);
}
ConstIterator Begin() const
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return ConstIterator(_tables[i], this);
}
}
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
:_tables(__stl_next_prime(1), nullptr)
, _n(0)
{
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 当前桶的节点重新映射挂到新表
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
auto it = Find(kot(data));
if (it != End())
return { it, false };
Hash hs;
// 负载因子==1扩容
if (_n == _tables.size())
{
//HashTable<K, V> newHT;
//newHT._tables.resize(_tables.size()*2);
//// 遍历旧表将所有值映射到新表
//for (auto cur : _tables)
//{
// while (cur)
// {
// newHT.Insert(cur->_kv);
// cur = cur->_next;
// }
//}
//_tables.swap(newHT._tables);
vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
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();
// 头插
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return { Iterator(newNode, this), true };
}
Iterator Find(const K& key)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
return { cur, this };
cur = cur->_next;
}
return End();
}
bool Erase(const K& key)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
//vector<list<pair<K, V>>> _tables;
vector<Node*> _tables;
size_t _n = 0; // 实际存储的数据个数
};
}本期内容就到这里了，喜欢请点个赞谢谢
封面图自取：
更多推荐
13
0- 0
已为社区贡献17条内容
所有评论(0)