|
|
|
在记录的存储位置与它的关键字之间建立一个确定的对应关系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-α≈α。
|
|
|
