|
在记录的存储位置与它的关键字之间建立一个确定的对应关系f,通过这个对应关系f找给定值k的像f(k),进行查找的方法为散列方法。称这个关系f为哈希函数,按此建立的表为哈希表。
|
|
|
设哈希表是一个地址为0~(n-1)的向量,冲突是指由关键字得到的哈希地址为j∈[0,n-1]的位置上已存有记录,而冲突处理就是为该关键字的记录找到另一个空的哈希地址。
|
|
|
|
|
.直接定址法:取关键字或关键字的某个线性函数值为哈希地址,即:H(key)=key或H(key)=a*key+b;其中a和b为常数。
|
|
|
.数字分析法:假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
|
|
|
.平方取中法:取关键字平方后的中间几位为哈希地址。
|
|
|
.折叠法:将关键字分割成位数相同的几部分,然后取这几部分的叠加和。
|
|
|
.除余数法:取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址,即:H(key)=key mod p,p≤m(注:p的选择很重要)。
|
|
|
.随机数法:选择一个随机函数,取关键字的随机函数值为它的哈希地址。即:H(key)=random(key)。
|
|
|
|
|
.开放地址法:Hi=(H(key)+di) mod m,i=1,2,3,…,n,其中,H(key)为哈希函数,m为哈希表表长,di为增量序列。若di=1,2,…,n,则称线性探测再散列;di=12,-12,22,-22,…,n2,-n2,则称二次探测再散列;di=伪随机数序列,则称伪随机探测再散列。
|
|
|
.再哈希法:Hi=RHi(key),i=1,2,…,n,其中,RHi均是不同的哈希函数,即在同义词产生地址冲突时计算另一个哈希函数地址,直到冲突不再发生。这种方法不易产生聚集,但增加了计算时间。
|
|
|
.链地址法:将所有关键字为同义词的记录存储在同一线性链表中。
|
|
|
.建立一个公共溢出区:关键字和基本表中关键字为同义词的记录,一旦发生冲突,就将其填入溢出表。
|
|
|
|
给定k值,根据造表时设定的哈希函数求得哈希地址,若表中此位置没有记录,则查找不成功;否则比较关键字,若和给定值相等,则查找成功;若不等,则根据造表时设定的处理冲突的方法查找下一个地址,直至某个位置上表为空或关键字比较相等为止。可见,比较关键字的个数取决于3个因素:哈希函数、处理冲突的方法和哈希表的装填因子。
|
|
|
哈希表的平均查找长度不是对象个数n的函数,而是装填因子α(α=n/m)的函数。线性探测法成功查找的平均查找长度为(1+1/(1-α))/2,而不成功查找的平均查找长度为(1+1/(1-α)2)/2;二次探测再散列法的成功查找的平均查找长度为-loge(1-α)/α,而不成功查找的平均查找长度为1/(1-α);链地址法成功查找的平均查找长度为1+α/2,而不成功查找的平均查找长度为α+e-α≈α。
|
|
|