前言
前面我们对哈希表进行了介绍并用线性探测和哈希桶两种方式进行了实现！本期我们在上期的基础上对哈希表进行改造，并封装出unordered_map和unordered_set！
本期内容介绍
• 改造哈希表的存储
• 实现哈希表的迭代器
• 对哈希表类进行完善
• 基于哈希表封装unordered_map和unordered_set
• 改造哈希表的存储
我们目前的哈希表只是可以存储pair的键值对，但是我们知道unordered_map和unordered_set，一个存在是K，一个存在的是<K,V>的键值对，难道我们得用两个哈希表分别来封装吗？显然不是的，前面map和set的封装也是同类的问题，他们底层用的是一颗红黑树，我们这里也是底层只用一个哈希表！那如何只用一个哈希表呢？答案是将哈希表和红黑树一样进行改造！本期我们就用拉链法实现的哈希表来封装unordered_map和unordered_set！
回忆一下map和set的封装：
可以看到，set的K和V都是K，而map的K就是K，V是pair<K,V>；当时我们是将红黑树的存储做了修改将其原本的pair<K,V>键值对修改成了T，上层给K，T就是K，上层给pair<K,V>就是键值对！
这里的思路和map和set的思路一模一样，也是这样做的！
template<class T>
struct HashNode
{
T _data;//存储的元素的类型改为T，T是什么上层决定
HashNode<T>* _next;//后继指针
//构造函数初始化
HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};• 如果存的T是pair，哈希表那一层如何知道是K还是piar呢？又如何获取K计算哈希地址呢？
其实很简单，哈希表那一层是不知道T是啥，但是上层的unordered_map和unordered_set知道所以和map和set一样，传一个获取当前K的类型给哈希表的末班参数即可，等需要获取T的K的时候创建获取K类的对象，调用提供的仿函数即可！
当把节点中存储的数据类型修改为T后，此时哈希表类的模板参数也需要修改：
相对应的其他接口也是需要改变的：
其他的就不在一一列举了，想获取K必须用KeyOfT的对象调用仿函数，原先的pair一律换成T!
OK，我们下来实现一下哈希表的迭代器：
• 实现哈希表的迭代器
哈希表的迭代器实现起来思路很简单！和前面链表以及红黑树的实现思路一样！
我们还是先回忆一下，用迭代器访问需要什么？OK是不是要：++，->, * , !=, begin, 以及end但是，begin和end迭代器类并不知道从哪里就开始和结束，他两是哈希表类才知道的，所以我们只需要实现其他的即可！
思路：我们需要一个节点的指针，由于我们在哈希表中遍历，所以需要一个哈希表的指针，我们这里只是遍历不修改，所以可以把哈希表的指针用const修饰！然后除了++以外的其他操作都是和以前的一模一样的！
//迭代器类的实现
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct _HTIterator
{
typedef _HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;//迭代器类
typedef HashNode<T> Node;//哈希表的节点
const HashTable<K, T, KeyOfT, Hash>* _pht;//指向哈希表的指针，这是只对哈希表查找
Node* _node;//迭代器节点指针
_HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
:_node(node)
,_pht(pht)
{}
Ref operator*()
{
return _node->_data;//返回该迭代器的指针节点指向的数据
}
Ptr operator->()
{
return &_node->_data;//返回该迭代器的指针节点指向的数据的地址
}
bool operator!=(const Self& it)
{
return _node != it._node;//直接比较两个迭代器节点的地址不等即可
}
bool operator==(const Self& it)
{
return _node == it._node;//直接比较两个迭代器节点的地址相等即可
}
};下面我们来单独讨论一下++：
思路：如果当前迭代器对象的节点指针的next不为空，++下一个节点就是当爱你节点的next，如果当节点的next为空，说明当前桶访问完了，下一个访问的下一个非空桶的内容！
Self& operator++()
{
//当前节点的后一个不为空
if (_node->_next)
{
_node = _node->_next;//++后迭代器的节点指针，指向当前节点的下一个
}
else
{
Hash hs;//获取key值对应整数的对象
KeyOfT kot;//获取key值的对象
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();//计算哈希地址
++hashi;//++一下hashi，看下一个桶
while (hashi < _pht->_tables.size())
{
Node* cur = _pht->_tables[hashi];
if (cur != nullptr)//找到一个不为空的桶
break;//跳出循环
++hashi;
}
//hashi已经到哈希表的结尾了
if (hashi == _pht->_tables.size())
_node = nullptr;//让_node节点指向空
else
_node = _pht->_tables[hashi];//让_node节点指向当前不为空的桶
}
return *this;//返回该迭代器对象
}我们现在有很尴尬的问题就是：
• 我们把迭代器类放到那个位置呢？把由于编译器是向上查找，把迭代器的类放到哈希表类的上面，此时迭代器类的上面没有哈希表的类，而用到了哈希表对象的指针，就会出报错！如果将迭代器的类放到哈希表类的下面，此时哈希表中访问迭代器又找不到迭代器了！！！如何解决呢？
• 解决方案：可以将迭代器类依旧放在哈希表类的上面，然后在迭代器类的上面进行哈希表类的声明即可！（内部类也可以）
• 迭代器类在哈希表的上面，而在迭代器其中要用哈希表对象的指针，即访问_tables，而_tables是哈希表的私有成员，也就是即使有声明迭代器还是访问不到哈希表！如何解决？
• 解决方案：上述的不变，可以在哈希表类中进行迭代器类的声明！
迭代器源码
//哈希表的前置声明
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 _HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;//迭代器类
typedef HashNode<T> Node;//哈希表的节点
const HashTable<K, T, KeyOfT, Hash>* _pht;//指向哈希表的指针，这是只对哈希表查找
Node* _node;//迭代器节点指针
_HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
:_node(node)
,_pht(pht)
{}
Ref operator*()
{
return _node->_data;//返回该迭代器的指针节点指向的数据
}
Ptr operator->()
{
return &_node->_data;//返回该迭代器的指针节点指向的数据的地址
}
bool operator!=(const Self& it)
{
return _node != it._node;//直接比较两个迭代器节点的地址不等即可
}
bool operator==(const Self& it)
{
return _node == it._node;//直接比较两个迭代器节点的地址相等即可
}
Self& operator++()
{
//当前节点的后一个不为空
if (_node->_next)
{
_node = _node->_next;//++后迭代器的节点指针，指向当前节点的下一个
}
else
{
Hash hs;//获取key值对应整数的对象
KeyOfT kot;//获取key值的对象
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();//计算哈希地址
++hashi;//++一下hashi，看下一个桶
while (hashi < _pht->_tables.size())
{
Node* cur = _pht->_tables[hashi];
if (cur != nullptr)//找到一个不为空的桶
break;//跳出循环
++hashi;
}
//hashi已经到哈希表的结尾了
if (hashi == _pht->_tables.size())
_node = nullptr;//让_node节点指向空
else
_node = _pht->_tables[hashi];//让_node节点指向当前不为空的桶
}
return *this;//返回该迭代器对象
}
};• 对哈希表类进行完善
拷贝构造
思路：先让当前的哈希表对象走默认构造，让表的大小为要拷贝表的长度，然后遍历要拷贝的表，如果当前桶不为空，让当前哈希对象直接调插入，直到拷贝完所有桶的数据即可！
//拷贝构造
HashTable(const HashTable& ht)
:_tables(ht._tables.size())//设置大小为被拷贝一样的大小
, _size(0)
{
//遍历ht，将ht表中的数据插入到当前的表即可
for (auto cur : ht._tables)
{
while (cur)
{
Insert(cur->_data);
cur = cur->_next;
}
}
}赋值拷贝
赋值拷贝有两种写法：传统写法和现代写法！
传统写法：先判断是不是给字赋值，然后再将当前的表调用Clear方法清空，最后遍历被拷贝的表，如果当前桶不为空，直接调Insert，直到将所有不为空的桶遍历完！
现代写法：先判断是不是给字赋值，将形参不要加引用，因为形参是实参的拷贝所以可以与当前对象交换即可！现代写法本质是一种复用~！
//赋值拷贝 -> 现代写法
HashTable& operator=(HashTable ht)
{
if (this != &ht)//自己不要给自己赋值
{
_tables.swap(ht._tables);
_size = ht._size;
}
return *this;
}
//赋值拷贝 -> 传统写法
HashTable& operator=(const HashTable& ht)
{
if (this != &ht) // 自己不要给自己赋值
{
Clear(); // 清空当前对象
//遍历ht的表，如果不为空，将ht表中的 数据插入到当前的表中
for (auto cur : ht._tables)
{
while (cur)
{
Insert(cur->_data);
cur = cur->_next;
}
}
}
return *this;
}迭代器实现
先在哈希表中将迭代器类进行重命名
//迭代器
typedef _HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef _HTIterator<K, T, const T&, const T*, KeyOfT, Hash> Const_Iterator;begin
思路：找到哈希表中第一个不为空的桶，将该位置和当前的哈希表对象歘构造一个迭代器对象即可！
如何获取当前哈希表的对象呢？那个哈希表对象调掉this就是谁，所以当前的哈希表对象的指针就是this
Iterator Begin()
{
//找第一个不为空的哈希桶
for (auto& cur : _tables)
{
if (cur)
{
return Iterator(cur, this);
}
}
return End();//没找到直接返回End
}End
思路：最后一个哈希桶的下一个位置，也就是nullptr,所以可以用nullptr和this构造一个迭代器对象返回即可！
Iterator End()
{
return Iterator(nullptr, this);//最后一个和哈希桶的下一个位置
}Const_Begin
思路：用nullptr和this构造一个const迭代器对象返回即可！
Const_Iterator Begin() const
{
//找第一个不为空的哈希桶
for (auto& cur : _tables)
{
if (cur)
{
return Const_Iterator(cur, this);
}
}
return End();//没找到直接返回End
}Const_End
思路：用nullptr和this构造一个const迭代器对象返回即可！
Const_Iterator End() const
{
return Const_Iterator(nullptr, this);//最后一个和哈希桶的下一个位置
}Find
引入了迭代器之后，我们的返回值也不能再是Node*了，应该换成迭代器（方便后面的对unordered_map和unordered_map进行封装）！
Iterator Find(const K& key)
{
//表中没有元素
if (_size == 0)
return End();
Hash hs;//获取key值对应整数的对象
KeyOfT kot;//获取key值的对象
size_t hashi = hs(key) % _tables.size();//获取哈希地址
Node* cur = _tables[hashi];//获取头结点的地址
while (cur) //遍历桶
{
if (kot(cur->_data) == key)
return Iterator(cur, this);//找到了
cur = cur->_next;
}
return End();//没找到
}Insert
为了方便后续对unoreder_map的[]的封装，我们直接将Insert的返回值改造成pair<Iterator, bool>，顺便也把以前的Find进行稍微修改！
pair<Iterator, bool> Insert(const T& data)
{
Hash hs;//获取key值对应整数的对象
KeyOfT kot;//获取key值的对象
//要插入的元素在哈希表中已经存在
//if (Find(kot(data)))
//return false;
Iterator it = Find(kot(data));//要插入的元素在哈希表中已经存在
if (it != End())
return make_pair(it, false);
//扩容 - 》现代写法（效率不好，相当于将旧表中的数据节点拷贝到新表，然后再将旧表释放）
//if (_size == _tables.size())
//{
// size_t newSize = _tables.size() * 2;
// HashTable<K, T, KeyOfT, Hash> newTable;
// newTable._tables.resize(newSize);
// //遍历旧表
// for (auto& cur : _tables)
// {
// while (cur)
// {
// newTable.Insert(cur->_data);
// cur = cur->_next;
// }
// }
// _tables.swap(newTable._tables);
//}
//扩容 -> 传统写法（直接将旧表中的节点拿下来，映射到新表）
if (_size == _tables.size())
{
size_t newSize = _tables.size() * 2;
//创建一个新的哈希表，大小是旧表的2倍
vector<Node*> newTable(newSize, nullptr);
//遍历旧表
for (auto& cur : _tables)
{
while (cur)
{
Node* next = cur->_next;//保存下一个节点
size_t hashi = hs(kot(cur->_data)) % newTable.size();//算出当前节点在新表中的哈希地址
//头插映射到新表
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;//当前节点的指针指向下一个节点
}
cur = nullptr;//将一个桶映射完了，将该位置置空
}
_tables.swap(newTable);//交换新表和旧表
}
//插入
size_t hashi = hs(kot(data)) % _tables.size();
Node* newnode = new Node(data);
//头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
_size++;//有效元素+1
return make_pair(Iterator(newnode, this), true);
}删除没有要改的，就是在遍历桶对比Key时应该使用KeyOfT的对象获取T的key!Size， Clear以及Empty都不变！
Count
这是新增的一个接口！它的作用是通过key判断key对应的元素在不在，如果在返回1，否则返回0！实现这个主要是为了上层封装方便，但是写到一半发现这个下层不实现，上层也可以实现，但是写了一半了就含泪写完了^_^！
思路：利用Find查找key对应的元素是否存在即返回的是否是End，如果Find返回的是End说明，不存在，返回0即可，否则返回1！
size_t Count(const K& key)
{
Iterator ret = Find(key);
return ret == End() ? 0 : 1;//如果没有查找到，直接返回0，找到了返回1
}Swap
这个接口也是为了上层交换方便封装！
思路：让_tables表调用vector的swap,然后用std的swap交换_size即可
void Swap(HashTable& ht)
{
_tables.swap(ht._tables);//调用vextor的swap
std::swap(_size, ht._size);//调用std里面的将两个整数交换即可
}OK，至此，哈希表类的改造以及迭代器的实现均已完毕！下面我们就可以封装unordered_map和unordered_set了！
• 基于哈希表封装unordered_map和unordered_set
直到底层的哈希表和迭代器没问题，unordered_map和unordered_set的封装就是套一层壳！唯一有挑战的就是unordered_map的[ ]；下面也只是介绍一下[]，其他接口直接调用哈希表的即可！
[ ]在map的使用就介绍过，他是给他key值就会给你返回key对应的val引用！如何实现呢？
思路：基于插入，我们前面把哈希表中的插入修改了，返回值改成了pair<iterator, bool>就是为了这里！我们可以现将key去插入，然后返回插入返回ret的first即当前元素的指针，然后因为存的是<K,V>，在通过->second就可以获取到key对应的val的引用了！
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert({ key, V() });
return ret.first->second;
}另外，unordered_map的K是不可修改的！所以在迭代器以及，下面_ht表那里都是用const修饰的！
unordered_map源码
#pragma once
template<class K, class V, class Hash = hash_bucket::HashFunc<K>>
class my_unordered_map
{
struct KeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::_HTIterator<K, pair<const K,V>, pair<const K, V>&, pair<const K, V>*, KeyOfT, Hash> iterator;
typedef typename hash_bucket::_HTIterator<K, pair<const K,V>, const pair<const K, V>&, const pair<const K, V>*, KeyOfT, Hash> const_iterator;
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
const_iterator begin() const
{
return _ht.Begin();
}
const_iterator end() const
{
return _ht.End();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert({ key, V() });
return ret.first->second;
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
size_t size() const
{
return _ht.Size();
}
bool empty() const
{
return _ht.Empty();
}
void clear()
{
_ht.Clear();
}
size_t count(const K& key)
{
return _ht.Count(key);
}
void swap(my_unordered_map& ump)
{
_ht.Swap(ump._ht);
}
private:
hash_bucket::HashTable<K, pair<const K, V>, KeyOfT, Hash> _ht;//K不允许修改
};unordered_set源码
unordered_set注意的是他存的K也是不可修改的，所以存的K也是用const修饰的！而且防止在迭代器变中对K修改所以我们可以让正常迭代器和const迭代器都是const迭代器！（库里面就是这样做的）
#pragma once
template<class K, class Hash = hash_bucket::HashFunc<K>>
class my_unordered_set
{
struct KeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//typedef typename hash_bucket::_HTIterator<K, K, K&, K*, KeyOfT, Hash> iterator;
//这里不管是否是const迭代器，我们底层都给成const的，防止修改K
typedef typename hash_bucket::_HTIterator<K, const K, const K&, const K*, KeyOfT, Hash> const_iterator;
typedef typename hash_bucket::_HTIterator<K, const K, const K&, const K*, KeyOfT, Hash> iterator;
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
const_iterator begin() const
{
return _ht.Begin();
}
const_iterator end() const
{
return _ht.End();
}
pair<iterator, bool> insert(const K& kv)
{
return _ht.Insert(kv);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
size_t size() const
{
return _ht.Size();
}
bool empty() const
{
return _ht.Empty();
}
void clear()
{
_ht.Clear();
}
size_t count(const K& key)
{
return _ht.Count(key);
}
void swap(my_unordered_set& ust)
{
_ht.Swap(ust._ht);
}
private:
hash_bucket::HashTable<K, const K, KeyOfT, Hash> _ht;
};哈希表的源码
#pragma once
#include <vector>
namespace hash_bucket
{
template<class K>
struct HashFunc
{
//解决浮点数和负数
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>//模板的特化
struct HashFunc<string>
{
//字符串哈希算法
size_t operator()(const string& key)
{
size_t sum = 0;
for (auto& c : key)
{
sum *= 131;//乘以131可以更好的降低冲突
sum += c;
}
return sum;
}
};
template<class T>
struct HashNode
{
T _data;//存储的元素的类型改为T，T是什么上层决定
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 _HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;//迭代器类
typedef HashNode<T> Node;//哈希表的节点
const HashTable<K, T, KeyOfT, Hash>* _pht;//指向哈希表的指针，这是只对哈希表查找
Node* _node;//迭代器节点指针
_HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
:_node(node)
,_pht(pht)
{}
Ref operator*()
{
return _node->_data;//返回该迭代器的指针节点指向的数据
}
Ptr operator->()
{
return &_node->_data;//返回该迭代器的指针节点指向的数据的地址
}
bool operator!=(const Self& it)
{
return _node != it._node;//直接比较两个迭代器节点的地址不等即可
}
bool operator==(const Self& it)
{
return _node == it._node;//直接比较两个迭代器节点的地址相等即可
}
Self& operator++()
{
//当前节点的后一个不为空
if (_node->_next)
{
_node = _node->_next;//++后迭代器的节点指针，指向当前节点的下一个
}
else
{
Hash hs;//获取key值对应整数的对象
KeyOfT kot;//获取key值的对象
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();//计算哈希地址
++hashi;//++一下hashi，看下一个桶
while (hashi < _pht->_tables.size())
{
Node* cur = _pht->_tables[hashi];
if (cur != nullptr)//找到一个不为空的桶
break;//跳出循环
++hashi;
}
//hashi已经到哈希表的结尾了
if (hashi == _pht->_tables.size())
_node = nullptr;//让_node节点指向空
else
_node = _pht->_tables[hashi];//让_node节点指向当前不为空的桶
}
return *this;//返回该迭代器对象
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
typedef HashNode<T> Node;
//将迭代器进行友元声明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct _HTIterator;
public:
//迭代器
typedef _HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef _HTIterator<K, T, const T&, const T*, KeyOfT, Hash> Const_Iterator;
Iterator Begin()
{
//找第一个不为空的哈希桶
for (auto& cur : _tables)
{
if (cur)
{
return Iterator(cur, this);
}
}
return End();//没找到直接返回End
}
Iterator End()
{
return Iterator(nullptr, this);//最后一个和哈希桶的下一个位置
}
Const_Iterator Begin() const
{
//找第一个不为空的哈希桶
for (auto& cur : _tables)
{
if (cur)
{
return Const_Iterator(cur, this);
}
}
return End();//没找到直接返回End
}
Const_Iterator End() const
{
return Const_Iterator(nullptr, this);//最后一个和哈希桶的下一个位置
}
//开放地址法，没有写构造，扩容有两种情况，这里写一个构造，扩容就只是负载因子引起的
HashTable()
:_tables(4, nullptr)//一开始的大小给为4
, _size(0)
{}
//拷贝构造
HashTable(const HashTable& ht)
:_tables(ht._tables.size())//设置大小为被拷贝一样的大小
, _size(0)
{
//遍历ht，将ht表中的数据插入到当前的表即可
for (auto cur : ht._tables)
{
while (cur)
{
Insert(cur->_data);
cur = cur->_next;
}
}
}
//赋值拷贝 -> 现代写法
HashTable& operator=(HashTable ht)
{
if (this != &ht)//自己不要给自己赋值
{
_tables.swap(ht._tables);
_size = ht._size;
}
return *this;
}
//赋值拷贝 -> 传统写法
//HashTable& operator=(const HashTable& ht)
//{
// if (this != &ht) // 自己不要给自己赋值
// {
// Clear(); // 清空当前对象
//
// //遍历ht的表，如果不为空，将ht表中的 数据插入到当前的表中
// for (auto cur : ht._tables)
// {
// while (cur)
// {
// Insert(cur->_data);
// cur = cur->_next;
// }
// }
// }
// return *this;
//}
//这里必须得写析构函数，否则会出现内存泄漏
~HashTable()
{
Clear();
}
Iterator Find(const K& key)
{
//表中没有元素
if (_size == 0)
return End();
Hash hs;//获取key值对应整数的对象
KeyOfT kot;//获取key值的对象
size_t hashi = hs(key) % _tables.size();//获取哈希地址
Node* cur = _tables[hashi];//获取头结点的地址
while (cur) //遍历桶
{
if (kot(cur->_data) == key)
return Iterator(cur, this);//找到了
cur = cur->_next;
}
return End();//没找到
}
pair<Iterator, bool> Insert(const T& data)
{
Hash hs;//获取key值对应整数的对象
KeyOfT kot;//获取key值的对象
//要插入的元素在哈希表中已经存在
//if (Find(kot(data)))
//return false;
Iterator it = Find(kot(data));//要插入的元素在哈希表中已经存在
if (it != End())
return make_pair(it, false);
//扩容 - 》现代写法（效率不好，相当于将旧表中的数据节点拷贝到新表，然后再将旧表释放）
//if (_size == _tables.size())
//{
// size_t newSize = _tables.size() * 2;
// HashTable<K, T, KeyOfT, Hash> newTable;
// newTable._tables.resize(newSize);
// //遍历旧表
// for (auto& cur : _tables)
// {
// while (cur)
// {
// newTable.Insert(cur->_data);
// cur = cur->_next;
// }
// }
// _tables.swap(newTable._tables);
//}
//扩容 -> 传统写法（直接将旧表中的节点拿下来，映射到新表）
if (_size == _tables.size())
{
size_t newSize = _tables.size() * 2;
//创建一个新的哈希表，大小是旧表的2倍
vector<Node*> newTable(newSize, nullptr);
//遍历旧表
for (auto& cur : _tables)
{
while (cur)
{
Node* next = cur->_next;//保存下一个节点
size_t hashi = hs(kot(cur->_data)) % newTable.size();//算出当前节点在新表中的哈希地址
//头插映射到新表
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;//当前节点的指针指向下一个节点
}
cur = nullptr;//将一个桶映射完了，将该位置置空
}
_tables.swap(newTable);//交换新表和旧表
}
//插入
size_t hashi = hs(kot(data)) % _tables.size();
Node* newnode = new Node(data);
//头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
_size++;//有效元素+1
return make_pair(Iterator(newnode, this), true);
}
bool Erase(const K& key)
{
Hash hs;//获取key值对应整数的对象
KeyOfT kot;//获取key值的对象
size_t hashi = hs(key) % _tables.size();//计算哈希地址
Node* cur = _tables[hashi];
Node* prev = nullptr;//前驱
while (cur)
{
Node* next = cur->_next;
//找到关键码和key一样的桶了
if (kot(cur->_data) == key)
{
if (prev == nullptr)//头删
_tables[hashi] = next;
else
prev->_next = next;//正常删除
delete cur;
cur = nullptr;
--_size;
return true;
}
else//没找到继续找
{
prev = cur;
cur = next;
}
}
return false;//没找到删除的
}
size_t Size() const
{
return _size;//返回成员变量_size即可
}
bool Empty() const
{
return _size == 0;//返回_size是否==0即可
}
void Clear()
{
//遍历整个哈希表
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])//当前桶不为空
{
Node* cur = _tables[i];//当前节点的下一个位置
while (cur)
{
Node* next = cur->_next;//保存下一个节点的指针
delete cur;
cur = next;
}
_tables[i] = nullptr;//将每个桶的链表清理完了后置为空
}
}
_size = 0;//将有效元素的个数置0
}
size_t Count(const K& key)
{
Iterator ret = Find(key);
return ret == End() ? 0 : 1;//如果没有查找到，直接返回0，找到了返回1
}
void Swap(HashTable& ht)
{
_tables.swap(ht._tables);//调用vextor的swap
std::swap(_size, ht._size);//调用std里面的将两个整数交换即可
}
private:
vector<Node*> _tables;//哈希表
size_t _size;//有效元素的个数
};
}• unordered_map和unordered_set的测试
测试unordered_map
void Test_My_umap1()
{
my_unordered_map<int, int> ump;
ump.insert({ 1,1 });
ump.insert({ 2,1 });
ump.insert({ 3,1 });
ump.insert({ 4,1 });
ump.insert({ 5,1 });
for (auto& e : ump)
{
cout << e.first << " : " << e.second << endl;
}
cout << "size: " << ump.size() << endl;
cout << "empty: " << ump.empty() << endl;
ump.erase(1);
cout << "-------------------------" << endl;
Print(ump);
cout << "size: " << ump.size() << endl;
cout << "empty: " << ump.empty() << endl;
ump.clear();
Print(ump);
cout << "size: " << ump.size() << endl;
cout << "empty: " << ump.empty() << endl;
}
void Test_My_umap2()
{
my_unordered_map<string, int> ump;
string ss[] = { "aaa", "bbb", "ccc", "aaa", "ccc", "香蕉", "西瓜", "香蕉" };
for (auto& s : ss)
{
ump[s]++;//验证[]
}
for (auto& e : ump)
{
cout << e.first << " : " << e.second << endl;
}
cout << "-------------------------" << endl;
my_unordered_map<string, int> um1 = ump;//拷贝构造
for (auto& e : um1)
{
cout << e.first << " : " << e.second << endl;
}
cout << um1.size() << endl;
my_unordered_map<string, int> um2;
um2.insert({ "1a", 1 });
um2.insert({ "2b", 1 });
um2.insert({ "3c", 1 });
um2.insert({ "d4", 1 });
cout << "-------------------------" << endl;
um1 = um2;//赋值拷贝
for (auto& e : um1)
{
cout << e.first << " : " << e.second << endl;
}
}
void Test_My_umap4()
{
my_unordered_map<int, int> ump;
ump.insert({ 1,1 });
ump.insert({ 2,1 });
ump.insert({ 3,1 });
my_unordered_map<int, int> map;
map.insert({ 10,1 });
map.insert({ 20,1 });
Print(ump);
cout << endl;
Print(map);
cout << "ump.size()" << ump.size() << endl;
cout << "map.size()" << map.size() << endl;
cout << "--------------------------------------" << endl;
map.swap(ump);
Print(ump);
cout << endl;
Print(map);
cout << "ump.size()" << ump.size() << endl;
cout << "map.size()" << map.size() << endl;
auto ret = map.find(10);
if (ret != map.end())cout << ret->first << " " << ret->second << endl;
else cout << "没找到" << endl;
cout << "cnt :" << map.count(10) << endl;
}
unordered_set的测试
template<class K>
void print(const my_unordered_set<K>& ust)
{
for (auto& e : ust)
{
cout << e << endl;
}
}
void Test_My_ust1()
{
my_unordered_set<int> ust;
ust.insert(1);
ust.insert(2);
ust.insert(3);
ust.insert(4);
ust.insert(11);
for (auto& e : ust)
{
cout << e << endl;
}
cout << endl;
ust.erase(1);
print(ust);
cout << ust.count(1) << endl;
auto ret = ust.find(20);
if (ret != ust.end()) cout << *ret << endl;
else cout << "没找到" << endl;
cout << "-------------------------------" << endl;
ust.clear();
print(ust);
void Test_My_ust2()
{
my_unordered_set<int> ust;
ust.insert(1);
ust.insert(2);
ust.insert(3);
ust.insert(4);
ust.insert(11);
my_unordered_set<int> st;
st.insert(100);
st.insert(200);
st.insert(300);
print(ust);
print(st);
cout << "-------------------------------" << endl;
ust.swap(st);
print(ust);
print(st);
}
OK，测试就到这里，没有问题（其实我测了好多情况~）！
OK，本期分享就到这里，好兄弟，我们下期再见！
结束语：我见青山多妩媚，料青山见我应如是！
