哈希的基本概念.docx

该【哈希的基本概念 】是由【淘气小宇】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【哈希的基本概念 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。6。8哈希表及其查找★3◎4
哈希译自“hash"一词,也称为散列或杂凑。
哈希表查找的基本思想是:依据目前待查找数据的特点,以记录重点字为自变量,设计一个哈希函数,依该函数按重点码计算元素的储存地点,并按此寄存;查找时,由同一个函数对给定值key计算地点,将key与地点单元中元素重点
码进行比较,(杂凑
函数),按这个思想结构的表称为哈希表(杂凑表)。
关于n个数据元素的会合,总能找到重点码与寄存地点一一对应的函数。若
最大重点为m,能够分派m个数据元素寄存单元,选用函数f(key)=key即可,
但这样会造成储存空间的很大浪费,甚至不行能分派这么大的储存空间。往常重点码的会合比哈希地点会合大得多,因此经过哈希函数变换后,可能将不一样的重点码映照到同一个哈希地点上,这种现象称为矛盾(Collision)。映照到同一哈
希地点上的重点码称为同义词。能够说,矛盾不行能防止,,哈希方法需要解决以下两个问题:
(1)结构好的哈希函数
①所选函数尽可能简单,以便提升变换速度。
②所选函数对重点码计算出的地点,应在哈希地点集中大概均匀散布,以减少空间浪费。
(2)拟订解决矛盾的方案

(1)直接定址法
即取重点码的某个线性函数值为哈希地点,这种函数是一一对应函数,不会产生矛盾,但要求地点会合与重点码会合大小相同,所以,关于较大的重点码集
{100,300,500,700,800,900},选用哈希函数为
Hash(key)=key/100,则寄存如表6-3所示.
表6—3直接定址法结构哈希表
地点
0
1
2
3
4
5
6
7
8
9
重点码
100
300
500
700
800
900
(2)除留余数法
即取重点码除以p的余数作为哈希地点。使用除留余数法,选用适合的p
很重要,若哈希表表长为m,则要求p≤m,且靠近m或等于m。p一般选用
质数,也能够是不包括小于20质因子的合数。
(3)数字剖析法
设重点码会合中,每个重点码均由m位构成,每位上可能有r种不一样的符
号。
数字剖析法依据r种不一样的符号及在各位上的散布状况,选用某几位,组合成
哈希地点。所选的位应是各样符号在该位上出现的频次大概相同.
(4)平方取中法
对重点码平方后,按哈希表大小,取中间的若干位作为哈希地点。
(5)折叠法(Folding)
此方法将重点码自左到右分红位数相等的几部分,最后一部分位数能够短
些,而后将这几部分叠加乞降,并按哈希表表长,取后几位作为哈希地点。这种方法称为折叠法.
有两种叠加方法:
①移位法-—将各部分的最后一位对齐相加.
②间界叠加法——从一端向另一端沿各部分分界往返折叠后

,最后一位对
齐相加。
如对重点码为key=25346358705,设哈希表长为3位数,则可对重点码每
3位一部分来切割。重点码切割为以下4组:25346358705分别用上述方
法计算哈希地点如图6-12所示。关于位数好多的重点码,且每一位上符号散布
较均匀时,可采纳此方法求得哈希地点。

(1)开放定址法
所谓开放定址法,即由重点码获得的哈希地点一旦产生了矛盾,也就是说,
该地点已经寄存了数据元素。我们需要找寻下一个空的哈希地点,只需哈希表足够大,空的哈希地点总能找到,并将数据元素存入。常用的找空哈希地点方法有以下三种.
①线性探测法
此中,Hash(key)为哈希函数,m为哈希表长度,为增量序列1,2,,
m—1,且=i。
设重点码集为{47,7,29,11,16,92,22,8,3},哈希表表长为
11,Hash(key)=keymod11,用线性探测法办理矛盾,结构哈希表如表6—4所
示。
表6-4哈希表
0
1
2
3
4
5
6
7
8
9
10
11
22
47
92
16
3
7
29
8
△▲
△△
47,7,11,16,92均是由哈希函数获得的没有矛盾的哈希地点,因此是直接
存入的。
Hash(29)=7,哈希地点上矛盾,需找寻下一个空的哈希地点:
此外,22,8相同在哈希地点上有矛盾,也是由找到空的哈希地点的;而Hash(3)=3,哈希地点上矛盾,因为:
线性探测法可能使第i个哈希地点的同义词存入第i+1个哈希地点,这样本应存入第i+1个哈希地点的元素变为了第i+2个哈希地点的同义词所以,可能出现好多元素在相邻的哈希地点上“聚积”起来,大大降低了查找效率。为此,可采纳二次探测法,或再哈希函数探测法,以改良“聚积”问题。
②二次探测法
此中,Hash(key)为哈希函数,m为哈希表长度,为增量序列12,
12,
22,22,,q2,q2且
仍对前面例子的重点码序列{47,7,29,11,16,92,22,8,3},用二次
探测法办理矛盾,结构哈希表如表6—5所示。
表6—5二次探测法结构哈希表
0
1
2
3
4
5
6
7
8
9
10
11
22
3
47
92
16
7
29
8
△▲△△
与重点码找寻空的哈希地点只有3这个重点码不一样,Hash(3)=3,哈希地点
上矛盾,由
H2=(Hash(3)+12)%11=2,找到空的哈希地点,存入.
③再哈希法
此中,Hash(key),ReHash(key)是两个哈希函数,m为哈希表长度.
再哈希法,先用第一个函数Hash(key)对重点码计算哈希地点,一旦产生
地点矛盾,再用第二个函数ReHash(key)确立挪动的步长因子,最后,经过步长因子序列由探测函数找寻空的哈希地点。
比方,Hash(key)=a时产生地点矛盾,就计算ReHash(key)=b,则探测的地点序列为:
(2)链地点法
又称拉链法,设哈希函数获得的哈希地点域在区间[0,m-1]上,以每个哈希地点作为一个指针,指向一个链,即分派指针数组:
ElemType*eptr[m];
成立m个空链表,由哈希函数对重点码变换后,映照到同一哈希地点i的
同义词均加入*eptr[i]指向的链表中。
对重点码序列为{47,7,29,11,16,92,22,8,3,50,37,89,94,21},
哈希函数为Hash(key)=keymod11,用拉链法办理矛盾,建表如图6—13所
示。
(3)成立一个公共溢出区
设哈希函数产生的哈希地点集为[0,m-1],则分派两个表:
一个基本表ElemTypebase_tbl[m];每个单元只好寄存一个元素.
一个溢出表ElemTypeover_tbl[k];只需重点码对应的哈希地点在基本表
上产生矛盾,则全部这样的元素一律存入该表中。查找时,对给定值kx经过哈希函
数计算出哈希地点i,先与基本表的base_tbl[i]单元比较,若相等,查找成功;
不然,再到溢出表中进行查找。

哈希表的查找过程基本上和造表过程相同。一些重点码可经过哈希函数变换
的地点直接找到,另一些重点码在哈希函数获得的地点上产生了矛盾,需要按处
,产生矛盾后的查找仍
然是给定值与重点码进行比较的过程。所以,对哈希表查找效率的量度,依旧用均匀查找长度来权衡。
查找过程中,重点码的比较次数取决于产生矛盾的多少。假如产生的矛盾少,
查找效率就高,假如产生的矛盾多,查找效率就低。所以,影响产生矛盾多少的因
素,:
①哈希函数能否均匀;
②办理矛盾的方法;
③哈希表的装填因子.
剖析这三个要素,只管哈希函数的“利害”直接影响矛盾产生的频度,但一
般状况下,我们总以为所选的哈希函数是“均匀的”。所以,可不考虑哈希函数对均匀查找长度的影响。
是哈希表装满程度的标记因子。因为表长是定值,α与“填入表中的元素个数"成正比,所以,α越大,填入表中的元素许多,产生矛盾的可能性就越大;α越小,填入表中的元素较少,产生矛盾的可能性就越小。
实质上,哈希表的均匀查找长度是装填因子α的函数,不过不一样办理矛盾的
-6为几种不一样办理矛盾方法的均匀查找长度。
表6—6几种不一样办理矛盾方法的均匀查找长度
均匀查找长度
办理矛盾的方法
查找成功时查找不行功时
线性探测法
二次探测法与再哈希法
链地点法
哈希方法存取速度快、节俭空间,静态查找、动向查找均合用,但因为存取是
随机的,所以,不便于次序查找.