C++进阶 哈希表封装unordered_map和unordered_set

news/2024/11/27 19:30:25/

作者：@小萌新
专栏：@C++进阶
作者简介：大二学生 希望能和大家一起进步！
本篇博客简介：使用哈希表封装unordered_map和unordered_set

哈希表源代码

我们下面会对一个 K V 模型的哈希表进行封装

使用之来模拟实现STL库中的unordered_map和unordered_set

其中哈希表的源代码如下

//每个哈希桶中存储数据的结构
template<class K, class V>
struct HashNode
{pair<K, V> _kv;HashNode<K, V>* _next;//构造函数HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};//哈希表
template<class K, class V>
class HashTable
{typedef HashNode<K, V> Node; //哈希结点类型
public://获取本次增容后哈希表的大小size_t GetNextPrime(size_t prime){const int PRIMECOUNT = 28;//素数序列const size_t primeList[PRIMECOUNT] ={53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};size_t i = 0;for (i = 0; i < PRIMECOUNT; i++){if (primeList[i] > prime)return primeList[i];}return primeList[i];}//插入函数bool Insert(const pair<K, V>& kv){//1、查看哈希表中是否存在该键值的键值对Node* ret = Find(kv.first);if (ret) //哈希表中已经存在该键值的键值对（不允许数据冗余）{return false; //插入失败}//2、判断是否需要调整哈希表的大小if (_n == _table.size()) //哈希表的大小为0，或负载因子超过1{//增容//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍（若哈希表大小为0，则将哈希表的初始大小设置为10）vector<Node*> newtable;newtable.resize(GetNextPrime(_table.size()));//b、将原哈希表当中的结点插入到新哈希表for (size_t i = 0; i < _table.size(); i++){if (_table[i]) //桶不为空{Node* cur = _table[i];while (cur) //将该桶的结点取完为止{Node* next = cur->_next; //记录cur的下一个结点size_t index = cur->_kv.first%newtable.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）//将该结点头插到新哈希表中编号为index的哈希桶中cur->_next = newtable[index];newtable[index] = cur;cur = next; //取原哈希表中该桶的下一个结点}_table[i] = nullptr; //该桶取完后将该桶置空}}//c、交换这两个哈希表_table.swap(newtable);}//3、将键值对插入哈希表size_t index = kv.first % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）Node* newnode = new Node(kv); //根据所给数据创建一个待插入结点//将该结点头插到新哈希表中编号为index的哈希桶中newnode->_next = _table[index];_table[index] = newnode;//4、哈希表中的有效元素个数加一_n++;return true;}//查找函数HashNode<K, V>* Find(const K& key){if (_table.size() == 0) //哈希表大小为0，查找失败{return nullptr;}size_t index = key % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）//遍历编号为index的哈希桶HashNode<K, V>* cur = _table[index];while (cur) //直到将该桶遍历完为止{if (cur->_kv.first == key) //key值匹配，则查找成功{return cur;}cur = cur->_next;}return nullptr; //直到该桶全部遍历完毕还没有找到目标元素，查找失败}//删除函数bool Erase(const K& key){//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）size_t index = key % _table.size();//2、在编号为index的哈希桶中寻找待删除结点Node* prev = nullptr;Node* cur = _table[index];while (cur) //直到将该桶遍历完为止{if (cur->_kv.first == key) //key值匹配，则查找成功{//3、若找到了待删除结点，则删除该结点if (prev == nullptr) //待删除结点是哈希桶中的第一个结点{_table[index] = cur->_next; //将第一个结点从该哈希桶中移除}else //待删除结点不是哈希桶的第一个结点{prev->_next = cur->_next; //将该结点从哈希桶中移除}delete cur; //释放该结点//4、删除结点后，将哈希表中的有效元素个数减一_n--;return true; //删除成功}prev = cur;cur = cur->_next;}//假删除可能会导致迭代器失效return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败}
private:vector<Node*> _table; //哈希表size_t _n = 0; //哈希表中的有效元素个数
};

哈希模板参数的控制

我们都知道

  • unordered_map是KV模型的容器
  • unordered_set是K模型的容器

那么我们应该如何使用一份哈希表来封装它们呢？

这里就涉及到模板参数控制的一些技巧

我们这里可以将哈希模板的第二个参数改为T

template<class K ,class T>
class Hashtable

那么这样子的话 假设上层使用的是unordered_map容器 那么参数应该是这么传递的

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

假设上层使用的是unordered_set容器 那么参数应该是这么传递的

template<class K>
class unordered_set
{
public://...
private:HashTable<K, K> _ht; //传入底层哈希表的是K和K
};

我们可以发现 通过这种方式就能很好的控制原来哈希表中的value值

  • 上层容器是unordered_set时 传入的T是键值 哈希结点中存储的就是键值
  • 上层容器是unordered_map时 传入的T是键值对 哈希结点中存储的就是键值对

当我们更改模板之后我们可以发现节点的代码会变成这样子

template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}
};

模板参数仿函数的增加

在哈希映射中 我们需要通过元素的key值来计算它的函数地址

可是经过我们上面的操作 我们并不知道T是个什么东西 它有可能是键值 有可能是一个键值对

那么这里我们就需要想出一个方法来统一获取T的键值

这里使用到的方法就是仿函数

我们在使用unordered_map和unordered_set 再增加一个仿函数 使用这个仿函数来获取它们的key值

代码表示如下

template<class K, class V>
class unordered_map
{//仿函数struct MapKeyOfT{const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值key{return kv.first;}};
public://...
private:HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};
template<class K>
class unordered_set
{//仿函数struct SetKeyOfT{const K& operator()(const K& key) //返回键值key{return key;}};
public://...
private:HashTable<K, K, SetKeyOfT> _ht;
};

当然 最后我们的哈希表代码也需要修改 增加一个参数来接受上层容器传递过来的仿函数

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

String对象无法取模问题

我们在哈希表中使用的是除留余数法 那么对于整数或者说可以隐式类型转化成无符号数的类型来说 我们只需要强制类型转换一下即可

但是对于字符串类型来说呢？

字符串并不是整型 不可以直接强制类型转换 我们不可以使用除留余数法

于是我们必须自己实现一种方法来使得字符串数据可以转化为整型数据

但是我们要明白的是字符组合式无穷无尽的 但是在计算机中无符号数确实有穷尽的

所以说我们不可能实现一种算法使得字符串和无符号数一一对应 所以说哈希冲突在所难免

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

于是我们可以在哈希的模板参数中加上一个仿函数

template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable

如果上层没有传入仿函数 我们就使用该默认仿函数 将key强制类型转化成无符号数

如果式字符串 则就使用仿函数的特化版本 使用BKDRHash算法返回一个无符号数

代码表示如下

template<class K>
struct Hash
{size_t operator()(const K& key) //返回键值key{return key;}
};
//string类型的特化
template<>
struct Hash<string>
{size_t operator()(const string& s) //BKDRHash算法{size_t value = 0;for (auto ch : s){value = value * 131 + ch;}return value;}
};

哈希表类的实现

构造函数

我们可以看到哈希表的代码中有两个成员变量

vector<Node*> _table; //哈希表
size_t _n = 0; //哈希表中的有效元素个数
  • vector会调用自己的默认构造函数来进行初始化
  • 元素个数_n已经被我们初始化为0了

所以说实际上我们不需要写构造函数 构造函数直接让它默认生成就可以

这里使用default关键字来让他默认生成构造函数

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

这里解释下为什么使用default关键字

在我们前面讲类和对象的时候就说过拷贝构造函数就是一种特殊的构造函数

而我们如果写了构造函数就不会生成默认构造函数了

结合这两点 由于我们下面既需要写拷贝构造函数 又需要默认构造函数

所以必须要写defalut关键字让他生成默认构造函数

拷贝构造函数

哈希表在拷贝的时候需要进行深拷贝 否则拷贝出来的节点就会和原来的节点相同

所以说哈希表拷贝构造的实现逻辑如下

  1. 将哈希表的大小调整为ht._table的大小
  2. 将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中
  3. 更改哈希表当中的有效数据个数

代码表示如下

//拷贝构造函数
HashTable(const HashTable& ht)
{//1、将哈希表的大小调整为ht._table的大小_table.resize(ht._table.size());//2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝）for (size_t i = 0; i < ht._table.size(); i++){if (ht._table[i]) //桶不为空{Node* cur = ht._table[i];while (cur) //将该桶的结点取完为止{Node* copy = new Node(cur->_data); //创建拷贝结点//将拷贝结点头插到当前桶copy->_next = _table[i];_table[i] = copy;cur = cur->_next; //取下一个待拷贝结点}}}//3、更改哈希表当中的有效数据个数_n = ht._n;
}

赋值运算符重载

在实现赋值运算符重载的时候 我们可以通过参数来间接调用拷贝构造函数

因为我们前面说过 形参本质上是实参的一份临时拷贝 且会在出作用域后自动销毁

所以我们拷贝构造后只需要交换两个对象的成员变量 甚至都不用自己去释放空间

形参走出作用域之后会自动帮我们销毁

代码表示如下

//赋值运算符重载函数
HashTable& operator=(HashTable ht)
{//交换哈希表中两个成员变量的数据_table.swap(ht._table);swap(_n, ht._n);return *this; //支持连续赋值
}

析构函数

因为哈希表中储存的节点全部都是new出来的 所以说结束的时候我们必须全部delete掉 来避免内存泄漏

这个时候我们只需要一个个遍历一个个delete就好了

//析构函数
~HashTable()
{//将哈希表当中的结点一个个释放for (size_t i = 0; i < _table.size(); i++){if (_table[i]) //桶不为空{Node* cur = _table[i];while (cur) //将该桶的结点取完为止{Node* next = cur->_next; //记录下一个结点delete cur; //释放结点cur = next;}_table[i] = nullptr; //将该哈希桶置空}}
}

哈希表的正向迭代器的实现

哈希表的迭代器实际上就是对其指针进行了封装 因为我们在实现++运算符重载的时候

要在哈希表中寻找下一个非空哈希桶 所以说我们的迭代器中需要存储哈希表的地址

//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{typedef HashNode<T> Node; //哈希结点的类型typedef HashTable<K, T, KeyOfT, HashFunc> HT; //哈希表的类型typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器的类型Node* _node; //结点指针HT* _pht; //哈希表的地址
};

构造函数

我们在构造正向迭代器的时候不仅需要节点的指针 还需要其在哈希表中的地址

所以说构造函数应该这么写

//构造函数
__HTIterator(Node* node, HT* pht):_node(node) //结点指针, _pht(pht) //哈希表地址
{}

解引用操作

我们使用解引用操作的时候 我们想要的是返回是节点的数据

代码表示如下

T& operator*()
{return _node->_data; //返回哈希结点中数据的引用
}

–>操作

当我们使用–>操作的时候 我们想要获得的是数据的地址

T* operator->()
{return &_node->_data; //返回哈希结点中数据的地址
}

相等和不相等

等我们判断两个迭代器是否相等的时候我们只需要判断被封装的节点是否相同即可 代码如下

bool operator!=(const Self& s) const
{return _node != s._node; //判断两个结点的地址是否不同
}bool operator==(const Self& s) const
{return _node == s._node; //判断两个结点的地址是否相同
}

前置++

++运算符实际上就是从哈希表中找到下一个节点的位置

逻辑上没有什么难点

  • 如果当前节点不是哈希桶中的最后一个节点 那么返回下一个节点即可
  • 如果当前节点是哈希桶中的最后一个节点 那么往后找到下一个非空桶返回第一个节点即可

代码表示如下

//前置++
Self& operator++()
{if (_node->_next) //该结点不是当前哈希桶中的最后一个结点{_node = _node->_next; //++后变为当前哈希桶中的下一个结点}else //该结点是当前哈希桶中的最后一个结点{KeyOfT kot;HashFunc hf;size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //通过哈希函数计算出当前所处哈希桶编号index（除数不能是capacity）index++; //从下一个位置开始找一个非空的哈希桶while (index < _pht->_table.size()) //直到将整个哈希表找完{if (_pht->_table[index]) //当前哈希桶非空{_node = _pht->_table[index]; //++后变为当前哈希桶中的第一个结点return *this;}index++; //当前哈希桶为空桶，找下一个哈希桶}_node = nullptr; //哈希表中已经没有空桶了，++后变为nullptr}return *this;
}

我们实现了正向迭代器之后还需要在哈希表中实现这样子的几个操作

  1. 进行正向迭代器类型的typedef 因为我们外部需要使用迭代器 所以说要在public区域封装
  2. 因为++操作符会访问 哈希表的内部元素 所以说我们要在哈希表中声明友元
  3. 将哈希表查找函数的返回值改为由节点指针和哈希表地址构成的正向迭代器
  4. 将插入函数的返回值改为由迭代器和bool类型组成的键值对

哈希表的begin和end

  1. 对于begin来说我们只需要返回第一个非桶中的第一个节点就可以
  2. 对于end来说直接返回一个空节点构造的正向迭代器
//哈希表的实现
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable
{//将正向迭代器类声明为哈希表类的友元template<class K, class T, class KeyOfT, class HashFunc>friend struct __HTIterator;typedef HashNode<T> Node; //哈希结点类型
public:typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator; //正向迭代器的类型iterator begin(){size_t i = 0;while (i < _table.size()) //找到第一个非空哈希桶{if (_table[i]) //该哈希桶非空{return iterator(_table[i], this); //返回该哈希桶中的第一个结点的正向迭代器}i++;}return end(); //哈希桶中无数据，返回end()}iterator end(){return iterator(nullptr, this); //返回nullptr的正向迭代器}
private:vector<Node*> _table; //哈希表size_t _n = 0; //哈希表中的有效元素个数
};

源代码

哈希表

//哈希结点的定义
template<class T>
struct HashNode
{T _data;HashNode<T>* _next;//构造函数HashNode(const T& data):_data(data), _next(nullptr){}
};
template<class K>
struct Hash
{size_t operator()(const K& key) //返回键值key{return key;}
};
//string类型的特化
template<>
struct Hash<string>
{size_t operator()(const string& s) //BKDRHash算法{size_t value = 0;for (auto ch : s){value = value * 131 + ch;}return value;}
};
//哈希表的实现
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable
{//将正向迭代器类声明为哈希表类的友元template<class K, class T, class KeyOfT, class HashFunc>friend struct __HTIterator;//friend struct __HTIterator<K, T,KeyOfT, HashFunc>;typedef HashNode<T> Node; //哈希结点类型
public:typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator; //正向迭代器的类型iterator begin(){size_t i = 0;while (i < _table.size()) //找到第一个非空哈希桶{if (_table[i]) //该哈希桶非空{return iterator(_table[i], this); //返回该哈希桶中的第一个结点的正向迭代器}i++;}return end(); //哈希桶中无数据，返回end()}iterator end(){return iterator(nullptr, this); //返回nullptr的正向迭代器}//构造函数HashTable() = default; //显示指定生成默认构造//拷贝构造函数HashTable(const HashTable& ht){//1、将哈希表的大小调整为ht._table的大小_table.resize(ht._table.size());//2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝）for (size_t i = 0; i < ht._table.size(); i++){if (ht._table[i]) //桶不为空{Node* cur = ht._table[i];while (cur) //将该桶的结点取完为止{Node* copy = new Node(cur->_data); //创建拷贝结点//将拷贝结点头插到当前桶copy->_next = _table[i];_table[i] = copy;cur = cur->_next; //取下一个待拷贝结点}}}//3、更改哈希表当中的有效数据个数_n = ht._n;}//赋值运算符重载函数HashTable& operator=(HashTable ht){//交换哈希表中两个成员变量的数据_table.swap(ht._table);swap(_n, ht._n);return *this; //支持连续赋值}//析构函数~HashTable(){//将哈希表当中的结点一个个释放for (size_t i = 0; i < _table.size(); i++){if (_table[i]) //桶不为空{Node* cur = _table[i];while (cur) //将该桶的结点取完为止{Node* next = cur->_next; //记录下一个结点delete cur; //释放结点cur = next;}_table[i] = nullptr; //将该哈希桶置空}}}//获取本次增容后哈希表的大小size_t GetNextPrime(size_t prime){const int PRIMECOUNT = 28;//素数序列const size_t primeList[PRIMECOUNT] ={53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};size_t i = 0;for (i = 0; i < PRIMECOUNT; i++){if (primeList[i] > prime)return primeList[i];}return primeList[i];}//插入函数pair<iterator, bool> Insert(const T& data){KeyOfT kot;//1、查看哈希表中是否存在该键值的键值对iterator ret = Find(kot(data));if (ret != end()) //哈希表中已经存在该键值的键值对（不允许数据冗余）{return make_pair(ret, false); //插入失败}//2、判断是否需要调整哈希表的大小if (_n == _table.size()) //哈希表的大小为0，或负载因子超过1{//增容//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍（若哈希表大小为0，则将哈希表的初始大小设置为10）HashFunc hf;vector<Node*> newtable;//size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;//newtable.resize(newsize);newtable.resize(GetNextPrime(_table.size()));//b、将原哈希表当中的结点插入到新哈希表for (size_t i = 0; i < _table.size(); i++){if (_table[i]) //桶不为空{Node* cur = _table[i];while (cur) //将该桶的结点取完为止{Node* next = cur->_next; //记录cur的下一个结点size_t index = hf(kot(cur->_data))%newtable.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）//将该结点头插到新哈希表中编号为index的哈希桶中cur->_next = newtable[index];newtable[index] = cur;cur = next; //取原哈希表中该桶的下一个结点}_table[i] = nullptr; //该桶取完后将该桶置空}}//c、交换这两个哈希表_table.swap(newtable);}//3、将键值对插入哈希表HashFunc hf;size_t index = hf(kot(data)) % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）Node* newnode = new Node(data); //根据所给数据创建一个待插入结点//将该结点头插到新哈希表中编号为index的哈希桶中newnode->_next = _table[index];_table[index] = newnode;//4、哈希表中的有效元素个数加一_n++;return make_pair(iterator(newnode, this), true);}//查找函数iterator Find(const K& key){if (_table.size() == 0) //哈希表大小为0，查找失败{return end();}KeyOfT kot;HashFunc hf;size_t index = hf(key) % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）//遍历编号为index的哈希桶HashNode<T>* cur = _table[index];while (cur) //直到将该桶遍历完为止{if (kot(cur->_data) == key) //key值匹配，则查找成功{return iterator(cur, this);}cur = cur->_next;}return end(); //直到该桶全部遍历完毕还没有找到目标元素，查找失败}//删除函数bool Erase(const K& key){KeyOfT kot;HashFunc hf;//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）size_t index = hf(key) % _table.size();//2、在编号为index的哈希桶中寻找待删除结点Node* prev = nullptr;Node* cur = _table[index];while (cur) //直到将该桶遍历完为止{if (kot(cur->_data) == key) //key值匹配，则查找成功{//3、若找到了待删除结点，则删除该结点if (prev == nullptr) //待删除结点是哈希桶中的第一个结点{_table[index] = cur->_next; //将第一个结点从该哈希桶中移除}else //待删除结点不是哈希桶的第一个结点{prev->_next = cur->_next; //将该结点从哈希桶中移除}delete cur; //释放该结点//4、删除结点后，将哈希表中的有效元素个数减一_n--;return true; //删除成功}prev = cur;cur = cur->_next;}//假删除可能会导致迭代器失效return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败}
private:vector<Node*> _table; //哈希表size_t _n = 0; //哈希表中的有效元素个数
};

unordered_map

	template<class K, class V>class unordered_map{//仿函数struct MapKeyOfT{const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值key{return kv.first;}};public:typedef typename HashTable<K, pair<K, V>, 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 = insert(make_pair(key, V()));iterator it = ret.first;return it->second;}//删除函数void erase(const K& key){_ht.Erase(key);}//查找函数iterator find(const K& key){return _ht.Find(key);}private:HashTable<K, pair<K, V>, MapKeyOfT> _ht;};

unordered_set

template<class K>class unordered_set{//仿函数struct SetKeyOfT{const K& operator()(const K& key) //返回键值key{return key;}};public://现在没有实例化，没办法到HashTable里面找iterator，所以typename就是告诉编译器这里是一个类型，实例化以后再去取typedef typename HashTable<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}//插入函数pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}//删除函数void erase(const K& key){_ht.Erase(key);}//查找函数iterator find(const K& key){return _ht.Find(key);}private:HashTable<K, K, SetKeyOfT> _ht;};

正向迭代器

//前置声明
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{typedef HashNode<T> Node; //哈希结点的类型typedef HashTable<K, T, KeyOfT, HashFunc> HT; //哈希表的类型typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器的类型Node* _node; //结点指针HT* _pht; //哈希表的地址//构造函数__HTIterator(Node* node, HT* pht):_node(node) //结点指针, _pht(pht) //哈希表地址{}T& operator*(){return _node->_data; //返回哈希结点中数据的引用}T* operator->(){return &_node->_data; //返回哈希结点中数据的地址}bool operator!=(const Self& s) const{return _node != s._node; //判断两个结点的地址是否不同}bool operator==(const Self& s) const{return _node == s._node; //判断两个结点的地址是否相同}//前置++Self& operator++(){if (_node->_next) //该结点不是当前哈希桶中的最后一个结点{_node = _node->_next; //++后变为当前哈希桶中的下一个结点}else //该结点是当前哈希桶中的最后一个结点{KeyOfT kot;HashFunc hf;size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //通过哈希函数计算出当前所处哈希桶编号index（除数不能是capacity）index++; //从下一个位置开始找一个非空的哈希桶while (index < _pht->_table.size()) //直到将整个哈希表找完{if (_pht->_table[index]) //当前哈希桶非空{_node = _pht->_table[index]; //++后变为当前哈希桶中的第一个结点return *this;}index++; //当前哈希桶为空桶，找下一个哈希桶}_node = nullptr; //哈希表中已经没有空桶了，++后变为nullptr}return *this;}
};

http://www.ppmy.cn/news/19030.html

相关文章

Vue TypeScript 使用eval函数的坑

Vue TypeScript 使用eval函数的坑

正常情况下&#xff0c;项目里不会用eval函数&#xff0c;但是万一要调用一个全局的js库&#xff0c;就需要用eval做些骚操作&#xff0c;这个时候编译会提示&#xff1a; is strongly discouraged as it poses security risks and may cause issues with minification. 警告是…
阅读更多...
ARP渗透与攻防(三)之流量分析

ARP渗透与攻防(三)之流量分析

ARP攻击-流量分析 ARP渗透与攻防(一)之ARP原理 ARP渗透与攻防(二)之断网攻击 系列文章 1.环境准备 1.kali作为攻击机 2.win10作为靶机 IP地址&#xff1a;192.168.110.11 3.网关 IP地址&#xff1a;192.168.110.1 2.kali数据包转发 出于安全考虑&#xff0c;Linux系统默…
阅读更多...
Godot根据遮罩图移动粒子

Godot根据遮罩图移动粒子

前言 目前UI粒子特效unity引擎比较多&#xff0c;也好找资料&#xff0c;但是一般都是利用模型&#xff0c;使用3D粒子伪装2D效果。 Godot中也可以做到这一点&#xff0c;并且Godot有专门的2D粒子系统&#xff0c;可以通过一张遮罩图对粒子的位置进行设置。 godot粒子教程 …
阅读更多...
深度学习网络---YOLO系列

深度学习网络---YOLO系列

深度学习网络—YOLO yolov1&#xff08;仅适用一个卷积神经网络端到端地实现检测物体的目的&#xff09; 首先将输入图片resize到448448&#xff0c;然后送入CNN网络&#xff0c;最后处理预测的结果得到检测的目标&#xff1b;yolov1的具体思想是将全图划分为SS的格子&#xf…
阅读更多...
第五十三章 使用 ^SystemPerformance 监视性能 - InterSystems IRIS Linux 平台性能数据报告

第五十三章 使用 ^SystemPerformance 监视性能 - InterSystems IRIS Linux 平台性能数据报告

文章目录第五十三章 使用 ^SystemPerformance 监视性能 - InterSystems IRIS Linux 平台性能数据报告第五十三章 使用 ^SystemPerformance 监视性能 - InterSystems IRIS Linux 平台性能数据报告 %SS - 使用 ALL^%SS 命令在运行过程中采集了四个样本。 Configuration * - 来自…
阅读更多...
CSDN原创图片链接失效分析

CSDN原创图片链接失效分析

过年花了5个小时&#xff0c;把我的所有BLOG&#xff08;200多篇&#xff09;检查了一遍&#xff0c;更正了几十处图片链接失效。 1. 现象 几个月来&#xff0c;由于在写书&#xff0c;不停地回翻自己以前的文章。结果&#xff0c;不断发现大量辛辛苦苦绘制的图片打不开了&am…
阅读更多...
C语言之程序设计概述

C语言之程序设计概述

1.1.1 程序的概念 程序&#xff1a;算法 数据结构 程序设计方法 语言工具和环境数据结构&#xff1a;数据的类型和数据的组织方式算法&#xff1a;对数据操作的方法和步骤 1.1.2 程序设计语言的种类 第一代语言&#xff08;机器语言&#xff09;&#xff1a;执行效率高、…
阅读更多...
C++:类的构造函数与析构函数

C++:类的构造函数与析构函数

目录 一.前言 二.类的构造函数 1.构造函数基本概念与语法细则 2.编译器默认生成的无参构造函数和自定义构造函数 3.构造函数的特性(可重载) 4.关于构造函数的注意事项 5.构造函数的应用示例&#xff1a; 三.类的拷贝构造函数 1.拷贝构造函数基本概念 2.编译器默认生成…
阅读更多...
最新文章

Copyright @ 2022~2023