用哈希表封装unordered_map与unordered_set
哈希表封装unordered_map与unordered_set
- 1. 源码及框架分析
- 2. 模拟实现unordered_map和unordered_set
- 2.1 实现出复⽤哈希表的框架,并⽀持insert
- 2.2 ⽀持iterator的实现
- 2.3 map⽀持[]
- 2.4 TSY::unordered_map和TSY::unordered_set代码实现
1. 源码及框架分析
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);
const_iterator find(const key_type& key) const;
};
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>
• 需要注意的是源码⾥⾯跟map/set源码类似,命名⻛格⽐较乱,这⾥⽐map和set还乱,hash_set模板参数居然⽤的Value命名,hash_map⽤的是Key和T命名,可⻅⼤佬有时写代码也不规范,乱弹琴。下⾯我们模拟⼀份⾃⼰的出来,就按⾃⼰的⻛格⾛了。
2. 模拟实现unordered_map和unordered_set
2.1 实现出复⽤哈希表的框架,并⽀持insert
• 参考源码框架,unordered_map和unordered_set复⽤之前我们实现的哈希表。
• 我们这⾥相⽐源码调整⼀下,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⽐较相等,具体细节参考如下代码实现。
// MyUnorderedSet.h
namespace bit
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
bool insert(const K& key)
{
return _ht.Insert(key);
}
private:
hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}
// MyUnorderedMap.h
namespace bit
{
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:
bool insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
private:
hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
};
}
//hashtable.h
namespace hash_bucket
{
template<class T>
struct HashData
{
T _data;
HashData<T>* _next;
HashData(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 HashIterator
{
typedef HashData<T> Node;
typedef HashTable<k, T, KeyOfT, Hash> Table;
typedef HashIterator<k, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const Table* _tb;
HashIterator( Node* node, Table* table) :
_node(node), _tb(table)
{}
Self operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(_node->_data)) % _tb->_table.size();
hashi++;
while (hashi < _tb->_table.size())
{
_node = _tb->_table[hashi];
if (_node)
break;
else
hashi++;
}
if (hashi == _tb->_table.size())
{
_node = nullptr;
}
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class k, class T, class KeyOfT, class Hash>
class HashTable
{
typedef HashData<T> Node;
public:
template<class k, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct HashIterator;
typedef HashIterator<k, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HashIterator<k, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
HashTable() :
_table(__stl_next_prime(0)),
_n(0)
{}
Iterator Begin()
{
if (_n==_table.size())
{
return End();
}
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
return Iterator(_table[i], this);
}
return End();
}
Iterator End()
{
return Iterator(nullptr, this);
}
ConstIterator Begin()const
{
if (_n == _table.size())
{
return End();
}
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
return Iterator(_table[i], this);
}
return End();
}
ConstIterator End()const
{
return Iterator(nullptr, *this);
}
pair<Iterator,bool> Insert(const T& data)
{
Hash hs;
KeyOfT kot;
Iterator it = Find(kot(data));
if (it!=End())
return { it,false };
//不允许冗余
if (_n / _table.size() == 1)
{
//扩容
vector<Node*> tmp;
tmp.resize(__stl_next_prime(_table.size() + 1));
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t Hashi = hs(kot(cur->_data)) % tmp.size();
cur->_next = tmp[Hashi];
tmp[Hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
swap(tmp, _table);
}
size_t hashi = hs(kot(data)) % _table.size();
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
_n++;
return { Iterator(newnode,this),true };
}
Iterator Find(const k& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (hs(key) == hs(kot(cur->_data)))
return Iterator(cur, this);
cur = cur->_next;
}
return End();
}
bool Erase(const k& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _table.size();
Node* Prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (hs(kot(cur->_data)) == key)
{
if (Prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
Prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
Prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector< HashData<T>*> _table;
size_t _n;
};
}
2.2 ⽀持iterator的实现
iterator核⼼源代码
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
hashtable;
typedef __hashtable_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
iterator;
typedef __hashtable_const_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
node* cur;
hashtable* ht;
__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
bool operator!=(const iterator& it) const { return cur != it.cur; }
};
template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{
const node* old = cur;
cur = cur->next;
if (!cur) {
size_type bucket = ht->bkt_num(old->val);
while (!cur && ++bucket < ht->buckets.size())
cur = ht->buckets[bucket];
}
return *this;
}
iterator实现思路分析
• 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;
2.3 map⽀持[]
• unordered_map要⽀持[]主要需要修改insert返回值⽀持,修改HashTable中的insert返回值为
pair<Iterator, bool> Insert(const T& data)
2.4 TSY::unordered_map和TSY::unordered_set代码实现
unordered_map
#include"HashTable.h"
namespace TSY
{
template<class k, class T, class Hash = HashFunc<k>>
class unordered_map
{
struct KeyOfMap
{
const k& operator()(const pair<k,T>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<k, pair<k, T>, KeyOfMap, Hash> ::Iterator iterator;
typedef typename hash_bucket::HashTable<k, pair<k, T>, KeyOfMap, Hash>::Iterator const_iterator;
pair<iterator, bool> insert(const pair<k, T>& kv)
{
return _h.Insert(kv);
}
iterator begin()
{
return _h.Begin();
}
iterator end()
{
return _h.End();
}
const_iterator begin()const
{
return _h.Begin();
}
const_iterator end()const
{
return _h.End();
}
T& operator[](const k& key)
{
pair<iterator, bool > ret = insert({key,T()});
return ret.first->second;
}
private:
hash_bucket::HashTable<k, pair<k, T>, KeyOfMap, Hash> _h;
};
}
unordered_set
#include"HashTable.h"
namespace TSY
{
template<class k, class Hash = HashFunc<k>>
class unordered_set
{
struct KeyOfSet
{
const k& operator()(const k& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<k, k, KeyOfSet, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<k, k, KeyOfSet, Hash>::Iterator const_iterator;
void insert(const k& key)
{
_h.Insert(key);
}
iterator begin()
{
return _h.Begin();
}
iterator end()
{
return _h.End();
}
const_iterator begin()const
{
return _h.Begin();
}
const_iterator end()const
{
return _h.End();
}
private:
hash_bucket::HashTable<k, k, KeyOfSet, Hash> _h;
};
}
test.cpp
#include"HashTable.h"
#include"unordered_map.h"
#include"unordered_set.h"
void test1()
{
TSY::unordered_map<string, int> Map;
Map.insert({ "apple",1 });
Map.insert({ "banana",1 });
Map.insert({ "penapple",1 });
Map.insert({ "bucket",1 });
/*for (auto& e : Map)
{
cout << e.first << " " << e.second << endl;
}*/
Map["apple"] = { 4 };
Map["tsy"] = { 20 };
for (auto& e : Map)
{
cout << e.first << " " << e.second << endl;
}
}
void test2()
{
TSY::unordered_set<string> set;
set.insert("apple");
set.insert("wanxi");
set.insert("songxueyu");
set.insert("maishuiguo");
for (auto& e : set)
{
cout << e << " " << endl;
}
cout << endl;
}
int main()
{
test1();
return 0;
}