[工学]数据结构 第9章 查找.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 6. 随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random (key)，其中random为随机函数。 通常，当关键字长度不等时采用此法构造哈希函数较恰当。 实际工作中需视不同情况采用不同的哈希函数。通常考虑的因素： (1)计算哈希函数所需时间(包括硬件指令的因素)； (2)关键字的长度； (3)哈希表的大小； (4)关键字的分布情况； (5)记录的查找频率。 9.3.3 处理冲突的方法 1.开放地址法 开放地址就是表中尚未被占用的地址，当新插入的记录所选地址已被占用时，即转而寻找其它尚未开放的地址。 （1）线性探测法 设散列函数 H（K）=K mod m （m为表长），若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为： Hi=(H(K)+di) mod m (di=1,2,…,m-1) 例 关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表： 0 1 2 3 4 5 6 7 8 9 10 47 7 29 11 16 92 22 8 3 线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素； 线性探测法的缺点：可能使第i 个哈希地址的同义词存入第i+1 个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……， 因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。 可采用二次探测法或伪随机探测法，以改善“堆积”问题。 1.开放地址法 （2）二次探测法 二次探测法对应的探查地址序列的计算公式为： Hi = ( H(k)+di ) mod m 其中di =12,-12,22,-22,…,j2,-j2 (j≤m/2)。 0 1 2 3 4 5 6 7 8 9 10 11 22 3 47 92 16 7 29 8 若di＝伪随机序列，就称为伪随机探测法 例 关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用二次探测法处理冲突。建哈希表如下： Hi = ( H(k)+di ) mod m 其中di =12,-12,22,-22,…,j2,-j2 (j≤m/2) 2.链地址法 优点：插入、删除方便。 缺点：占用存储空间多。 基本思想： 将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设 m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。 例：设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为：Hash(key)=key mod 11，用拉链法处理冲突，建表。 0 1 2 3 4 5 6 7 8 9 10 22 11 89 3 47 37 92 29 7 16 50 8 10 ? ? ? ? ? ? ? ? ? ? ? 有冲突的元素可以插在表尾,也可以插在表头。 3.再哈希法 Hi= RHi(key) RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。不易产生“聚集”，但是增加了计算时间。 4.建立一个公共溢出区 9.3.4 哈希表的查找及其分析 散列表的目的主要是用于快速查找。 在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。 例：设有一组关键字{ 19, 01, 23, 14, 55, 20, 84, 27, 68, 11, 10, 77 }，采用哈希函数为： H（k）=k mod 13。采用开放地址的线性探测法解决冲突，试在0～18的散列地址空间中，对该关键字序列构造哈希表。 解：依题意 m=19，得到线性探测法对应的探查地址序列计算公式为： di=(H(k)+j)