深圳幻海软件技术有限公司 欢迎您！
更多

【高阶数据结构】封装unordered_map 和 unordered_set

2023-04-27

node hash cur
🌈欢迎来到数据结构专栏~~封装unordered_map和unordered_set(꒪ꇴ꒪(꒪ꇴ꒪)🐣,我是Scort目前状态：大三非科班啃C++中🌍博客主页：张小姐的猫~江湖背景快上车🚘，握好方向盘跟我有一起打天下嘞！送给自己的一句鸡汤🤔：🔥真正的大师永远怀着一颗学徒的心作者水平很有

🌈欢迎来到数据结构专栏~~封装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 K, class T>
class HashTable

  • 1
  • 2

T模板参数可能只是键值Key，也可能是由Key和Value共同构成的键值对。如果是unordered_set容器，那么它传入底层哈希表的模板参数就是Key和Key：

template<class K>
class unordered_set
{
public:
//...
private:
HashTable<K, K> _ht; //传入K和K
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

但如果是unordered_map容器，那么它传入底层哈希表的模板参数就是Key和Key和Value构成的键值对：

template<class K, class V>
class unordered_map
{
public:
//...
private:
HashTable<K, pair<K, V>> _ht; //传入K以及K和V构成的键值对
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

这样一来就可以实现泛型了，当上层容器是unordered_set的时候，结点当中存储的是键值Key；当上层容器是unordered_map的时候，结点当中存储的就是<Key, Value>键值对

所以更改后的节点定义如下：

template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;

//构造函数
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

为了得到元素的键值，通过哈希计算出对应的哈希地址

我们插入的时候当然不能用data直接去比较

  • 对于unordered_set而言是Key，可以比较
  • 但是对于unordered_map是pair，那我们要取其中的first来比较，但是我们能取first吗？
  • 这个地方的data有可能是unordered_map；也有可能是unordered_map

所以要实现一个仿函数，如果是unordered_map那就是用于获取T当中的键值Key

template<class K, class V>
class unordered_map
{
//仿函数
struct MapKeyOfT
{
const K& operator() (const pair<K, V>& kv)
{
return kv.first;
}
};

private:
Bucket::HashTable<K, pair<K, V, MapKeyOfT>> _ht;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

当然unordered_set也必不可缺，直接返回key即可

template<class K>
class unordered_set
{
//仿函数
struct SetKeyOfT
{
const K& operator() (const K& key)
{
return key;
}
};
private:
Bucket::HashTable<K, K, SetKeyOfT>> _ht;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

所以在哈希表上也要加上这个仿函数

template<class K, class T, class KeyOfT>
struct HashTable

  • 1
  • 2

二. String类型无法取模问题

字符串无法取模，是哈希表中的老问题了吧

上文提到过了，我们都能想到的，写库的大佬还不能想到吗？早就预留了一个模板参数，此时无论上层容器是unordered_set还是unordered_map，我们都能够通过上层容器提供的仿函数获取到元素的键值

因为没有使得字符串与整型之间一一对应的方法，因为整型大小是有限的，最大的无符号整型是 4294967295，但是字符串的排列却是无穷的，因此我们提出了 BKDRHash算法

经过前辈们实验后发现，BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie的《The C Programing Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的hash算法

如果是在我们实现哈希表的时候，此仿函数就应该加在哈希表中，如今我们要把哈希封装起来，我们就根本不通过底层的哈希表来调用，而是上层的 unordered_map等，所以 仿函数加在上层！

template<class K, class V, class Hash = Hashfunc<K>>
class unordered_map

  • 1
  • 2

上层传入的数据：符合string类型的优先走string类型

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& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}
return val;
}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

三. 默认成员函数实现

🌏构造函数

哈希表中有两个成员变量，当我们实例化一个对象时：

_table会自动调用vector的默认构造函数进行初始化
_size会根据我们所给的缺省值被设置为0

private:
vector<Node*> _table;
size_t _size = 0; //存储的有效数据个数

  • 1
  • 2
  • 3

vector会自动去调用自己的构造，内置类型的size不处理，所以直接置0

这里默认构造已经完美完成了构造的任务，我们就不需要画蛇添足后期再去写一个构造函数，但是因为我们需要自己写拷贝构造函数，会使得初始化不使用默认构造，因此我们需要 default 关键字修饰来让他保持默认构造的属性

HashTable() = default; //显示指定默认构造函数

  • 1

🌏析构函数

因为哈希表当中存储的结点都是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;
}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

四. 正向迭代器

哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，实现++运算符重载，使他可以访问下一个非空的桶，所以每个正向迭代器里面存的都是哈希表地址。

template<class K, class T, class Hash, class KeyOfT>
struct HashTable;

template<class K, class T, class Hash, class KeyOfT>
struct __HashIterator
{
typedef HashNode<T> Node;//节点类型
typedef HashTable<K, T, Hash, KeyOfT> HT;//哈希表类型
typedef __HashIterator<K, T, Hash, KeyOfT> Self;//迭代器类型

Node* _node;
HT* _pht;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

所以在构造迭代器的时候就需要知道节点的指针，以及节点所在哈希表的地址：

__HashIterator(Node* node, HT* pht)
:_node(node)
,_pht(pht)
{}

  • 1
  • 2
  • 3
  • 4

++ 的实现逻辑也非常简单，只需要注意一下如果当前元素是该桶最后一个元素，那么 ++ 就是跳到下一个非空桶

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;
}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

哈希表的迭代器类型是单向迭代器，没有反向迭代器，即没有实–运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构

下面开始抠细节了：

  1. 由于 ++ 重载函数在寻找下一个结点时，会访问哈希表成员变量 _table，而 _table 是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元
  2. 接下来就可以进行正向迭代器类型的 typedef，需要注意的是，为了让外部能够使用 typedef 后的正向迭代器类型 iterator，我们需要在 public 区域进行 typedef
template<class K, class T, class Hash, class KeyOfT>
struct HashTable
{
typedef HashNode<T> Node;

//模板的友元要带上声明
template<class K, class T, class Hash, class KeyOfT>
friend struct __HashIterator;
public: 

typedef __HashIterator<K, T, Hash, KeyOfT> iterator;

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<Node*> _table; //哈希表
size_t _n = 0; //有效元素个数
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

[ ]的实现

首先把Insert的返回值改成pair<iterator, bool>，随后的返回值也要跟着改

如果表内有重复的元素就返回这个找到的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);

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

面试题

一个类型去做set和unordered_set的模板参数有什么要求？

  • set要求支持小于比较，或者显示提供比较的仿函数
  • unordered_set：
    • K类型对象可以转换整形取模 or 提供转成整形的仿函数
    • K类型对象可以支持等于比较 or 提供等于比较的仿函数

unordered_set的实现

#include"HashTable.h"

namespace ljj
{
template<class K, class Hash = Hashfunc<K>>
class unordered_set
{
//仿函数
struct SetKeyOfT
{
const K& operator() (const K& key) //返回key
{
return key;
}
};

public:
//因为是调用的是内嵌类型，typename防止编译器认成静态变量， 是类型！！！
typedef typename Bucket::HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;

iterator begin()
{
return _ht.begin();
}

iterator end()
{
return _ht.end();
}

pair<iterator, bool> Insert(const K& key)
{
return _ht.Insert(key);
}

private:
Bucket::HashTable<K, K, Hash, SetKeyOfT> _ht;
};
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

unordered_map的实现

#include"HashTable.h"

namespace ljj
{
template<class K, class V, class Hash = Hashfunc<K>>
class unordered_map
{
//仿函数
struct MapKeyOfT
{
const K& operator() (const pair<K, V>& kv) //返回键值对当中的键值key
{
return kv.first;
}
};

public:
//因为是调用的是内嵌类型，typename防止编译器认成静态变量， 是类型！！！
typedef typename Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator;

iterator begin()
{
return _ht.begin();
}

iterator end()
{
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(make_pair(key, V()));
return ret.first->second;
}

private:
Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;
};
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

哈希表代码

namespace Bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;

//构造函数
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};

//前置声明
template<class K, class T, class Hash, class KeyOfT>
struct HashTable;

template<class K, class T, class Hash, class KeyOfT>
struct __HashIterator
{
typedef HashNode<T> Node;//节点类型
typedef HashTable<K, T, Hash, KeyOfT> HT;//哈希表类型
typedef __HashIterator<K, T, Hash, KeyOfT> Self;//迭代器类型

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<class K, class T, class Hash, class KeyOfT>
struct HashTable
{
typedef HashNode<T> Node;

//模板的友元要带上声明
template<class K, class T, class Hash, class KeyOfT>
friend struct __HashIterator;
public: 

typedef __HashIterator<K, T, Hash, KeyOfT> iterator;

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<iterator, bool> Insert(const T& data)
{
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<Node*> newTable;
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<Node*> _table;
size_t _size = 0; //存储的有效数据个数
};
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256

📢写在最后

鹅鹅鹅

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览45136 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪