文章目录
1 哈希表的基本改造
基本框架的改造：
namespace BucketHash
{
template<class T>
struct BucketHashNode
{
BucketHashNode* _next;
T _data;
BucketHashNode(const T& data)
:_next(nullptr)
,_data(data)
{}
};
template<class K>
struct HashTranfor
{
size_t operator()(const K& k)
{
return (size_t)k;
}
};
//特化一个版本出来
template<>
struct HashTranfor<string>
{
// BKDR
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}
return val;
}
};
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
};
template<class K, class T,class Hash,class KeyOfT>//给出第一个模板参数的目的是为了Insert
//时能够正确将K插入
class HashTable
{
private:
typedef BucketHashNode<T> Node;
vector<Node*> _tables;
size_t _size = 0;
public:
size_t GetCapacity(size_t sz)
{
int i = 0;
for (; i < __stl_num_primes; ++i)
{
if (sz < __stl_prime_list[i]) break;
}
return __stl_prime_list[i];
}
~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;
}
}
size_t Size()const
{
return _tables.size();
}
size_t BucketSize()const
{
int cnt = 0;
for (int i = 0; i < Size(); ++i)
{
if (_tables[i])
++cnt;
}
return cnt;
}
size_t MaxBucketSize()const
{
int maxLen = 0;
for (int i = 0; i < Size(); ++i)
{
Node* cur = _tables[i];
int len = 0;
while (cur)
{
++len;
cur = cur->_next;
}
maxLen = max(maxLen, len);
}
return maxLen;
}
};
注意：
2 迭代器
封装中最重要的一环就是迭代器了，那么究竟该如何设计迭代器呢？
2.1 迭代器的大致框架
首先我们来想想：迭代器究竟该有哪些成员？
由于迭代器要支持++操作（这里的迭代器不支持- -操作，因为是单向迭代器(底层用的是单链表)),所以我们得来方便我们遍历，我们还需要来帮助我们取数据。
所以我们就能够搭建出迭代器的大致框架了：
//前置声明
template<class K, class T, class Hash, class KeyOfT>
class HashTable;
//迭代器
template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
struct __TableIterator
{
typedef BucketHashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfT> HTable;
typedef __TableIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
typedef __TableIterator<K, T, T&, T*, Hash, KeyOfT> Iterator;
Node* _node;//结点指针，方便取数据
HTable* _ht;//找到哈希表
__TableIterator(Node* node,HTable* ht)
:_node(node)
,_ht(ht)
{}
__TableIterator(const Iterator& it)
:_node(it._node)
,_ht(it._ht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator==(const Self& self)const
{
return self._node == _node;
}
bool operator!=(const Self& self)const
{
return self._node != _node;
}
};
注意：迭代器的成员变量由于用到了哈希桶结构，而哈希桶的实现在迭代器的下面，所以我们要在迭代器前面加上一个前置声明。
现在的关键是如何实现出++运算符的重载。
2.2 ++运算符重载的实现
其实这个的实现也不难，我们已经拿到了哈希表，所以只需要从当前位置找到表中下一个位置即可：
Self& operator++()
{
if (_node->_next)
_node = _node->_next;
else
{
Hash hash;
KeyOfT kot;
size_t hashi = hash(kot(_node->_data)) % _ht->Size();
++hashi;
for (; hashi < _ht->Size(); ++hashi)
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
}
if (hashi == _ht->Size())
_node = nullptr;
}
return *this;
}
但是还有一个问题：我们哈希表的实现中成员变量是私有的，所以迭代器是不能够访问的，为了方便我们可以在哈希表结构中加上友元声明，当然大家自己也可以实现get接口取数据，方法有很多，大家可以自行选择。
class HashTable
{
private:
template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
friend struct __TableIterator;
typedef BucketHashNode<T> Node
};
2.3 哈希表的完善
template<class K, class T,class Hash,class KeyOfT>//给出第一个模板参数的目的是为了Insert
//时能够正确将K插入
class HashTable
{
private:
template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
friend struct __TableIterator;
typedef BucketHashNode<T> Node;
vector<Node*> _tables;
size_t _size = 0;
public:
typedef __TableIterator<K, T, T&, T*, Hash, KeyOfT> iterator;
typedef __TableIterator<K, T, const T&, const T*, Hash, KeyOfT> const_iterator;
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);
}
const_iterator begin()const
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
return const_iterator(_tables[i], this);
}
return end();
}
const_iterator end()const
{
return const_iterator(nullptr, this);
}
size_t GetCapacity(size_t sz)
{
int i = 0;
for (; i < __stl_num_primes; ++i)
{
if (sz < __stl_prime_list[i]) break;
}
return __stl_prime_list[i];
}
~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;
Hash hash;
auto ret = Find(kot(data));
if (ret != end())
return make_pair(ret, false);
//扩容，负载因子为1
if (_size == _tables.size())
{
//int newcapacity = _tables.size() == 0 ? 10 : _tables.size() * 2;
int newcapacity =GetCapacity(_tables.size());
vector<Node*> newTables;//这里直接用vector的目的是可以直接用原表的结点直接链接即可
//不必多拷贝结点
newTables.resize(newcapacity);
for (int i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
//头插
while (cur)
{
Node* next = cur->_next;
size_t hashi = hash(kot(cur->_data)) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur=next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = hash(kot(data)) % _tables.size();
Node* newNode = new Node(data);//这里不要加kot
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_size;
return make_pair(iterator(newNode,this), true);
}
iterator Find(const K& k)
{
if (_tables.size()==0)
return end();
KeyOfT kot;
Hash hash;
size_t hashi = hash(k) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == k)
return iterator(cur,this);
cur = cur->_next;
}
return end();
}
bool Erase(const K& k)
{
if (Find(k) == nullptr)
return false;
KeyOfT kot;
Hash hash;
size_t hashi = hash(k) % _tables.size();
if (kot(_tables[hashi]->_data) == k)
{
Node* del = _tables[hashi];
_tables[hashi] = del->_next;
delete del;
--_size;
return true;
}
Node* cur = _tables[hashi];
while (cur->_next && kot(cur->_next->_data) != k)
{
cur = cur->_next;
}
Node* del = cur->_next;
cur->_next = del->_next;
delete del;
--_size;
return true;
}
size_t Size()const
{
return _tables.size();
}
size_t BucketSize()const
{
int cnt = 0;
for (int i = 0; i < Size(); ++i)
{
if (_tables[i])
++cnt;
}
return cnt;
}
size_t MaxBucketSize()const
{
int maxLen = 0;
for (int i = 0; i < Size(); ++i)
{
Node* cur = _tables[i];
int len = 0;
while (cur)
{
++len;
cur = cur->_next;
}
maxLen = max(maxLen, len);
}
return maxLen;
}
};
注意：由于迭代器的构造中我们需要哈希表的指针，而恰好，所以我们传入this即可。另外find和inset时为了与STL保持一致，我们将返回值分别修改为iterator和pair<terator,bool>。
3 unordered_map和unordered_set的封装
但是unordered_set中这样实现就会有一些问题：我们用了普通迭代器构造了const迭代器，这样肯定是会编译报错的，所以在迭代器的中我们还得增加一个构造：
typedef __TableIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
typedef __TableIterator<K, T, T&, T*, Hash, KeyOfT> Iterator;
Node* _node;//结点指针
HTable* _ht;//找到哈希表
__TableIterator(const Iterator& it)
:_node(it._node)
,_ht(it._ht)
{}
这样如果上层传入的是普通迭代器那么就是一个拷贝构造，传入的是const迭代器的话就是用了普通迭代器构造const迭代器。这点大家一定要注意。
3.1 unordered_map
template<class K, class V, class Hash = BucketHash::HashTranfor<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};
private:
BucketHash::HashTable<K, pair<const K,V>, Hash, MapKeyOfT> _tab;
public:
typedef typename BucketHash::HashTable<K, pair<const K,V>, Hash, MapKeyOfT>::iterator iterator;
//这里要加上typename 的原因是告诉编译器这里是模板的声明而不是静态成员的声明
iterator begin()
{
return _tab.begin();
}
iterator end()
{
return _tab.end();
}
pair<iterator, bool> insert(const pair<K,V>& kv)
{
return _tab.Insert(kv);
}
V& operator[](const K& k)
{
auto ret = _tab.Insert(make_pair(k, V()));
return ret.first->second;
}
};
3.2 unordered_set
template<class K, class Hash = BucketHash::HashTranfor<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
private:
BucketHash::HashTable<K, K, Hash, SetKeyOfT> _tab;
public:
typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator;
//这里要加上typename 的原因是告诉编译器这里是模板的声明而不是静态成员的声明
typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _tab.begin();
}
iterator end()
{
return _tab.end();
}
const_iterator begin()const
{
return _tab.begin();
}
const_iterator end()const
{
return _tab.end();
}
pair<iterator, bool> insert(const K& k)
{
return _tab.Insert(k);
}
};
好了，这样封装基本上大致框架也就完成了。
如果该文对你有帮助的话能不能一键三连支持博主呢？💘💘💘