Java 中有HashMap,了解哈希的原理,不仅有助于用好HashMap,也有助于理解其它开源产品,甚至自己可以编写效率更高的哈希算法,例如在MemCached(著名的Cache开源产品)中,客户端根据key值定位到哪台server上,用的是求模哈希函数,进行哈希表的地址定位。
哈希最主要是用在查找上,可以说是查找效率最高的算法,但是用好哈希,还是需要了解原理,因为好的哈希实现,首先要解决哈希地址的冲突问题,为什么会造成冲突,请看下面的原理:
哈希表是用来查找元素的,在多种类型的查找中,例如顺序查找时,比较的结果为“=”与“<>”两种可能,在折半查找、二叉排序树查找和B-树插好时,比较的结果为“<”、“=”和“>”三种可能,查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是希望不经过任何比较,一次存取便能得到所查记录,那就必须在记录的存储位置和它的key之间建立一种确定的对应关系f,似的每个关键字和结构中一个唯一的存储位置相对应,因而在查找时,只要根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上,由此,不需要进行比较便可以直接存取所查记录。在此,我们称这种对应关系f为哈希函数,按这个思想建立的表为哈希表。
哈希函数是一个映像,因此哈希函数的设定很灵活,只要使得任何关键字由此所得到的哈希函数值都落在表长允许范围之内即可;
对不同的关键字可能得到同一个哈希地址,即key1<>key2,而f(key1)=f(key2),这种现象称“冲突”。在一般情况下,冲突只能进可能地少,而不能完全避免。因为,哈希函数是从关键字集合到地址集合的映像。通常,关键字集合比较大,它的元素包括所有可能的关键字,而地址集合的元素仅为哈希表中的地址值。
一。哈希函数
哈希函数的构造方法很多,好的哈希函数对哈希表的查找性能有直接影响:
若对于关键字集合中的任意一个关键字 ,经哈希函数映像到地址集合中的任何一个地址的概率是相等的,则称此类哈希函数为均匀的哈希函数。换句话说,就是使关键字经过哈希函数得到一个“随机的地址”,一遍使一组关键字的哈希地址均匀分布在整个地址区间中,从而减少冲突。
1.直接定址法:
取关键字或者关键字的某个线性函数值为哈希地址。即:H(key)=a.key+b
其中a和b为常数
直接定址所得地址集合和关键字集合的大小相同。因此,对于不同的关键字会发生冲突,但实际中能使用这种哈希函数的情况很少。
2.数字分析法
假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
事先知道数据的特点,比较少见,可适用的场合比较少。在此不再赘述。
3.平方取中法
取关键字的平方后的中间几位为哈希地址。这是一种较常见的构造哈希函数的方法。通常在选择哈希函数时不一定能知道关键字的全部情况,取其中哪几位也不一定合适,而一个数的平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
4.折叠法
将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。这种方法称为折叠法。
5.求模法
取关键字被某个不大于哈希表表长m的数p除后,所得的模(余数)为哈希地址。即
H(key)=key MOD p p<=m
这是一种最简单,也是最常用的构造哈希函数的方法,它不仅可以对关键字直接取模(MOD),也可在折迭、平方取中等运算之后取模。
注意,在使用求模发时,对p的选择很重要。若p选的不好,容易生成相同的哈希地址。
由众人的经验得知:一般情况下,可以选p为质数或者不包含小于20的质因素的合数。
注:质数为除了1或者自身整除的数称为质数。例如2是最小的质数。
6.随机数法:
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key)=random(key),其中random为随机函数。通常当关键字长度不等时采用此法构造哈希函数较恰当。
二、处理冲突的方法
上面讲到均匀的哈希函数可以减少冲突,但不能避免,因此,如何处理冲突是哈希造表不可缺少的另一方面。
假设哈希表的地址集0-(n-1),冲突是指由关键字得到的哈希地址为j(0<=j<=n-1)的位置上已存有记录,则处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。
通常用的处理冲突的方法有下列几种:
1.开放定址法
分享到:
相关推荐
哈希查找数据结构实验报告 本实验报告的标题是 "哈希查找数据结构实验报告.pdf", 描述是 "哈希查找数据结构实验报告.pdf", 标签是 "考试"。该实验报告讲述了哈希表的造表和查找算法的实现。 第一部分:需求分析 ...
//哈希查找法 #include #include #include<iomanip.h> #define datawidth 5 //设置数据显示宽度 #define arraymaxnum 21 //约定数组大小,0号单元默认不用,故用户数据可以接受20个 #define defaultnum 10 //约定...
哈希查找是数据结构中的一个重要组成部分,它提供了一种快速定位数据的方法。在这个主题中,我们将深入探讨哈希查找的概念、实现、优势以及在C语言中如何构建一个友好的用户界面来实现这一功能。 哈希查找的基本...
### 哈希查找链地址法知识点解析 #### 一、引言 本文将详细介绍一个基于C语言实现的哈希表查找系统,该系统利用链地址法处理冲突,并支持基本的增删查操作。通过本篇文章,您将了解哈希表的基本原理、链地址法的...
总之,哈希表和哈希查找是计算机科学中重要的数据结构和算法,它们提供了一种快速访问数据的方式,广泛应用于数据库系统、编译器、缓存管理等多个领域。理解并熟练掌握哈希表的原理和实现,对于提升程序性能和解决...
c/c++语言程序-哈希查找
哈希查找算法的源代码c语言 哈希查找算法是软件网络技术中一种常用的查找算法,它通过将关键字转换为数组的索引来实现快速查找。该算法的实现需要解决两个主要问题:哈希函数的设计和冲突的处理。 哈希函数的设计 ...
哈希查找算法是一种高效的数据检索方法,它通过计算哈希函数将关键字映射到一个固定大小的哈希表中,以此实现快速查找。在本文中,我们将深入探讨如何利用Microsoft Foundation Classes (MFC) 来实现哈希查找算法。...
在数据结构课程设计中,哈希查找是一种高效的数据组织和检索方法。哈希表是实现哈希查找的基础,它通过将关键字(key)映射到一个固定大小的数组索引来快速定位数据。在这个课程设计中,我们将使用C语言来实现这一...
易语言万倍哈希查找源码,万倍哈希查找,操作函数,加入,取回,删除,成员数,内部哈希,线程等待,取时间戳_易,创建进入许可证_,进入许可区_,退出许可区_,删除进入许可证_,启动线程_,销毁线程_,寻找字节集_,内存_申请,内存_...
C 言语 哈希查找算法 数据结构教才答案
哈希查找 C++源代码 数据结构。 数据结构课作业。
本主题将深入探讨三种常见的查找方法:哈希查找、折半查找(又称二分查找)以及顺序查找。 首先,我们来理解哈希查找。哈希查找基于哈希表,这是一种能够快速访问数据的结构。哈希函数是哈希查找的核心,它能将输入...
哈希查找算法是一种在计算机科学中广泛使用的数据结构和算法技术,它主要依赖于哈希函数来实现快速的查找操作。哈希函数是将输入(通常是一个字符串或对象)映射到一个固定大小的数值(通常是一个数组的索引)的过程...
建立哈希表查找c++中32个关键字,其中哈希表长为M=101 32个关键字为auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof ...
在这个“易语言源码易语言万倍哈希查找源码.rar”压缩包中,包含的是一个易语言编写的哈希查找算法的源代码。哈希查找是一种在数据结构中快速定位目标元素的技术,它的核心思想是通过哈希函数将键(key)转化为哈希...
输入:待哈希数据序列 功能要求:输出哈希方法和解决冲突的方法(文字输出),输出哈希表
哈希查找利用哈希函数将关键字映射到一个固定大小的表中,以实现快速查找。理想情况下,哈希函数能够均匀分布关键字,避免冲突,这样查找只需要一次操作。当发生冲突时,可以采用开放地址法或链地址法等策略处理。...
《万倍哈希查找》是针对计算机编程领域中的一种高效数据查找技术的实践应用,尤其在处理大量数据时,能够显著提升查找效率。哈希查找是计算机科学中的一个重要概念,它利用哈希函数将数据映射到一个固定大小的表中,...
C语言哈希查找_哈希查找