lyhk又称散列法、杂凑发、关键字地址计算法,相应的表成为哈希表、散列表等。
lyhk的基本思想:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H,是的p=H(k),H成为哈希函数。
五个因素:①计算哈希函数所需的时间。②关键字长度。③哈希表的大小。④关键字分布情况。⑤记录查找的频率。
哈希函数的构造方法构造哈希函数原则:一是函数本身便于计算;二是计算出来的地址分布均匀。
1、数字分析法:事先要知道关键字集合,并且每个关键字的位数比哈希表的地址为数多时,可以从关键字中选出分布均匀的若干位构成哈希地址。
2、平方取中法:当无法确定关键字中那几位分布较均匀时,可以先求出关键字的平方值,然后取平方值中间的几位作为哈希地址。
3、分段叠加法:按哈希表地址为数将关键字分成位数相等的几部分,然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。
4、除留余数法:假设哈希表的长度为m,p为小于等于m的最大素数,则哈希函数为其中,%的模p为取余运算。
5、伪随机数法:采用一个为随机函数作为哈希函数,即H(key)=random(key)
处理冲突的方法通过构造性能良好的哈希函数,可以减少冲突,但一般不节能完全避免冲突,因此解决冲突时lyhk的另一个关键技术。
1、开放定址法:这种方法也成再散列法,其基本思想是当关键字key的初始哈希地址出现冲突时,以 h0 h 0
为基础产生另一个地址 h1 h 1 如果仍然冲突,再以
h0 h 0 为基础,产生地址,直到不冲突地址
hi h i 将相应元素存入。
2、在lyhk:这种方法的基本思想是同时构造多个不同的哈希函数:
Hi=RHi(key)i=1,2,3...,k H i = R H i ( xhdzt ) i = 1 , 2 , 3... , k
当哈希地址 H1=RH1(key) H 1 = R H 1 ( xhdzt ) 冲突时,在计算 H2=RH2(key) H 2 = R H 2 ( xhdzt ) 直到冲突不在产生。这种方法不易产生聚集,但增加了计算时间。
3、链地址法:这种方法的基本思想是将所有的哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入、删除、主要在同义词链中进行。
4、建立公共溢出区:这种方法的基本思想是将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素一律填入溢出表。
哈希表的查找过程①首先计算 h0=hash(K) h 0 = h a s h ( K ) ;
②如果单元 h0 h 0 为空,则所查元素不存在;
③如果单元 h0 h 0 中元素的关键字为K,则查找到所查元素。
④否则重复下述解决冲突的过程:
a、按解决冲突的方法,找出下一个哈希地址 hi h i ;
b、如果单元 hi h i 为空,则所查元素不存在;
c、如果单元 hi h i 中元素的关键字为K,则查找到所查元素。