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

数据结构————哈希表

哈希表(Hash table),也被称为散列表,是一种根据关键值(Key value)而直接进行访问的数据结构。它通过把关键值映射到表中的一个位置来访问记录,从而加快查找的速度。这个映射函数被称为散列函数或哈希函数,而存放记录的数组则被称为散列表或哈希表。

基本概念

  • 散列函数:将任意长度的输入(称为预映射或pre-image)通过散列算法变换成固定长度的输出,该输出即为散列值或哈希值。这个转换过程是一种压缩映射,不同的输入可能会映射到相同的输出。
  • 散列表:用于存放通过散列函数处理后的记录的数组。

工作原理

哈希表的基本工作原理是将关键字(Key)通过哈希函数转换为一个整型数字(哈希值),然后将该数字对数组长度进行取余操作,取余结果作为数组的下标,将对应的值(Value)存储在该下标对应的数组空间中。当进行查找时,再次使用哈希函数将关键字转换为对应的数组下标,并直接定位到该空间获取值。

常用方法

哈希表的实现方法多种多样,其中一些常用的方法包括:

  1. 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。
  2. 数字分析法:通过分析数据的特征,选择分布均匀的若干位数字作为散列地址。
  3. 平方取中法:先求关键字的平方值,然后取平方值的中间几位作为散列地址。
  4. 折叠法:将关键字分割成位数相同的几部分(最后一部分位数可以不同),然后取这几部分的叠加和(去除进位)作为散列地址。
  5. 随机数法:选择一随机函数,取关键字的随机值作为散列地址。
  6. 除留余数法:取关键字被某个不大于散列表表长的数除后所得的余数为散列地址。

处理冲突

由于哈希表的特殊性质,不同的关键字可能会映射到相同的散列地址,这种现象称为哈希冲突。处理冲突的方法主要有以下几种:

  1. 开放寻址法:当发生冲突时,使用某种探测序列在散列表中查找一个空闲的位置,并将记录存入。
  2. 再散列法:当发生冲突时,使用另一个散列函数计算新的散列地址,直到冲突不再发生。
  3. 链地址法:将具有相同散列地址的记录存储在同一个链表中,每个散列地址对应一个链表。

优缺点

优点

  1. 快速访问:哈希表通过哈希函数将关键字映射到数组的一个索引位置,从而实现快速的数据访问。在平均情况下,哈希表的查找、插入和删除操作的时间复杂度都是O(1),即常数时间复杂度。

  2. 高效的空间利用率:相比于其他需要维持数据顺序的数据结构(如链表、树),哈希表在存储相同数量的元素时,通常能够占用更少的空间。这是因为哈希表通过哈希函数直接定位元素的存储位置,避免了元素之间的额外空间浪费。

  3. 灵活性:哈希表支持动态扩容,当元素数量超过当前容量的一定比例时,可以自动增加容量并重新计算哈希值,从而避免性能下降。此外,哈希表也支持删除操作,可以灵活地管理数据。

  4. 适用范围广:哈希表广泛应用于各种场景,包括缓存、数据去重、计数、快速查找等。

缺点

  1. 冲突问题:由于哈希函数的输出范围有限,而输入范围可能很大,因此不同的关键字可能会映射到相同的索引位置,即发生冲突。虽然可以通过各种冲突解决方法(如开放寻址法、链地址法等)来处理冲突,但这些方法可能会增加哈希表的查找、插入和删除操作的时间复杂度。

  2. 哈希函数的选择:哈希表的性能很大程度上取决于哈希函数的选择。一个好的哈希函数应该尽可能减少冲突的发生,并且具有较快的计算速度。然而,找到一个完美的哈希函数是非常困难的,因为不同的应用场景对哈希函数的要求也不同。

  3. 扩容和重新哈希的代价:当哈希表的元素数量超过当前容量的一定比例时,需要进行扩容并重新计算所有元素的哈希值。这个过程可能会比较耗时,并且需要额外的内存空间来存储新的哈希表。

  4. 数据无序:哈希表中的数据是无序的,即无法直接通过索引来遍历哈希表中的元素。如果需要遍历哈希表中的所有元素,通常需要额外的数据结构(如链表)来记录元素的顺序。

  5. 空间浪费:虽然哈希表在大多数情况下能够高效地利用空间,但在某些情况下可能会浪费一些空间。例如,当哈希表的负载因子(已填充元素与总容量的比例)较低时,哈希表中可能会存在大量的空闲空间。此外,如果哈希表的容量设置得过大,也可能会导致空间的浪费。

应用场景

哈希表在多个领域都有广泛的应用,包括但不限于:

  • 快速查找:在需要快速查找未排序的数据的场景中,哈希表可以显著提高查找效率。
  • 数据去重:利用哈希表中每个键的唯一性,可以轻松实现数据的去重操作。
  • 缓存:将经常访问的数据存储在哈希表中,可以加快数据的访问速度。
  • 计数:在统计数据的出现次数时,哈希表可以方便地记录每个数据项的出现次数。
  • 图形算法:在图形算法中,哈希表可以用于存储和检索节点的相关信息。
HSnode_t *hashtable[HASH_SIZE] = {NULL};int hash_function(char key)
{if(key >= 'a' && key <= 'z'){return key - 'a';}else if(key >= 'A' && key <= 'Z'){return key - 'A';}else{return HASH_SIZE - 1;}
}int insert_hashtable(HSdatatype data)
{int addr = hash_function(data.name[0]);HSnode_t *p = malloc(sizeof(HSnode_t));if(NULL == p){perror("malloc error!");return -1;}p->data = data;p->next = NULL;if(hashtable[addr] == NULL){hashtable[addr] = p;}else if(hashtable[addr] ->next == NULL){hashtable[addr]->next = p;}else{HSnode_t *q = hashtable[addr];while(q->next != NULL){q = q->next;}q->next = p;}return 0;
}HSnode_t *find_hash(char *name)
{int addr = hash_function(name[0]);HSnode_t *p = hashtable[addr];while(p != NULL){if(strcmp(p->data.name,name) == 0){return p;}p = p->next;}return NULL;
}void printf_hash()
{HSnode_t *p = hashtable[0];int i = 1;while(i < HASH_SIZE){while(p != NULL){printf("name = %s   tel = %s\n",p->data.name,p->data.tel);p = p->next;}p = hashtable[i];++i;}
}void destroy_hash()
{for(int i = 0;i < HASH_SIZE; ++i){while(hashtable[i] != NULL){HSnode_t *p = hashtable[i];hashtable[i] = p->next;free(p);}}
}

相关文章:

数据结构————哈希表

哈希表&#xff08;Hash table&#xff09;&#xff0c;也被称为散列表&#xff0c;是一种根据关键值&#xff08;Key value&#xff09;而直接进行访问的数据结构。它通过把关键值映射到表中的一个位置来访问记录&#xff0c;从而加快查找的速度。这个映射函数被称为散列函数或…...

element select + tree

element select tree的使用 <template slot"action1" slot-scope"text, record, index"><el-select v-model"record.tagValue" multiple placeholder"请选择":filter-method"(e) > filterTree(e, index)" filt…...

LeetCode之矩阵

36. 有效的数独 class Solution {// 方法 isValidSudoku 接收一个字符二维数组 board&#xff0c;表示数独棋盘&#xff0c;返回是否有效public boolean isValidSudoku(char[][] board) {// 创建三个二维数组来记录每一行、列和子框中数字的出现次数int[][] rows new int[9][…...

Windows文件系统介绍与基本概念解析

1. 引言 1.1 什么是文件系统 文件系统是一种管理和组织计算机存储设备上文件和文件夹的方法。它提供了文件的创建、读取、写入、删除等操作,并负责文件在存储设备上的存储和访问。 在操作系统中,文件系统是一个重要的组成部分,它使得用户可以方便地使用计算机存储设备来存…...

使用 Apache POI 实现 Java Word 模板占位符替换功能

使用 Apache POI 实现 Java Word 模板占位符替换功能 在日常开发中&#xff0c;我们经常会遇到生成 Word 文档的需求&#xff0c;特别是在需要从模板导出 Word 文件时&#xff0c;比如生成合同、报告等。通过使用模板&#xff0c;开发者可以减少重复的工作&#xff0c;将预定义…...

第三届人工智能与智能信息处理国际学术会议(AIIIP 2024)

目录 大会介绍 基本信息 合作单位 主讲嘉宾 会议组委 征文主题 ​ 参会方式 会议日程 中国-天津 | 2024年10月25-27日 | 会议官网&#xff1a;www.iiip.net 大会介绍 第三届人工智能与智能信息处理国际学术会议&#xff08;AIIIP 2024&#xff09;将于202…...

【动手学深度学习】04 数据操作 + 数据预处理(个人向笔记)

数据操作 N维数组是机器学习和神经网络的主要数据结构其中 2-d 矩阵中每一行表示每一行表示一个样本 当维度来到三维的时候则可以表示成一张图片&#xff0c;再加一维就可以变成多张图片&#xff0c;再加一维则可以变成一个视频 访问元素 冒号表示从冒号左边的元素到冒号右…...

本地搭建 Whisper 语音识别模型

Whisper 是由 OpenAI 开发的一款强大的语音识别模型&#xff0c;具有出色的多语言处理能力。搭建和使用 Whisper 模型可以帮助您将音频内容转换为文本&#xff0c;这在语音转写、语音助手、字幕生成等应用中都具有广泛的用途。本指南将对如何在本地环境中搭建 Whisper 语音识别…...

数据集成-缝合一套数据仓库Infra的臆想

一、数据集成当前困境 目前数据集成基础设施建设仅一个单一数据库&#xff0c;无法很好支持上层应用的建设步骤&#xff0c;继续采用当前设施跟随产品的策略&#xff0c;数据产品开发受限巨大&#xff0c;从目前实施的几个产品看&#xff0c;存在以下主要问题&#xff1a; 功能…...

运营有哪几种?

运营又有很多类&#xff0c;分为&#xff1a;内容运营、用户运营、活动运营、产品运营、新媒体运营、社群运营、电商运营、短视频运营 1.内容运营&#xff1a; 做内容提升各类数据&#xff0c;比如内容的数量/浏览数量/互动数传播数等。 适合人群&#xff1a;适合喜欢看文章热…...

Android视频编辑:利用FFmpeg实现高级功能

在移动设备上进行视频编辑的需求日益增长&#xff0c;用户期望能够在智能手机或平板电脑上轻松地编辑视频&#xff0c;以满足社交媒体分享或个人存档的需求。Android平台因其广泛的用户基础和开放的生态系统&#xff0c;成为视频编辑应用的理想选择。FFmpeg&#xff0c;作为一个…...

图片无损缩放PhotoZoom Pro 9.0.2绿色版 +免费赠送PhotoZoom激活优惠代码

PhotoZoom Pro 9.0.2 是一款专业的图片无损缩放软件&#xff0c;该软件采用了 benvista s-spline 独特技术&#xff0c;增强了对图像格式的支持&#xff0c;多处理器支持&#xff0c;GPU 加速&#xff0c;win10和 Photoshop CC 支持。带来一流的数字图形扩展与缩减技术。该软件…...

tekton pipelineresources

PipelineResource 代表着一系列的资源&#xff0c;主要承担作为 Task 的输入或者输出的作用。它有以下几种类型&#xff1a; git&#xff1a;代表一个 git 仓库&#xff0c;包含了需要被构建的源代码。将 git 资源作为 Task 的 Input&#xff0c;会自动 clone 此 git 仓库。pu…...

OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1、选择映射&#xff08;SLM&#xff09; 4.2 相位截断星座图&#xff08;PTS&#xff09; 5.算法完整程序工程 1.算法运行效果图预览 (完整程序运行后无水印) 2.算法运行软件版本 mat…...

常见概念 -- 光回波损耗

什么是回波损耗 回波损耗&#xff0c;又称为反射损耗&#xff0c;当高速信号进入或退出光纤的某个部分&#xff08;例如光纤连接器&#xff09;&#xff0c;不连续和阻抗不匹配会引起反射&#xff0c;这就是光纤回波损耗。器件的回波损耗Return Loss(RL)是光信号的输入端口的反…...

uni-app环境搭建

目录 一、下载HBuilder X: 二、创建项目 1、通过HBuliderX创建 2、通过vue-cli命令行创建 三、app真机运行 1、真机运行: 2、打包发行 四、微信小程序调试 1、下载微信小程序开发者工具 2、运行项目&#xff1a;运行---> 运行到小程序模拟器----> 微信开发者工…...

数据结构 栈 队列

系统栈&#xff1a; 保护局部变量 函数的形参和返回值 函数的调用关系&#xff08;保护现场&#xff0c;恢复现场操作&#xff0c;遵循先进后出&#xff0c;后进先出&#xff09; 数据结构栈&#xff08;顺序栈&#xff0c;链式栈&#xff09;&#xff1a; 同样遵遵循先进…...

嵌入式学习路线+嵌入式校招建议 嵌入式学习面试规划

随着物联网、人工智能以及5G等技术的迅猛发展&#xff0c;嵌入式系统的需求逐渐增多。作为毕业生&#xff0c;如何制定一个合理的学习路线&#xff0c;以确保在找工作、参加校招时有足够的竞争力&#xff0c;是非常重要的。我会为你提供一个更加详细、系统的学习路线建议&#…...

服务器深度学习环境配置

学校提供的服务器&#xff0c;参考意见比较低 目录 公有云操作云主机操作系统修改&#xff1a; xshell连接深度学习环境配置显卡驱动检查安装检查 CUDA检查CUDA下载配置环境变量检查 conda 公有云操作 打开控制中心 节点选择 山东-青岛20 打开弹性云主机 云主机 系统已经默认…...

使用 Parallel 类进行多线程编码(下)

2.Parallel.ForEach() 的使用 从 ForEach() 这个名字可以看出该方法是用来遍历泛型集合的&#xff0c;新建一个 ASP.NET Core Web应用的项目&#xff0c;如下&#xff1a; 在 Index.cshtml.cs 文件中增加一个 UserInfo.cs 的类&#xff0c;代码如下&#xff1a; public class U…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...