哈希(hash)函数


本文已收录至《全国计算机等级考试——信息 安全技术》专栏

哈希函数,也称为散列函数
或杂凑函数,指将哈希表中元素的关键键值映射为元素存储位置的函数。是一种将任意长度的数据映射到固定长度输出的函数。哈希函数的特点包括压缩性,即输入数据的空间通常远大于输出哈希值的空间;单向性,即从哈希值难以反向推导出原始输入数据;碰撞抵抗性,即难以找到两个不同的输入产生相同的哈希值。

一般的线性表记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。

哈希函数在计算机科学中有多种应用,包括但不限于数据完整性验证、单项数据加密、数字签名等。例如,在数据完整性验证中,通过哈希函数生成的数据或文件的哈希值,可以在后续验证时与原始哈希值进行比较,以检测数据是否被篡改;在单向数据加密中,哈希函数用于存储用户密码的哈希值,并在验证时比较用户输入的密码哈希值与存储的哈希值;在数字签名中,哈希函数用于生成只有发送者知道的信息的唯一标识,接收者可以通过这个标识来验证信息的完整性和来源。

在实际应用中,人们经常使用各种密码学安全的哈希函数,如SHA-256、MD5和SHA-1
等。这些哈希函数不仅具有上述通用特性,还经过了特殊设计以提供额外的安全性。例如,SHA-256可以生成256比特的哈希值,其安全性基于目前计算能力下的碰撞抵抗性。然而,需要注意的是,某些哈希函数(如MD5和SHA-1)已经因为安全性问题而被建议不再使用。

哈希表的概念及作用

哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量,通过一定的函数关系(称为哈希函数),计算出的值,即为该元素的存储地址。表示为:

Addr = H(key)

为此在建立一个哈希表之前需要解决两个主要问题:

⑴构造一个合适的哈希函数

均匀性 H(key)的值均匀分布在哈希表中;

简单 以提高地址计算的速度

⑵冲突的处理

冲突:在哈希表中,不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2,但H(K1)= H(K2)。均匀的哈希函数可以减少冲突,但不能避免冲突。发生冲突后,必须解决;也即必须寻找下一个可用地址。

解决冲突的方法

⑴链接法(拉链法)。将具有同一散列地址的记录存储在一条线性链表中。例,除留余数法中,设关键字为 (18,14,01,68,27,55,79),除数为13。散列地址为 (5,1,1,3,1,3,1),哈希散列表如图。

⑵开放定址法。如果h(k)已经被占用,按如下序列探查:(h(k)+p⑴)%TSize,(h(k)+p⑵)%TSize,…,(h(k)+p(i))%TSize,…

其中,h(k)为哈希函数,TSize为哈希表长,p(i)为探查函数。在 h(k)+p(i-1))%TSize的基础上,若发现冲突,则使用增量 p(i) 进行新的探测,直至无冲突出现为止。其中,根据探查函数p(i)的不同,开放定址法又分为线性探查法(p(i) = i : 1,2,3,…),二次探查法(p(i)=(-1)^(i-1)*((i+1)/2)^2,探查序列依次为:1, -1,4, -4, 9 …),随机探查法(p(i): 随机数),双散列函数法(双散列函数h(key) ,hp (key)若h(key)出现冲突,则再使用hp (key)求取散列地址。探查序列为:h(k),h(k)+ hp(k),…,h(k)+ i*hp(k))。

⑶桶定址法。桶:一片足够大的存储空间。桶定址:为表中的每个地址关联一个桶。如果桶已经满了,可以使用开放定址法来处理。例如,插入A5,A2,A3,B5,A9,B2,B9,C2,采用线性探查法解决冲突。

86143dcacd044402bbc3fa6b18453838.gif

哈希表的构造方法

直接定址法

例如:有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。

数字分析法

有学生的生日数据如下:

年.月.日

75.10.03

75.11.23

76.03.02

76.07.12

75.04.21

76.02.15

...

经分析,第一位,第二位,第三位重复的可能性大,取这三位造成冲突的机会增加,所以尽量不取前三位,取后三位比较好。

平方取中法

取关键字平方后的中间几位为哈希地址。

折叠法

将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。

例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。

除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

H(key)=random(key),其中random为随机函数。通常用于关键字长度不等时采用此法。

若已知哈希函数及冲突处理方法,哈希表的建立步骤如下:

步骤1:取出一个数据元素的关键字key,计算其在哈希表中的存储地址D=H(key)。若存储地址为D的存储空间还没有被占用,则将该数据元素存入;否则发生冲突,执行步骤2。

步骤2:根据规定的冲突处理方法,计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用,则存入;否则继续执行步骤2直到找出一个存储空间没有被占用的存储地址为止。

冲突

无论哈希函数设计有多么精细,都会产生冲突现象,也就是2个关键字处理函数的结果映射在了同一位置上,因此,有一些方法可以避免冲突。

拉链法

拉出一个动态链表代替静态顺序存储结构,可以避免哈希函数的冲突,不过缺点就是链表的设计过于麻烦,增加了编程复杂度。此法可以完全避免哈希函数的冲突。

多哈希法

设计二种甚至多种哈希函数,可以避免冲突,但是冲突几率还是有的,函数设计的越好或越多都可以将几率降到最低(除非人品太差,否则几乎不可能冲突)。

开放地址法

开放地址法有一个公式:Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)

其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1,称线性探测再散列。

如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)

称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

建域法

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

袁庭新ES系列18节|Spring Data Elasticsearch高级

前言 这一章节袁老师将带领同学们来学习Spring Data Elasticsearch高级操作相关的内容。我们继续来探索SDE是如何将原始操作Elasticsearch的客户端API进行封装的&#xff0c;以及通过Spring Data Elasticsearch如何来操作ES。准备好了吗&#xff1f;我们继续来探索ES的内容。 …

Android Studio 调试:快速入门指南

作为一名Android应用开发人员&#xff0c;调试是你不可或缺的技能之一。通过调试&#xff0c;你可以定位和解决各种问题&#xff0c;包括崩溃、性能问题、UI错误等。在本文中&#xff0c;我们将分享一些实用的Android调试技巧&#xff0c;帮助你提高应用开发效率。 Android St…

餐后血糖波动?学会在米饭里加两物

米饭里加两物&#xff0c;帮你平稳餐后血糖&#xff0c;餐后血糖稳稳的&#xff0c;别让你碗里的米饭太单调&#xff0c;搭着吃对血糖好。今天呢我教大家一招&#xff0c;在蒸米饭的时候&#xff0c;加上两种食材&#xff0c;能够改善餐后血糖。 第一就是在煮米饭的时候加点糙米…

STM32 F103C8T6学习笔记17:类IIC通信—MLX90614红外非接触温度计

今日学习配置MLX90614红外非接触温度计 与 STM32 F103C8T6 单片机的通信 文章提供测试代码讲解、完整工程下载、测试效果图 本文需要用到的大概基础知识&#xff1a;1.3寸OLED配置通信显示、IIC通信、 定时器配置使用 这里就只贴出我的 OLED驱动方面的网址链接了&#xff1a…

【热闻速递】Google 裁撤 Python研发团队

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 【&#x1f525;热闻速递】Google 裁撤 Python研发团队引入研究结论 【&#x1f5…

配置及使用OpenCV(Python)

python配置OpenCV相对于c的配置方法容易的多&#xff0c;但建议在Anaconda中的Python虚拟环境中使用&#xff0c;这样更方便进行包管理和环境管理&#xff1a; 先激活Anaconda的python虚拟环境&#xff1a; conda activate GGBoy 随后下载 opencv 包&#xff1a; conda ins…

数据结构——树概念以及结构

首先我们来复习一下顺序表和链表的优缺点。 顺序表缺点&#xff1a; 1.中间或者头部插入、删除数据需要挪动覆盖&#xff0c;效率低 2.空间不够只能扩容&#xff0c;扩容有消耗 3.倍数扩容&#xff0c;空间用不完&#xff0c;存在浪费空间 顺序表优点&#xff1a; 1.可以…

低代码工业组态数字孪生平台

2024 两会热词「新质生产力」凭借其主要特征——高科技、高效能及高质量&#xff0c;引发各界关注。在探索构建新质生产力的重要议题中&#xff0c;数据要素被视为土地、劳动力、资本和技术之后的第五大生产要素。数据要素赋能新质生产力发展主要体现为&#xff1a;生产力由生产…

电商日志项目(一)

电商日志项目 一、项目体系架构设计1. 项目系统架构2. 项目数据流程二、环境搭建1. NginxLog文件服务1.1. 上传,解压1.2. 编译安装1.3. 启动验证2. Flume-ng2.1. 上传解压2.2. 修改配置文件2.3. 修改环境变量2.4. 验证3. Sqoop3.1. 上传解压3.2. 配置环境变量3.3. 修改配置文件…

【19】JAVASE-多线程专题【从零开始学JAVA】

Java零基础系列课程-JavaSE基础篇 Lecture&#xff1a;波哥 Java 是第一大编程语言和开发平台。它有助于企业降低成本、缩短开发周期、推动创新以及改善应用服务。如今全球有数百万开发人员运行着超过 51 亿个 Java 虚拟机&#xff0c;Java 仍是企业和开发人员的首选开发平台。…

[高质量]2024五一数学建模A题保奖思路+代码(后续会更新)

你的点赞收藏是我继续更新的最大动力&#xff0c;可点击文末卡片获取更多资料 你是否在寻找数学建模比赛的突破点&#xff1f; 作为经验丰富的数学建模团队&#xff0c;我们将为你带来2024 年华东杯&#xff08;A题&#xff09;的全面解析包。这个解决方案包不仅包括完整的代…

2024年十款开源测试开发工具推荐(自动化、性能、混沌测试、造数据、流量复制)

今天为大家奉献一篇测试开发工具集锦干货。在本篇文章中&#xff0c;将给大家推荐10款日常工作中经常用到的测试开发工具神器&#xff0c;涵盖了自动化测试、性能压测、流量复制、混沌测试、造数据等。 1、AutoMeter-API 自动化测试平台 AutoMeter 是一款针对分布式服务&…

DigitalOcean 托管 Kafka 新增横向扩展功能

自2023年9月推出以来&#xff0c;DigitalOcean托管的Kafka已经使初创公司、不断增长的数字业务以及独立软件供应商(ISV)能够改善实时数据处理和分析&#xff0c;从而做出更具洞察力的决策。在新的一年里&#xff0c;我们很高兴地宣布DigitalOcean托管Kafka的横向扩展功能&#…

写文献综述常用的几种深度神经网络模型!

写文献综述常用的几种深度神经网络模型 卷积神经网络&#xff08;CNN&#xff09; 解释说明&#xff1a;专门用于处理图像和图像数据的深度学习模型。它通过卷积层、池化层等操作提取图像特征。应用&#xff1a;图像分类、目标检测、人脸识别等。未来改进&#xff1a;进一步提…

数据结构篇2—《单链表(不带头单向不循环链表)》

文章目录 &#x1f6a9;前言1、单链表的内涵(1) 逻辑结构(2) 物理结构 2、链表的分类3、单链表的具体实现(1) 框架结构(2) SingleLinkList.h头文件的实现(3)SingleLinkList.c源文件的实现①SLTPushBack()尾插函数②SLTPushFront()头插函数③SLTPopBack()尾删函数④SLTPopFront(…

高效管理—影视管理系统_后台源码+APP源码+电影数据

高效管理—影视管理系统 产品概述产品展示演示地址产品功能产品优势产品服务源码领取下期更新预报 产品概述 本产品是一个功能强大且易于使用的影视资源管理工具&#xff0c;它提供了一个集中管理和组织电影、电视剧、纪录片等影视作品的平台&#xff0c;帮助用户高效地管理和…

easyExcel - 带图片导出

目录 前言一、情景介绍二、问题分析三、代码实现1. 单图片导出2. 多图片导出3. 多图片导出&#xff08;优化&#xff09; 前言 Java-easyExcel入门教程&#xff1a;https://blog.csdn.net/xhmico/article/details/134714025 之前有介绍过如何使用 easyExcel&#xff0c;以及写…

中间件之异步通讯组件RabbitMQ入门

一、概述 微服务一旦拆分&#xff0c;必然涉及到服务之间的相互调用&#xff0c;目前我们服务之间调用采用的都是基于OpenFeign的调用。这种调用中&#xff0c;调用者发起请求后需要等待服务提供者执行业务返回结果后&#xff0c;才能继续执行后面的业务。也就是说调用者在调用…

【星海随笔】windows 上跑MySQL

step one 使用 WSL 在 Windows 上安装 Linux wsl官方文档 在管理员模式下打开 PowerShell windows上安装wsl wsl --install查看哪些是可用的 wsl --list --onlineC:\Windows\System32\drivers\hosts docker-desktop下载官网&#xff1a;Install Docker Desktop on Windows …

[ log日志画图]分割模型训练结束生成相关日志运用代码画图

文章目录 [ log日志画图]分割模型训练结束生成相关日志运用代码画图我的log文件&#xff1a;画图&#xff1a;1.loss1.1 loss是干嘛的1.2 代码1.3 生成图 2.DICE.IOU2.1 DICE,IOU是干嘛的(常规介绍)2.2 代码2.3 生成图小白tip [ log日志画图]分割模型训练结束生成相关日志运用代…