欢迎来到数据结构专栏~~封装unordered_map 和 unordered_set
(꒪ꇴ꒪(꒪ꇴ꒪ ),我是Scort目前状态：大三非科班啃C++中博客主页：张小姐的猫~江湖背景快上车，握好方向盘跟我有一起打天下嘞！送给自己的一句鸡汤樂：真正的大师永远怀着一颗学徒的心作者水平很有限，如果发现错误，可在评论区指正，感谢欢迎持续关注！
文章目录
欢迎来到数据结构专栏~~封装unordered_map 和 unordered_set一. 模板参数控制二. String类型无法取模问题三. 默认成员函数实现构造函数析构函数
四. 正向迭代器[ ]的实现面试题unordered_set的实现unordered_map的实现哈希表代码
写在最后
看了上两篇的文章：用红黑树封装出map和set，那么本文思路其实是大差不差的，虽然哈希表的实现比红黑树要简单，但是unordered_map 和 unordered_set 的封装却要更加复杂一点，往下看吧，发车咯
一. 模板参数控制
老规矩unordered_set 是 K 模型的容器，而 unordered_map 是 KV 模型的容器，如果要实现封装，那么参数就必须控制
template
class HashTable
T模板参数可能只是键值Key，也可能是由Key和Value共同构成的键值对。如果是unordered_set容器，那么它传入底层哈希表的模板参数就是Key和Key：
template
class unordered_set
{
public:
//...
private:
HashTable
};
但如果是unordered_map容器，那么它传入底层哈希表的模板参数就是Key和Key和Value构成的键值对：
template
class unordered_map
{
public:
//...
private:
HashTable
};
这样一来就可以实现泛型了，当上层容器是unordered_set的时候，结点当中存储的是键值Key；当上层容器是unordered_map的时候，结点当中存储的就是
所以更改后的节点定义如下：
template
struct HashNode
{
T _data;
HashNode
//构造函数
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
为了得到元素的键值，通过哈希计算出对应的哈希地址
我们插入的时候当然不能用data直接去比较
对于unordered_set而言是Key，可以比较但是对于unordered_map是pair，那我们要取其中的first来比较，但是我们能取first吗？这个地方的data有可能是unordered_map；也有可能是unordered_map
所以要实现一个仿函数，如果是unordered_map那就是用于获取T当中的键值Key
template
class unordered_map
{
//仿函数
struct MapKeyOfT
{
const K& operator() (const pair
{
return kv.first;
}
};
private:
Bucket::HashTable
};
当然unordered_set也必不可缺，直接返回key即可
template
class unordered_set
{
//仿函数
struct SetKeyOfT
{
const K& operator() (const K& key)
{
return key;
}
};
private:
Bucket::HashTable
};
所以在哈希表上也要加上这个仿函数
template
struct HashTable
二. String类型无法取模问题
字符串无法取模，是哈希表中的老问题了吧
上文提到过了，我们都能想到的，写库的大佬还不能想到吗？早就预留了一个模板参数，此时无论上层容器是unordered_set还是unordered_map，我们都能够通过上层容器提供的仿函数获取到元素的键值
因为没有使得字符串与整型之间一一对应的方法，因为整型大小是有限的，最大的无符号整型是 4294967295，但是字符串的排列却是无穷的，因此我们提出了 BKDRHash算法
经过前辈们实验后发现，BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie的《The C Programing Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的hash算法
如果是在我们实现哈希表的时候，此仿函数就应该加在哈希表中，如今我们要把哈希封装起来，我们就根本不通过底层的哈希表来调用，而是上层的 unordered_map等，所以 仿函数加在上层！
template
class unordered_map
上层传入的数据：符合string类型的优先走string类型
template
struct Hashfunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//特化版本
template<>
struct Hashfunc
{
//BKDR算法
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}
return val;
}
};
三. 默认成员函数实现
构造函数
哈希表中有两个成员变量，当我们实例化一个对象时：
_table会自动调用vector的默认构造函数进行初始化 _size会根据我们所给的缺省值被设置为0
private:
vector
size_t _size = 0; //存储的有效数据个数
vector会自动去调用自己的构造，内置类型的size不处理，所以直接置0
这里默认构造已经完美完成了构造的任务，我们就不需要画蛇添足后期再去写一个构造函数，但是因为我们需要自己写拷贝构造函数，会使得初始化不使用默认构造，因此我们需要 default 关键字修饰来让他保持默认构造的属性
HashTable() = default; //显示指定默认构造函数
析构函数
因为哈希表当中存储的结点都是new出来的，因此在哈希表被析构时必须进行结点的释放。在析构哈希表时我们只需要依次取出非空的哈希桶，遍历哈希桶当中的结点并进行释放即可
//析构 ： 内置类型不处理 但是桶要析构掉
~HashTable()
{
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete(cur);
cur = next;
}
_table[i] = nullptr;
}
}
四. 正向迭代器
哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，实现++运算符重载，使他可以访问下一个非空的桶，所以每个正向迭代器里面存的都是哈希表地址。
template
struct HashTable;
template
struct __HashIterator
{
typedef HashNode
typedef HashTable
typedef __HashIterator
Node* _node;
HT* _pht;
}
所以在构造迭代器的时候就需要知道节点的指针，以及节点所在哈希表的地址：
__HashIterator(Node* node, HT* pht)
:_node(node)
,_pht(pht)
{}
++ 的实现逻辑也非常简单，只需要注意一下如果当前元素是该桶最后一个元素，那么 ++ 就是跳到下一个非空桶
T& operator*()
{
return _node->_data;//返回节点数据的引用
}
T* operator->()
{
return &_node->_data;//返回节点数据的地址
}
Self& operator++()
{
if (_node->_next)//如果结点不是最后一个结点
{
//当前桶中迭代
_node = _node->_next;
}
else
{
//找下一个桶 : 先算当前的哈希地址
Hash hash;
KeyOfT kot;
size_t i = hash(kot(_node->_data)) % _pht->_table.size();//计算出哈希地址
++i;//从下一个位置开始找
for (; i < _pht->_table.size(); ++i)
{
if (_pht->_table[i])
{
_node = _pht->_table[i];//找到了node就跳转
break;
}
}
//说明后面没有 有数据的桶了
if (i == _pht->_table.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;
}
};
哈希表的迭代器类型是单向迭代器，没有反向迭代器，即没有实–运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构
下面开始抠细节了：
由于 ++ 重载函数在寻找下一个结点时，会访问哈希表成员变量 _table，而 _table 是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元接下来就可以进行正向迭代器类型的 typedef，需要注意的是，为了让外部能够使用 typedef 后的正向迭代器类型 iterator，我们需要在 public 区域进行 typedef
template
struct HashTable
{
typedef HashNode
//模板的友元要带上声明
template
friend struct __HashIterator;
public:
typedef __HashIterator
iterator begin()
{
for (int i = 0; i < _table.size(); ++i)
{
//遍历找到了，就返回
if (_table[i])
{
//this就是指向哈希表的指针
return iterator(_table[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
private:
vector
size_t _n = 0; //有效元素个数
}
[ ]的实现
首先把Insert的返回值改成pair
如果表内有重复的元素就返回这个找到的ret的迭代器 没有重复的就返回newnode这个迭代器
iterator ret = Find(kot(data));
if (ret != end())
{
return make_pair(ret, false);
}
//头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi]; // _table[hashi]指向的就是第一个结点
_table[hashi] = newnode;
++_size;
return make_pair(iterator(newnode, this), true);
面试题
一个类型去做set和unordered_set的模板参数有什么要求？
set要求支持小于比较，或者显示提供比较的仿函数unordered_set：
K类型对象可以转换整形取模 or 提供转成整形的仿函数K类型对象可以支持等于比较 or 提供等于比较的仿函数
unordered_set的实现
#include"HashTable.h"
namespace ljj
{
template
class unordered_set
{
//仿函数
struct SetKeyOfT
{
const K& operator() (const K& key) //返回key
{
return key;
}
};
public:
//因为是调用的是内嵌类型，typename防止编译器认成静态变量， 是类型！！！
typedef typename Bucket::HashTable
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair
{
return _ht.Insert(key);
}
private:
Bucket::HashTable
};
}
unordered_map的实现
#include"HashTable.h"
namespace ljj
{
template
class unordered_map
{
//仿函数
struct MapKeyOfT
{
const K& operator() (const pair
{
return kv.first;
}
};
public:
//因为是调用的是内嵌类型，typename防止编译器认成静态变量， 是类型！！！
typedef typename Bucket::HashTable
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
pair
return ret.first->second;
}
private:
Bucket::HashTable
};
}
哈希表代码
namespace Bucket
{
template
struct HashNode
{
T _data;
HashNode
//构造函数
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
//前置声明
template
struct HashTable;
template
struct __HashIterator
{
typedef HashNode
typedef HashTable
typedef __HashIterator
Node* _node;
HT* _pht;
__HashIterator(Node* node, HT* pht)
:_node(node)
,_pht(pht)
{}
T& operator*()
{
return _node->_data;//返回节点数据的引用
}
T* operator->()
{
return &_node->_data;//返回节点数据的地址
}
Self& operator++()
{
if (_node->_next)//如果结点不是最后一个结点
{
//当前桶中迭代
_node = _node->_next;
}
else
{
//找下一个桶 : 先算当前的哈希地址
Hash hash;
KeyOfT kot;
size_t i = hash(kot(_node->_data)) % _pht->_table.size();//计算出哈希地址
++i;//从下一个位置开始找
for (; i < _pht->_table.size(); ++i)
{
if (_pht->_table[i])
{
_node = _pht->_table[i];//找到了node就跳转
break;
}
}
//说明后面没有 有数据的桶了
if (i == _pht->_table.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
struct HashTable
{
typedef HashNode
//模板的友元要带上声明
template
friend struct __HashIterator;
public:
typedef __HashIterator
iterator begin()
{
for (int i = 0; i < _table.size(); ++i)
{
//遍历找到了，就返回
if (_table[i])
{
//this就是指向哈希表的指针
return iterator(_table[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
//析构 ： 内置类型不处理 但是桶要析构掉
~HashTable()
{
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete(cur);
cur = next;
}
_table[i] = nullptr;
}
}
pair
{
Hash hash;
KeyOfT kot;
//去重
iterator ret = Find(kot(data));
if (ret != end())
{
return make_pair(ret, false);
}
//负载因子到1就扩容
if (_size == _table.size())
{
size_t newsize = _table.size() == 0 ? 10 : 2 * _table.size();
vector
newTable.resize(newsize);
//旧表节点移动映射到新表中
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next; //记录cur的下一个节点
size_t hashi = hash(kot(cur->_data)) % newTable.size();//计算哈希地址
//头插
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;//原桶取完后置空
}
//交换
_table.swap(newTable);
}
size_t hashi = hash(kot(data)) % _table.size();
//头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi]; // _table[hashi]指向的就是第一个结点
_table[hashi] = newnode;
++_size;
return make_pair(iterator(newnode, this), true);
}
//查找
iterator Find(const K& key)
{
if (_table.size() == 0)//哈希表为0，没得找
{
return end();
}
Hash hash;
KeyOfT kot;
size_t hashi = hash(key) % _table.size();//招牌先算出哈希地址
Node* cur = _table[hashi];
while (cur)//知道桶为空
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return end();//遍历完桶，都没找到，返回空
}
bool Erase(const K& key)
{
if (_table.size() == 0)
{
return nullptr;
}
//1、通过哈希函数计算出对应的哈希桶编号hashi
Hash hash;
KeyOfT kot;
size_t hashi = hash(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
//头删
if (prev == nullptr)
{
_table[hashi] = cur->_next;//将第一个结点从该哈希桶中移除
delete cur;
}
else //中间删除
{
prev->_next = cur->_next;//将该结点从哈希桶中移除
delete cur;
}
--_size;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector
size_t _size = 0; //存储的有效数据个数
};
}
写在最后
鹅鹅鹅
发表评论