【C++】学习笔记——哈希_2

文章目录

  • 十八、哈希
    • 3. 实现哈希表
      • 哈希表的存储节点
      • 哈希函数
      • 哈希表的定义
      • 哈希表的插入
      • 哈希表的查找
      • 哈希表的删除
      • 测试函数
      • 完整代码+结果
  • 未完待续


十八、哈希

3. 实现哈希表

哈希表的实现方法有蛮多种,这里我们选一个比较经典的开散列法来实现哈希表。由于STL库里的哈希表都是将负载因子(插入的数据/哈希表的容量)设置为1,所以我们这里也将负载因子设置为1。

哈希表的存储节点

开散列法实现的哈希表,是通过数组来当哈希表,但是数组中存储的都是指针,像一个链表一样,将同索引的数据在这个指针下串联起来。

// 哈希表数据节点类型
template<class K, class V>
struct HashNode
{// 指向同一个桶的下一个节点HashNode<K, V>* _next;// 当前数据std::pair<K, V> _kv;HashNode(const std::pair<K, V>& kv):_next(nullptr),_kv(kv){}
};

哈希函数

哈希表是通过哈希函数来确定存储的位置的,但是对于不同的类型,我们无法统一看待。

// 哈希函数
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 哈希函数模板特化
template<>
struct HashFunc<std::string>
{size_t operator()(const std::string& s){// 哈希值size_t hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}
};

哈希表的定义

// 哈希表, Hash是仿函数(哈希函数)
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{typedef HashNode<K, V> Node;
public:// 构造函数HashTable(){_tables.resize(10, nullptr);_n = 0;}// 析构函数~HashTable(){// 遍历每个桶for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];// 遍历每个桶的每个数据节点while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}
private:// 哈希表每个位置都是一个链表(桶)std::vector<Node*> _tables;// 数据个数size_t _n;
};

哈希表的插入

// 插入数据
bool Insert(const std::pair<K, V>& kv)
{// 该数据存在就不插入if (Find(kv.first))return false;// 创建哈希函数对象Hash hs;// 负载因子到1就扩容(满了才扩容)if (_n == _tables.size()){// 创建临时哈希表对象std::vector<Node*> newTables(_tables.size() * 2, nullptr);// 遍历每个桶for (size_t i = 0; i < _tables.size(); ++i){// 遍历桶中的每个数据节点Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 通过哈希函数计算索引,将旧节点头插到新表size_t hashi = hs(cur->_kv.first) % newTables.size();// 新节点指向原本的首元节点cur->_next = newTables[hashi];// 头指针指向新节点newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}// 交换表_tables.swap(newTables);}// 通过哈希函数计算索引size_t hashi = hs(kv.first) % _tables.size();Node* newnode = new Node(kv);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;// 数据个数+1++_n;return true;
}

哈希表的查找

由于哈希表是通过哈希函数来确定存储位置的,所以我们也可以通过哈希函数来找到数据。

// 查找数据
Node* Find(const K& key)
{// 哈希函数对象Hash hs;// 通过哈希函数查找所在的桶size_t hashi = hs(key) % _tables.size();// 遍历Node* cur = _tables[hashi];while (cur){// 找到了if (cur->_kv.first == key){return cur;}cur = cur->_next;}// 没找到return nullptr;
}

哈希表的删除

// 删除数据
bool Erase(const K& key)
{// 哈希函数对象Hash hs;// 通过哈希函数查找所在的桶size_t hashi = hs(key) % _tables.size();// 遍历Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){// 删除if (prev){prev->_next = cur->_next;}else{_tables[hashi] = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;
}

测试函数

void TestHT1()
{HashTable<int, int> ht;int a[] = { 1,4,24,34,7,44,17,37 };for (auto e : a){ht.Insert(std::make_pair(e, e));}ht.Insert(std::make_pair(5, 5));ht.Insert(std::make_pair(15, 15));ht.Insert(std::make_pair(25, 25));ht.Erase(5);ht.Erase(15);ht.Erase(25);ht.Erase(35);HashTable<std::string, std::string> dict;dict.Insert(std::make_pair("sort", "排序"));dict.Insert(std::make_pair("string", "字符串"));
}

完整代码+结果

HashTable.h

#pragma once#include <iostream>
#include <vector>
#include <string>// 哈希函数
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 哈希函数模板特化
template<>
struct HashFunc<std::string>
{size_t operator()(const std::string& s){size_t hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}
};namespace hash_bucket
{// 哈希表数据节点类型template<class K, class V>struct HashNode{// 指向同一个桶的下一个节点HashNode<K, V>* _next;// 当前数据std::pair<K, V> _kv;HashNode(const std::pair<K, V>& kv):_next(nullptr),_kv(kv){}};// 哈希表template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:// 构造函数HashTable(){_tables.resize(10, nullptr);_n = 0;}// 插入数据bool Insert(const std::pair<K, V>& kv){// 该数据存在就不插入if (Find(kv.first))return false;// 创建哈希函数对象Hash hs;// 负载因子到1就扩容(满了才扩容)if (_n == _tables.size()){// 创建临时哈希表对象std::vector<Node*> newTables(_tables.size() * 2, nullptr);// 遍历每个桶for (size_t i = 0; i < _tables.size(); ++i){// 遍历桶中的每个数据节点Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 通过哈希函数计算索引,将旧节点头插到新表size_t hashi = hs(cur->_kv.first) % newTables.size();// 新节点指向原本的首元节点cur->_next = newTables[hashi];// 头指针指向新节点newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}// 交换表_tables.swap(newTables);}// 通过哈希函数计算索引size_t hashi = hs(kv.first) % _tables.size();Node* newnode = new Node(kv);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;// 数据个数+1++_n;return true;}// 查找数据Node* Find(const K& key){// 哈希函数对象Hash hs;// 通过哈希函数查找所在的桶size_t hashi = hs(key) % _tables.size();// 遍历Node* cur = _tables[hashi];while (cur){// 找到了if (cur->_kv.first == key){return cur;}cur = cur->_next;}// 没找到return nullptr;}// 删除数据bool Erase(const K& key){// 哈希函数对象Hash hs;// 通过哈希函数查找所在的桶size_t hashi = hs(key) % _tables.size();// 遍历Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){// 删除if (prev){prev->_next = cur->_next;}else{_tables[hashi] = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}// 析构函数~HashTable(){// 遍历每个桶for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];// 遍历每个桶的每个数据节点while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}private:// 哈希表每个位置都是一个链表(桶)std::vector<Node*> _tables;// 数据个数size_t _n;};void TestHT1(){HashTable<int, int> ht;int a[] = { 1,4,24,34,7,44,17,37 };for (auto e : a){ht.Insert(std::make_pair(e, e));}ht.Insert(std::make_pair(5, 5));ht.Insert(std::make_pair(15, 15));ht.Insert(std::make_pair(25, 25));ht.Erase(5);ht.Erase(15);ht.Erase(25);ht.Erase(35);HashTable<std::string, std::string> dict;dict.Insert(std::make_pair("sort", "排序"));dict.Insert(std::make_pair("string", "字符串"));}
}

test.cpp

#include <iostream>
#include "HashTable.h"
using namespace std;int main()
{hash_bucket::TestHT1();return 0;
}

结果:
在这里插入图片描述
在这里插入图片描述


未完待续

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1487108.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

免费【2024】springboot北京医疗企业固定资产管理系统的设计与实现

博主介绍&#xff1a;✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术范围&#xff1a;SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化…

学术研讨 | 区块链网络体系结构研讨会顺利召开

添加图片注释&#xff0c;不超过 140 字&#xff08;可选&#xff09; 近日&#xff0c;国家区块链技术创新中心组织了“区块链网络体系结构研讨会”&#xff0c;会议面向跨域交互多、计算规模大、数据管理复杂、性能与扩展性要求高等特征的区块链网络的体系结构展开交流研讨&…

linux下磁盘分区工具GParted

最近发现安装的redhat机器部分磁盘大小分配不合理 使用gpated对磁盘重新分区 1、使用U盘制作一个启动盘 下载启动盘制作工具Index of /downloads 使用非常简单&#xff0c;选择gparted-live-1.1.0-3-i686.iso包即可 2、制作完成后&#xff0c;重启机器&#xff0c;选择U盘…

【测开能力提升-Javascript】JavaScript运算符流程结构

1. 递增递减运算符 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><script>// 前置递增运算符var age10age //类似于ageage1&#xff0c; 先加1后返回值alert(age)// 后置…

VUE3学习第二篇:报错记录

1、在我整理好前端代码框架后&#xff0c;而且也启动好了对应的后台服务&#xff0c;访问页面&#xff0c;正常。 2、报错ReferenceError: defineModel is not defined 学到这里报错了 在vue网站的演练场&#xff0c;使用没问题 但是在我自己的代码里就出问题了 3、watchEffec…

JAVA.4.继承

1.特点 java只支持单继承&#xff0c;一个儿子继承一个父亲 但可以多层继承&#xff0c;a继承b&#xff0c;b继承c b是a的直接父类&#xff0c;c是a的间接父类 每个类都直接或者简介继承Object&#xff0c;不写继承就默认继承它 2.注意事项 构造方法 父类的构造方法&#…

Java实现七大排序(二)

一.交换排序 1.冒泡排序 这个太经典了&#xff0c;每个学编程都绕不开的。原理跟选择排序差不多&#xff0c;不过冒泡排序是直接交换。 public static void bubbleSort(int[] array){for (int i 0; i < array.length - 1; i) {for (int j 0; j < array.length-1-i; j…

unity2D游戏开发02添加组件移动玩家

添加组件 给PlayGame和EnemyObject添加组件BoxCollider 2D碰撞器&#xff0c;不用修改参数 给PlayGame添加组件Rigibody 2D 设置数据 添加EnemyObject&#xff0c;属性如下 Edit->project setting->Physics 2D 将 y的值改为0 给playerObject添加标签 新建层 将PlayerObj…

安宝特方案|解放双手,解决死角,AR带来质量监督新体验

AR质量监督 解放双手&#xff0c;解决死角 在当今制造业快速发展的背景下&#xff0c;质量监督成为确保产品高质量和完善的管理制度的关键环节。然而&#xff0c;传统的质量监督方式存在诸多挑战&#xff0c;如人工操作带来的效率低下、查岗不及时、摄像头死角等问题。 为了解…

【Django】在vscode中新建Django应用并新增路由

文章目录 打开一个终端输入新建app命令在app下的views.py内写一个视图app路由引入该视图项目路由引入app路由项目(settings.py)引入app&#xff08;AntappConfig配置类&#xff09;运行项目 打开一个终端 输入新建app命令 python manage.py startapp antapp在app下的views.py内…

C++学习笔记——模板

学习视频 文章目录 模板的概念函数模板函数模板语法函数模板注意事项函数模板案例普通函数与函数模板的区别普通函数与函数模板的调用规则模板的局限性 类模板类模板与函数模板区别类模板中成员函数创建时机类模板对象做函数参数类模板与继承类模板成员函数类外实现类模板分文件…

大数据技术--实验06-Spark的安装与使用【实测可行】

下面详细讲解有关Hadoop2.6.0上的spark1.5.2集群如何搭建。 一、Spark安装前提 安装Spark之前需要先安装Hadoop集群&#xff0c;因为之前已经安装了hadoop&#xff0c;所以我直接在之前的hadoop集群上安装spark&#xff0c;选择master以及slave安装spark集群。 二、Spark安装步…

【JavaEE】线程安全问题

目录 一.线程安全问题 1.什么是线程安全 2.线程不安全的原因 3.如何解决线程安全问题&#xff1f; 3.1synchronized的使用方式 3.2解决示例自增带来的线程安全问题 (1&#xff09;对代码块进行加锁 (2)对方法进行加锁 4.synchronized的特性 5.死锁 5.1两个线程两把锁…

Python+Flask+MySQL+日线指数与情感指数预测的股票信息查询系统【附源码,运行简单】

PythonFlaskMySQL日线指数与情感指数预测的股票信息查询系统【附源码&#xff0c;运行简单】 总览 1、《股票信息查询系统》1.1 方案设计说明书设计目标工具列表 2、详细设计2.1 登录2.2 程序主页面2.3 个人中心界面2.4 基金详情界面2.5 其他功能贴图 3、下载 总览 自己做的项…

H3CNE(路由基础、直连路由与静态路由)

目录 6.1 直连路由 6.2 静态路由理解性实验 6.2.1 配置直连路由 6.2.2 配置静态路由 6.3 路由表的参数与比较 6.3.1 优先级的比较 6.3.2 开销的比较 6.4 路由器中的等价路由、浮动路由、默认路由 6.4.1 等价路由 6.4.2 浮动路由 6.4.3 默认路由(缺省路由) 6.1 直连路…

C++:模板(函数模板,类模板)

目录 泛型编程 函数模板 函数模板格式 函数模板的原理 函数模板的实例化 类模板 类模板格式 类模板实例化 模板分为函数模板和类模板 在C中使用模板可以让我们实现泛型编程 泛型编程 如果我们需要实现一个加法add函数&#xff0c;那么会怎么实现呢&#xff1f; int…

opencv grabCut前景后景分割去除背景

参考&#xff1a; https://zhuanlan.zhihu.com/p/523954762 https://docs.opencv.org/3.4/d8/d83/tutorial_py_grabcut.html 环境本次&#xff1a; python 3.10 提取前景&#xff1a; 1、需要先把前景物体框出来 需要坐标信息&#xff0c;可以用windows自带的画图简单提取像素…

如何合并电脑硬盘分区?轻松合并电脑硬盘分区

在日常使用电脑的过程中&#xff0c;我们有时需要对硬盘进行分区管理。然而&#xff0c;随着时间的推移&#xff0c;我们可能会发现原有的分区设置不再满足需求&#xff0c;这时就需要对分区进行调整&#xff0c;甚至合并分区。那么&#xff0c;我们该如何合并电脑硬盘分区呢&a…

【Vue实战教程】之Vue工程化项目详解

Vue工程化项目 随着多年的发展&#xff0c;前端越来越模块化、组件化、工程化&#xff0c;这是前端发展的大趋势。webpack是目前用于构建前端工程化项目的主流工具之一&#xff0c;也正变得越来越重要。本章节我们来详细讲解一下如何使用webpack搭建Vue工程化项目。 1 使用we…