大话数据结构-8.9 散列表查找(哈希表)概述 - 高飞网

8.9 散列表查找(哈希表)概述

2017-01-22 17:39:51.0

8.9 散列表查找概述

8.9.1 散列表查找定义

    存储位置=f(关键字)

    散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关键f,使得每个关键字key对应一个存储位置f(key)。

    f称为散列函数,又称为哈希(hash)函数。采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)。

8.9.2 散列表查找步骤

    1)在存储时,通过散列函数计算记录的散列地址,并按此散列地址存储该记录。

    2)当查找记录时,通过同样的散列函数计算记录的散列地址,按此散列地址访问该记录。

    对于两个关键字key1≠key2,但是却有f(key1)=f(key2),这种现象称为冲突,并把key1和key2称为这个散列函数的同义词。

8.10 散列函数的构造方法

    什么才算是好的散列函数?

    1)计算简单

    2)散列地址分布均匀:让空间有效利用,并减少处理冲突而耗费的时间    

8.10.1 直接定址法

    取关键字的某个线性函数值为散列地址,即:f(key)=a*key+b(a、b为常数)

    这样的散列函数优点是简单、均匀,也不会产生冲突,但问题是这需要事先知道关键字的分布情况,适合查找较小且连续的情况。

8.10.2 数字分析法

    使用关键的一部分来计算散列存储位置的方法。如手机号152****2720,使用尾号来计算散列地址。

    数字分析法通常适合处理关键字位置比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀,就可以考虑使用。

8.10.3 平方取中法

    关键字1234,计算方法为:1234---(平方)-->1522756--(取中)-->227,用做列表地址。

    平方取中法比较适合用于不知道关键字的分布,而位数又不是很大的情况。

8.10.4 折叠法

    将关键字从左到右分割成位数相等的几部分,然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。

    如:9876543210---(分割)-->987|654|321|0--(求和)-->987+654+321+0=1962,再求后3位得到散列地址为962。

    有时可能还不能够保证分布均匀,可以从一端向另一端来回折叠对齐再相加,如上面的,可:

    9876543210---(分割)-->987|654|321|0--折叠-->789|654|123|0--(求和)-->789+654+123+0=1566-->566。

    折叠法事先不需要知道关键字的分布,适合关键字位数较多的情况。

8.10.5 除留余数法

    此方法为最常用的构造散列函数的方法:

    f(key)=key mod p(p<=m)。

    因为避免冲突,若散列表表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。

8.10.6 随机数法

    选择一个随机数,取关键字的随机函数值为它的散列地址。即f(key)=random(key)

8.11 处理散列冲突的方法

8.11.1 开放定址法

    一旦发生冲突,就去寻找下一个空的散列地址,只要散列表够大,空的散列地址总能找到,将将记录存入。

    fi(key)=(f(key)+di) mod 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。

    

    对于37,37%12=1与25冲突,于是1+1=2可存在索引2处。

    这种解决冲突的开放定址法称为线性探测法

    在解决冲突的时候,还会遇到48和37这种本来不是同义词却要争夺一个地址的情况,称为堆积

8.11.2 再散列函数法

    对于散列表来说,事先准备多个散列函数:

    fi(key)=RHi(key)   (i=1,2,...,k)    

    每当发生散列地址冲突时,就换一个散列函数计算,总有一个可以把冲突解决掉。缺点是增加了计算的时间。

8.11.3 链地址法

    将所有关键字为同义词的记录存储在一个单链表中,称这种表为同义词子表,在散列表中只存储所有同义词子表的头指针。

    链地址法对于可能会造成很多冲突的散列函数来说,提供了绝对不会出现找不到地址的保障。当然也带来了查找时需要遍历单链表的性能损耗。

8.11.4 分散溢出区法

    对于有冲突的关键词,单独放到一个溢出表中。

    在查找时,对给定值通过散列函数计算出列表地址后,先与基本表的相应位置进行比对,如果相等,则查找成功;如果不相等,则到溢出表去进行顺序查找。如果相对于基本表面言,有冲突的数据很少的情况下,公共溢出区的结构对查找性能宫玉国ip 非常高的。

8.12.2 散列表查找性能分析

    1. 散列函数是否均匀
    2. 处理冲突的方法
    3. 散列表的装填因子
    所谓装填因子α=填入表中的记录个数/散列表长度α标志着散列表的填满的程序。当记录越多,α越大,产生冲突的可能性就越大。散列表的平均查找长度取决于装填因子,而不是取决于查找集合中的记录个数。