当前位置： 首页 > news >正文

封装哈希表

news 2025/8/31 6:16:04

封装哈希表

代码：

fz_Hash.h

#pragma once
#include<iostream>
#include<cassert>
#include<utility>
#include<vector>
using namespace std;template<class T>
struct HashNode
{T _data;HashNode<T>* _next = nullptr;HashNode(const T& data):_data(data), _next(nullptr){}
};template<class K>
struct HashFunc
{size_t operator()(const K& key){return size_t(key);}
};//模版特化,当数据类型是string类型的时候,会直接用写好了的这个
//讲模版的时候讲过了:如果有现成的,就用现成的.
template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto e : s){hash += e;//这里是 + e的Ascll码hash *= 13;}return hash;}
};template<class K, class T, class KeyOfT, class Hash>
class HashTables;//前置声明，因为__HTiterator要用到HashTablestemplate<class K, class T, class KeyOfT, class Hash>
struct __HTiterator
{typedef HashNode<T> Node;typedef HashTables<K, T, KeyOfT, Hash> HT;typedef __HTiterator<K, T, KeyOfT, Hash> Self;Node* _node;//节点指针HT* _ht;//哈希表（HashTables）对象的指针__HTiterator(Node* node, HT* ht):_node(node),_ht(ht){}T& operator*(){return _node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){if (_node->_next != nullptr)//当前下标的链表还没遍历完，还有节点{_node = _node->_next;}else{// 当前桶走完了，找下一个桶KeyOfT kot;Hash hs;//这里说一下，因为我们要计算当前节点的下标，所以我们要用到_Table//所以我们才会在迭代器里面包含HashTables,//和为什么要在迭代器的封装前面做一个HashTables的前置声明//我们是在HashTables里声明了迭代器结构体是友元类了的,//所以是可以使用私有的成员变量的.size_t hash_i = hs(kot(_node->_data)) % _ht->_Table.size();//去找一下个有存储东西的桶hash_i++;while (hash_i < _ht->_Table.size()){if (_ht->_Table[hash_i] != nullptr){_node = _ht->_Table[hash_i];break;}hash_i++;}//后面没桶了if (hash_i == _ht->_Table.size()){_node = nullptr;}}return *this;}
};template<class K, class T, class KeyOfT, class Hash>
class HashTables
{
public:template<class K, class T, class KeyOfT, class Hash>friend struct __HTiterator;typedef HashNode<T> Node;typedef __HTiterator<K, T, KeyOfT, Hash> iterator;iterator begin(){for (size_t i = 0; i < _Table.size(); i++){if (_Table[i] != nullptr){return iterator(_Table[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}HashTables(size_t size = 10){_Table.resize(size, nullptr);_n = 0;}~HashTables(){for (size_t i = 0; i < _Table.size(); i++){Node* cur = _Table[i];while (cur != nullptr){Node* next = cur->_next;delete cur;cur = next;}_Table[i] = nullptr;}}HashNode<T>* find(const K& key);bool inserta(const T& data);bool insertb(const T& data);bool erase(const K& key);private:vector<Node*> _Table;//指针数组size_t _n = 0;//存储已有数据个数
};template<class K, class T, class KeyOfT, class Hash>
HashNode<T>* HashTables<K, T, KeyOfT, Hash>::find(const K& key)
{Hash hs;//仿函数对象,用来调整key的,让key的类型变为为size_tKeyOfT kot;//仿函数对象，从data中获取key//先用哈希函数算位置size_t Hash_i = hs(key) % _Table.size();//判断理想下标处是否是目标值Node* cur = _Table[Hash_i];while (cur != nullptr){if (kot(cur->_data) == key){return cur;}cur = cur->_next;}return nullptr;
}template<class K, class T, class KeyOfT, class Hash>
bool HashTables<K, T, KeyOfT, Hash>::inserta(const T& data)
{KeyOfT kot;//仿函数对象，从data中获取key//先判断新数据是否是重复值if (find(kot(data)) != nullptr){return false;}//然后计算负载因子,判断是否扩容double LoadFactor = (double)_n / (double)_Table.size();if (LoadFactor >= 1){//扩容size_t newsize = _Table.size() * 2;//用newsize创建一个新的哈希表对象vector<Node*> newTable(newsize);for (size_t i = 0; i < _Table.size(); i++){Node* cur = _Table[i];while (cur != nullptr){Node* next = cur->_next;cur->_next = nullptr;Hash hs;//仿函数对象size_t Hash_i = hs(kot(cur->_data)) % newTable.size();if (newTable[Hash_i] == nullptr){newTable[Hash_i] = cur;}else{Node* now = newTable[Hash_i];while (now->_next != nullptr){now = now->_next;}now->_next = cur;}cur = next;}_Table[i] = nullptr;}newTable.swap(_Table);}Hash hs;//仿函数对象size_t Hash_i = hs(kot(data)) % _Table.size();Node* cur = new Node(data);//尾插Node* start = _Table[Hash_i];if (_Table[Hash_i] == nullptr){_Table[Hash_i] = cur;}else{while (start->_next != nullptr){start = start->_next;}start->_next = cur;}_n++;return true;
}template<class K, class T, class KeyOfT, class Hash>
bool HashTables<K, T, KeyOfT, Hash>::insertb(const T& data)
{KeyOfT kot;//仿函数对象，从data中获取key//先判断新数据是否是重复值if (find(kot(data)) != nullptr){return false;}//然后计算负载因子,判断是否扩容//此刻是负载因子=1时扩容if (_n == _Table.size()){//扩容//用newsize创建一个vector对象vector<Node*> newTable(_Table.size() * 2);for (size_t i = 0; i < _Table.size(); i++){Node* cur = _Table[i];while (cur != nullptr){Node* next = cur->_next;Hash hs;//仿函数对象size_t Hash_i = hs(kot(cur->_data)) % newTable.size();cur->_next = newTable[Hash_i];newTable[Hash_i] = cur;cur = next;}_Table[i] = nullptr;}newTable.swap(_Table);}Hash hs;//仿函数对象size_t Hash_i = hs(kot(data)) % _Table.size();Node* newNode = new Node(data);//头插newNode->_next = _Table[Hash_i];_Table[Hash_i] = newNode;_n++;return true;
}template<class K, class T, class KeyOfT, class Hash>
bool HashTables<K, T, KeyOfT, Hash>::erase(const K& key)
{Hash hs;//仿函数对象,用来调整key的,让key的类型变为为size_tKeyOfT kot;//仿函数对象，从data中获取key//先用哈希函数算位置size_t Hash_i = hs(key) % _Table.size();//判断理想下标处是否有目标值Node* cur = _Table[Hash_i];Node* prev = nullptr;while (cur != nullptr){if (kot(cur->_data) == key){if (prev != nullptr){prev->_next = cur->_next;}else{_Table[Hash_i] = cur->_next;}delete cur;_n--;return true;}prev = cur;cur = cur->_next;}return false;
}

My_UnOrderedMap.h

#pragma once
#include"fz_Hash.h"
template<class K, class V, class Hash = HashFunc<K>>
class M_unordered_map
{
public:struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};typedef typename HashTables<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const pair<K,V>& kv){return _ht.insertb(kv);}private:HashTables<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};

My_UnOrderedSet.h

#pragma once
#include"fz_Hash.h"template<class K,class Hash = HashFunc<K>>
class M_unordered_set
{
public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef typename HashTables<K, const K, SetKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const K& key){return _ht.insertb(key);}private:HashTables<K, const K, SetKeyOfT, Hash> _ht;
};

test.cpp

#include"My_UnOrderedMap.h"
#include"My_UnOrderedSet.h"//void test1()
//{
//	HashTables<int, int> ht;
//	ht.inserta(make_pair(23, 1));
//	ht.inserta(make_pair(3, 1));
//	ht.inserta(make_pair(45, 1));
//	ht.inserta(make_pair(5, 1));
//	ht.inserta(make_pair(15, 1));
//	ht.inserta(make_pair(12, 1));
//	ht.inserta(make_pair(67, 1));
//
//	ht.inserta(make_pair(56, 1));
//	ht.inserta(make_pair(92, 1));
//
//	//ht.erase(12);
//	//ht.erase(3);
//	//ht.erase(5);
//	//ht.erase(15);
//
//	ht.inserta(make_pair(89, 1));	
//	ht.inserta(make_pair(56, 1));
//	ht.inserta(make_pair(92, 1));
//	ht.inserta(make_pair(19, 1));
//
//	/* HashNode<int, int>* rt = ht.find(15);
//	 rt = ht.find(23);
//	 rt = ht.find(5);
//	 rt = ht.find(12);*/
//
//}
//
//void test2()
//{
//	HashTables<int, int> ht;
//	ht.insertb(make_pair(23, 1));
//	ht.insertb(make_pair(3, 1));
//	ht.insertb(make_pair(45, 1));
//	ht.insertb(make_pair(5, 1));
//	ht.insertb(make_pair(15, 1));
//	ht.insertb(make_pair(12, 1));
//	ht.insertb(make_pair(67, 1));
//
//	ht.insertb(make_pair(56, 1));
//	ht.insertb(make_pair(92, 1));
//
//	//ht.erase(12);
//	//ht.erase(3);
//	//ht.erase(5);
//	//ht.erase(15);
//
//	ht.insertb(make_pair(99, 1));
//	ht.insertb(make_pair(26, 1));
//	ht.insertb(make_pair(62, 1));
//	ht.insertb(make_pair(19, 1));
//
//	/* HashNode<int, int>* rt = ht.find(15);
//	 rt = ht.find(23);
//	 rt = ht.find(5);
//	 rt = ht.find(12);*/
//
//}
//void test3()
//{
//	HashTables<string, string, HashFunc<string>> ht;
//	ht.inserta(make_pair("apple", "苹果"));
//	ht.inserta(make_pair("sort","排序"));
//	ht.inserta(make_pair("black","黑色"));
//	ht.inserta(make_pair("hello","你好"));
//
//
//	ht.erase("apple");
//	HashNode<string,string>* tt = ht.find("black");
//
//}void test_map1()
{M_unordered_map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("right", "右边"));for (auto& kv : dict){//kv.first += 'x';//kv.second += 'y';cout << kv.first << ":" << kv.second << endl;}
}void test_set1()
{M_unordered_set<int> us;us.insert(3);us.insert(1);us.insert(5);us.insert(15);us.insert(45);us.insert(7);M_unordered_set<int>::iterator it = us.begin();while (it != us.end()){//*it += 100;cout << *it << " ";++it;}cout << endl;for (auto e : us){cout << e << " ";}cout << endl;
}int main()
{test_set1();test_map1();return 0;
}

教训

这次最大的感悟就是，头文件顶头的那句#pragma once千万不要删掉。这个东西叫头文件保护宏，没了可能就会出问题，但是你是不知道哪里出的问题的。

其他的不想多讲了，重要的东西我也在代码里写了注释。这里主要变更的就是多加了一个迭代器，不过迭代器没啥难的这里。

http://www.xdnf.cn/news/1399591.html

相关文章：

  • 基于SpringBoot的流浪动物领养系统【2026最新】
  • macOS 15.6 ARM golang debug 问题
  • Rust Web 模板技术~MiniJinja入门：一款适用于 Rust 语言的轻依赖强大模板引擎
  • Fourier 级数展开（案例：级数展开 AND 求和）
  • Prompt Engineering：高效构建智能文本生成的策略与实践
  • 单例模式的mock类注入单元测试与友元类解决方案
  • Android15适配16kb
  • ros2 foxy没有话题问题解决
  • Axios 实例配置指南
  • Keil5 MDK_541官网最新版下载、安装
  • 从 0 到 1 构建零丢失 RabbitMQ 数据同步堡垒：第三方接口数据零丢失的终极方案
  • comfUI背后的技术——VAE
  • 线性代数理论——状态空间
  • 聊一聊耳机串扰-Crosstalk
  • Vue常用指令和生命周期
  • 118、【OS】【Nuttx】【周边】效果呈现方案解析：作用域？
  • 生成一份关于电脑电池使用情况、健康状况和寿命估算的详细 HTML 报告
  • 软考中级习题与解答——第一章_数据结构与算法基础（2）
  • 【Redisson 加锁源码解析】
  • VuePress添加自定义组件
  • 【MySQL数据库】索引 - 结构 学习记录
  • 加速智能经济发展：如何助力“人工智能+”战略在实时视频领域的落地
  • Swift 解法详解：LeetCode 367《有效的完全平方数》
  • Kafka入门
  • 开源 C++ QT Widget 开发（八）网络--Http文件下载
  • 《微服务架构从故障频发到自愈可控的实战突围方案》
  • CSDN博客语法（不常用但有用）
  • 谷歌 “Nano Banana“ 深度解析：AI 图像的未来是精准编辑，而非从零生成
  • ⚡ Linux find 命令参数详解
  • MySQL基础理解入门