查找过程当中,症结码的比较次数,取决于发作争执的若干,发作的争执少,查找效力就高,发作的争执多,查找效力就低。因而,影响发作争执若干的要素,也就是影响查找效力的要素。影响发作争执若干有以下三个要素:
1. 散列函数是不是匀称;
2. 处置惩罚争执的要领;
3. 散列表的装填因子。
散列表的装填因子定义为:α= 填入表中的元素个数 / 散列表的长度
α是散列表装满水平的标志因子。因为表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,发作争执的可能性就越大;α越小,填入表中的元素较少,发作争执的可能性就越小。
实际上,散列表的均匀查找长度是装填因子α的函数,只是差别处置惩罚争执的要领有差别的函数。
处理哈希争执的要领平常有:
NO.1开放定址法
所谓的开放定址法就是一旦发作了争执,就去寻觅下一个空的散列地点,只需散列表足够大,空的散列地点总能找到,并将纪录存入。
公式:f(key)=(f(key)+di)%m(di=1,2,3….m-1)
比如说,症结字鸠合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},表长为12。散列函数f(key) = key mod 12。
当盘算前5个数{12, 67, 56, 16, 25}时,都是没有争执的散列地点,直接存入;盘算key = 37时,发明f(37) = 1,此时就与25地点的位置争执。因而运用上面的公式f(37) = (f(37) + 1) mod 12 =2,。因而将37存入下标为2的位置。接下来22,29,15,47都没有争执,一般的存入。到了48,盘算获得f(48) = 0,与12地点的0位置争执了,没关联,我们f(48) = (f(48) + 1) mod 12 = 1,此时又与25地点的位置争执。因而f(48) = (f(48) + 2) mod 12 = 2,照样争执......一直到f(48) = (f(48) + 6) mod 12 = 6时,才有空位,如下表所示。
序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
症结字 | 12 | 25 | 16 | 67 | 56 |
NO.2再哈希法
关于散列表来讲,可以事前预备多个散列函数。
公式:fi(key)=RHi(key)(i=1,2,3…,k)
这里RHi 就是差别的散列函数,可以把除留余数、折叠、平方取中悉数用上。每当发作散列地点争执时,就换一个散列函数盘算。
这类要领可以使得症结字不发作群集,但响应地也增加了盘算的时候。
NO.3链地点法(拉链法)
将一切症结字为同义词的纪录存储在一个单链表中,称这类表为同义词子表,在散列表中只存储一切同义词子表前面的指针。关于症结字鸠合{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},用前面一样的12为余数,举行除留余数法,可以获得下图构造。
NO.4竖立大众溢出区
这个要领是当你时从新给你找个地点,为一切争执的症结字竖立一个大众的溢出区来寄存。
就前面的例子而言,共有三个症结字37、48、34与之前的症结字位置有争执,那就将它们存储到溢出表中。如下图所示。
在查找时,对给定值经由过程散列函数盘算出散列地点后,先与基础表的响应位置举行比对,假如相称,则查找胜利;假如不相称,则到溢出表中举行递次查找。假如相干于基础表而言,有争执的数据很少的情况下,大众溢出区的构造对查找机能来讲照样异常高的。
【引荐课程:C++相干课程】
以上就是数据构造中散列表(哈希表)典范之争执处置惩罚的细致内容,更多请关注ki4网别的相干文章!